[ C++11 - Part 4 ] STL - iterators

Standard Template Library

---

A major part of C++ is the Standard Template Library ( STL ). It is quite large and it contains both containers ( like vector, stack and maps ) with a lot of functionality for using these. In this post, we'll look at one part of the STL, iterator, and in the following post we'll look at other parts of STL like the algorithms library

Iterators

---

Iterators can be looked at like pointers. They reference an item in a data structure( including string ). They can also be used with streams. The iterators enables us to iterate through them using various operations like ++.

But we need different types of iterators because data structures can often be iterated in different ways. Some ways are efficient on some containers while they might be inefficient or even impossible on other containers.

Let's take a look at the different type of iterators.

• Output iterators
• Very restricted
• Can only be written to ( not read )
• Can only move forward after writing
• Example : std::cout
• Input iterators
• Counterpart of output iterators
• Can only be read ( not written to )
• Move forward after reading
• Example : std::cin
• Forward iterator
• Can do everything input iterator can do
• Can also move forward at any time
• Example : std::forward_list
• Bidirectional iterator
• Can do everything forward iterator
• Can also move backwards at any time
• Example std::list
• Random access iterator
• Can do everything bidirectional iterator can do
• Also supports random access ( [] )
• Example : std::vector and std::array

Here's a simple overview :

The properties of the various iterators here are the bare minimum of the "pure" version of the iterators. Some implementations might support more operations.

Note that forward iterator, bidirectional iterator and random access iterator does not implement output iterators. This means that they can't, by definition, write to the object they refer to. We'll get back to this later.

Let's start by looking at the first type of iterator, output iterator.

Output iterator

---

As mentioned earlier, output iterator is a very limited type of iterator it is also the only iterator that can write to the object.

You can't go back with an output iterator, and you can't iterate over the same range twice. And there is no guarantee that you can write to the same position twice without incrementing the operator. And you can't compare two output iteratrs either. What you're basically doing is writing into a "black hole"; you're just writing and you can't see what you have written.

This might seem very constrictive, there's very little we can do. But these rules only apply in some cases, like when writing to streams, which we'll look at later. You can look at the iterators that follows everything described above as pure output iterators

Most iterators, though implement output iterators but also has other traits that enables more functionality. We'll look at these later.

A simple example

---

This is a very simple example of the intended usage for output iterators :

OutputIterator r2;
while ( ... )
{
    *r2 = x;
    r2++;
}

Or, in other words :

• Write
• Move forward
• Write
• Move forward
• ...

A bit more complex example

---

In C++ you have streams, which allows you to to either write or read from them using the >> and << operators. Examples of this is cout ( write ) cin ( read ). This makes cout output operators ( because they output to the terminal. )

cout is of the type ostream. You also have an iterator to this type, called ostream_iterator that can be set to an ostream Writing to this iterator writes to the ostream it's an iterator to.

Using this knowledge, we can create an iterator to cout, this enables us to write to the terminal using an iterator

#include < iterator >
#include < iostream >

int main()
{
    // Create an ostream_iterator to std::cout.
    // The "\n" means we add a line every time we write
    std::ostream_iterator< int32_t > it(std::cout, "\n");

    *it = 11;
    it++;
    *it = 44;
    it++;
    *it = 33;
    it++;
}

Output :

11
44
33

The ostream_iterators are output iterators. Using cout like this shows how output iterators works ; you can only write and the writing has to be sequential. You can newer go back. Once you've written something, you can't "go back" and write something in the position before what you just wrote.

Input iterator

---

The counterpart of output iterators is input iterators. But where output iterators can only write, input iterators can read but there is also a small changes in the restrictions :

• You can compare two iterators
• Comparing two  iterators is not guaranteed to work unless at least one of them is past the end ( like std::end )
• Since you can read, you can also use the -> operator to access member variables

A simple example

---

The following example shows the essential use of an input iterator :

while( ... )
{
    std::cout << *pos;
    ++pos;
}

Or, in other words :

• Read
• Move forward
• Read
• Move forward
• ...

A more complex example

