Continued from http://en.sfml-dev.org/forums/index.php?topic=10046.msg69235#msg69235I have written a benchmark to compare iteration through random access containers. The code is rather complex, because I tried to make the comparison as fair as possible. Every iteration is executed multiple times, and the different iterations are executed in random order to reduce uneven conditions.
ComparisonIterations: iterator,
operator[]Containers:
std::vector,
std::dequeElement types:
int,
std::stringCode#include <SFML/System/Clock.hpp>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <deque>
#include <map>
#include <array>
#include <functional>
#include <algorithm>
#include <cstdlib>
inline void compute(int& v) { v = (v + 25) % 13; }
inline void compute(std::string& v) { v = "x"; }
template <typename Container>
sf::Time testIterator(Container& c)
{
sf::Clock clock;
for (auto itr = c.begin(), end = c.end(); itr != end; ++itr)
compute(*itr);
return clock.getElapsedTime();
}
template <typename Container>
sf::Time testIndex(Container& c)
{
sf::Clock clock;
for (std::size_t i = 0, size = c.size(); i != size; ++i)
compute(c[i]);
return clock.getElapsedTime();
}
template <typename T>
void benchmark(std::map<std::string, sf::Time>& times, const std::string& type, std::size_t elements)
{
std::vector<T> vector(elements);
std::deque<T> deque(elements);
std::array<std::function<void()>, 4> array =
{
[&] () { times["vector<" + type + "> iterator"] += testIterator(vector); },
[&] () { times[" deque<" + type + "> iterator"] += testIterator(deque); },
[&] () { times["vector<" + type + "> index "] += testIndex(vector); },
[&] () { times[" deque<" + type + "> index "] += testIndex(deque); },
};
// Make sure the single tests are executed in random order
std::random_shuffle(array.begin(), array.end());
std::for_each(array.begin(), array.end(), [] (std::function<void()>& fn) { fn(); });
// Prevent optimization of unused containers
if (std::rand() < 0)
std::cout << vector[std::rand() % vector.size()] << deque[std::rand() % deque.size()];
}
int main()
{
std::map<std::string, sf::Time> times;
const std::size_t outer = 10000;
const std::size_t inner = 100000;
for (std::size_t m = 0; m < outer; ++m)
{
benchmark<int> (times, "int ", inner);
benchmark<std::string>(times, "string", inner);
}
for (auto itr = times.begin(); itr != times.end(); ++itr)
std::cout << itr->first << " " << std::setw(6) << std::right << itr->second.asMilliseconds() << "\n";
std::cin.get();
}
ResultsVC++ 10, Release mode, without debugger, NDEBUG defined
deque<int > index 10779
deque<int > iterator 4884
deque<string> index 20268
deque<string> iterator 14991
vector<int > index 4711
vector<int > iterator 4764
vector<string> index 13953
vector<string> iterator 13459
g++ 4.6.2 (MinGW), -std=c++0x -O2 -DNDEBUG
deque<int > index 5456
deque<int > iterator 4914
deque<string> index 45758
deque<string> iterator 42905
vector<int > index 4896
vector<int > iterator 4908
vector<string> index 42874
vector<string> iterator 42547
ConclusionsFor
std::vector, both index operator and iterator take more or less the same execution time.
For
std::deque, iterator is a clear winner, especially on VC++.
Tell me when you see any flaws in the code or the compiler flags. Of course, the rather simple operations in the loop are not representative of every possible iteration use case. However, the more complex the loop body becomes, the more time it takes to execute, while iteration itself becomes more negligible.
Since iterators are not slower, I suggest to follow the simple rule:
Use iterators when you iterate and index operator when you need random access. 
