1

Слышал, что если делать в вектор push_back, то если у него не хватает внутреннего буфера, то он увеличивается в 1.5 раза. Правда ли?

Будет ли тоже самое происходить когда я буду делать последовательно resize:

for(int i=0; i<N; i++) {
    b.resize(i+1);
    b[i] = i;
}

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

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

int main() {
    const int N = 10000000;

    clock_t tStart;

    vector<int> a;

    tStart = clock();
    for(int i=0; i<N; i++) a.push_back(i);
    printf("Time taken: %.4f sec\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);

    vector<int> b;

    tStart = clock();
    for(int i=0; i<N; i++) {
        b.resize(i+1);
        b[i] = i;
    }
    printf("Time taken: %.4f sec\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);

    return 0;
}

Пример вывода на ideone:

Time taken: 0.0649 sec
Time taken: 0.0692 sec
2
  • 1
    Не совсем правда — это нигде не прописано, но разные реализации используют различные коэффициенты увеличения размера, при нехватке места в текущем выделенном пространстве. Все известные мне реализации увеличивают размер на число большее, чем требуется для одной операции помещения в контейнер.
    – ixSci
    18 мая 2017 в 18:21
  • При resize реализация скорее всего вмешиваться не будет и будет выделять ровно столько, сколько попросили. resize и reserve в цикле является пессимизацией и ошибкой.
    – ixSci
    18 мая 2017 в 18:24

1 ответ 1

-1

Лучше для добавления элементов брать не vector, а list или unordered_set. Вектор хорошо удаляет и добавляет элементы только в конец. В остальных случаях на сколько-то больших данных вектор начинает двигать элементы и это может плохо сказаться на производительности. Можно конечно не передвигать при удалении, но тогда нарушается порядок элементов.

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

Вобщем есть дофига вариаций, когда что быстрее.

Можно запустить вот это и узнать что происходит с вектором.

for(int i=0; i<N; i++) {
b.resize(i+1);
cout<<i+1<<" "<<b.capacity()<<endl;
}

В одной онлайн IDE

1 1

2 2

3 4

4 4

5 8

...

16 16 17 32

b.resize(i+1);
b[i] = i;

Два раза присваивается значение сначала 0 потом цифра наверное поэтому дольше.

9
  • 1
    вот честно 1 фраза убила. С чего это вдруг list быстрее оказывается?
    – pavel
    18 мая 2017 в 17:39
  • 3
    Есть золотое правило: всегда бери вектор, пока не доказана необходимость брать другой контейнер.
    – ixSci
    18 мая 2017 в 18:22
  • 1
    @ixSci откуда такое правило?) Мне казалось золотое правило - сначала думать какие операции будут, а потом контейнер выбирать.
    – pavel
    18 мая 2017 в 19:15
  • @pavel, вектор, как правило, оказывается быстрее других контейнеров, даже в тех случаях, когда кажется, что другой контейнер подходит лучше. За последние три года конференций CppCon этот вопрос там поднимался неоднократно.
    – ixSci
    19 мая 2017 в 5:01
  • 1
    По моему, надо все таки сначала думать, а потом уже выбирать контейнер. В пользу списка можно отнести значительно меньшее число копирований объектов контейнера при его расширении (move-семантика от этого не спасет). Лучше всего предполагать использование списка, т.е. ориентироваться на работу с итераторами, а уже сам контейнер после этого поменять будет несложно. Профилировщик покажет, какой контейнер эффективнее. Только надо учитывать, что он это покажет на конкретных тестах. Вполне можно подобрать примеры, когда разное тестовое воздействие покажет плюсы как для вектора так и для списка.
    – mega
    1 янв 2018 в 17:33

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

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