Tag Archives: STL

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

Why STL iterator ranges go [begin, end)

At first sight, it seems strange that STL iterators go [begin, end), including begin but not end in the range, but when you think about it more you realise that this is exactly the way conventional loops work.

STL iteration loop

A typical STL iteration loop goes:

for (it = begin; it != end; ++it) {
    // do something with *it
}

Note that:

  • The iterator end is not part of the range processed
  • After the end of the loop it is equal to end, i.e., one past the end of the range
  • The size of range traversed is endbegin

Now consider the following loops:

Loop over an array with an index

    int numbers[] = {1, 2, 3, 4, 5, 6};
    const size_t n = sizeof(numbers) / sizeof(int);
    int i;
    for (int i = 0; i < n; ++i) {
        std::cout << numbers[i] << "\n";
    }
    std::cout << i << "\n";

Here, our range of indices processed is [0, n).

  • numbers[n] is not part of the range processed
  • After the end of the loop, i is n, i.e., one past the end of the range
  • The size of range traversed is n - 0 = n , i.e., the end – the beginning

Loop over a string


    const char str[] = "The quick brown fox jumps over the lazy dog";
    for (i = 0; str[i] != '\0'; ++i) {
        std::cout << str[i] << "\n";
    }
    for (const char* c = str; c != '\0'; ++c) {
        std::cout << *str << "\n";
    }

A string is defined by [str[0], '\0'), or [*str, '\0')

  • The '\0' character is not part of the string
  • After the end of the loop, the pointer or index points to the '\0'.
  • The size of range traversed is (position of the '\0') – 0 = strlen(str), i.e., the end – the beginning

Loop over an array of pointers with sentinel

    const char* strings[] = {"apples", "pears", "bananas", "cherries", NULL};
    for (i = 0; strings[i] != NULL; ++i) {
        std::cout << strings[i] << "\n";
    }
    for (const char** pc = strings; *pc != NULL ; ++pc) {
        std::cout << *pc << "\n";
    }

Similarly, here the range is [strings[0], NULL), or [*strings, NULL)

  • The NULL is not considered part of the range processed
  • After the end of the loop, the pointer or index points to the NULL
  • The size of range traversed is (position of the NULL) – 0 = the position of the NULL, i.e., the end – the beginning

Hopefully, this has demonstrated that STL iterators have exactly the same semantics as ordinary loop variables.

I’ll leave the last word to E. W. Dijkstra, with his explanation of Why numbering should start at zero.

Erasing from a vector by index

Use the vector::erase function to erase an element, or range of elements from a vector. It returns an iterator pointing to the element after the last one erased:

v.erase(v.begin() + pos);
v.erase(v.begin() + start, v.begin() + end);

For example, this program populates a vector with the numbers 0 to 9 and then erases 8, before erasing 3 to 5:

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

int main()
{
    typedef std::vector<int> intvec;
    intvec v(10);
    std::iota(v.begin(), v.end(), 0);
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    std::cout << "erase 8:\n";
    intvec::const_iterator it = v.erase(v.begin() + 8);
    std::cout << "next element is " << *it << "\n";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    std::cout << "erase 3 to 5:\n";
    it = v.erase(v.begin() + 3, v.begin() + 6);
    std::cout << "next element is " << *it << "\n";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
}

You can make a generic function to erase from a container by index by using std::advance to move to the first (and optionally last) element to remove and then calling the container’s own erase method:

template <class Container>
typename Container::iterator erase(Container& cont, size_t pos, size_t len = 1)
{
    typename Container::iterator it1 = cont.begin();
    std::advance(it1, pos);
    typename Container::iterator it2 = it1;
    std::advance(it2, len);
    return cont.erase(it1, it2);
}

Use it like this:

erase(vec, 8);    // erase 8
erase(vec, 3, 3); // erase 3 to 5

Note that this will be O(n) for lists because their iterators are not RandomAccessIterators.

Finding the size of arrays and containers

Arrays

You can find the size of an array with the following template function:

template <typename T, size_t N>
size_t size(T (&)[N])
{
    return N;
}

Example:

#include <iostream>

int main()
{
    int ints[] = {1, 2, 3, 4};
    const char *pchars[] = {"a", "b", "c", "d"};
 
    std::cout << size(ints) << "\n";
    std::cout << size(pchars) << "\n";
}
4
4

Note that once an array has decayed to a pointer by being passed to a function, this will not work.

Containers

