c/c++开发，无可避免的模板编程实践（篇十)-c++11原位构造元素（emplace）

一、容器修改器的新特性

        c++11以前，标准库的容器修改器功能提供了数据插入成员函数inset、push_back，而在 c++11标准化，标准库的容器修改器增加了emplace、emplace_back、emplace_front等插入成员函数。同样是插入函数，两者有何区别呢。

        1.1 内存分配器

        在c++11中，其实容器的构造及元素空间分配充分利用了std::allocator系列分配器。emplace为原位构造元素，通过 std::allocator_traits::construct 构造元素，用布置 new 在容器提供的位置原位构造元素；将参数 args... 作为 std::forward<Args>(args)... 转发给构造函数。 args... 可以直接或间接地指代容器中的值。

        来看一下这些容器的一个类模板定义，都是依赖std::allocator分配器构造的：

//deque
template< class T, class Allocator = std::allocator<T> > class deque;
//list
template< class T, class Allocator = std::allocator<T> > class list;
//map
template< class Key, class T, class Compare = std::less<Key>,class Allocator = std::allocator<std::pair<const Key, T> > > class map;
//set
template< class Key, class Compare = std::less<Key>,class Allocator = std::allocator<Key> > class set;
//.......

        c++11标准库提供了各类式分配器。

//分配器，配器是封装内存分配策略的类模板。这允许泛型容器从数据自身将内存管理解耦合。
//定义于头文件 <memory>
allocator           //默认的分配器(类模板) 
allocator_traits    //(C++11)  提供关于分配器类型的信息(类模板) 
allocation_result   //(C++23)  记录由 allocate_at_least 分配的存储的地址与实际大小(类模板) 
allocate_at_least   //(C++23)  经由分配器分配至少与请求的大小一样大的存储(函数模板) 
allocator_arg_t     //(C++11)  标签类型，用于选择具分配器的构造函数重载(类) 
allocator_arg       //(C++11)  用于选择具分配器的构造函数的 std::allocator_arg_t 对象(常量) 
uses_allocator      //(C++11)  检查指定的类型是否支持使用分配器的构造(类模板) 
uses_allocator_construction_args //(C++20)  准备匹配给定类型所要求的使用分配器构造的口味的参数列表(函数模板) 
make_obj_using_allocator //(C++20)  以使用分配器构造的手段创建给类型的对象(函数模板) 
uninitialized_construct_using_allocator //(C++20)  以使用分配器构造的手段在指定的内存位置创建给定类型的对象(函数模板) //定义于头文件 <scoped_allocator>
scoped_allocator_adaptor //(C++11)  为多级容器实现的多级分配器(类模板) //定义于头文件 <memory_resource>,定义于命名空间 std::pmr
polymorphic_allocator (C++17) //以 std::memory_resource 构造，支持基于它的运行时多态的分配器(类模板) 

        std::allocator 类模板是所有标准库容器所用的默认分配器 (Allocator) ，若不提供用户指定的分配器。默认分配器无状态，即任何给定的 allocator 实例可交换、比较相等，且能解分配同一 allocator 类型的任何其他实例所分配的内存。

//std::allocator,定义于头文件 <memory>
template< class T > struct allocator; 
template<> struct allocator<void>;     //特化，(C++17 中弃用)(C++20 中移除) 

        现在以std::deque容器为例，来探究一下std::allocator 的用处，首先它是用于为容器所有内存分配实现使用的，可处理容器对内存的分配与释放请求。C++的库的容器其共同特征之一，就是其大小可以在程序的运行时改变；为了实现这一点，进行动态内存分配就显得尤为必要，在此分配器就用于处理容器对内存的分配与释放请求。那么和emplace又有何关系呢

        1.2 emplace原位构造元素

        std::allocator支持可以移动赋值、构造、插入等操作方式或可复制赋值、构造、插入等操作方式，前者是原来的insert、push_back等处理方式，需要初始化新元素T 的副本，移动 T进新元素，本质上是采用了operator new分配方式。后者为emplace、emplace_back等处理方式，用布置 new 于容器所提供的位置原位构造元素，即在预分配内存直接构造元素，采用的是std::allocator_traits<Alloc>::construct分配方式。

        下来将看这个两种构建元素的方式在内存操作上如何。在这之前了解一下c++11标准里的原子操作的概念，标准库已经倾斜了对原子类型及原子操作的使用比例。

       创建test.cpp源文件，输入：

void atomic_optest(void)
{int x = 10;int y = x;x++;y+=1;    
}

        上述函数的执行语句，那些是原子操作，那些不是呢。

        通过汇编输出查看一下，编译命令如下：g++ -S test.cpp -o test.s，和cat test.s:

         向一个执行语句只做了一次内存操作，可以认为是原子操作，而int y = x；显然不符合原子操作。

        1.3 容器新旧两种修改器方式比对

        下来再test.cpp中再定义一个函数：

