Скорость доступа к std::vector с помощью итератора с помощью оператора []/index?

Ответ 1

Разница в производительности, вероятно, небрежна или ничто (компилятор может оптимизировать их, чтобы быть идентичным); вы должны беспокоиться о других вещах, например, правильно ли ваша программа (медленная, но правильная программа лучше быстрой и неправильной программы). Существуют и другие преимущества использования итераторов, например, возможность изменить базовый контейнер на единицу без operator[] без изменения ваших циклов. Подробнее см. этот вопрос.

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

Короче говоря, оптимизация не должна беспокоить вас до тех пор, пока не произойдут две вещи: 1) вы заметили, что она работает слишком медленно и 2) вы профилировали узкие места. Для 1), если он работает в десять раз медленнее, чем он мог, но только когда-либо запускается один раз и занимает 0,1 мс, кого это волнует? Для 2) убедитесь, что это определенно узкое место, иначе его оптимизация почти не окажет заметного влияния на производительность!

Ответ 2

Простой петлевой тест был выполнен. Я использовал VS 2010 SP1 (версия выпуска).

• Используйте итераторы (* it = * it + 1;)
• Использовать индексы (vs [i] = vs [i] + 1;)

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

Ответ 3

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

Если это не имеет значения, вы выполняете преждевременную оптимизацию и должны делать STOP.

Ответ 4

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

Ответ 5

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

Ответ 6

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

По крайней мере, вы можете уменьшить количество используемых переменных:)

for( i = 0; i < size ; i++){
    // some operations on v items
    v[i];
    v[size-i+1];
}

О const_iterator: Pls ссылается на мой Q: A re const_iterators быстрее?

Ответ 7

Вы не только преждевременно оптимизируете, но и оптимизируете микро-оптимизацию. Это зло почти так же плохо, как и первое (разница в том, что очень, очень, очень редко на самом деле необходимо микро-оптимизировать). Поместите их вместе, и у вас есть рецепт катастрофы.

Если вы запускаете профилировщик и обнаруживаете, что эта область кода является узким местом, вам нужно будет оптимизировать. Вы не оптимизируете, пытаясь сократить ваш цикл от 23 тактовых циклов до 22. Оптимизируйте, найдя способы уменьшить O() вашего алгоритма. Но пока вы не запускаете профилировщик, вы должны уделять больше внимания дизайну, чем любая другая проблема.

Ответ 8

Я бы пошел на итераторы, но то, что я бы оптимизировал, вызывает 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
}

И я не думаю, что это преждевременная микрооптимизация, она просто пишет лучший код. Гораздо менее зло, чем призывать каждую попытку написать эффективный код преждевременной микрооптимизации и подменять мышление профилированием.

Ответ 9

Я был смущен примерно чем-то подобным и написал программу для проверки производительности: https://github.com/rajatkhanduja/Benchmarks/blob/master/C%2B%2B/vectorVsArray.cpp

Здесь соответствующие наблюдения для чтения/записи в вектор <int> размером 1 м с использованием g++ (без каких-либо флагов оптимизации), на Linux-i686 (64-разрядная машина) с 7,7 ГБ оперативной памяти: -

Время, затраченное на запись в вектор с использованием индексов.: 11.3909 мс

Время, затраченное на чтение из вектора с использованием индексов, последовательно.: 4.09106 мс

Время, затраченное на чтение из вектора с использованием индексов, случайным образом.: 39 мс

Время, затраченное на запись в вектор с использованием итераторов (последовательно).: 24.9949 мс

Время считывания с вектора с использованием итераторов (последовательно).: 18.8049 мс

Ответ 10

При оптимизации (-O2) тайминги должны улучшаться (должны быть почти одинаковыми).

Ответ 11

Вчера у меня был тест, используйте [] vs iterator, код создает вектор с некоторыми элементами и удаляет некоторые элементы из вектора. Это код использует оператор [] для доступа к элементам

  TimeSpent([](){
    std::vector<int> vt = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    for (int i = int(vt.size()) - 1; i >= 0; i--)
    {
      if (vt[i] % 2 == 0)
      {
        //cout << "removing " << vt[i] << endl;
        vt.erase(vt.begin() + i);
      }
    }
  });

Следующий код относится к элементам вектора доступа с помощью итератора

  TimeSpent([](){
    std::vector<int> vt = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    for (std::vector<int>::iterator num = vt.begin(); num != vt.end();)
    {
      if (*num % 2 == 0)
      {
        num = vt.erase(num);
      }
      else
      {
        ++num;
      }
    }
  });

Протестировано, вызвав их этой функцией отдельно

void TimeSpent(std::function<void()> func)
{
  const int ONE_MIL = 10000;
  long times = ONE_MIL;
  std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
  while (times > 0)
  {
    func();
    --times;
  }
  std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
  cout << "time elapsed : " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << endl;
}

Протестированная среда - visual studio 2013 pro. версия 4.5.51650
Результаты:
оператор []: 192
итератор: 212
Резюме: при доступе к векторному контейнеру оператор [] работает быстрее, чем итератор.