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

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

результаты теста для итераций 500м, размер вектора 10, с ГКК 4.3.3 (- O3), linux 2.6.29.1 x86_64:
at(): 9158ms
operator[]: 4269ms
iterator: 3914ms

YMMV, но если использование индекса делает код более читаемым/понятным, вы должны это сделать.

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

индексация предназначена для прямого доступа. Скобки и at способ сделать это. at будет, в отличие от [], Проверьте за пределами индексации, так что это будет медленнее.

кредо: Не просите то, что вам не нужно. Тогда компилятор не будет взимать плату за то, что вы не делаете использовать.

поскольку вы смотрите на эффективность, вы должны понимать, что следующие варианты потенциально более эффективны:

//1. Using vector<string>::iterator:

vector<string> vs = GetVector();
for(vector<string>::iterator it = vs.begin(), end = vs.end(); it != end; ++it)
{
   //...
}

//2. Using size_t index:

vector<string> vs = GetVector();
for(size_t i = 0, size = vs.size(); i != size; ++i)
{
   //...
}

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

Как все остальные здесь говорят, делать тесты.

сказав это, я бы сказал, что итератор быстрее, так как at() также проверяет диапазон, т. е. он выбрасывает исключение out_of_range, если индекс выходит за пределы. Эта проверка сама по себе propbably несет некоторые накладные расходы.

Я бы предположил, что первый вариант быстрее.

но это зависит от реализации. Чтобы убедиться, что вы должны профилировать свой собственный код.

зачем профилировать свой собственный код?

потому что все эти факторы будут варьировать результаты:

• ОС
• какой компилятор
• какая реализация STL использовалась
• были ли включены оптимизации?
• ... (другие факторы)

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

вы можете использовать этот тестовый код и сравните результаты! Дио это!

#include <vector> 
#include <iostream> 
#include <ctime> 
using namespace std;; 


struct AAA{
    int n;
    string str;
};
int main() { 
    const int BIG = 5000000; 
    vector <AAA> v; 
    for ( int i = 0; i < BIG; i++ ) { 
        AAA a = {i, "aaa"};
        v.push_back( a ); 
    } 

    clock_t now;
    cout << "start" << endl; 
    int n = 0; 
    now = clock(); 
    for(vector<AAA>::iterator it = v.begin(); it != v.end(); ++it) { 
        n += it->n; 
    } 
   cout << clock() - now << endl; 

    n = 0;
    now = clock(); 
    for(size_t i = 0; i < v.size(); ++i) { 
        n += v[i].n; 
    } 
    cout << clock() - now << endl; 

    getchar();
    return n != 0; 
} 

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

например:

векторная итерация и вытягивание двух функций за проход.

vector<MyTpe> avector(128);
vector<MyTpe>::iterator B=avector.begin();
vector<MyTpe>::iterator E=avector.end()-1;
for(int i=0; i<1024; ++i){
 B=avector.begin();
   while(B!=E)
   {
       float t=B->GetVal(Val1,12,Val2); float h=B->GetVal(Val1,12,Val2);
    ++B;
  }}

вектор взял 90 кликов (0.090000 секунд)

но если вы сделали это с указатели...

for(int i=0; i<1024; ++i){
MyTpe *P=&(avector[0]);
   for(int i=0; i<avector.size(); ++i)
   {
   float t=P->GetVal(Val1,12,Val2); float h=P->GetVal(Val1,12,Val2);
   }}

вектор взял 18 кликов (0.018000 секунд)

что примерно эквивалентно...

MyTpe Array[128];
for(int i=0; i<1024; ++i)
{
   for(int p=0; p<128; ++p){
    float t=Array[p].GetVal(Val1, 12, Val2); float h=Array[p].GetVal(Val2,12,Val2);
    }}

массив занял 15 кликов (0,015000 секунд).

если вы исключите вызов avector.размер (), время становится одинаковым.

наконец, звоню с [ ]

for(int i=0; i<1024; ++i){
   for(int i=0; i<avector.size(); ++i){
   float t=avector[i].GetVal(Val1,12,Val2); float h=avector[i].GetVal(Val1,12,Val2);
   }}

вектор взял 33 кликов (0.033000 секунд)

синхронизированный с часами()

это зависит.

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

at всегда медленнее, чем итераторы или operator[].
Но для operator[] против итераторов, это зависит от:

1. как именно вы используете operator[].

2. имеет ли ваш конкретный процессор индекс регистров (ESI/EDI on x86).

3. сколько другое код также использует тот же индекс, передаваемый operator[].
   (например, вы индексируете через несколько массивов в lockstep?)

вот почему:

1. если вы делаете что-то вроде

   std::vector<unsigned char> a, b;
   for (size_t i = 0; i < n; ++i)
   {
       a[13 * i] = b[37 * i];
   }
   

   тогда этот код, вероятно, будет намного медленнее, чем версия итератора, так как он выполняет умножение операция на каждой итерация цикла!

   аналогично, если вы делаете что-то вроде:

   struct T { unsigned char a[37]; };
   std::vector<T> a;
   for (size_t i = 0; i < n; ++i)
   {
       a[i] = foo(i);
   }
   

   тогда это, вероятно,и быть медленнее, чем версия итератора, потому что sizeof(T) и не сила 2, и поэтому вы (снова) умножаете на 37 каждый раз, когда вы петли!

2. если ваш процессор имеет регистры индексов, то ваш код может работать также или даже лучше с индексами, а не с итераторами, если использование индексного регистра освобождает другой регистр для использования в цикле. Это не что-то вы можете сказать, просто глядя; вам придется профилировать код и/или разобрать его.

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

в общем, надо предпочитаю итераторы к индексам и индексам к указателям, пока и если вы не столкнетесь с узким местом, которое показывает профилирование, будет полезно переключиться, потому что итераторы общего назначения и уже, вероятно, будет самый быстрый подхода; они не требуют данные должны быть случайным образом адресуемыми,что позволяет при необходимости менять контейнеры. Индексы являются следующим предпочтительным инструментом, поскольку они по-прежнему не требуют прямого доступа к данным-они недействительны реже, и вы можете, например, заменить a deque на vector без каких-либо проблем. Указатели должны быть последним средством, и они окажутся полезными только в том случае, если итераторы уже не вырождаются в потайники в режиме выпуска.

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

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

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

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

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

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

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

ниже приводится урезанная версия кода, используемого во-первых:

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

    // Various other operations
}

частота кадров с помощью этого метод был около 7 кадров в секунду (FPS).

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

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

    // Various other operations
}

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

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

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

вот код, который я написал, скомпилированный в 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() который медленнее, чем прямые индексы.

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

EDIT: этот код был написан еще тогда, когда у меня было меньше опыта работы с C/C++. Дальнейшим тестовым случаем должно быть использование префиксных операторов инкремента вместо постфиксных. Это должно улучшить время работы.

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

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

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

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