#include <memory>
void emplace_stest(void)
{int *x = nullptr;std::allocator<int> alloc;alloc.construct(x,10);int *y = ::new int(10);//delete x;x = nullptr;delete y;y = nullptr;
}

        再次执行g++ -S test.cpp -o test.s，和cat test.s编译命令如下，可以看出，在调用_ZNSaIiEC1Ev实现alloc定义后，后面给*x构造时，是直接赋值的原子操作，而通过operator new构造元素，在调用_ZNSt15__new_allocatorIiE9constructIiJiEEEvPT_DpOT0_后，还需要进行移动多次原子操作：

         1.4 容器旧有修改器函数与emplace修改器效率比对

        下来在看第三函数，测试std::deque容器的push_back、push_front、emplace_back、emplace_front的效率，通过1000*100000数据入队列执行步骤做效率比对：

//test.h
#ifndef _TEST_H_
#define _TEST_H_
void emplace_Test(void);
#endif //_TEST_H_//test.cpp
#include <queue>
#include <chrono>
#include <iostream>void emplace_Test(void)
{const unsigned long sizel = 100000; std::deque<int> dque;//push_backauto start = std::chrono::system_clock::now();for (size_t i = 0; i < 1000; i++)for (size_t i = 0; i < sizel; i++){dque.push_back(i%3);}auto end = std::chrono::system_clock::now();std::chrono::duration<double,std::milli> diff = end-start;std::cout << "push_back test diff.count() = " <<  diff.count() << "ms\n";dque.clear();//emplace_backstart = std::chrono::system_clock::now();for (size_t i = 0; i < 1000; i++)for (size_t i = 0; i < sizel; i++){dque.emplace_back(i%3);}end = std::chrono::system_clock::now();diff = end-start;std::cout << "emplace_back diff.count() = " <<  diff.count() << "ms\n";dque.clear();//push_frontstart = std::chrono::system_clock::now();for (size_t i = 0; i < 1000; i++)for (size_t i = 0; i < sizel; i++){dque.push_front(i%3);}end = std::chrono::system_clock::now();diff = end-start;std::cout << "push_front diff.count() = " <<  diff.count() << "ms\n";dque.clear();//emplace_frontstart = std::chrono::system_clock::now();for (size_t i = 0; i < 1000; i++)for (size_t i = 0; i < sizel; i++){dque.emplace_front(i%3);}end = std::chrono::system_clock::now();diff = end-start;std::cout << "emplace_front diff.count() = " <<  diff.count() << "ms\n";
};
//main.cpp
#include "test.h"int main(int argc, char* argv[])
{emplace_Test();return 0;
}

        编译g++ main.cpp test.cpp -o test.exe -std=c++11，运行程序：

         可以看到，采用emplace原位构造元素的方式在效率上是略占优势的，这也就是c++11主推emplace方式实现容器修改器的原因，为了保持标准的延续性，又保留了原有的push_back、push_front、insert等成员函数。

二、emplace对容器的支持

        下来再次以std::deque看原位构造元素实现原理，std::deque容器提供了emplace、emplace_back、emplace_front三种修改器成员函数，以std::deque<T,Allocator>::emplace为例：

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

        该函数和传统的insert函数实现同样的功能，直接于 pos 前插入元素到容器中。它是通过 std::allocator_traits::construct 构造元素，常用布置 new 在容器提供的位置原位构造元素。然而若要求的位置已被既存的元素占据，则首先在另一位置构造被插入的元素，然后再将他移动赋值到要求的位置中。将参数 args... 作为 std::forward<Args>(args)... 转发给构造函数。 args... 可以直接或间接地指代容器中的值。要注意的是：所有迭代器，含尾后迭代器，都被非法化。引用亦被非法化，除非 pos == begin() 或 pos == end() ，该情况下它们不被非法化。

        2.1 容器emplace函数的用法

        emplace的用法和insert是一致的，在指定位置前插入元素：

