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 that you have read and understand our privacy policy and code of conduct.

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