How iterators are useful

[tomy12]

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?

[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.

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.

[wolle]

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.

[tomy12]

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:

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?

[tomy12]

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.

[tomy12]

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

[2kaud]

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:

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

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

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

    return temp;
}

[tomy12]

Thank you. I used this:

#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.

[2kaud]

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.

[tomy12]

Thank you for your answer.

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?

[superbonzo]

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 ).

[tomy12]

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?

[2kaud]

You overload the unary * operator for a class.

[superbonzo]

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*.