Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Iterator Invalidation in C++
#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);
});
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment