Обратные итераторы
Это приводит к тому, что * возвращает значение *(current-1)...
Да, по смыслу именно так:
24.4.1.3.3 operator* [lib.reverse.iter.op.star]
reference operator*() const;
Действия:
Iterator tmp = current; return *--tmp;
Т.е. каждый раз, когда вы применяете разыменование обратного итератора, происходит создание временного итератора, его декремент и разыменование. Не многовато ли, для такой простой и часто используемой (как правило, в цикле для каждого элемента) операции? Д-р Страуструп пишет по этому поводу следующее:
I don't think anyone would use a reverse iterator if an iterator was an alternative, but then you never know what people might know. When you actually need to go through a sequence in reverse order a reverse iterator is often quite efficient compared to alternatives. Finally, there may not be any overhead because where the iterator is a vector the temporary isn't hard to optimize into a register use. One should measure before worrying too much about overhead.
Я не думаю, что бы кто-то использовал обратный итератор там, где можно использовать обычный, но мы никогда не можем знать, что думают другие люди. Когда вам действительно нужно пройти последовательность в обратном порядке, обратный итератор является вполне приемлемой альтернативой. В принципе, иногда можно вообще избежать накладных расходов, например в случае обратного прохода по вектору, когда временная переменная-итератор без труда размещается в регистре. В любом случае, не стоит чрезмерно беспокоиться о производительности не проведя реальных измерений.
Вместе с тем, обратный итератор все-таки несет в себе ненужные накладные расходы, и для обратного прохода по последовательности лучше использовать обычный итератор с явным (пре)декрементом.
И раз уж речь зашла о реальных измерениях, давайте их произведем. #include <stdio.h> #include <stdlib.h> #include <time.h> #include <list>
long Count, Var;
typedef std::list<int> list_type; list_type lst;
void f1() { for (list_type::reverse_iterator ri=lst.rbegin(), rend=lst.rend(); ri!=rend; ++ri) Var+=*ri; }
void f2() { list_type::iterator i=lst.end(), beg=lst.begin(); if (i!=beg) { do { --i; Var+=*i; } while (i!=beg); } }
int main(int argc, char** argv) { if (argc>1) Count=atol(argv[1]);
for (int i=0; i<10000; i++) lst.push_back(i);
clock_t c1, c2; { c1=clock();
for (long i=0; i<Count; i++) for (long j=0; j<1000; j++) f1();
c2=clock(); printf("f1(): %ld ths calls per %.1f sec\n", Count, double(c2-c1)/CLK_TCK); } { c1=clock();
for (long i=0; i<Count; i++) for (long j=0; j<1000; j++) f2();
c2=clock(); printf("f2(): %ld ths calls per %.1f sec\n", Count, double(c2-c1)/CLK_TCK); } }
В данном примере список из 10 000 элементов проходится несколько тысяч раз (задается параметром) с использованием обратного (в f1()) и обычного (в f2()) итераторов. При использовании качественного оптимизатора разницы времени выполнения замечено не было, а для "обычных" реализаций она составила от 45% до 2.4 раза.
И еще одна проблема: приводит ли постинкремент итератора к существенным накладным расходам по сравнению с преинкрементом? Давайте внесем соответствующие изменения: void f1() { for (list_type::iterator i=lst.begin(), end=lst.end(); i!=end; ++i) Var+=*i; }
void f2() { for (list_type::iterator i=lst.begin(), end=lst.end(); i!=end; i++) Var+=*i; }
И опять все тот же результат: разницы может не быть, а там, где она проявлялась, ее величина находилась в пределах 5 - 30 процентов.
В целом, не стоит использовать потенциально более дорогие обратные итераторы и постинкременты, если вы не убедились в интеллектуальности используемого оптимизатора.
