iterators

[/Muad'Dib\]

Could someone explain to me the purpose of the STL iterators and generally when they should be used? Thanks.

[Prelude]

>Could someone explain to me the purpose of the STL iterators
Glorified pointers.

>and generally when they should be used?
When you use anything in the standard library that requires them.

[/Muad'Dib\]

Obviously. Exatly what requires them? I'm sure there are several reasons, one or two would help.

[jlou]

They are useful when using the STL containers themselves. Any time you want to go through the contents of a container, or search the contents of a container, or basically access any data in the container, the container interface uses iterators. There are some exceptions, for example string and vector provide array like interfaces that let you access elements without using iterators. For the most part, though, iterators are usedto gain access to the data stored in a container.

They are also useful when using STL containers with STL algorithms. Technically, any object that allows iteration over data and follows certain rules can be passed to most algorithms, but the iterators used in the STL containers are generally setup to work with the algorithms easily (or maybe the algorithms were set up to work with the container iterators ).

Here's a random example of accessing and printing the elements of a map:

#include <iostream>
#include <map>
#include <cstdlib>
#include <ctime>

int main()
{
    srand(time(0));
    std::map<int, int> m;
    for (int i = 0; i < 20; i++)
    {
        m.insert(std::make_pair(rand() % 100, rand() % 1000));
    }

    std::map<int, int>::const_iterator iterPair = m.begin();
    std::map<int, int>::const_iterator iterEnd = m.end();
    for (; iterPair != iterEnd; ++iterPair)
    {
        std::cout << "FirstNum: " << iterPair->first;
        std::cout << "\tSecondNum: " << iterPair->second << std::endl;
    }
}

[elad]

>>Could someone explain to me the purpose of the STL iterators.....
>>Exatly what requires them?

Maybe the questions can be rephrased as "why are iterators used in preference to routine pointers in the development of the Standard Template Library?"

[Hunter2]

And the answer is... *dadadada

Ask elad!

Actually, you CAN (at least in the case of a vector, I'm not sure about other containers) substitute a pointer for an iterator, in MSVC - although I believe that would depend on the implementation.

[Prelude]

>is the answer because you can't move through the elements of the containers, like lists, with pointers?
You can't move through an std::list with pointers unless you know something about the implementation. The elements of a list aren't required to be contiguous, so without something that knows how to move to the next element, a pointer isn't meaningful.

[elad]

>>You can't move through an std::list with pointers unless you know something about the implementation. The elements of a list aren't required to be contiguous, so without something that knows how to move to the next element, a pointer isn't meaningful.

Is there another way of aligning elements of a list (or other container) besides contiguous and non-contiguous? Can't routine pointers deal with both contiguous and non-contiguous alignments? Is it possible to implement iterators that don't include a pointer as member of an iterator class? Aren't all user defined types (STL containers, iterators, whatever) made up of aggregates of primitive types, like int, char, pointers, etc.?

So why not use a plain pointer instead of iterators with STL classes?

[Prelude]

>Is there another way of aligning elements of a list (or other container) besides contiguous and non-contiguous?
Well, with the proper hardware you could store the elements of a list in the same location with each element in a parallel dimension. Then a pointer could easily be used to traverse the dimensions and you don't lose the benefit of constant time insertion and removal. You also get the benefit of random access too if you believe the theory of quantum mechanics. It's the best of both worlds! ...or all worlds, as it were.

>Can't routine pointers deal with both contiguous and non-contiguous alignments?
Yes, but not the same way. With contiguous storage all you have to do is p++ or p--, but with non-contiguous storage you would have to chase links by saying something like p.next or p.prev. Built-in pointer types don't allow you to do both with the same operation.

>Is it possible to implement iterators that don't include a pointer as member of an iterator class?
Yes. The iterator for a container class can be implemented any way as long as the proper behavior and interface is satisfied.

>Aren't all user defined types (STL containers, iterators, whatever) made up of aggregates of primitive types, like int, char, pointers, etc.?
Yes.

>So why not use a plain pointer instead of iterators with STL classes?
Because STL classes may not be amenable to being traversed by a pointer. A good example is a list. With iterators the defined behavior is to allow ++it and --it, but if the container is implemented as a double linked list then ++p and --p won't work if you use a plain pointer.

[elad]

To paraphrase, to make sure I understand the answer: among other considerations, with iterators the desired behavior is to allow both ++ and --, irrespective of memory allocation pattern of the elements (contiguous vs non-contiguous), whereas with pointers you can only use ++ and -- if memory allocation is contiguous.

Thanks.

[Prelude]

>To paraphrase, <snip>
Yes.

[Prelude]

The answer to the first part of your question is that the two are equivalent. It's a matter of style as to which you use. The answer to the second part is that it's convenient to have a single object represent a related pair of items, such as in an asociative array.

[Hunter2]

>>i don't understand why they say this
I believe it's for the sake of language portability; that's how it has to be declared in C, but in C++ it makes no difference.

>>and why do we need to have a strucrure called Pair
I don't know why there's a typedef for a Pair<int, float> but I do know that std::map's use Pair's a lot (the first in the pair is the key, and the second is the value).

[Prelude]

>I believe it's for the sake of language portability
Sure, using the struct keyword goes toward compatibility, but the instant you get to the template arguments, compatibility with C goes out the window.

>I don't know why there's a typedef for a Pair<int, float>
For the same reason one would do this:

typedef std::map< string, pair<int, float> > point_map;

So we can do things like this:

point_map::iterator it;

Instead of

std::map< string, pair<int, float> >::iterator it;

>but why did they make a function "make_pair() when you have a constructor that does the same job?
For convenience.

[Prelude]

Yes.