c++ - Insertar o push_back al final de un std:: vector?

performance c++11

Question

¿Hay alguna diferencia en el rendimiento entre los dos métodos a continuación para insertar nuevos elementos al final de un std::vector :

Método 1

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

Método 2

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

Personalmente, me gusta el método 2 porque es agradable y conciso e inserta todos los elementos nuevos de una matriz de una sola vez. Pero

• ¿Hay alguna diferencia en el rendimiento?
• Después de todo, hacen lo mismo. Ellos no?

Actualizar

La razón por la que no estoy inicializando el vector con todos los elementos, para empezar, es que en mi programa estoy agregando los elementos restantes en función de una condición.

Answer 1

Después de todo, hacen lo mismo. Ellos no?

No. Son diferentes El primer método que usa std::vector::push_back sufrirá varias reasignaciones en comparación con std::vector::insert .

La insert asignará memoria internamente, de acuerdo con la std::vector::capacity actual de std::vector::capacity antes de copiar el rango. Vea la siguiente discusión para más información:

¿Std :: vector :: insert reserva por definición?

¿Pero hay alguna diferencia en el rendimiento?

Debido a la razón explicada anteriormente, el segundo método mostraría una ligera mejora en el rendimiento. Por ejemplo, vea la marca de referencia rápida a continuación, usando http://quick-bench.com :

Ver referencia en línea

O escriba un programa de prueba para medir el rendimiento (como lo mencionó @Some programmer dude en los comentarios). El siguiente es un programa de prueba de muestra:

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

lanzamiento de la construcción con mi sistema (MSVS2019: / Ox / std: c ++ 17 , AMD Ryzen 7 2700x _{(8 núcleos, 3.70 Ghz)} , x64 Windows 10 )

#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;
}

Lo que se muestra para el escenario dado, std::vector::insert inserting es aproximadamente 2.7 veces más rápido que std::vector::push_back .

Vea lo que otros compiladores ( clang 8.0 y gcc 9.2 ) quieren decir, de acuerdo con sus implementaciones: https://godbolt.org/z/DQrq51

Answer 2

El principal factor contribuyente serán las reasignaciones. vector tiene que hacer espacio para nuevos elementos.

Considere estos 3 sinppets.

 //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};

Para confirmar las reasignaciones que vec.reserve(5) en la imagen, después de agregar un vec.reserve(5) en versiones pushback e insert, obtenemos los siguientes resultados.

Answer 3

Puede haber una diferencia entre los dos enfoques si el vector necesita reasignarse.

Su segundo método, llamando a la función miembro insert() una vez con un rango de iterador:

// 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)

sería capaz de proporcionar la optimización de asignar toda la memoria necesaria para la inserción de los elementos de un solo golpe ya que insert() está obteniendo iteradores de acceso aleatorio , es decir, se necesita tiempo constante para conocer el tamaño del rango, por lo que toda la memoria la asignación se puede hacer antes de copiar los elementos, y no se realizarán reasignaciones durante la llamada.

Su primer método, llamadas individuales a la función miembro push_back() , puede desencadenar varias reasignaciones, dependiendo del número de elementos a insertar y la memoria inicialmente reservada para el vector.

Tenga en cuenta que la optimización explicada anteriormente puede no estar disponible para iteradores directos o bidireccionales, ya que tomaría un tiempo lineal en el tamaño del rango para saber la cantidad de elementos que se insertarán. Sin embargo, el tiempo necesario para múltiples asignaciones de memoria probablemente eclipsa el tiempo necesario para calcular la longitud del rango para estos casos, por lo que probablemente todavía implementen esta optimización. Para los iteradores de entrada , esta optimización ni siquiera es posible ya que son iteradores de paso único.

Answer 4

push_back inserta un solo elemento, por lo tanto, en el peor de los casos, puede encontrar múltiples reasignaciones.

Por el bien del ejemplo, considere el caso donde la capacidad inicial es 2 y aumenta en un factor de 2 en cada reasignación. Entonces

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

Por supuesto, puede evitar reasignaciones innecesarias llamando a

vec.reserve(num_elements_to_push);

Sin embargo, si de alguna manera inserta desde una matriz, la forma más idónea es usar insert .