Что быстрее, итерация вектора STL с помощью vector :: iterator или at ()?

Question

С точки зрения производительности, что будет работать быстрее? Есть ли разница? Это зависит от платформы?

//1. Using vector<string>::iterator:
vector<string> vs = GetVector();

for(vector<string>::iterator it = vs.begin(); it != vs.end(); ++it)
{
   *it = "Am I faster?";
}

//2. Using size_t index:
for(size_t i = 0; i < vs.size(); ++i)
{
   //One option:
   vs.at(i) = "Am I faster?";
   //Another option:
   vs[i] = "Am I faster?";
}

Answer 1

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

Справочная информация: У меня есть 4 вектора, размеры которых варьируются от 6 до 12. Запись происходит только один раз в начале кода, и чтение происходит для каждого из элементов в векторах каждые 0,1 миллисекунды

Ниже приведена сокращенная версия кода, использованного первой:

for(vector<T>::iterator it = someVector.begin(); it < someVector.end(); it++)
{
    T a = *it;

    // Various other operations
}

Частота кадров с использованием этого метода составляла около 7 кадров в секунду (кадр / с).

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

for(size_t index = 0; index < someVector.size(); ++index)
{
    T a = someVector[index];

    // Various other operations
}

Answer 2

Если вы используете VisualStudio 2005 или 2008, чтобы получить максимальную производительность от вектора, вам нужно определить _SECURE_SCL = 0

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

Answer 3

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

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

Доступ к элементам с "at" должен занять немного больше времени, чем прямой доступ к нему с помощью [], потому что он проверяет, находитесь ли вы в границах вектора, и выдает исключение, если вы выходите за пределы (кажется [] обычно просто использует арифметику указателей - так должно быть быстрее)

Answer 4

Только немного по касательной к исходному вопросу, но самый быстрый цикл будет

for( size_t i=size() ; i-- ; ) { ... }

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

Так что при доступе оператора [] это может быть быстрее, чем во многих уже опубликованных примерах.

Answer 5

Вот код, который я написал, скомпилированный в Code :: Blocks v12.11, с использованием компилятора mingw по умолчанию. Это создает огромный вектор, а затем обращается к каждому элементу с помощью итераторов, at () и index. Каждый зацикливается один раз, вызывая последний элемент по функции, и один раз, сохраняя последний элемент во временной памяти.

Синхронизация выполняется с использованием GetTickCount.

#include <iostream>
#include <windows.h>
#include <vector>
using namespace std;

int main()
{
    cout << "~~ Vector access speed test ~~" << endl << endl;
    cout << "~ Initialization ~" << endl;
    long long t;
    int a;
    vector <int> test (0);
    for (int i = 0; i < 100000000; i++)
    {
        test.push_back(i);
    }
    cout << "~ Initialization complete ~" << endl << endl;


    cout << "     iterator test: ";
    t = GetTickCount();
    for (vector<int>::iterator it = test.begin(); it < test.end(); it++)
    {
        a = *it;
    }
    cout << GetTickCount() - t << endl;



    cout << "Optimised iterator: ";
    t=GetTickCount();
    vector<int>::iterator endofv = test.end();
    for (vector<int>::iterator it = test.begin(); it < endofv; it++)
    {
        a = *it;
    }
    cout << GetTickCount() - t << endl;



    cout << "                At: ";
    t=GetTickCount();
    for (int i = 0; i < test.size(); i++)
    {
        a = test.at(i);
    }
    cout << GetTickCount() - t << endl;



    cout << "      Optimised at: ";
    t = GetTickCount();
    int endof = test.size();
    for (int i = 0; i < endof; i++)
    {
        a = test.at(i);
    }
    cout << GetTickCount() - t << endl;



    cout << "             Index: ";
    t=GetTickCount();
    for (int i = 0; i < test.size(); i++)
    {
        a = test[i];
    }
    cout << GetTickCount() - t << endl;



    cout << "   Optimised Index: ";
    t = GetTickCount();
    int endofvec = test.size();
    for (int i = 0; i < endofvec; i++)
    {
        a = test[i];
    }
    cout << GetTickCount() - t << endl;

    cin.ignore();
}

Исходя из этого, я лично понял, что "оптимизированные" версии работают быстрее, чем "неоптимизированные". Итераторы медленнее, чем vector.at (), который медленнее, чем прямые индексы.

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

РЕДАКТИРОВАТЬ : Этот код был переписан, когда у меня было меньше опыта работы с C / C ++. Еще одним тестовым примером должно быть использование префиксных операторов приращения вместо постфикса. Это должно улучшить время работы.

Answer 6

Разница должна быть незначительной. std :: vector гарантирует, что его элементы последовательно размещаются в памяти. Поэтому большинство реализаций stl реализуют итераторы в std :: vector как простой указатель. Учитывая это, единственная разница между двумя версиями должна заключаться в том, что первая увеличивает указатель, а во второй увеличивает индекс, который затем добавляется к указателю. Таким образом, мое предположение было бы вторым, возможно, это одна чрезвычайно быстрая (с точки зрения циклов) машинная инструкция больше.

Попробуйте проверить машинный код вашего компилятора.

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