итератор по сравнению с reverse_iterator

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

«Преждевременная оптимизация - это корень проблемы. все зло. "- Дональд Кнут

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

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

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

Мне кажется, нет смысла использовать reverse_iterator; это противоречит интуиции.

Из-за этого код будет труднее понять, кто-то посмотрит на код и скажет «черт возьми»; и если вам нужно добавить комментарий, чтобы объяснить почему, это, вероятно, означает, что это не лучший код для начала.

Для записи, разыменование reverse_iterator на std :: map и std: : set контейнеров вдвое медленнее , чем при использовании итератора - и с -O3 gcc 3.4.6, и с MSVC на процессорах Intel / AMD (почти в 3 раза медленнее на архитектурах PPC .) То же самое верно для const_reverse_iterator vs. 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;
}