The advantages of iterators

[Frank14]

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?

[Golden Lizard]

Iterators are a kind of abstraction, think of them as an interface between the user and the data structure.

[JLBorges]

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

For example:
N == 3 std::vector<>, std::deque<>, std::list<>
M == 4 std::find(), std::count(), std::fill(), std::reverse()

N*M == 12:
find in vector, find in deque, find in list; count in vector, count in deque, count in list;
fill vector, fill deque, fill list; reverse vector, reverse deque, reverse list;


> If the data is of K different types, we could even end up with N*M*K

For example, several more different versions of find:
find int in vector of int, find int in deque of int, find int in list of int;
find string in vector of string, find string in deque of string, find string in list of string;
find point in vector of point, find point in deque of point, find point in list of point;

and likewise for count, fill and reverse.

[Frank14]

Thanks. I got that part.

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.

I think by this the author meant using templates. Right?

By using iterators to access data in any kind of container from any algorithm, we can make do with N+M
algorithms.

I can't understand this part. Does it mean that we can assign an iterator of, E.g., std::vector to an iterator of std::list or other ones?
Like this 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;
}

int main()
{
   std::vector<int> vi = {3, 4, 6, 8};
   cout << largest(vi.begin(), vi.end()) << endl;

   std::list<string> ls = { "C++", "OpenGL", "Qt", "QML"};
   cout << largest(ls.begin(), ls.end()) << endl;

   return 0;
}

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.

I think we can't assign the iterator of a container to the iterator of another container which are not the same type.

[JLBorges]

> I think by this the author meant using templates. Right?

Yes; in the C++ standard library, by using templates.


> By using iterators to access data in any kind of container from any algorithm, we can make do with N+M algorithms. I can't understand this part.
> Does it mean that we can assign an iterator of, E.g., std::vector to an iterator of std::list or other ones?

No. It means that, with the earlier example, where
N == 3 std::vector<>, std::deque<>, std::list<>
M == 4 std::find(), std::count(), std::fill(), std::reverse()
K == 3 int, string, point

We can make do with N containers + M algorithms.

If a new algorithm is required (let us say max_element), we only need to add that one algorithm; it will work with all N containers and all K suitable data types

If a new container is required (let us say my_fancy_list), we only need to add that one generic container; it will work with all N algorithms and all K suitable data types.

And finally, if we need to support a new data type, nothing needs to be added to the set of N containers + M algorithms.



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

What this means is that we can use std::copy() to copy any sequence to any other compatible sequence:
vector of int to list of double, deque of char* to list of string etc. The input iterator iterating over the source sequence and the output iterator iterating over the target sequence need not be of the same type.

[Frank14]

Theory is fine but when there is an example (on the explained subject), it comes to be easily understood.