You can extend this to containers with the following two functions, which take template template parameters:

template <template<class, class> class Container, class T, class Allocator>
size_t size(const Container<T, Allocator>& cont)
{
    return cont.size();
}

template <template<class, class, class, class> class Container, class Key, class T, class Compare,
        class Allocator>
size_t size(const Container<Key, T, Compare, Allocator>& cont)
{
    return cont.size();
}

Example:

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

int main()
{
    std::vector<int> vec(10);
    std::iota(vec.begin(), vec.end(), 0);
    std::map<std::string, int> dict;
    dict["apples"] = 7;
    dict["pears"] = 9;

    std::cout << size(vec) << "\n";
    std::cout << size(dict) << "\n";
}
10
2

C++11

In C++11, you can use decltype to select the container overload, so the two template template functions can be replaced with this:

template <class Container> 
auto size(const Container& cont) -> decltype(cont.size())
{
    return cont.size();
}

C++17

C++17 has added the std::size() function, which probably uses the size_t overload for arrays, and the one using decltype for containers.

Getting the Index of an Iterator

Method 1: Subtract the iterator from the beginning of the container

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

int main()
{
    typedef std::vector<int> intvec;
    intvec vec(10);
    std::iota(vec.begin(), vec.end(), 0);
    for (intvec::const_iterator it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " is at " << it - vec.begin() << "\n";
    }
}

Note that this will only work with a RandomAccessIterator.

Method 2: Use std::distance on the beginning of the container and the iterator

#include <list>
#include <algorithm>
#include <iostream>

int main()
{
    typedef std::list<std::string> stringlist;
    stringlist list;
    const char *words[] = {"The", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"};
    const size_t n = sizeof(words) / sizeof(const char*);
    std::copy(words, words + n, std::back_inserter(list));
    for (stringlist::const_iterator it = list.begin(); it != list.end(); ++it) {
        std::cout << *it << " is at " << std::distance(list.cbegin(), it) << "\n";
    }
}

This will work with any kind of iterator, but will be O(n) for a list iterator.
Notice the use of cbegin() to get a const iterator to the beginning. The iterator returned by begin() is non-const, and so cannot be compared to a const iterator by distance() as it’s a different type.

Populate a map with literal values

Method 1: Use parallel arrays

#include <map>
#include <string>

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

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

Method 2: Use an array of structs

#include <map>
#include <string>

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

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

Method 3: Use an array of std::pairs and the range constructor

#include <map>
#include <string>

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

    std::pair<std::string, unsigned int> months3[] = {
        std::make_pair("JAN", 31), std::make_pair("FEB", 28), std::make_pair("MAR", 31),
        std::make_pair("APR", 30), std::make_pair("MAY", 31), std::make_pair("JUN", 30),
        std::make_pair("JUL", 31), std::make_pair("AUG", 31), std::make_pair("SEP", 30), 
        std::make_pair("OCT", 31), std::make_pair("NOV", 30), std::make_pair("DEC", 31)};
    map_string_to_uint monthdays3(months3, months3 + n);
}

Method 4: Use Boost.Assign

#include <map>
#include <string>
#include <boost/assign.hpp>

int main()
{
    typedef std::map<std::string, unsigned int> map_string_to_uint;

    map_string_to_uint monthdays4 = boost::assign::map_list_of ("JAN", 31) ("FEB", 28) ("MAR", 31)
        ("APR", 30) ("MAY", 31) ("JUN", 30) ("JUL", 31) ("AUG", 31) ("SEP", 30) 
        ("OCT", 31) ("NOV", 30) ("DEC", 31);
}

Method 5: Use a C++11 initializer

#include <map>
#include <string>

int main()
{
    typedef std::map<std::string, unsigned int> map_string_to_uint;

    /* Method 5: Use a C++11 initializer */
    map_string_to_uint monthdays5 =  {{"JAN", 31}, {"FEB", 28}, {"MAR", 31},
        {"APR", 30}, {"MAY", 31}, {"JUN", 30}, {"JUL", 31}, {"AUG", 31}, {"SEP", 30},
        {"OCT", 31}, {"NOV", 30}, {"DEC", 31}};
}

Populate a vector with literal values

Method 1: Use an array and the range constructor

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

int main()
{
    typedef std::vector<int> intvec;

    int arr[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30};
    const size_t n = sizeof(arr) / sizeof(int);
    intvec vec1(arr, arr + n);
    
    std::copy(vec1.begin(), vec1.end(), std::ostream_iterator<int>(std::cout, " "));
}

