c++ - Einfügen oder push_back zum Ende eines std::-Vektors?




performance c++11 (3)

Gibt es Leistungsunterschiede zwischen den beiden folgenden Methoden, um neue Elemente an das Ende eines std::vector einzufügen:

Methode 1

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

Methode 2

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

Ich persönlich mag Methode 2, weil sie schön und übersichtlich ist und alle neuen Elemente aus einem Array auf einmal einfügt. Aber

  • Gibt es Leistungsunterschiede?
  • Immerhin machen sie das Gleiche. Nicht wahr

Aktualisieren

Der Grund, warum ich den Vektor nicht mit allen Elementen initialisiere, ist, dass ich in meinem Programm die restlichen Elemente basierend auf einer Bedingung hinzufüge.


Immerhin machen sie das Gleiche. Nicht wahr

Nein, sie sind unterschiedlich. Die erste Methode, die std::vector::push_back wird im Vergleich zu std::vector::insert mehreren Neuzuordnungen unterzogen.

Die insert reserviert intern Speicher gemäß der aktuellen std::vector::capacity bevor der Bereich kopiert wird. Weitere Informationen finden Sie in der folgenden Diskussion:

Ist std :: vector :: per definitionem reserviert?

Aber gibt es Leistungsunterschiede?

Aus dem oben erläuterten Grund würde die zweite Methode eine leichte Leistungsverbesserung zeigen. Siehe zum Beispiel die kurze Benck-Markierung unten unter http://quick-bench.com :

Siehe Online-Benchmark

Oder schreiben Sie ein Testprogramm, um die Leistung zu messen (wie in den Kommentaren erwähnt). Es folgt ein Beispiel für ein Testprogramm:

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

Release-Erstellung mit meinem System (MSVS2019: / Ox / std: c ++ 17 , AMD Ryzen 7 2700x (8-Kern, 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;
}

Was für das gegebene Szenario zeigt, ist std::vector::push_back ungefähr 2.7 mal schneller als std::vector::push_back .

Sehen Sie, was andere Compiler ( clang 8.0 und gcc 9.2 ) je nach Implementierung sagen möchten: https://godbolt.org/z/DQrq51


Der Hauptfaktor wird die Neuzuteilung sein. vector muss platz für neue elemente schaffen.

Betrachten Sie diese 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};

Um zu bestätigen, dass die Neuzuordnungen im Bild sind, erhalten wir nach dem Hinzufügen einer vec.reserve(5) in Pushback- und Insert-Versionen die folgenden Ergebnisse.


push_back fügt ein einzelnes Element ein, daher können im schlimmsten Fall mehrere Neuzuordnungen auftreten.

Betrachten Sie für das Beispiel den Fall, in dem die Anfangskapazität 2 ist und sich bei jeder Neuzuweisung um den Faktor 2 erhöht. Dann

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

Sie können unnötige Neuzuordnungen natürlich durch einen Anruf verhindern

vec.reserve(num_elements_to_push);

Wenn Sie jedoch aus einem Array einfügen, ist die Verwendung von insert die idomatischere Methode.





insert