Являются ли const_iterators быстрее?
Наши правила кодирования предпочитают const_iteratorпотому что они немного быстрее по сравнению с нормальным iterator, Кажется, что компилятор оптимизирует код при использовании const_iterator,
Это действительно правильно? Если да, то что на самом деле происходит внутри, что делает const_iterator Быстрее?.
РЕДАКТИРОВАТЬ: я написал небольшой тест, чтобы проверить const_iterator против iterator и нашел разные результаты:
Для итерации 10000 объектов const_terator занимал несколько миллисекунд (около 16 мс) меньше. Но не всегда. Были итерации, в которых оба были равны.
11 ответов
Если ничего другого, то const_iterator читает лучше, так как он говорит любому, кто читает код: "Я просто перебираю этот контейнер, не перебирая содержащиеся в нем объекты".
Это очень большая победа, не говоря уже о различиях в производительности.
Руководство, которое мы используем:
Всегда предпочитайте const, а не const
Если вы склонны использовать объект const, вы привыкнете использовать только постоянные операции над объектами, которые вы получаете, и это все равно, что использовать const_iterator настолько, насколько это возможно.
Constness обладает вирусным свойством. Как только вы его используете, он распространяется на весь ваш код. Ваши немутантные методы становятся постоянными, и для этого нужно использовать только постоянные операции над атрибутами и передавать постоянные ссылки, что само по себе вызывает только постоянные операции...
Для меня преимущество в производительности использования постоянных итераторов по сравнению с непостоянными итераторами (если они вообще есть) гораздо менее важно, чем улучшение самого кода. Операции, предназначенные (предназначенные) для того, чтобы не иметь мутаций, являются постоянными.
Они для нетривиальных контейнеров / итераторов. Откорректируйте свои привычки, и вы не потеряете производительность, когда это важно.
Кроме того, есть несколько причин предпочесть const_iterator, несмотря ни на что:
- Использование const выражает намерение кода (т. Е. Только чтение, без изменения этих объектов).
- Использование const(_iterator) предотвращает случайное изменение данных. (см. выше)
- Некоторые библиотеки используют нехватку констант
begin()помечать данные как "грязные" (то есть OpenSG) и отправлять их другим потокам / по сети при синхронизации, чтобы они имели реальные последствия для производительности. - Кроме того, разрешение доступа к неконстантным функциям-членам может иметь побочные эффекты, которые вы не намерены (во многом аналогично описанным выше), например отсоединение контейнеров копирования при записи от общих данных. 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,
Конечно, есть точки данных в другом направлении:
- Для контейнеров STL и многих других семантических контейнеров с простым копированием это не повлияет на производительность. Код эквивалентен. Тем не менее, возможность написать чистый код и избежать ошибок выигрывает.
- Const является вирусным, поэтому, если вы работаете в устаревшей кодовой базе, где const плохо (или просто не реализован), вам, возможно, придется работать с неконстантными итераторами.
- По-видимому, в некоторых C++0x STL есть ошибка, из-за которой const_iterators нельзя было использовать для стирания () элементов из контейнеров.
Я не могу понять, почему они будут - константность - это проверка времени компиляции. Но очевидный ответ - написать тест.
Изменить: Вот мой тест - он дает идентичные тайминги на моей машине:
#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;
}
Это зависит от контейнера и реализации, которую вы используете.
Да, const_iterator может работать лучше.
Для некоторых контейнеров реализация константных итераторов и изменяемых итераторов может отличаться. Первый пример, который я могу вспомнить, - это контейнер SGL STL. Изменяемый итератор имеет дополнительный указатель на родительский трос для поддержки обновлений. Это подразумевает дополнительные ресурсы, потраченные впустую на обновления подсчета ссылок + память для указателя на родительский трос. Смотрите замечания по реализации здесь.
Однако, как говорили другие, компилятор не может использовать const Самостоятельно делать оптимизацию. const просто предоставляет доступ только для чтения к указанному объекту, а не говорит, что он неизменен. Для контейнера, как std::vector, чьи итераторы обычно реализованы как простые указатели, различий не будет.
Наши правила написания кода говорят, предпочитают const_iterator
Взгляните на эту статью Скотта Мейерса здесь. Он объясняет, почему следует предпочесть итератор, а не const_iterator.
Они должны быть идентичны, так как 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)
Когда вы тестируете что-либо из этого, убедитесь, что используете соответствующий уровень оптимизации - вы получите совершенно разные значения времени, используя "-O0" против "-O" и т. д.
container<T>::const_iterator::operator* возвращает const T& вместо T&Таким образом, компилятор может сделать обычные оптимизации для константных объектов.
"Константность", как ограничение доступа (общедоступное, защищенное, частное), приносит пользу программисту больше, чем помогает в оптимизации.
На самом деле компиляторы не могут оптимизировать столько ситуаций, связанных с использованием const, сколько может показаться, по многим причинам (например, const_cast, изменяемые члены данных, псевдонимы указателей / ссылок). Однако наиболее важной причиной здесь является то, что тот факт, что const_iterator не позволяет изменять данные, на которые он ссылается, не означает, что эти данные нельзя изменить другими способами. И если компилятор не может определить, что данные доступны только для чтения, тогда он не сможет оптимизировать намного больше, чем для случая неконстантного итератора.
Дополнительную информацию и примеры можно найти по адресу: http://www.gotw.ca/gotw/081.htm
По моему опыту, компилятор не выполняет какую-либо измеримую оптимизацию при использовании константных итераторов. Несмотря на то, что утверждение "это может" верно, и ссылки не определены как указатели в стандарте.
Однако у вас может быть две ссылки на один и тот же объект, поэтому одна может быть const, одна не const. Затем, я предполагаю, что ответы в этом потоке на ограничительные указатели применимы: компилятор не может знать, был ли объект изменен, например, другим потоком или некоторым кодом обработки прерываний.