Search

16.3 — STL iterators overview

An Iterator is an object that can traverse (iterate over) a container class without the user having to know how the container is implemented. With many classes (particularly lists and the associative classes), iterators are the primary way elements of these classes are accessed.

An iterator is best visualized as a pointer to a given element in the container, with a set of overloaded operators to provide a set of well-defined functions:

  • Operator* -- Dereferencing the iterator returns the element that the iterator is currently pointing at.
  • Operator++ -- Moves the iterator to the next element in the container. Most iterators also provide Operator-- to move to the previous element.
  • Operator== and Operator!= -- Basic comparison operators to determine if two iterators point to the same element. To compare the values that two iterators are pointing at, deference the iterators first, and then use a comparison operator.
  • Operator= -- Assign the iterator to a new position (typically the start or end of the container’s elements). To assign the value of the element the iterator is point at, deference the iterator first, then use the assign operator.

Each container includes four basic member functions for use with Operator=:

  • begin() returns an iterator representing the beginning of the elements in the container.
  • end() returns an iterator representing the element just past the end of the elements.
  • cbegin() returns a const (read-only) iterator representing the beginning of the elements in the container.
  • cend() returns a const (read-only) iterator representing the element just past the end of the elements.

It might seem weird that end() doesn’t point to the last element in the list, but this is done primarily to make looping easy: iterating over the elements can continue until the iterator reaches end(), and then you know you’re done.

Finally, all containers provide (at least) two types of iterators:

  • container::iterator provides a read/write iterator
  • container::const_iterator provides a read-only iterator

Lets take a look at some examples of using iterators.

Iterating through a vector

This prints the following:

0 1 2 3 4 5

Iterating through a list

Now let’s do the same thing with a list:

This prints:

0 1 2 3 4 5

Note the code is almost identical to the vector case, even though vectors and lists have almost completely different internal implementations!

Iterating through a set

In the following example, we’re going to create a set from 6 numbers and use an iterator to print the values in the set:

This program produces the following result:

-6 -4 1 2 7 8

Note that although populating the set differs from the way we populate the vector and list, the code used to iterate through the elements of the set was essentially identical.

Iterating through a map

This one is a little trickier. Maps and multimaps take pairs of elements (defined as a std::pair). We use the make_pair() helper function to easily create pairs. std::pair allows access to the elements of the pair via the first and second members. In our map, we use first as the key, and second as the value.

This program produces the result:

1=banana 2=orange 3=grapes 4=apple 5=peach 6=mango

Notice here how easy iterators make it to step through each of the elements of the container. You don’t have to care at all how map stores its data!

Conclusion

Iterators provide an easy way to step through the elements of a container class without having to understand how the container class is implemented. When combined with STL’s algorithms and the member functions of the container classes, iterators become even more powerful. In the next lesson, you’ll see an example of using an iterator to insert elements into a list (which doesn’t provide an overloaded operator[] to access its elements directly).

One point worth noting: Iterators must be implemented on a per-class basis, because the iterator does need to know how a class is implemented. Thus iterators are always tied to specific container classes.

16.4 -- STL algorithms overview
Index
16.2 -- STL containers overview

