emplace_back/emplace 与 push_back/insert 效率的详细比较

锺玺

2023-12-01

在 STL 的容器中，除了给 vector 等序列容器定义了push_back方法之外，还定义了emplace_back方法；除了给 map 等关联容器定义了insert方法外，还定义了emplace方法。
那么，emplace_back/emplace 和 push_back/insert 的区别是什么？前者是否比后者更快呢？

区别分析

首先谈谈区别。
如果要将一个结构体类型的实例，放入容器中，一般有2个步骤：

构造这个实例
copy这个实例到容器中
注意，这个copy的动作有2种方法：
1> 通过普通的拷贝构造函数完成
2> 自C++11起可以通过移动构造函数来完成的

那么，push_back 和 insert 就是按照这2个步骤来做的；
但是 emplace_back/emplace 并不是，它是在指定位置构造出实例。这就是区别。
因此， emplace_back/emplace 的参数也是很有特点，它并不是容器元素类型，而是容器元素的构造函数所需要的类型。

譬如 vector 的emplace_back的声明是这样的：

template <class... Args>
  void emplace_back (Args&&... args);

而 map 的emplace的声明是这样的：

template <class... Args>
  pair<iterator,bool> emplace (Args&&... args);

那么，根据以上分析，emplace_back/emplace 应该只做了一次构造，而 push_back 无论是哪一种拷贝，都需要做一次构造和一次拷贝。
显然，emplace系列应该少了一次拷贝。
事实确实如此，但略有微小差异。请看下面的程序：

#include <vector>
#include <map>
#include <string>
#include <iostream>
using namespace std;


struct President  
{  
    std::string name;  
    std::string country;  
    int year;  

    President(std::string p_name, std::string p_country, int p_year)  
        : name(std::move(p_name)), country(std::move(p_country)), year(p_year)  
    {  
        cout << "    Construction\n";  
    }
    President(const President& other)
        : name(std::move(other.name)), country(std::move(other.country)), year(other.year)
    {
        cout << "    Copy Construction\n";
    }
    President(President&& other)  
        : name(std::move(other.name)), country(std::move(other.country)), year(other.year)  
    {  
        cout << "    Move Construction\n";  
    }
};  

int main()  
{
    cout << "emplace_back to vector:\n"; 
    vector<President> v1;
    v1.emplace_back("Nelson Mandela", "South Africa", 1994); 
    
    cout << "\npush_back to vector (way-1 - right value reference as parameter):\n";
    vector<President> v2;
    v2.push_back(President("Nelson Mandela", "South Africa", 1994));
    
    cout << "\npush_back to vector (way-2 - left value as parameter):\n";
    vector<President> v3;
    President p1("Nelson Mandela", "South Africa", 1994);
    v3.push_back(p1);
    
    cout << "\ninsert into map: \n";
    map<int, President> m1;
    m1.insert(make_pair<int, President>(10, President("Nelson Mandela", "South Africa", 1994)));
    
    cout << "\nemplace into map: \n";
    map<int, President> m2;
    m2.emplace(10, President("Nelson Mandela", "South Africa", 1994));
    
    return 0;
}

程序的输出是：

emplace_back to vector:
    Construction

push_back to vector (way-1 - right value reference as parameter):
    Construction
    Move Construction

push_back to vector (way-2 - left value as parameter):
    Construction
    Copy Construction

insert into map:
    Construction
    Move Construction
    Move Construction

emplace into map:
    Construction
    Move Construction

由上可见：

使用vector::emplace_back 需做一次构造函数
使用vector::push_back(value_type&& val) 需做一次构造函数和一次移动构造函数
使用vector::push_back(const value_type& val)需做一次构造函数和一次拷贝构造函数
使用map::insert(const value_type& val) 需做一次构造函数，2次移动构造函数
使用map::empalce(Args&&... args) 需做一次构造函数，1次移动构造函数

总之，emplace系列总是会少一次移动构造函数或一次拷贝构造函数；
（为什么 map 的 insert 和 emplace 比起 vector 的 push_back 和 emplace_back，都分别要多一次移动构造函数呢？
这应该是在做 pair 的时候多出来的一次。）

性能比较

既然emplace系列会少一次移动构造或拷贝构造，那么，是不是使用 emplace 系列就一定会快呢？
理论上是这样的，但实际测试中会有小坑。
先看最终版的测试程序：