//test1.h
#ifndef _TEST_1_H_
#define _TEST_1_H_void emplace_data(void);#endif //_TEST_1_H_
//test1.cpp
#include "test1.h"#include <iostream>
#include <string>
#include <deque>struct A {std::string s;A(std::string str) : s(std::move(str))  { std::cout << " constructed\n"; }A(const A& o) : s(o.s) { std::cout << " copy constructed\n"; }A(A&& o) : s(std::move(o.s)) { std::cout << " move constructed\n"; }A& operator=(const A& other) {s = other.s;std::cout << " copy assigned\n";return *this;}A& operator=(A&& other) {s = std::move(other.s);std::cout << " move assigned\n";return *this;}
};void emplace_data(void)
{std::deque<A> container;std::cout << "construct 2 times A:\n";A two { "two" };A three { "three" };std::cout << "emplace with A&:\n";container.emplace(container.end(), two);std::cout << "emplace:\n";container.emplace(container.begin(), "one");std::cout << "emplace with A&&:\n";container.emplace(container.end(), std::move(three));std::cout << "emplace:\n";container.emplace(std::next(container.begin(),3), "four");std::cout << "content:\n";for (const auto& obj : container)std::cout << ' ' << obj.s;std::cout << '\n';
}
//main.cpp
#include "test1.h"int main(int argc, char* argv[])
{emplace_data();return 0;
}

        emplace、emplace_back、emplace_front成员函数还支持next等迭代器操作符给出的指定位置插入数据：

//迭代器操作，定义于命名空间 std::experimental::ranges
advance    //令迭代器前进给定的距离(函数模板) 
distance   //返回迭代器和哨位之间的距离，或范围起始和结尾间的距离(函数模板) 
next       //自增迭代器(函数模板) 
prev       //自减迭代器(函数模板) 

        2.2 emplace对不同容器的支持

        针对不同的容器，emplace的成员操作略有不同：

/*相当于原来的insert*/
emplace        //顺序容器、关联容器、无序关联容器、variant any 
/*在容器中的指定位置后插入新元素。原位构造元素，即不进行复制或移动操作。*/
emplace_after //forward_list
/*相当于原来的push_back*/
emplace_back  //deque list vector
/*相当于原来的push_front*/
emplace_front //deque list forward_list
/*插入新元素到容器中尽可能接近于恰在 hint 前的位置(建议性)。原位构造元素，即不进行复制或移动操作*/
emplace_hint  //关联容器、无序关联容器

        emplace_hint成员函数插入新元素到容器中尽可能接近于恰在 hint 前的位置。原位构造元素，即不进行复制或移动操作。参数args 为转发给元素构造函数的参数，以 std::forward<Args>(args)... 转发调用元素的构造函数。返回指向新插入元素的迭代器，而在因元素已存在而插入失败，则返回指向拥有等价关键的既存元素的迭代器。

template <class... Args> iterator emplace_hint( const_iterator hint, Args&&... args );

        emplace_hint成员函数执行复杂度，通常与容器大小成对数，但若新元素正好被插入到 hint 之前则为均摊常数。

//test2.h
#ifndef _TEST_1_H_
#define _TEST_1_H_void emplace_hint_test();#endif //_TEST_1_H_
//test2.cpp
#include "test2.h"#include <chrono>
#include <iostream>
#include <iomanip>
#include <functional>#include <set>
#include <unordered_set>typedef  std::set<int> myset;
// typedef  std::unordered_set<int> myset;const int nof_operations = 10000000;int set_emplace_hint() {myset set;auto it = set.begin();for(int i = 0; i < nof_operations; ++i) {set.emplace_hint(it, i);it = set.end();}return set.size();
}int set_emplace_hint_wrong() {myset set;auto it = set.begin();for(int i = nof_operations; i > 0; --i) {set.emplace_hint(it, i);it = set.end();}return set.size();
}int set_emplace_hint_corrected() {myset set;auto it = set.begin();for(int i = nof_operations; i > 0; --i) {set.emplace_hint(it, i);it = set.begin();}return set.size();
}int set_emplace_hint_closest() {myset set;auto it = set.begin();for(int i = 0; i < nof_operations; ++i) {it = set.emplace_hint(it, i);}return set.size();
}void timeit(std::function<int()> set_test, std::string what = "") {auto start = std::chrono::system_clock::now();int setsize = set_test();auto stop = std::chrono::system_clock::now();std::chrono::duration<double, std::milli> time = stop - start;if (what.size() > 0 && setsize > 0) {std::cout << std::fixed << std::setprecision(2)<< time.count() << "  ms for " << what << '\n';}
}void emplace_hint_test() 
{timeit(set_emplace_hint, "emplace with correct hint");timeit(set_emplace_hint_wrong, "emplace with wrong hint");timeit(set_emplace_hint_corrected, "corrected emplace");timeit(set_emplace_hint_closest, "emplace using returned iterator");
};
//main.cpp
#include "test2.h"int main(int argc, char* argv[])
{emplace_hint_test();return 0;
}

        编译测试g++ main.cpp test2.cpp -o test.exe -std=c++11，set_emplace_hint_wrong是尾部插入由大到小的数据，因此排序很耗时间：

         采用无序关联容器unordered_set测试，调整一下代码：

// typedef  std::set<int> myset;
typedef  std::unordered_set<int> myset;

        再次编译g++ main.cpp test2.cpp -o test.exe -std=c++11测试：

        而对于无序容器，元素的插入效率几乎保持一致。