Вставить или push_back в конец std::vector?

Ответ 1

  В конце концов, они делают то же самое. Не так ли?

Нет, они разные. Первый метод с использованием std::vector::push_back претерпит несколько перераспределений по сравнению с std::vector::insert.

insert будет внутренне распределять память в соответствии с текущим std::vector::capacity перед копированием диапазона. См. следующее обсуждение для получения дополнительной информации:

Защищает ли std::vector :: insert по определению?

Но есть ли разница в производительности?

По причине, описанной выше, второй метод продемонстрировал бы небольшое улучшение производительности. Например, см. быстрый тест ниже, используя http://quick-bench.com:

Посмотреть онлайн-тест

Или напишите тестовую программу для измерения производительности (как упомянул в комментариях программист @Some). Ниже приведен пример тестовой программы:

#include <iostream>
#include <chrono>
#include <algorithm>
#include <vector>
using namespace std::chrono;

class Timer final
{
private:
    time_point<high_resolution_clock> _startTime;

public:
    Timer() noexcept
        : _startTime{ high_resolution_clock::now() }
    {}
    ~Timer() noexcept {  Stop(); }
    void Stop() noexcept
    {
        const auto endTime = high_resolution_clock::now();
        const auto start = time_point_cast<microseconds>(_startTime).time_since_epoch();
        const auto end = time_point_cast<microseconds>(endTime).time_since_epoch();
        const auto durationTaken = end - start;
        const auto duration_ms = durationTaken * 0.001;
        std::cout << durationTaken.count() << "us (" << duration_ms.count() << "ms)\n";
    }
};
// Method 1: push_back
void push_back()
{
    std::cout << "push_backing:    ";
    Timer time{};
    for (auto i{ 0ULL }; i < 1000'000; ++i)
    {
        std::vector<int> vec = { 1 };
        vec.push_back(2);
        vec.push_back(3);
        vec.push_back(4);
        vec.push_back(5);
    }
}
// Method 2: insert_range
void insert_range()
{
    std::cout << "range-inserting: ";
    Timer time{};
    for (auto i{ 0ULL }; i < 1000'000; ++i)
    {
        std::vector<int> vec = { 1 };
        int arr[] = { 2,3,4,5 };
        vec.insert(std::end(vec), std::cbegin(arr), std::cend(arr));
    }
}

int main()
{
    push_back();
    insert_range();
    return 0;
}

сборка релизов с моей системой (MSVS2019: /Ox/std: c ++ 17, AMD Ryzen 7 2700x_{(8-ядерный, 3,70 ГГц)}, x64 Windows 10)

// Build - 1
push_backing:    285199us (285.199ms)
range-inserting: 103388us (103.388ms)

// Build - 2
push_backing:    280378us (280.378ms)
range-inserting: 104032us (104.032ms)

// Build - 3
push_backing:    281818us (281.818ms)
range-inserting: 102803us (102.803ms)

Что показывает для данного сценария, std::vector::insert ing примерно в 2.7 раз быстрее, чем std::vector::push_back.

Посмотрите, что другие компиляторы (clang 8.0 и gcc 9.2) хотят сказать в соответствии с их реализациями: https://godbolt.org/z/DQrq51

Ответ 2

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

Ваш второй метод, вызывающий функцию-член insert() один раз с диапазоном итераторов:

vec.insert(std::end(vec), std::begin(arr), std::end(arr));

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

Ваш первый метод, отдельные вызовы функции-члена push_back(), может инициировать несколько перераспределений в зависимости от количества вставляемых элементов и памяти, изначально зарезервированной для вектора.

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

Ответ 3

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

Для примера рассмотрим случай, когда начальная емкость равна 2 и увеличивается в 2 раза при каждом перераспределении. Тогда

std::vector<int> vec = { 1 }; 
vec.push_back(2);             
vec.push_back(3);                 // need to reallocate, capacity is 4
vec.push_back(4);                   
vec.push_back(5);                  // need to reallocate, capacity is 8

Конечно, вы можете предотвратить ненужные перераспределения, позвонив

vec.reserve(num_elements_to_push);

Хотя, если вы все равно вставляете из массива, более нелепым является использование insert.

Ответ 4

Основным способствующим фактором будет перераспределение. vector должен освободить место для новых элементов.

Рассмотрим эти 3 синапса.

 //pushback
 std::vector<int> vec = {1};
 vec.push_back(2);
 vec.push_back(3);
 vec.push_back(4);
 vec.push_back(5);

 //insert
 std::vector<int> vec = {1};
 int arr[] = {2,3,4,5};
 vec.insert(std::end(vec), std::begin(arr), std::end(arr));


 //cosntruct
 std::vector<int> vec = {1,2,3,4,5};

Чтобы подтвердить перераспределения, приходящие в картину, после добавления vec.reserve(5) в версии с возвратом и вставкой мы получаем следующие результаты.