#include <vector> 
#include <map>
#include <string>
#include <chrono>
#include <iostream>
#include <sstream>
using namespace std;

#define  CHECK_TIME_START  std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();

#define  CHECK_TIME_END    \
    std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now(); \
    std::chrono::duration<double> time_span = std::chrono::duration_cast<std::chrono::duration<double>>(end - start); \
    std::cout << "Time Cost: " << time_span.count() << " seconds." << endl;


struct President  
{
    static long NumberOfConstruction;
    static long NumberOfCopyConstruction;
    static long NumberOfMoveConstruction;
    
    std::string name;  
    std::string country;  
    int year;  

    President(std::string p_name, std::string p_country, int p_year)  
        : name(std::move(p_name)), country(std::move(p_country)), year(p_year)  
    {
        NumberOfConstruction ++;
    }
    President(const President& other)
        : name(std::move(other.name)), country(std::move(other.country)), year(other.year)
    {
        NumberOfCopyConstruction ++;
    }
    President(President&& other)  
        : name(std::move(other.name)), country(std::move(other.country)), year(other.year)  
    {
        NumberOfMoveConstruction ++;
    }
    
    static void reset_counters() {
        President::NumberOfConstruction = 0;
        President::NumberOfCopyConstruction = 0;
        President::NumberOfMoveConstruction = 0;
    }
    
    static void print_counters() {
        cout << "President::NumberOfConstruction = " << President::NumberOfConstruction << endl;
        cout << "President::NumberOfCopyConstruction = " << President::NumberOfCopyConstruction << endl;
        cout << "President::NumberOfMoveConstruction = " << President::NumberOfMoveConstruction << endl;
    }
};

long President::NumberOfConstruction = 0;
long President::NumberOfCopyConstruction = 0;
long President::NumberOfMoveConstruction = 0;

int main()  
{  
    const int VEC_SIZE = 1e7;
    const int MAP_SIZE = 3e6;

    {
        std::cout << "\npush_back to vector (way-1):\n";  
        std::vector<President> v2;  
        v2.reserve(VEC_SIZE);
        President::reset_counters();
        
        CHECK_TIME_START
        for (int i=0; i<VEC_SIZE; i++) {
            stringstream ss; 
            ss << i+1 << "Nelson Mandela"; 
            v2.push_back(President(string(ss.str()), "South Africa", 1994));
        }
        CHECK_TIME_END
        President::print_counters();
    }
    
    {
        std::cout << "\npush_back to vector (way-2):\n";  
        std::vector<President> v3;  
        v3.reserve(VEC_SIZE);
        President::reset_counters();
        
        CHECK_TIME_START
        for (int i=0; i<VEC_SIZE; i++) {
            stringstream ss; 
            ss << i+1 << "Nelson Mandela"; 
            President p1(string(ss.str()), "South Africa", 1994);
            v3.push_back(p1);
        }
        CHECK_TIME_END
        President::print_counters();
    }
    
    {
        std::cout << "\nemplace_back to vector:\n"; 
        std::vector<President> v1;
        v1.reserve(VEC_SIZE);
        President::reset_counters();
        
        CHECK_TIME_START
        for (int i=0; i<VEC_SIZE; i++) {
            stringstream ss; 
            ss << i+1 << "Nelson Mandela"; 
            v1.emplace_back(string(ss.str()), "South Africa", 1994); //没有类的创建  
        }
        CHECK_TIME_END
        President::print_counters();
    }
    
    {
        std::cout << "\ninsert into map:\n";  
        std::map<int, President> m1;
        President::reset_counters();
        
        CHECK_TIME_START
        for (int i=0; i<MAP_SIZE; i++) {
            stringstream ss; 
            ss << i+1 << "Nelson Mandela"; 
            m1.insert(make_pair<int, President>(i+1, President(string(ss.str()), "South Africa", 1994)));
        }
        CHECK_TIME_END
        President::print_counters();
    }
    
    {
        std::cout << "\nemplace into map:\n";  
        std::map<int, President> m2;
        President::reset_counters();
        
        CHECK_TIME_START
        for (int i=0; i<MAP_SIZE; i++) {
            stringstream ss; 
            ss << i+1 << "Nelson Mandela"; 
            m2.emplace(i+1, President(string(ss.str()), "South Africa", 1994));
        }
        CHECK_TIME_END
        President::print_counters();
    }
    
    return 0;
}

