Являются ли const_iterators быстрее?

Question

Наши рекомендации по кодированию предпочитают const_iterator, потому что они немного быстрее по сравнению с обычным iterator. Кажется, что компилятор оптимизирует код, когда вы используете const_iterator.

Это действительно правильно? Если да, то что на самом деле происходит внутри, что делает const_iterator быстрее?.

РЕДАКТИРОВАТЬ: я написал небольшой тест для проверки const_iterator против iterator и нашел разные результаты:

Для итерации 10 000 объектов const_terator занимал несколько миллисекунд (около 16 мс) меньше. Но не всегда . Были итерации, в которых оба были равны.

Answer 1

Если ничего другого, то const_iterator лучше читает , поскольку он говорит всем, кто читает код «Я просто перебираю этот контейнер, не перебирая содержащиеся в нем объекты».

Это огромная победа, не говоря уже о различиях в производительности.

Answer 2

Указание, которое мы используем:

Всегда предпочитайте const, а не const

Если вы склонны использовать объект const, вы привыкнете использовать только постоянные операции над объектами, которые вы получаете, и это все равно, что максимально использовать const_iterator .

Constness обладает вирусным свойством. Как только вы его используете, он распространяется на весь ваш код. Ваши немутантные методы становятся постоянными, и для этого нужно использовать только постоянные операции над атрибутами и передавать постоянные ссылки, что само по себе вызывает только постоянные операции ...

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

Answer 3

Они для нетривиальных контейнеров / итераторов. Откорректируйте свои привычки, и вы не потеряете производительность, когда это важно.

Кроме того, есть несколько причин, чтобы предпочесть const_iterator, несмотря ни на что:

1. Использование const выражает намерение кода (т. Е. Только чтение, без изменения этих объектов).
2. Использование const (_iterator) предотвращает случайное изменение данных. (см. выше)
3. В некоторых библиотеках используется отсутствие констант begin(), чтобы пометить данные как «грязные» (то есть OpenSG) и отправить их в другие потоки / по сети при синхронизации, поэтому там это влияет на производительность.
4. Кроме того, разрешение доступа к неконстантным функциям-членам может иметь побочные эффекты, которые вы не намерены (во многом аналогично описанным выше), например, отсоединение контейнеров копирования при записи от общих данных. Qt для одного, делает именно это.

В качестве примера последнего пункта выше приведен отрывок из qmap.h в Qt:

inline iterator begin() { detach(); return iterator(e->forward[0]); }
inline const_iterator begin() const { return const_iterator(e->forward[0]); }

Даже если итератор и const_iterator практически эквивалентны (за исключением const), detach() создает новую копию данных, если ее используют два или более объектов. Это совершенно бесполезно, если вы просто собираетесь читать данные, которые вы указываете с помощью const_iterator.

Конечно, есть точки данных в другом направлении:

1. Для контейнеров STL и многих других семантических контейнеров простого копирования это не имеет значения для производительности. Код эквивалентен . Тем не менее, возможность написать чистый код и избежать ошибок побеждает.
2. Const является вирусным, поэтому, если вы работаете в устаревшей базе кода, где const плохо (или просто не реализован), вам, возможно, придется работать с неконстантными итераторами.
3. По-видимому, в некоторых до C ++ 0x STL есть ошибка, из-за которой const_iterators нельзя было использовать для стирания () элементов из контейнеров.

Answer 4

Я не понимаю, почему это так - константность - это проверка времени компиляции. Но очевидный ответ - написать тест.

Редактировать: Вот мой тест - он дает идентичные тайминги на моей машине:

#include <vector>
#include <iostream>
#include <ctime>
using namespace std;;


int main() {
    vector <int> v;
    const int BIG = 10000000;
    for ( int i = 0; i < BIG; i++ ) {
        v.push_back( i );
    }
    cout << "begin\n";
    int n = 0;
    time_t now = time(0);
    for ( int a = 0; a < 10; a++ ) {
        for( vector <int>::iterator it = v.begin(); it != v.end(); ++it ) {
            n += *it;
        }
    }
    cout << time(0) - now << "\n";
    now = time(0);
    for ( int a = 0; a < 10; a++ ) {
        for( vector <int>::const_iterator cit = v.begin(); cit != v.end(); ++cit ) {
            n += *cit;
        }
    }
    cout << time(0) - now << "\n";;

    return n != 0;

}

