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

Question

Некоторым из вас это может показаться легкомысленным, но какой из следующих двух способов итерации над контейнером STL лучше? Почему

class Elem;
typedef vector<Elem> ElemVec;
ElemVec elemVec;

// Method 0
for (ElemVec::iterator i = elemVec.begin(); i != elemVec.end(); ++i)
{
    Elem& e = *i;
    // Do something
}

// Method 1
for (int i = 0; i < elemVec.size(); ++i)
{
    Elem& e = elemVec.at(i);
    // Do something
}

Метод 0 кажется более чистым STL, но метод 1 достигает того же с меньшим кодом. Простая итерация над контейнером - это то, что появляется all в любом месте исходного кода. Итак, я склонен выбрать метод 1, который, кажется, уменьшает визуальный беспорядок и размер кода.

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

Answer 1

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

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

Как обычно, не существует простого ответа "этот лучше", я боюсь.

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

Answer 6

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

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

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

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

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

Answer 7

По совпадению я недавно сделал тест скорости (заполняя 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  

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

Answer 8

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

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

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

Answer 9

Возможность, не рассмотренная выше: в зависимости от деталей «Сделай что-нибудь», можно использовать метод 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
}

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