---

In the previous example, we saw that ostream_iterators are output iteratorss. Which means we can use them to write to cout. Similar to this, we have istream_iterators that are input operators. And where we can use ostream_iterators with cout, we can use istream_iterators with cin which reads input.

Here too we have to work consecutively, we can't go back or skip ahead, we can read input in a similar to when we wrote to cout

#include <iterator>
#include <iostream>

int main()
{
    // ...
    std::cout << "Write something " << std::endl;
    std::istream_iterator< int > intReader( std::cin );

    // readerEnd refers to the end element of the stream
    // This is similar to std::end()
    std::istream_iterator< int > readerEnd;

    while ( intReader != readerEnd )
    {
        std::cout<<"Write     "<< *intReader<< std::endl;         std::cout<<"You wrote "<< *intReader<< std::endl;         ++intReader;
    }
}

Example input :

3
2
6
f

Output :

Write 3
You wrote 3
2
Write 2
You wrote 2
6
Write 6
You wrote 6
f

Since we've specified int as the template argument of the input_iterator, the input_iterator ( intReader ) will become the same as invalid, which in C++ means the iterator will point to the element past the end element. This is the same as readerEnd and the loop will terminate.

Forward iterator

---

If you take a look at the iterator overview above, you'll see that the forward iterator implements output iterator. This means a forward iterator can do anything an output iterator can do but with a few more properties :

• Two forward iterators are guaranteed to compare as equal if they refer to the same element
• An input iterator can, as we saw above, be compared to another output iterator, but the operation is only guaranteed to be true  if one of them is past the end of the container
• Example :

Forward_Iterator it1 = beginIterator; Forward_Iterator it2 = beginIterator; // Compare bool ( it1 == it2 );

The compare operation ( it1 == it2 ) is not guaranteed to be true for  output iterators or input iterators, but it is for forward iterators

---

• A  forward iterator can also iterate forward as many times as you like before reading
• With  output iterators or input iterators we would have to read or write in between each time we iterate forward.
• Example :

Forward_Iterator it1 = beginIterator;

// Iterate it1 forward a few steps
++it1;
++it1;
++it1;

// Use (*it1) for something
// ....

If we had used an output iterator or an input iterator to do the multiple iterations would have caused the iterators to become invalid.

---

• Finally, a  forward iterator can iterate over the same range twice.
• output iterators or input iterators are intended to only iterate over the same range once ( single-pass ) but are intended to be able to do this ( multi-pass )
  
• Example :

Forward_Iterator it1 = beginIterator;

// Iterate it1 forward a few steps
++it1;

// Use (*it1) for something
// ....

// Go back to beginIterator
it1 = beginIterator;

// Iterate it1 forward a few steps
++it1;

// Use (*it1) for something
// ...

Here we've effectively moved back and continued moving forward, which again would not be possible with code>output iterators or input iterators.
As you can see, using  forward iterators is in many ways more convenient than using output iterators or input iterators, but some object only has very few operations, like the streams we looked at earlier.

Luckily, most ( if not all ) structures in the C++11 supports at least the functionality of forward iterators. Most of them provide iterators that has more properties, but this time we'll look at a structure that only provides forward iterators

Forward list

---

A linked list is a container that works a bit different from the array-like containers. Basically, each element has a pointer to the next element and previous. So that all the elements are chained together using pointers. If you want to go from one element to another, you use the next pointer ( or the previous if you want to go back ) This can mean a lot of operations if the list is very large.

The objects will not be one contiguous piece of memory like arrays are. This means there are no quick ways to go from the first to the last element. So if we wanted to go from Node 1 to Node 2 in the above illustration, we would have to go via Node 3. And if we wanted to go back from Node 3 to Node 1 we would have a problem. There is no pointer that goes back in a forward list. If you want to get to a previous node, you would need a pointer to an earlier element. The forard_list itself keeps a pointer to the first element in order to be able to access all elements.

A container in like this didn't exist in C++ until C++11 which has the container forward list.

Iterating forward lists

---

