Iterator Invalidation in C++

gistfile1.cpp

#include <boost/container/stable_vector.hpp>
#include <boost/timer/timer.hpp>
#include <vector>
#include <cstring>
#include <sys/time.h>
#include <iostream>
#include <cstdlib>

template <typename Container>
void randomize (Container &container)
{
    /* Add 3 elements */
    for (size_t i = 0; i < 3; ++i)
        container.push_back (0);

    /* Delete 2 elements at random */
    for (size_t i = 0; i < 2; ++i)
    {
        size_t distance = (rand () * container.size ()) % container.size ();
        auto it = container.begin ();
        std::advance (it, distance);
        container.erase (it);
    }
}

template <typename Container>
void fill (Container &container, std::array <int, 10000> &value)
{
    auto containerEnd = container.end ();
    for (auto i = container.begin (); i != containerEnd; ++i)
        (*i) = value.data () + ((rand () * 9999) % 9999);
}

template <typename Container>
size_t iterate (Container &container)
{
    auto volatile size = container.size ();
    auto containerEnd = container.end ();
    for (auto i = container.begin (); i != containerEnd; ++i)
    {
        int volatile const item = *(*(i));
    }
    return size;
}

template <typename Function>
void benchmark (std::string const name, size_t iterations, Function const &f)
{
    auto func = [&iterations, &f]() {
                    boost::timer::auto_cpu_timer t;
                    for (size_t i = 0; i < iterations; ++i)
                    {
                        volatile auto q = f ();
                    }
                };

    std::cout << iterations << " of " << name << " (cold)" << std::endl;
    func ();

    std::cout << iterations << " of " << name << " (warm)" << std::endl;
    func ();
}

int main (int argc, char **argv)
{
    size_t iterations = atoi (argv[1]);

    std::array <int, 10000> values;

    /* Setup containers */
    boost::container::stable_vector <int *> bcv;
    std::vector <int *> vec;
    std::list <int *> list;

    for (size_t i = 0; i < 20; ++i)
    {
        randomize (bcv);
        fill (bcv, values);
        randomize (vec);
        fill (vec, values);
        randomize (list);
        fill (list, values);
    }

    benchmark ("boost::stable_vector",
               iterations,
               [&bcv]() {
                    return iterate (bcv);
               });
    benchmark ("std::vector",
               iterations,
               [&vec]() {
                    return iterate (vec);
               });
    benchmark ("std::list",
               iterations,
               [&list]() {
                    return iterate (list);
               });
}