Method 2: Use boost::assign::list_of

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <boost/assign/list_of.hpp>
#include <boost/range/algorithm/copy.hpp>

int main()
{
    typedef std::vector<int> intvec;

    int arr[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30};
    const size_t n = sizeof(arr) / sizeof(unsigned int);
    
    intvec vec2 = boost::assign::list_of(31)(28)(31)(30)(31)(30)(31)(31)(30)(31)(30);
    
    boost::copy(vec2, std::ostream_iterator<int>(std::cout, " "));
}

Method 3: Use boost::assign

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <boost/assign/std/vector.hpp>
#include <boost/range/algorithm/copy.hpp>
using namespace boost::assign; // bring 'operator+=()' into scope

int main()
{
    typedef std::vector<int> intvec;

    intvec vec3;
    vec3 += 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30;
    
    boost::copy(vec3, std::ostream_iterator<int>(std::cout, " "));
}

Method 4: Use a C++11 initializer

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

int main()
{
    typedef std::vector<int> intvec;

    intvec vec4 = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30};
    
    std::copy(vec4.begin(), vec4.end(), std::ostream_iterator<int>(std::cout, " "));
}

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

Iterator invalidation rules for C++ containers

If you need to worry about iterator invalidation it may be that you should be using an existing algorithm so that you do not need to modify the container’s contents directly.
You definitely need to understand invalidation however, if you want to write an algorithm.

Insertion

Sequence containers

vector

All iterators and references before the point of insertion are unaffected, unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated).
Reason: A vector is a contiguous array, so an insertion causes a block shift which moves all elements after the point of insertion. If the capacity is increased, the whole block is reallocated, potentially changing its address, and so the addresses of all elements.

deque

All iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected).
Reason: A deque is an array of fixed-size arrays (see Deque in C). Addition to the either end (i.e., to the free space in one of the arrays on an end), cannot cause elements to move, so references remain valid. However, as iterators are based on counting, they are all invalidated by addition.

list

All iterators and references unaffected.
Reason: A list is a linked list. Only the connections between nodes are affected by addition, not the nodes themselves.

Associative containers

set, map, multiset, multimap

All iterators and references unaffected.
Reason: They are all binary trees. Only the connections between nodes are affected by addition, not the nodes themselves.

Container adaptors

stack and queue

Inherited from underlying container.

priority_queue

Inherited from underlying container.

Erasure

Sequence containers

vector

Every iterator and reference after the point of erase is invalidated.
Reason:An erasure causes a block shift leftwards of the succeeding elements, so iterators to them become invalid.

deque

All iterators and references are invalidated, unless the erased members are at an end (front or back) of the deque (in which case only iterators and references to the erased members are invalidated)
Reason:Removing from the end arrays cannot affect the other elements.

list

Only the iterators and references to the erased element is invalidated
Reason: As per addition.

Associative containers

set, map, multiset, multimap

Only iterators and references to the erased elements are invalidated.
Reason: As per addition.

Container adaptors

stack, queue, and priority_queue

Inherited from underlying container.

Resizing

vector, deque, and list

As per insert/erase.

Finding an element in a container

To find an element in a C++ container, or indeed between any pair of InputIterators, use find or find_if.

Use find to find an element with a value you specify. It will return an iterator pointing to the element being sought if successful, and the end of the range if it isn’t found.


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

int main()
{
    std::vector<unsigned int>numbers(3);
    std::iota(numbers.begin(), numbers.end(), 4); // Populate with 4, 5, 6
    if (std::find(numbers.begin(), numbers.end(), 5) != numbers.end()) {
        std::cout << "Found 5" << "\n";
    }
    else {
        std::cout << "5 not found" << "\n";
    }
}

Use find_if to find an element that satisfies a predicate.

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

struct divides_by_3
{
public:
    bool operator()(int i)
    {
        return i % 3 == 0;
    }
};

int main()
{
    std::vector<unsigned int>numbers(3);
    std::iota(numbers.begin(), numbers.end(), 4); // Populate with 4, 5, 6
    std::vector<unsigned int>::const_iterator it = 
            std::find_if(numbers.begin(), numbers.end(), divides_by_3());
    if (it != numbers.end()) {
        std::cout << "Found a number that divides by 3: " << *it << "\n";
    }
    else {
        std::cout << "Not found" << "\n";
    }
}