2

Знаю, что добавление элементов в std::vector работает медленее, чем в std::list, так как при добавлении нового элемента в vector, в нём пересоздаётся массив, и все элементы копируются. Я хотел понять насколько это критично, написал такой код:

#include <list>
//#include <vector>

int main()
{
    std::list<int> test;
    //std::vector<int> test;
    
    for(int i = 0; i < 100000000; ++i)
        test.push_back(1);

    return 0;
}

Скомпилировал с помощью g++(gcc version 11.2.0 (Ubuntu 11.2.0-19ubuntu1)), с ключем -O0, чтобы убрать оптимизацию. Замерял с помощью time.

Результат для std::list:

real    0m6,675s
user    0m5,963s
sys     0m0,712s

Результат для std::vector:

real    0m2,153s
user    0m1,941s
sys     0m0,212s

Почему так, где я допустил ошибку?

3
  • 2
    «в нём пересоздаётся массив» — не пересоздаётся, если в массиве есть свободное место под новый элемент. А когда места нет и всё-таки пересоздаётся, то место выделяется не под один элемент, а с запасом — если интернет не врёт, GCC выполняет увеличение в 2 раза. Таким образом, вероятно, в вашем коде всего около 27 пересозданий массива — недостаточно для того, чтобы стали видны тормоза
    – andreymal
    11 окт 2022 в 22:42
  • @andreymal, спасибо большое, я думаю, что это можно считать ответом на мой вопрос, но поскольку он был дан в комментариях, я не могу выбрать его решением(насколько понимаю), не могли бы вы оставить его именно ответом?
    – DmPA
    11 окт 2022 в 22:56
  • См. ru.stackoverflow.com/q/698129/195342
    – Harry
    12 окт 2022 в 5:00

1 ответ 1

5

В качестве эпиграфа :) — работа с памятью — это достаточно медленная операция.

А теперь посмотрите сами, что происходит при работе со списком: надо выделить память для отдельного нового элемента, добавить указатели на предыдущий элемент списка и в предыдущем — на текущий, причем все это, вполне вероятно, не в кэше...

Вектор... Перераспределение делается только изредка (порядка O(log N) раз), причем память выделяется блоками, так что элементы лежат рядом и потому, вероятно, вся работа выполняется в кэше...

Да еще и не надо править никакие указатели, просто — положить элемент в нужное место и все.

А если вы еще допишете

vector<int> test;
test.reserve(100000000);

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

P.S. А вот если вы начнете вставлять элементы в список и вектор в начало... но не буду лишать вас удовольствия провести собственный эксперимент и посмотреть результаты :)

1
  • Спасибо большое за подробный ответ, теперь мне стало гораздо понятнее, думаю, его можно считать решением :)
    – DmPA
    12 окт 2022 в 8:52

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.