Tag Archives: Iteration

Looping over the keys and values in a map

Say we have this map:

#include <map>
#include <string>

typedef std::map<std::string, unsigned int> map_string_to_uint;
const size_t n = 12;

map_string_to_uint monthdays;
const char *months[] 
        = {"JAN", "FEB", "MAR", "APR", "MAY", "JUN", "JUL", "AUG", "SEP", "OCT", "NOV", "DEC"};
unsigned int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
for (int m = 0; m < n; ++m) {
    monthdays[months[m]] = days[m];
}

And we want to loop over the keys and values.

Method 1: Use an iterator

    for (map_string_to_uint::const_iterator it = monthdays.begin(); it != monthdays.end(); ++it) {
        std::cout << it->first << ": " << it->second << "\n";
    }

Method 2: Use a range-based for loop (C++11)

    for (const auto& pair : monthdays) {
        std::cout << pair.first << ": " << pair.second << "\n";
    }

Method 3: Use Boost.Foreach

#include <boost/foreach.hpp>

BOOST_FOREACH(const map_string_to_uint::value_type& pair, monthdays) {
    std::cout << pair.first << ": " << pair.second << "\n";
}

Reference: Boost.Foreach

Looping over a container in C++

It’s best to use an algorithm when processing a container, or the contents of any pair of iterators, in C++, but it’s good to know how to iterate when you have to.

Here’s the vector we’re going to use:

#include <iostream>
#include <vector>
#include <algorithm>

typedef std::vector<int> intvec;

int main()
{  
    intvec v(10);
    std::iota(v.begin(), v.end(), 0);
    iterate(v);
}

Method 1: Use iterators

This is the most familiar interface.

void iterate(const intvec& v)
{
    for (intvec::const_iterator it = v.begin(); it != v.end(); ++it) {
        // Do something with *it
    }
}

Method 2: Use indices

Note that only random access containers like vector and deque support indexed access.

void iterate(const intvec& v)
{
    for (intvec::size_type i = 0; i < v.size(); ++i) {
        // Do something with v[i]
    }
}

Method 3: Use Boost.Foreach

This was the most elegant method until C++11.

#include <boost/foreach.hpp>

void iterate(const intvec& v)
{
    BOOST_FOREACH(intvec::value_type el, v) {
        // Do something with el
    }
}

Reference: Boost.Foreach

Method 4: Use a range-based for loop

This is now the recommended method.

void iterate(const intvec& v)
{
    for (const auto& el: v) {
        // Do something with el
    }
}

The yield keyword in Python

To understand how yield works, you need to understand iterables, iterators, and generators

Iterables

An iterable is an object capable of returning its members one at a time. Iterables include:
All sequence types, such as:

  • list
  • str
  • tuple

Some none-sequence types, such as:

  • dict
  • file objects
  • any objects of user-defined classes with an __iter__() method or with a __getitem__() method that implements Sequence
    semantics (see below)

Iterables can be used in a for loop and in many other places where a sequence is needed:

  • zip()
  • map()

When an iterable object is passed to the built-in function iter(), it returns an iterator for the object.
The iterator is good for one pass over the set of values
It is usually not necessary to call iter() directly, as the for statement does this for you, creating a temporary unnamed
variable to hold the iterator for the duration of the loop.

User-defined iterables need to define one of __iter__() or __getitem__().

__iter__()
Called when an iterator is required for a container.
Iterator objects also need to implement this method; they are required to return themselves.

__getitem__()
Called to implement self[key].
For sequence types, the accepted keys should be integers or slice objects.
The interpretation of negative slices is the responsibility of the __getitem__() method.
If key is of the wrong type, a TypeError may be raised.
If the key is of a value outside the set of indexes for the sequence, an IndexError should be raised.
For mapping types, if key is missing, a KeyError should be raised.

Iterators

An iterator is an object representing a stream of data.
Calls to the object’s __next__() method (or passing it to the built-in function next()) return successive items in the
stream.
When no more data are available, a StopIteration exception is raised.
The iterator is then exhausted, and any subsequent calls to __next__() method will raise a StopIteration again.
Iterators are required to have an __iter__() method so every iterator is also iterable and may be used in most places where
other iterables are accepted.

Generators

The word generator refers to two things: a generator function and a generator iterator.

Generator function
A generator function is like a normal function except that it contains one or more yield expressions.
When a generator function is called, its code is not executed, and instead it returns a generator iterator.

Generator iterator
This is an iterator that controls the execution of the generator function in response to calls to the next() function.
Each yield in the associated generator function causes execution to be temporarily suspended. When the iterator resumes, execution continues from where it left off.