итератор против reverse_iterator

Это действительно имеет значение? это типы микрооптимизаций, которые вы должны стараться избегать ИМХО. Кроме того, даже если время итерации изменяется для очень большого количества элементов карты, тот факт, что вы пытаетесь перебрать все элементы такой большой карты, означает, что, скорее всего, вы выбрали неправильную структуру данных.

Для справки: разыменование reverse_iterator в контейнерах std::map и std::set вдвое медленнее, чем при использовании iterator -- как с -O3 gcc 3.4.6, так и с MSVC на процессорах Intel/AMD ( почти в 3 раза медленнее на архитектурах PPC.) То же самое верно для const_reverse_iterator по сравнению с const_iterator. Это связано с тем, что reverse_iterator на самом деле указывает на узел дерева, следующий сразу за узлом дерева, который нужно разыменовать, поэтому требуется дополнительная работа. Итераторы std::vector демонстрируют гораздо более мягкую разницу (reverse_iterator всего на ~30% медленнее на PPC, практически неразличима на Intel/AMD). Между прочим, итератор std::vector примерно в 20 раз быстрее, чем итератор std::map или std::set.

#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;
}

Если вы не профилировали свой код и не обнаружили существенной разницы, я бы просто не беспокоился об этом.

«Преждевременная оптимизация — корень всех зол». - Дональд Кнут

Разницы скорее всего не будет. std::reverse_iterator — это просто оболочка шаблона, которая переводит ++ в -- во время компиляции.

Для вектора или другого непрерывного контейнера хранения прямой итератор может немного лучше взаимодействовать с кешем, чем обратный итератор (вряд ли вы сможете его обнаружить), но для древовидного контейнера он не будет иметь никакого значения. разница вообще - не будет никакой локальности ссылки на эксплойт.

Я думаю, что нет смысла использовать reverse_iterator; это противоречит интуиции.

Это затруднит понимание кода, кто-то посмотрит на код и скажет "wtf"; и если вам нужно поставить комментарий, чтобы объяснить, почему, это, вероятно, означает, что это не очень хороший код для начала.

Меня интересует необходимость повторения. Карта содержит пары ключ-значение, и обычно вы используете ее для поиска. Если по каким-то причинам вам по-прежнему необходимо повторить карту (может быть, удаление указателей, содержащихся внутри карты и т. д.), вы можете использовать std::for_each. Забудьте о микрооптимизациях и попробуйте повысить читаемость кода.