Iterator Invalidation in C++
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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