29 comments to 16.3 — STL iterators overview

  • maalika

    Under “Iterating through a map” section, did you mean std:: pair instead of “stl::pair”? May be just a typo? Or does it mean, STL?

  • abhishekp

    Just to add, We may insert element in map by directly giving it’s index. for example in the above mentioned program mymap[6]=”mango”; rather than to use mymap.insert(make_pair(6, “mango”));

  • Neha Kumari

    Hi,

    Which is better List or Vector? And when to use list and when to use vector?

    • Alex

      It really depends on the needs of your application.

      If you need random access to elements, probably Vector. If you need to insert a lot of elements and don’t need random access to the elements, probably List.

  • Anthony

    How does the List version work?

    while (it != li.end())

    li.end is not efficient in a linked list.

    The whole iterator seems completely wrong. It should be

    while (!it.end())

    Too much C hackery in the design.

  • foobar

    typo?
    "Most iterators also provide Operator- to move to the previous element." => Operator- ?

    Edit: I see. I entered Operator dash dash and it is displayed as Operator dash. Weird.

  • tata

    Somehow the syntax below appears to be asking for a static member variable called const_iterator; but const_iterator is obviously not a member variable, but the name of a type/class.

    If we’ve previously seen the scope operator used this way, could someone help point out the chapter, thanks (is it that const_iterator is a class defined in the namespace of vector?)

    A quick google has yet to produce accessible material that explains away this use of the scope operator; I’m most likely forgetting and missing something simple

    • tata

      It appears that this is an example of nested classes described here: http://en.cppreference.com/w/cpp/language/nested_types

      If this is wrong, please correct me

    • Alex

      This version of const_iterator is a typedef defined in the public part of std::vector, so yes, const_iterator is essentially in the namespace of class std::vector.

  • Marek

    When moving iterator to next element, pre-increment should be preferred, it’s more efficient on iterators.

  • Stas

    I think you made a small typo in the conclusion, I’m still new to C++ but I just want to clarify. You wrote, "Iterators provide an easy way to step through the elements of a container class without having to understand how the container class is implemented.", and a bit after this you write, "the iterator does need to know how a class is implemented".

    Isn’t this a contradiction or am I under-informed on the vocab you’re using? Thanks in advance.

    • Alex

      Let me use an analogy here. You don’t have to know how your TV is built to use a TV remote, but your TV remote does need to know how the TV is built in order to send a command to it.

      You don’t need to know how a class is implemented to use an iterator, but the iterator does need to know how the class is implemented to iterate through it.

      Make sense?

  • Matt

    Found some typos:
    * "Operator-" should be "Operator--" (two hyphens): "Most iterators also provide Operator- to move to the previous element."
    * "stl" should be "std": "(defined as an stl::pair)"
    * "it’s" should be "its": "(which doesn’t provide an overloaded operator[] to access it’s elements directly)"

  • Reaversword

    How its possible to use "const_iterator" (that I understand, it’s a constant, and thereby, it can’t change), and even being constant, it remains being possible to cycle it with ++ or -?.

    I can understand when you make the FIRST "++" or "-", you’re pointing to the "next" or "previous" memory address (as temporary address, since iterator is constant and cannot change), but not why this works for next iterations. If iterator pointer is constant, I understand the iterator should be using something like "iterator+n". But despite of to be constant, I see clearly not to be "read only".

    So, in which sense "const_iterator" is really constant?. It is just about you can’t change iterator directly assigning it a position? (const_iterator = 3)?.

    • Alex

      A const_iterator isn’t constant itself. Rather, it treats the values it is iterating over as const (and returns a const reference to them, instead of a normal reference).

      Thus, a const_iterator is a good choice when you want a read-only iterator, because it will prevent you from changing the values you are iterating over.

  • Mekacher Anis

    <code>vector<int>::const_iterator</code>
    does this mean that iterators belong to classes ?

  • SJ

    Maybe you could briefly talk about rbegin() and rend() as well.

  • Darren

    Interesting, you use while loops to iterate through containers. **While** you are entitled to your opinion, **for** that I much prefer for loops.

    Also what about the keyword ‘auto’ (c++11 onwards)? Could save on a lot of typing!

  • Matt

    In the code under "Iterating through a vector", in the first comment, "an" should be "a".

  • Matt

    In your last code example, under "Iterating through a map", you wrote:
    cout << it->first << "=" << it->second << " ";

    Since "first" and "second" are member functions, don’t they need to have parentheses at the end?

    • Alex

      No, first and second are not member functions. They’re members of the pair. You can access them directly.

      • Matt

        I’m still confused about this, because in the paragraph above this code example, you characterize first and second as member functions:
        " std::pair allows access to the elements of the pair via the first() and second() member functions. In our map, we use first() as the key, and second() as the value."

        • Alex

          My mistake -- they aren’t functions, they’re just normal members. I’ve updated the lesson accordingly.

          Basically, std::pair looks something like this:

Leave a Comment

Put C++ code inside [code][/code] tags to use the syntax highlighter