这个测试程序的运行结果如下：

push_back to vector (way-1):
Time Cost: 5.37667 seconds.
President::NumberOfConstruction = 10000000
President::NumberOfCopyConstruction = 0
President::NumberOfMoveConstruction = 10000000

push_back to vector (way-2):
Time Cost: 5.77395 seconds.
President::NumberOfConstruction = 10000000
President::NumberOfCopyConstruction = 10000000
President::NumberOfMoveConstruction = 0

emplace_back to vector:
Time Cost: 5.26875 seconds.
President::NumberOfConstruction = 10000000
President::NumberOfCopyConstruction = 0
President::NumberOfMoveConstruction = 0

insert into map:
Time Cost: 2.49609 seconds.
President::NumberOfConstruction = 3000000
President::NumberOfCopyConstruction = 0
President::NumberOfMoveConstruction = 6000000

emplace into map:
Time Cost: 2.29844 seconds.
President::NumberOfConstruction = 3000000
President::NumberOfCopyConstruction = 0
President::NumberOfMoveConstruction = 3000000

这个测试结果和我们的推测是一致的，即：

empalce系列都是最快的；
右值参数版 push_back 比左值版的 push_back 快
各个类型的构造函数的调用次数也和预期的一致： emplace系列确实要少一次移动构造或拷贝构造

但是为什么好像empalce系列没快多少呢？
原因应该是它所节省的移动构造太快了，大约就是改个指针。

那为什么好像emplace_back比左值参数的 push_back 也快得有限呢？
应该是因为我们举的这个例子里拷贝构造并不复杂，所以没有拉开差距。

前面所说的坑，在哪里呢？
注意，以上程序中，放入容器中的string是具有一定随机性的，因为将index i放进了string中，因此编译器无法做优化。
假设将上述程序中的 string name 换成一个固定的 string 再去测试，笔者做过实验，右值参数版的 push_back 比 emplace_back 还快。
不过，这又是开了-O3优化的结果；如果用默认的-O0，则即使用固定的 string name，也还是 emplace_back 快一点。

另一个小程序

前面用了宏来做时间的测试。我们也可以不用宏，而用传递函数对象的方法来做。看下面的小程序：

// g++ 1.cpp -O3

#include <iostream>
#include <chrono>
#include <string>
#include <map>
#include <functional>
#include <sstream>
using namespace std;

void check_time_cost(std::function<void()> func)
{
    std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
    
    func();
    
    std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
    std::chrono::duration<double> time_span = std::chrono::duration_cast<std::chrono::duration<double>>(end - start);
    std::cout << "Time Cost: " << time_span.count() << " seconds." << endl;
}


void test_1(int map_size)
{
    string s = "ABCDEFGH";
    map<int, string> mymap;
    
    for (int i=0; i<map_size; i++) {
        stringstream ss; 
        ss << i << "_" << s;
        mymap.insert(make_pair(i, ss.str()));
    }
}

void test_2(int map_size)
{
    string s = "ABCDEFGH";
    map<int, string> mymap;
    
    for (int i=0; i<map_size; i++) {
        stringstream ss; 
        ss << i << "_" << s;
        mymap.emplace(i, ss.str());
    }
}

int main()
{
    check_time_cost(std::function<void()>(std::bind(test_1, 1e7)));
    check_time_cost(std::function<void()>(std::bind(test_2, 1e7)));
    
    return 0;
}

运行的结果和我们的预期会略有不同：

Time Cost: 12.3401 seconds.
Time Cost: 12.6046 seconds.

对这种简单的、以string作为value的map来说，看起来普通的insert比emplace还更快一点。

结论：

在 vector 这样的序列容器中， emplace_back比右值参数的push_back少做一次移动构造，比左值参数的push_back少做一次拷贝构造；
在 map 这样的关联容器中，emplace比insert少做一次移动构造；
节省的移动构造的开销其实很小；而节省的拷贝构造的开销则依赖于自定义类型的复杂程度：复杂程度越高，节省开销越多
对于 key 和 value 都是相对比较简单的类型时，emplace 可能比 insert 还更慢一些。

（完）

emplace_back/emplace 与 push_back/insert 效率的详细比较

区别分析

性能比较

另一个小程序

结论：

相关阅读

相关文章

相关问答

相关文档