C ++ STL: какой метод итерации по контейнеру STL лучше?

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

Вторая версия работает только для векторов и других контейнеров с целочисленным индексом. Это было бы несколько более идиоматично для этих контейнеров, будет легко понятно новичкам в C ++ и будет полезно, если вам нужно сделать что-то еще с индексом, что не редкость.

Боюсь, что, как обычно, простого ответа «этот лучше» не существует.

Если вы не возражаете против (очень?) Небольшой потери эффективности, я бы рекомендовал использовать Boost.Foreach

BOOST_FOREACH( Elem& e, elemVec )
{
    // Your code
}

Метод 0 быстрее и поэтому рекомендуется.

Метод 1 использует size (), которому разрешено быть O (1), в зависимости от контейнера и реализации stl.

Лучше всего использовать следующий метод итерации по контейнеру стандартной библиотеки.

Используйте c ++ 11 (и не только) for-loop на основе диапазона с auto спецификатор:

// Method 2
for (auto& e: elemVec)
{
    // Do something with e...
}

Это похоже на ваш Method 0, но требует меньше ввода, меньше обслуживания и работает с любым контейнером, совместимым с std::begin() и std::end(), включая plain- старые массивы.

Еще несколько преимуществ метода 0:

• если вы перейдете из вектора в другой контейнер, цикл останется прежним,
• легко перейти от итератора к const_iterator, если вам нужно,
• когда появится c ++ 0x, автоматическая типизация уменьшит беспорядок в коде.

Основным недостатком является то, что во многих случаях вы сканируете два контейнера, и в этом случае индекс чище, чем сохранение двух итераторов.

Метод 0 по нескольким причинам.

• Он лучше выражает ваше намерение, что способствует оптимизации компилятора, а также удобочитаемости.
• Поочередные ошибки менее вероятны
• Это работает, даже если вы замените вектор списком, в котором нет оператора []

Конечно, лучшим решением часто будет решение 2: один из стандартных алгоритмов. std :: for_each, std :: transform, std :: copy или все, что вам нужно. У этого есть еще несколько преимуществ:

• Он еще лучше выражает ваше намерение и допускает некоторые значительные оптимизации компилятора (безопасный SCL MS выполняет проверку границ для ваших методов 0 и 1, но пропускает его в алгоритмах std)
• Это меньше кода (по крайней мере, на сайте вызова. Конечно, вам нужно написать функтор или что-то еще, чтобы заменить тело цикла, но на сайте использования код немного очищается, что, вероятно, является наиболее важным. .

В общем, избегайте чрезмерного определения кода. Укажите именно то, что вы хотите сделать, и ничего больше. Обычно лучше всего подходят алгоритмы std, но даже без них, если вам не нужен индекс i, зачем он? В этом случае используйте итераторы.

Так совпало, что недавно я провел тест скорости (заполнив 10 * 1024 * 1024 целых с помощью rand ()).
Это 3 запуска, время в наносекундах

vect[i] time      : 373611869  
vec.at(i) time    : 473297793  
*it = time        : 446818590  
arr[i] time       : 390357294  
*ptr time         : 356895778  

ОБНОВЛЕНИЕ: добавлен stl-алгоритм std :: generate, который, кажется, работает быстрее всего из-за специальной оптимизации итератора (VC ++ 2008). время в микросекундах.

vect[i] time      : 393951
vec.at(i) time    : 551387
*it = time        : 596080
generate = time   : 346591
arr[i] time       : 375432
*ptr time         : 334612

Вывод: используйте стандартные алгоритмы, они могут быть быстрее, чем явный цикл! (а также хорошая практика)

Обновление: указанное выше время было в ситуации, связанной с вводом-выводом, я провел те же тесты с привязкой к ЦП (итерация по относительно короткому вектору, который должен многократно помещаться в кеш, умножение каждого элемента на 2 и запись обратно в вектор )

//Visual Studio 2008 Express Edition
vect[i] time      : 1356811
vec.at(i) time    : 7760148
*it = time        : 4913112
for_each = time   : 455713
arr[i] time       : 446280
*ptr time         : 429595

//GCC
vect[i] time      : 431039
vec.at(i) time    : 2421283
*it = time        : 381400
for_each = time   : 380972
arr[i] time       : 363563
*ptr time         : 365971  

Интересно, что итераторы и operator [] значительно медленнее в VC ++ по сравнению с for_each (который, похоже, ухудшает итераторы до указателей с помощью некоторой магии шаблонов для повышения производительности).
В GCC время доступа только хуже для at (), что нормально , потому что это единственная функция тестов с проверкой диапазона.

Это зависит от того, какой тип тары. Для vector, вероятно, не имеет значения, что вы используете. Метод 0 стал более идиоматичным, но, как все говорят, это не большая разница.

Если бы вы решили использовать list, вместо этого метод 1, в принципе, был бы O(N), но на самом деле метода list at() нет, поэтому вы даже не можете сделать это таким образом. (Так что на каком-то уровне ваш вопрос складывается в колоду.)

Но это само по себе является еще одним аргументом для метода 0: он использует один и тот же синтаксис для разных контейнеров.

Возможность, не рассмотренная выше: в зависимости от деталей «Сделать что-нибудь», можно использовать метод 0 и метод 1 одновременно, вам не нужно выбирать:

for (auto i = elemVec.begin(), ii = 0; ii < elemVec.size(); ++i, ++ii)
{
    // Do something with either the iterator i or the index ii
}

Таким образом, поиск индекса или доступ к соответствующему члену выполняются с тривиальной сложностью.