iterator vs reverse_iterator

Question

I'm using std::map to store a lot of elements (pairs of elements) and I have a "little" doubt. What is more efficient to iterate all elements over my std::map, iterator or reverse_iterator?

Answer 1

For the record, dereferencing reverse_iterator on std::map and std::set containers is twice as slow as using iterator -- with both -O3 gcc 3.4.6 and MSVC on Intel/AMD processors (almost 3x as slow on PPC architectures.) Same holds for const_reverse_iterator vs. const_iterator. This is due to the fact that reverse_iterator actually points to the tree node immediately following the tree node to be dereferenced, hence the extra work. std::vector iterators exhibit a much milder difference (reverse_iterator is only ~30% slower on PPC, virtually indistinguishable on Intel/AMD.) Incidentally, a std::vector iterator is about 20x faster than a std::map or std::set iterator.

#include <set>
#include <vector>
#include <stdio.h>
#ifdef _WIN32
#include <sys/timeb.h>
#else
#include <sys/time.h>
#endif
#include <time.h>

#define CONTAINER std::set< int >

double
mygettime(void) {
# ifdef _WIN32
  struct _timeb tb;
  _ftime(&tb);
  return (double)tb.time + (0.001 * (double)tb.millitm);
# else
  struct timeval tv;
  if(gettimeofday(&tv, 0) < 0) {
    perror("oops");
  }
  return (double)tv.tv_sec + (0.000001 * (double)tv.tv_usec);
# endif
}


int main() {
  int i, x = 0;
  CONTAINER bla;
  for (i = 0; i < 10000; bla.insert(bla.end(), i++)) ;

  double t1 = mygettime();

  for (i = 0; i < 100; ++i) {
    for (CONTAINER::iterator it = bla.begin(); it != bla.end(); ++it) {
      x ^= *it;
    }
  }

  printf("forward: %f\n", mygettime() - t1);

  double t2 = mygettime();

  for (i = 0; i < 100; ++i) {
    for (CONTAINER::reverse_iterator it = bla.rbegin(); it != bla.rend(); ++it) {
      x ^= *it;
    }
  }

  printf("reverse: %f\n", mygettime() - t2);

  return 0;
}

Answer 2

Does it really matter? these are the types of the micro optimizations you must try to avoid IMHO. Also, even if the iteration time changes for very large number of elements in the map, the fact that you are trying to iterate through all the elements of such a big map means that most probably you have chosen a wrong data structure.