欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

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

程序员文章站 2022-03-21 15:16:23
...

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

区别分析

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

  1. 构造这个实例
  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

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

  1. empalce系列都是最快的；
  2. 右值参数版 push_back 比左值版的 push_back 快
  3. 各个类型的构造函数的调用次数也和预期的一致： 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还更快一点。

结论：

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

（完）

相关标签： # C++11 c++ stl

上一篇： .NET Core2.1如何获取自定义配置文件信息详解

下一篇： 详解vue项目优化之按需加载组件-使用webpack require.ensure

推荐阅读