c++ - 插入或push_back到std:: vector的末尾?




performance c++11 (3)

下面兩種在 std::vector 的末尾插入新元素的方法在性能上是否有任何區別:

方法1

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

方法二

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

就我個人而言,我喜歡 方法2, 因為它很好且簡潔,可以一次性插入數組中的所有新元素。 但

  • 在性能上有什麼區別嗎?
  • 畢竟,他們做同樣的事情。 不是嗎

更新

首先,我不使用所有元素初始化向量的原因是,在我的程序中,我根據條件添加了其餘元素。


畢竟,他們做同樣的事情。 不是嗎

不,他們不同。 與 std::vector::insert 相比,使用 std::vector::push_back 的第一種方法將進行一些重新分配。

在復制範圍之前, insert 將根據當前的 std::vector::capacity 在內部分配內存。 有關更多信息,請參見以下討論:

std :: vector :: insert是否按定義保留?

但是性能上有什麼區別嗎?

由於上述原因,第二種方法將表現出輕微的性能改進。 例如,使用 http://quick-bench.com 參見下面的快速benck標記:

查看在線基準

或編寫一個測試程序來衡量性能(如評論中提到的 @Some程序員伙計 )。 以下是一個示例測試程序:

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

使用我的系統發布版本(MSVS2019: / Ox / std:c ++ 17 AMD Ryzen 7 2700x (8核,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;
}

對於給定的場景,顯示 std::vector::push_back 速度大約是 std::vector::push_back 2.7 倍。

根據其實現,查看其他編譯器( clang 8.0和gcc 9.2 )要說的內容: https://godbolt.org/z/DQrq51 : https://godbolt.org/z/DQrq51


主要的影響因素將是重新分配。 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) 後,我們得到以下結果。


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





insert