How iterators are useful
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Member
Join Date
Jun 2015
Posts
155

How iterators are useful

Hello all,

I finished chapter 20 of the book "Programming Principle and Practice using C++". There is a postscript at the end of this chapter:

"If we have N kinds of containers of data and M things we’d like to do with them, we can easily end up writing N*M pieces of
code. If the data is of K different types, we could even end up with N*M*K pieces of code. The STL addresses this
proliferation by having the element type as a parameter (taking care of the K factor) and by separating access to data from
algorithms. By using iterators to access data in any kind of container from any algorithm, we can make do with N+M
algorithms. This is a huge simplification. For example, if we have 12 containers and 60 algorithms, the brute-force approach
would require 720 functions, whereas the STL strategy requires only 60 functions and 12 definitions of iterators: we just saved
ourselves 90% of the work. In fact, this underestimates the saved effort because many algorithms take two pairs of iterators and
the pairs need not be of the same type (e.g., see exercise 6). In addition, the STL provides conventions for defining algorithms
that simplify writing correct code and composable code, so the saving is greater still.
"

Although I've done the exercises of the chapter and worked with iterators much, I don't understand the advantages of above all.
Would you please offer an example showing the benefits of using iterators as the postscript says?

2. Re: How iterators are useful

Look at the STL functions described here http://www.cplusplus.com/reference/algorithm/

These take iterators as parameters. This is what makes them so flexible and powerful. If the underlying data structure provides the required iterators, then these functions can be used. So if you code a new structure and provide the iterators for it, then these STL functions will work and can be used for the new structure without the functions knowing anything about this structure.

Also, if you want to write a new function that works with data structures then if you write it to use iterators then the function will work with any structure that provides the required iterators - the function doesn't need to know anything else about the structure. As the book states, this is very powerful and very flexible.
Last edited by 2kaud; October 11th, 2017 at 05:30 AM.

3. Member
Join Date
Feb 2017
Posts
227

Re: How iterators are useful

Originally Posted by tomy12
the benefits of using iterators as the postscript says?
The postscript you refer to describes the benefits of a general language feature called polymorphism. Lets say you have a bunch of containers that are all sequentially iterable. In the object oriented (OO) approach one would express this by letting them inherit and implement an Iterable interface. Then if a piece of code uses the Iterable type it will work when supplied with any container that implements the Iterable interface. That's polymorphism in action.

The STL library is not OO for historical reasons so the STL containers are not related by shared interfaces. Still relationships can be formed by letting the containers share function names. Instead of an Iterable interface containers may express the fact that they are sequentially iterable by sharing the two functions begin() and end(). These return a start iterator and a stop iterator respectively which can be used to facilitate iteration through a range. Then if a piece of code is written that uses begin() and end() it will work when supplied with any container sporting a begin() function and an end() function (returning iterators capable of sequential iteration).

So one use of iterators in STL is to provide the benefits of polymorphism for containers but without OO. Rather than expressing a type relationship by sharing a common interface like in OO, the STL containers express a functional relationship by sharing common functions. This kind of polymorphism is called ad-hoc polymorphism and is central to all of STL really.
Last edited by wolle; October 12th, 2017 at 07:36 AM.

4. Member
Join Date
Jun 2015
Posts
155

Re: How iterators are useful

Originally Posted by 2kaud
Look at the STL functions described here http://www.cplusplus.com/reference/algorithm/

These take iterators as parameters. This is what makes them so flexible and powerful. If the underlying data structure provides the required iterators, then these functions can be used. So if you code a new structure and provide the iterators for it, then these STL functions will work and can be used for the new structure without the functions knowing anything about this structure.
Well I think iterators work well because they also gain the advantages of templates. Do you by "if you code a new structure" mean another container, because iterators should iterate over some container?

And "provide the iterators for it": Does it mean simply creating a class that comprises that new container and provide functions: begin, end, arithmetic and so on, constructors that send pointers and we can use those pointers as iterators?
I need the subject in its most basic level to figure it out completely.

Also, if you want to write a new function that works with data structures then if you write it to use iterators then the function will work with any structure that provides the required iterators - the function doesn't need to know anything else about the structure. As the book states, this is very powerful and very flexible.
It sounds that iterators work as template parameters that needn't know about the (pointer) type that will be sent to them.
For example:

Code:
```template <class T>
T largest(std::iterator s, std::iterator e)
{
T temp = T();
for(auto it = s; it != e; ++it)
if( *it > temp)
temp = *t
return temp;
}```
Did you mean something like that for the latter part of our discussion?

5. Member
Join Date
Jun 2015
Posts
155

Re: How iterators are useful

Originally Posted by wolle
The STL library is not OO for historical reasons so the STL containers are not related by shared interfaces.
So that's why we can't assign an iterator of, E.g., std::vector to that of std::list. It's on the contrary to what I though I'd gotten from the subject and to the snip code I offered.
Still relationships can be formed by letting the containers share function names. Instead of an Iterable interface containers may express the fact that they are sequentially iterable by sharing the two functions begin() and end(). These return a start iterator and a stop iterator respectively which can be used to facilitate iteration through a range. Then if a piece of code is written that uses begin() and end() it will work when supplied with any container sporting a begin() function and an end() function (returning iterators capable of sequential iteration).
So the snip code might not be that wrong.

