Получить индекс вектора с помощью итераторов

Question

При переборе элементов вектора предпочтительно использовать итераторы вместо индекса (см. Зачем использовать итераторы вместо индексов массива?).

std::vector<T> vec;
std::vector<T>::iterator it;
for ( it = vec.begin(); it != vec.end(); ++it )
{
   // do work
}

Однако может возникнуть необходимость использовать индекс в теле цикла.Что из следующего будет предпочтительнее в этом случае с учетом производительности и гибкости/расширяемости?

1. Вернуться к индексированному циклу

   std::vector vec;
   size_t i;
   for ( i = 0; i < vec.size(); ++i )
   {
      // use i
   }
   

2. Рассчитать смещение

   std::vector vec;
   std::vector::iterator it;
   for ( it = vec.begin(); it != vec.end(); ++it )
   {
      size_t i = it - vec.begin(); 
      // use i
   }
   

3. Используйте std::distance

   std::vector vec;
   std::vector::iterator it;
   for ( it = vec.begin(); it != vec.end(); ++it )
   {
      size_t i = std::distance( vec.begin(), it );
      // use i
   }
   

Answer 1

Если вы планируете использовать исключительно вектор, возможно, вам захочется вернуться к индексированному циклу, поскольку он передает ваше намерение более четко, чем цикл-итератор.Однако, если развитие вашей программы в будущем может привести к смене контейнера, вам следует придерживаться итераторов и использовать std::distance, который гарантированно будет работать со всеми стандартными итераторами.

Answer 2

Использование std::distance является немного более общим, поскольку оно работает для всех итераторов, а не только для итераторов произвольного доступа.И он должен быть таким же быстрым, как It - vec.begin() в случае итераторов произвольного доступа.

Это vec.begin() — это, по сути, арифметика указателей.

Answer 3

std::distance(vec.begin(), it) даст вам индекс it указывает на, предполагая, что он указывает на vec.

Карл

Answer 4

Вернитесь к индексированному циклу.

В принципе в 90% случаев итераторы превосходят, это один из тех 10%.Используя итератор, вы делаете код более сложным и, следовательно, более трудным для понимания, тогда как вся причина использования итератора в первую очередь заключалась в упрощении вашего кода.

Answer 5

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

Answer 6

Я всегда склонялся к использованию итераторов по соображениям будущего развития.

В приведенном выше примере, если вы, возможно, решили заменить std::vector на std::set (возможно, вам нужна уникальная коллекция элементов), использование итераторов и distance() продолжит работать.

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

Answer 7

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

Векторные итераторы теоретически могут быть немного быстрее, чем индексы, поскольку они используют арифметику указателей для перебора списка.Однако обычно я считаю, что читаемость стоит минимальной разницы во времени выполнения.

Я использую итераторы для других типов контейнеров, а иногда и тогда, когда вам не нужна переменная цикла.Но если вам нужна переменная цикла, вы ничего не делаете, кроме как усложняете ввод цикла.(Я не могу дождаться авто C++ 0x..)