C++ vector вставка и разность push_back

Question

Я хочу знать, в чем разница (ы) между vector"s push_back а также insert функции.

Есть структурные различия?

Есть ли действительно большая разница в производительности?

Answer 1

Самое большое отличие заключается в их функциональности. push_back всегда ставит новый элемент в конце vector а также insert позволяет выбрать позицию нового элемента. Это влияет на производительность. vector элементы перемещаются в память только тогда, когда необходимо увеличить их длину, потому что для нее было выделено слишком мало памяти. С другой стороны insert заставляет перемещать все элементы после выбранной позиции нового элемента. Вы просто должны найти место для этого. Вот почему insert часто может быть менее эффективным, чем push_back,

Answer 2

The functions have different purposes. vector::insert allows you to insert an object at a specified position in the vector, в то время как vector::push_back will just stick the object on the end. Смотрите следующий пример:

using namespace std;
vector<int> v = {1, 3, 4};
v.insert(next(begin(v)), 2);
v.push_back(5);
// v now contains {1, 2, 3, 4, 5}

Ты можешь использовать insert to perform the same job as push_back с v.insert(v.end(), value),

Answer 3

Помимо того, что push_back(x) делает так же, как insert(x, end()) (возможно, с немного лучшей производительностью), есть несколько важных вещей, которые нужно знать об этих функциях:

1. push_back существует только на BackInsertionSequence контейнеры - так, например, он не существует на set, Не мог, потому что push_back() дарует вам, что он всегда будет добавлять в конце.
2. Некоторые контейнеры также могут удовлетворить FrontInsertionSequence и у них есть push_front, Это удовлетворено dequeно не vector,
3. insert(x, ITERATOR) из InsertionSequenceчто характерно для set а также vector, Таким образом, вы можете использовать либо set или же vector в качестве цели для нескольких вставок. Тем не мение, set имеет дополнительно insert(x), который делает практически то же самое (эта первая вставка в set означает только для ускорения поиска подходящего места, начиная с другого итератора - функция, не используемая в этом случае).

Обратите внимание на последний случай, что если вы собираетесь добавить элементы в цикл, то container.push_back(x) а также container.insert(x, container.end()) будет эффективно делать то же самое. Однако это не будет правдой, если вы получите это container.end() сначала, а затем использовать его во всем цикле.

Например, вы можете рискнуть следующим кодом:

copy(a.begin(), a.end(), inserter(v, v.end());

Это будет эффективно копировать весь a в v вектор, в обратном порядке, и только если вам повезло, что вы не получили вектор, перераспределенный для расширения (вы можете предотвратить это, вызвав reserve() первый); если вам не так повезет, вы получите так называемый UndefinedBehavior(tm). Теоретически это не допускается, поскольку итераторы вектора считаются недействительными при каждом добавлении нового элемента.

Если вы делаете это так:

copy(a.begin(), a.end(), back_inserter(v);

это будет копировать a в конце v в первоначальном порядке, и это не несет риска аннулирования итератора.

Answer 4

Поскольку фактических данных о производительности нет, я неохотно написал код для их создания. Имейте в виду, что я написал этот код, потому что задавался вопросом: «Должен ли я push_back несколько отдельных элементов или использовать вставку?».

      #include <iostream>
#include <vector>
#include <cassert>
#include <chrono>

using namespace std;

vector<float> pushBackTest()
{
    vector<float> v;
    for(int i =0;i<10000000;i++)
    {
        // Using a for-loop took 200ms more (in the output)
        v.push_back(0);
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);
        v.push_back(6);
        v.push_back(7);
        v.push_back(8);
        v.push_back(9);
    }
    return v;
}

vector<float> insertTest()
{
    vector<float> v;
    for(int i =0;i<10000000;i++)
    {
        v.insert(v.end(), {0,1,2,3,4,5,6,7,8,9});
    }
    return v;
}

int main()
{
    std::chrono::steady_clock::time_point start = chrono::steady_clock::now();
    vector<float> a = pushBackTest();
    cout<<"pushBackTest: "<<chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count()<<"ms"<<endl;
    start = std::chrono::steady_clock::now();
    vector<float> b = insertTest();
    cout<<"insertTest: "<<chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count()<<"ms"<<endl;
    assert(a==b);
    return 0;
}

Выход:

      pushBackTest: 5544ms
insertTest: 3402ms

Поскольку любопытство убило мое время, я провел аналогичный тест, но добавил одно число вместо нескольких. Итак, две новые функции:

      vector<float> pushBackTest()
{
    vector<float> v;
    for(int i =0;i<10000000;i++)
    {

        v.push_back(1);

    }
    return v;
}

vector<float> insertTest()
{
    vector<float> v;
    for(int i =0;i<10000000;i++)
    {
        v.insert(v.end(), 1);
    }
    return v;
}

Выход:

      pushBackTest: 452ms
insertTest: 615ms

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

Answer 5

Я не видел этого ни в одном из комментариев выше, но важно знать:

Если мы хотим добавить новый элемент в заданный вектор, а новый размер вектора (включая новый элемент) превышает текущую емкость вектора, это вызовет автоматическое перераспределение выделенного пространства для хранения. И поскольку выделение памяти — это действие, которое мы хотим свести к минимуму, оно увеличит емкость как в push_back, так и в вставке одинаковым образом (для вектора с n элементы добавят около n/2).

Так что с точки зрения эффективности памяти можно с уверенностью сказать, используйте то, что вам больше нравится. Например:

      std::vector<int> test_Insert = { 1,2,3,4,5,6,7 };
std::vector<int> test_Push_Back = { 1,2,3,4,5,6,7 };

std::cout << test_Insert.capacity() << std::endl;
std::cout << test_Push_Back.capacity() << std::endl;

test_Insert.push_back(8);
test_Push_Back.insert(test_Push_Back.end(), 8);

std::cout << test_Insert.capacity() << std::endl;
std::cout << test_Push_Back.capacity() << std::endl;

Этот код напечатает:

7

7

10

10