So one use of iterators in STL is to provide the benefits of polymorphism for containers but without OO. Rather than expressing a type relationship by sharing a common interface like in OO, the STL containers express a functional relationship by sharing common functions. This kind of polymorphism is called ad-hoc polymorphism and is central to all of STL really.
I've read about polymorphism in books IIRC. It talks about functions having different type/order/number of arguments I think.
Last edited by tomy12; October 13th, 2017 at 03:14 PM.

6. Member
Join Date
Jun 2015
Posts
155

Re: How iterators are useful

If there is an example that demonstrates what the postscript explained, it will be easily understood.

7. Re: How iterators are useful

Originally Posted by tomy12
Well I think iterators work well because they also gain the advantages of templates. Do you by "if you code a new structure" mean another container, because iterators should iterate over some container?

And "provide the iterators for it": Does it mean simply creating a class that comprises that new container and provide functions: begin, end, arithmetic and so on, constructors that send pointers and we can use those pointers as iterators?
I need the subject in its most basic level to figure it out completely.

It sounds that iterators work as template parameters that needn't know about the (pointer) type that will be sent to them.
For example:

Code:
```template <class T>
T largest(std::iterator s, std::iterator e)
{
T temp = T();
for(auto it = s; it != e; ++it)
if( *it > temp)
temp = *t
return temp;
}```
Did you mean something like that for the latter part of our discussion?
More like

Code:
```template <typename I>
I max_element (I s, I e )
{
I temp = s;

for (; s != e; ++s)
if (*s > *temp)
temp = s;

return temp;
}```

8. Member
Join Date
Jun 2015
Posts
155

Re: How iterators are useful

Thank you. I used this:

Code:
```#include <std_lib_facilities_4.h>
using namespace std;

template <typename T>
T max_elem(T first, T end)
{
T temp = first;
for (; first != end; ++first)
if (*first > *temp)
temp = first;
return temp;
}

int main()
{
vector<int> vi{ 3, 5, 7, 4 };
vector<double> vd{ 5.8, 4.5, 9.9, 9.8 };
list<string> ls{ "AB", "CD", "EF", "AD" };

cout << *max_elem(vi.begin(), vi.end()) << endl;
cout << *max_elem(vd.begin(), vd.end()) << endl;
cout << *max_elem(ls.begin(), ls.end()) << endl;

system("pause");
return 0;
}```
and it correctly showed the max element for each one. So using iterators we needn't write a given function for each container again, but we can this way take advantages of iterators and use the given function for any container. I got this case.
But apart from that, have iterators any other advantage (especially if it's stated in the postscript)?

If so, I would be thankful if your explain that and then use a example for it.

9. Re: How iterators are useful

In addition, the STL provides conventions for defining algorithms
that simplify writing correct code and composable code, so the saving is greater still
I think you are referring to this?

This is just a more generalisation of the first. So if you want to sort or search or merge or find or... then the c++ code more closely reflects the algorithm being used.

10. Member
Join Date
Jun 2015
Posts
155

Re: How iterators are useful

So to summarise, we can say that the whole power of iterators can be practically summarised to that simple code. I,e. it shows the whole case. Yes?

If so and you agree, so the power of iterators belongs completely to the pointers containers have declared as iterators to be used, "and" use of generic programming (template). Yes, again?

11. Senior Member
Join Date
Oct 2008
Posts
1,456

Re: How iterators are useful

Originally Posted by tomy12
so the power of iterators belongs completely to the pointers containers have declared as iterators to be used, "and" use of generic programming (template). Yes, again?
iterators need not to be pointers, nor to belong to some container. An iterator is just something that can be traversed and dereferenced ( how and when depending on its iterator category ).
For example, you could write an iterator representing pi’s digits, or a source of pseudo random numbers, or …, clearly no such container could exist.

Moreover, generic algorithms working on iterators are useful not just because they are polymorphic, but also because such polymorphism is resolved at compile time. This increases both type safety and optimization opportunities. It also allows iterators to be efficiently composed, in order to create new iterators from existing one or to use them as building blocks of higher abstractions ( eg. ranges ).

12. Member
Join Date
Jun 2015
Posts
155

Re: How iterators are useful

Thank you.
The only way I can think of something capable of being dereferenced is that when it is a pointer. Would you please offer a simple example which illustrates your meaning?

13. Re: How iterators are useful

You overload the unary * operator for a class.

14. Senior Member
Join Date
Oct 2008
Posts
1,456

Re: How iterators are useful

Originally Posted by tomy12
The only way I can think of something capable of being dereferenced is that when it is a pointer. Would you please offer a simple example which illustrates your meaning?
generally speaking, "dereferencing" means turning some kind of referee into its referent ( eg. the word 'apple' to a real apple, a postal address to a real house, an id-card to a real person, etc... ); as you can see, this concept can be applied to a lot of things, not just c++ pointers

anyway, in c++ this is idiomatically achieved via the unary *operator ( as mentioned by 2kaud ) for consistency with pointers ( this is not strictly required though, see the OOP iterator pattern for an example ).

Let's say you want to write an iterator representing an infinite sequence of numbers following some recursion relation; internally, this would not store any pointer at all, it would just store some numeric state to be 'incremented' via operator++ and 'returned' via its operator*.

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•