Answer 5

Это зависит от контейнера и используемой вами реализации.

Да, const_iterator может выступать лучше.

Для некоторых контейнеров реализация константных итераторов и изменяемых итераторов может отличаться . Первый пример, который я могу вспомнить, это веревочный контейнер STL SGI . Изменяемый итератор имеет дополнительный указатель на родительский трос для поддержки обновлений. Это подразумевает дополнительные ресурсы, потраченные впустую на обновления подсчета ссылок + память для указателя на родительский трос. См. замечания по реализации здесь .

Однако, как говорили другие, компилятор не может самостоятельно использовать const для оптимизации. const просто предоставляет доступ только для чтения к указанному объекту, а не говорит, что он неизменен. Для контейнера типа std::vector, чьи итераторы обычно реализованы в виде простых указателей, различий не будет.

Answer 6

В наших правилах написания кода предпочтение отдается const_iterator

Взгляните на эту статью Скотта Мейерса здесь . Он объясняет, почему следует предпочитать итератор, а не const_iterator.

Answer 7

Они должны быть идентичны, поскольку constness является проверкой во время компиляции.

Чтобы доказать себе, что не было никаких причуд, я взял код anon, изменил его для использования clock_gettime, добавил внешний цикл, чтобы избежать кеширования ошибок, и запустил его много раз. Результаты оказались на удивление противоречивыми - вверх и вниз на 20% (нет свободных ящиков) - но минимальные времена для iterator и const_iterator были практически идентичны .

Затем я получил свой компилятор (GCC 4.5.2 -O3) для генерации вывода сборки и визуально сравнил два цикла: идентичный (за исключением того, что порядок пары регистрируется был полностью изменен)

iterator петля

    call    clock_gettime
    movl    56(%esp), %esi
    movl    $10, %ecx
    movl    60(%esp), %edx
    .p2align 4,,7
    .p2align 3
.L35:
    cmpl    %esi, %edx
    je  .L33
    movl    %esi, %eax    .p2align 4,,7
    .p2align 3
.L34:
    addl    (%eax), %ebx
    addl    $4, %eax
    cmpl    %eax, %edx
    jne .L34
.L33:
    subl    $1, %ecx
    jne .L35
    leal    68(%esp), %edx
    movl    %edx, 4(%esp)
    leal    56(%esp), %esi
    movl    $1, (%esp)

const_iterator цикл:

    movl    60(%esp), %edx
    movl    $10, %ecx
    movl    56(%esp), %esi
    .p2align 4,,7
    .p2align 3
.L38:
    cmpl    %esi, %edx
    je  .L36
    movl    %esi, %eax
    .p2align 4,,7
    .p2align 3
.L37:
    addl    (%eax), %ebx
    addl    $4, %eax
    cmpl    %eax, %edx
    jne .L37
.L36:
    subl    $1, %ecx
    jne .L38
    leal    68(%esp), %edx
    movl    %edx, 4(%esp)
    leal    56(%esp), %esi
    movl    $1, (%esp)

Answer 8

, когда вы тестируете что-либо из этого, убедитесь, что используете соответствующий уровень оптимизации - вы получите совершенно разные значения времени, используя «-O0» и «-O» и т. Д.

Answer 9

«Константность», как и ограничение доступа (публичный, защищенный, приватный), приносит больше пользы программисту, чем помогает в оптимизации.
На самом деле компиляторы не могут оптимизировать столько ситуаций, в которых используется const, сколько можно подумать, по многим причинам (например, const_cast, изменяемые члены данных, псевдонимы указателей / ссылок). Однако наиболее важной причиной здесь является то, что тот факт, что const_iterator не позволяет изменять данные, на которые он ссылается, не означает, что эти данные нельзя изменить другими способами. И если компилятор не может определить, что данные доступны только для чтения, он не сможет оптимизировать намного больше, чем для случая неконстантного итератора.
Дополнительную информацию и примеры можно найти по адресу: http://www.gotw.ca/gotw/081.htm

Answer 10

container<T>::const_iterator::operator* возвращает const T& вместо T&, поэтому компилятор может выполнять обычные оптимизации для константных объектов.