The forward list is a great way of showing how the forward iterators works. The forward list can only be iterated forward and the forward iterator can only iterate forwards.

Let's look at an example :

std::forward_list< int32_t > list( { 43, 63, 11, 0, 5 } );

// Get a forward iterator to the first element of list
std::forward_list<int32_t>::iterator it=std::begin(list);

// Print value
for ( int32_t i = 0 ; i < 4 ; ++i )
{
    std::cout << (*it) << std::endl;
    ++it;
}


We are now at the fifth element ( 5 ), but say we want to print the previous element ( 0 )? We need to go back to the begin element and increment like above.

// Go back to the first element
it = std::begin( list );

// Iterate forwards to the element before the one above
for ( int32_t i = 0 ; i < 3 ; ++i )
    ++it;

std::cout << (*it) << std::endl;

Output

43
63
11
0
5
0


Forward iterators and input iterator

---

• Per definition, forward iterators  does not include the properties of output iterators. 
• Most implementations of forward iterators does however support assignment like output iterators. These iterator are called mutable forward iterators

Bidirectional iterator

---

The bidirectional iterator is very similar to forward iterator. The only different is that it also supports backwards iteration. And that's all the difference between code>forward iterator and bidirectional iterator.

Linked list

---

In the forward iterator section we looked at singly linked lists which has a pointer to the next element. But most linked lists also has a pointer to the previous element.These are called doubly linked lists or simply just linked list.

The container type doubly linked lists are identical to singly linked lists, with the one exception that each Node now has a pointer to the previous Node too.



The prev pointer enables us to iterate backwards, so now we need an iterator that can iterate backwards and forwards. This is where the bidirectional iterator comes in.

An example

---

The following example is the similar to the example for forward list but this time we solve the last problem in a different way.

std::list< int32_t > list( { 43, 63, 11, 0, 5 } );

// Get a forward iterator to the first element of list
std::list< int32_t >::iterator it = std::begin( list );

// Print value
for ( int32_t i = 0 ; i < 4 ; ++i )
{
    std::cout << (*it) << std::endl;
    ++it;
}

    std::cout << (*it) << std::endl;



We are now at the fifth element ( 5 ), but say we want to print the previous element (0 )? We can simply use the -- operator to iterate back;

--it;
std::cout << (*it) << std::endl;

Output

43
63
11
0
5
0


As you can see, bidirectional iterators can iterate back and forth without problems. Now let's look at the final iterator, bidirectional iterator.

Random access iterator

---

The final iterator is also the one with the most features. It can be used like a pointer. In fact, some implementations of STL uses pointers as random access iterators.

Here's a list of the features of a random access iterator

• All the features of bidirectional itearator
• Random access
• Access items by [] operator
• it[n] returns the value of the position it + n
• it[n] is the same as *( it + n )
• Iterator arithmetics
• This means you can add or subtract integer values and iterators
• it += n moves it forward n steps
• it -= n moves it backward n steps
• it + n returns an iterator to the element n steps after it
• n - it returns an iterator to the element n steps before it
• it - it2 returns the distance between it and it2
• Iterator comparison
• This means you can check which if one iterator is before another iterator
• it1 < it2 returns true if it1 is before it2
• it1 > it2 returns true if it1 is after it2
• it1 >= it2 returns true if it1 is not before it2
• it1 >= it2 returns true if it1 is not after it2
not it1 < it2 

Array-like containers

---

Array like containers are all containers that are organized as a continuous piece of memory. This means you can predict where the next item is, since it the next item will always be the previous item + the size of each item. Using this knowledge, it's easy to jump forward or backwards. An example of these containers is vector, which I covered in a previous part.

The above example shows how any array-like container ( vector, array, queue, deque, ... ) is laid out in memory. Everything is in one continuous block which means we always know where the next element is.

An example

---

The following example shows usage of random access iterators:



As you can see, the + operators of random access iterators are very useful. We will be using this for the upcoming post about STL algorithms.

---

For a full list of my tutorials / posts, click here. Feel free to comment if you have anything to say, any suggestion or any questions. I always appreciate getting comments.