Подтвердить что ты не робот

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

Это может показаться несерьезным для некоторых из вас, но какой из следующих двух методов итерации над контейнером 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 достигает того же самого с меньшим кодом. Простая итерация над контейнером - это то, что появляется повсюду в любом исходном коде. Итак, я склонен выбрать метод 1, который, как представляется, уменьшает визуальный беспорядок и размер кода.

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

Ответ 2

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

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

Ответ 3

Метод 0 быстрее и, следовательно, рекомендуется.

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

Ответ 4

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

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

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

Ответ 5

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

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

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

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

Ответ 6

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

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

UPDATE: добавлен stl-алгоритм std:: generate, который, кажется, работает быстрее, из-за специальной оптимизации итератора (VС++ 2008). время в микросекундах.

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

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

Обновление: вышеуказанные времена были в ситуации с привязкой к I/O, я делал те же тесты с привязкой к процессору (перебирал относительно относительно короткий вектор, который должен входить в кеш многократно, умножать каждый элемент на 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

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

Ответ 7

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

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

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

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

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

Ответ 8

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

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

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

Ответ 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
}

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