Скорость, получающая доступ к станд.:: вектор итератором по сравнению с оператором [] / индекс?
Скажите, у меня есть a
std::vector<SomeClass *> v;
в моем коде и я должен получать доступ к его элементам очень часто в программе, цикличное выполнение их вперед и назад.
Который является самым быстрым типом доступа между теми двумя?
Доступ итератора:
std::vector<SomeClass *> v;
std::vector<SomeClass *>::iterator i;
std::vector<SomeClass *>::reverse_iterator j;
// i loops forward, j loops backward
for( i = v.begin(), j = v.rbegin(); i != v.end() && j != v.rend(); i++, j++ ){
// some operations on v items
}
Нижний доступ (индексом)
std::vector<SomeClass *> v;
unsigned int i, j, size = v.size();
// i loops forward, j loops backward
for( i = 0, j = size - 1; i < size && j >= 0; i++, j-- ){
// some operations on v items
}
И, const_iterator предлагает более быстрый путь к элементам вектора доступа в случае, если я не должен изменять их?
7 ответов
Разница в производительности, скорее всего, незначительна или вообще отсутствует (компилятор может оптимизировать их как одинаковые); вам следует беспокоиться о других вещах, например, о корректности вашей программы (медленная, но корректная программа лучше, чем быстрая и некорректная). Однако у использования итераторов есть и другие преимущества, например, возможность изменить базовый контейнер на тот, в котором нет operator[] без изменения циклов. Подробнее см. в этом вопросе.
const_итераторы, скорее всего, не будут иметь никакой или незначительной разницы в производительности по сравнению с обычными итераторами. Они предназначены для улучшения корректности вашей программы, предотвращая изменение того, что не должно быть изменено, а не для повышения производительности. То же самое относится и к ключевому слову const в целом.
Короче говоря, оптимизация не должна вас волновать, пока не произойдут две вещи: 1) вы заметили, что он работает слишком медленно и 2) вы определили узкие места. Для 1), если он работает в десять раз медленнее, чем мог бы, но выполняется только один раз и занимает 0.1 мс, кого это волнует? Для 2) убедитесь, что это точно узкое место, иначе его оптимизация почти не окажет заметного влияния на производительность!
Я считаю, что векторные итераторы внутренне реализованы как указатели (в хорошей реализации STL), поэтому в целом следует быть незначительной разницей в производительности между двумя идиомами. Но если вы хотите узнать, как они работают на вашей платформе, почему бы вам не измерить их с помощью небольшой тестовой программы? Я не думаю, что для измерения времени выполнения, например, потребуется более 5 минут. 1 миллион итераций с обоими вариантами ...
Вы оптимизируете не только преждевременно, но и оптимизируете на микроуровне. Это зло почти так же плохо, как и первое (с той разницей, что очень, очень, очень редко требуется микрооптимизация). Соедините их вместе, и вы получите рецепт катастрофы.
Если вы запустите профилировщик и обнаружите, что эта область кода является узким местом, вам потребуется оптимизация. Вы не оптимизируете, пытаясь сократить свой цикл с 23 тактовых циклов до 22. Вы оптимизируете, находя способы уменьшить O () вашего алгоритма. Но пока вы не запустите профилировщик, вам следует уделять дизайну больше внимания, чем любой другой заботе.
Если скорость имеет значение, тогда у вас должно быть время и желание запустить на нем профилировщик и посмотреть, какой из них лучше всего работает в вашем случае.
Если это не имеет значения, значит, вы выполняете преждевременную оптимизацию и должны ПРЕКРАТИТЬ это делать.
Как всегда, это зависит от обстоятельств. Обычно я не думаю, что вы заметите какую-либо разницу, но только вы можете определить это, профилировав свой код. Некоторые компиляторы реализуют векторные итераторы как необработанные указатели, а некоторые - нет. Кроме того, в отладочных сборках некоторые компиляторы могут использовать проверенный итератор, который может работать медленнее. Но в производственном режиме все не может быть иначе. Профилируйте это и посмотрите.
Что касается скорости, я думаю, может быть почти таким же. Лучше, вы все равно можете профилировать и проверять.
По крайней мере, вы можете уменьшить количество используемых переменных :)
for( i = 0; i < size ; i++){
// some operations on v items
v[i];
v[size-i+1];
}
О const_iterator : Пожалуйста, обратитесь к моему Q: A re const_iterators быстрее?
Я бы выбрал итераторы, но я бы оптимизировал вызов end () в цикл и изменит преинкремент на постинкремент. Т.е. Я бы
std::vector<SomeClass *> v;
std::vector<SomeClass *>::iterator i,ie;
std::vector<SomeClass *>::reverse_iterator j,je;
// i loops forward, j loops backward
for( i=v.begin(),ie=v.end(), j=v.rbegin(),je=v.rend(); i!=ie && j!=je; ++i,++j ){
// some operations on v items
}
И я не думаю, что это преждевременная микрооптимизация, это просто написание лучшего кода. Намного меньшее зло, чем называть каждую попытку написать эффективный код преждевременной микрооптимизацией и заменять мышление профилированием.