C++ STL中的deque emplace

C++中的STL（标准模板库）是程序员们的好帮手，它为我们提供了许多容器和算法，其中之一就是deque（双向队列）。而在deque中，有一种很有用的函数emplace，可以帮助我们更加方便地进行元素的插入。

deque简介

deque，也称双向队列，是一种具有动态扩展的序列容器。

一个deque是一个具有两个前端的序列容器，这意味着可以在开头和结尾比O(1)更快的时间插入和删除元素。

因为deque内存是非连续的，所以双向队列既是一个向量（vector）又是一个链表（list）。

vector和list都是单头的，vector只能在尾端增加元素，而list只能够在头尾增加元素，deque则是双头的，同时任意一端都可以增删元素，是一种优秀的动态存储方式。

emplace函数

emplace函数是C++11中STL提供的一个函数，用于在容器中插入一个元素，同时避免了拷贝赋值带来的资源浪费和效率低下的问题。

emplace() 可以直接将参数放在 member object 中来构建它，而不需要进行拷贝或移动操作。

emplace使用方法

emplace 函数有两种形式：

template< class... Args >
iterator emplace( const_iterator pos, Args&&... args );

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

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

第一种是在deque的指定位置插入新的元素，第二种是在deque的末尾插入新的元素，第三种是在deque的头部插入新的元素。

需要注意的是，在使用emplace()函数时，Args序列中的元素数量和类型需要与该容器所持有的元素类型相匹配。

举个例子：

deque<pair<int, string> > d;

// 使用普通方法向容器中插入一对键值对
pair<int, string> p = make_pair(1, "hello");
d.push_back(p);

// 使用emplace()函数向容器中插入一对键值对
d.emplace_back(2, "world");

// emplace()函数的另一种形式
d.emplace(d.begin(), 3, "welcome");

在使用emplace()函数插入元素时，可以传入的参数可以是任何满足元素类型构造函数接受的类型。

例如，deque内部的元素类型为：

struct Item {
  int id;
  string name;
  int price;
  Item(int id, const string& name, int price) : id(id), name(name), price(price) {}
};

那么可以使用下面这种方式插入元素：

deque<Item> items;

items.emplace_back(1, "apple", 5);
items.emplace_front(2, "orange", 4);

emplace性能测试

对于emplace()函数的性能测试，可以使用time命令进行测量。以下是一个使用deque和vector的场景对比：

#include <iostream>
#include <deque>
#include <vector>
#include <chrono>
#include <ctime>
#include <cstdlib>

using namespace std;

int main()
{
    deque<int> d;
    vector<int> v;
    int n = 10000000;

    // deque
    auto start = std::chrono::system_clock::now();
    for (int i = 0; i < n; i++) {
        int x = rand() % 1000000;
        d.emplace_back(x);
    }
    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    cout << "deque elapsed time: " << elapsed_seconds.count() << "s\n";

    // vector
   start = std::chrono::system_clock::now();
    for (int i = 0; i < n; i++) {
        int x = rand() % 1000000;
        v.emplace_back(x);
    }
    end = std::chrono::system_clock::now();
    elapsed_seconds = end - start;
    cout << "vector elapsed time: " << elapsed_seconds.count() << "s\n";

    return 0;
}

以上代码中，我们使用了随机数生成器生成了10000000个随机整数，并分别使用了deque和vector进行了元素的插入。

在时间测量的结果中，可以看到，使用emplace()函数插入元素的deque的性能要优于vector。