Effective Modern C++ Item 42 考虑置入而非插入

如果你有个容器，持有一些，比如说，std::string型别的对象，那么似乎合乎逻辑的做法是用某个插入函数insertion function来向其中添加新元素，比如insert，push_front和push_back，又或者对于std::forward_list而言的insert_after，而传递给函数的元素型别将是std::string。毕竟，那正是容器持有物的型别。

1. 分析为什么push_back效率不高

说合乎逻辑倒也确实合乎逻辑，但却不一定合乎事实。考虑这段代码：

std::vector<std::string> vs;    //持有std::string型别对象的容器
vs.push_back("xyy");            //添加字符串字面量

这里，容器持有的是std::string型别对象，但你手上有的（实际上想要实施push_back的）是个字符串字面量，即，一对引号内的一串字符串。字符串字面量不是std::string，也就是说，传递给push_back的实参并非容器持有物的型别。

1.1 查看一个push_back的实现

std::vector的push_back针对左值和右值给出了不同的重载版本如下：

template<class T,                           //引自C++11标准
         class Allocator = allocator<T>>
class vector {
public:
    ...
    void push_back(const T& x);             //插入左值
    void push_back(T&& x);                  //插入右值
    ...
}

在下面的调用语句中：

vs.push_back("xyy");

编译器会看到实参型别const char[6]与push_back std::string的引用型别接受的形参性别之间的不匹配。而解决的办法就是通过生成代码以从字符串字面量触发创建std::string型别的临时变量，并将该临时对象传递给push_back。换言之，他们把这句调用看作下面这样：

vs.push_back(std::string("xyy"));   //创建std::string型别的临时对象
                                    //并将其传递给push_back

这段代码顺利通过编译并且运行无误，所有人都开心地打卡下班了。所有人，除了那些性能狂人们，正是他们，认识到这段代码不像它应有的那样高效。

1.2 分析push_back的实际操作流程

为了在持有std::string型别对象的容器中创建一个新的元素，他们明白，调用一次std::string的构造函数是应该的，但是上面的代码不会只发生一次构造函数调用。实际上，发生了两次。并且，还发生了一次std::string的析构函数调用。以下是对push_back的调用在运行期执行的全部动作：

a. 从字符串字面量xyy触发，创建std::string型别的临时对象。该对象没有名字，我们称之为temp。针对temp实施的构造，就是第一次的std::string构造函数的调用。因为是个临时对象，所以temp是个右值。

b. temp被传递给push_back的右值重载版本，在那里它被绑定到右值引用形参x。然后，会在内存中为std::vector构造一个x的副本。这一次的构造（已经是第二次）结果就是在std::vector内创建了一个新的对象（用于将x复制到std::vector的构造函数，是移动构造函数，因为作为右值引用的x，在复制之前被转换成了右值。有关将右值引用形式强制转型到右值的相关信息，参见Item 25）。

c. 紧接着push_back返回的那一时刻，temp就被析构，所以，这就需要调用一次std::string的析构函数。

性能狂人们肯定会不由自主的注意到，如果有什么办法能将字符串字面量直接传递给上述步骤2中那段在std::string内构造的std::string型别对象的代码，我们也就可以避免先构造再析构temp。这么一来，就可以达到效率最大化，即便是性能狂人也能安心打卡下班了。

1.3 分析emplace_back的好处

由于你是名C++程序员，所以你比起其他人群成为性能狂人的概率更高。即使你不是个性能狂人，你也很可能会认同他们的观点（如果你对性能不以为意，难道你不应该出门左转到Python之家去吗？，注：这句话是作者原句，感觉放到现在有点引战的味道。。）所以，我很乐意告诉你，确实有个办法能够使得push_back调用过程的效率最大化。办法就是不要调用push_back。调用push_back是弄错了函数。符合要求的函数是emplace_back。

emplace_back完全符合期望：它使用传入的任何实参在std::vector内构造一个std::string。不会涉及任何临时对象：

vs.emplace_back("xyy");         //直接从`xyy`出发，在vs内
                                //构造std::string型别对象

emplace_back使用了完美转发，所以只要你没有遭遇完美转发的限制（Item 30），就可以通过emplace_back传递任意型别的任意数量和任意组合的实参。例如，如果你想通过std::string的那个接受一个字符及重复技术的构造函数重载版本来创建一个std::string型别对象，下面的代码就可以做到：

vs.emplace_back(50, 'x');       //插入一个由50个`x`字符组成的
                                //consisting std::string 型别对象

emplace_back可用于任何支持push_back的标准容器。相似的，所有支持push_front的标准容器也支持emplace_front。还有，任何支持插入操作（即，除了std::forward_list和std::array以外的所有标准容器）都支持置入操作。关联容器提供了emplace_hint来补充它们带有hint迭代器的insert函数，而std::forward_list也有着emplace_after与其insert_after一唱一和。

1.4 分析emplace_back为何能超越push_back

使得置入函数超越插入函数成为可能的，是置入函数更加灵活的接口。插入函数接受的是待插入对象，而置入函数接受的则是待插入对象的构造函数实参。这一区别就让置入函数得以避免临时对象的创建和析构，但插入函数就无法避免。

因为具备容器所持有之物的实参可以被传递给一个置入函数（而后，该实参会引发函数执行复制或移动构造），所以即使在插入函数并不要求创建临时对象的情况下，也可以使用置入函数。在那种情况下，插入函数和置入函数本质上做的是同一件事。例如，给出下面的std::string型别对象：

std::string queenofDisco("Donna Summer");

下面两个调用语句都成立，并且对容器来说，净效果相同：

vs.push_back(queenofDisco);     //在vs的尾部复制构造了queenofDisco
vs.emplace_back(queenofDisco);  //同上

2. 看似完美的emplace_back也有不足

这么一来，置入函数就能做到插入函数所能做到的一切。有时，他们可以比后者做的更高效一些，而且，至少在理论上，它们应该不会比后者效率更低。既然如此，何不总是使用置入函数呢？

因为，从理论上说，理论和实践没有区别，但从实践上说，理论和实践是有区别的。从标准库的当前实现情况来看，在有些情况下，正如预期的那样，置入的性能优于插入，但是，不幸的是，还是存在插入函数运行得更快的情况。后面一种情况不太容易表征，因为具体来说，取决于：

a. 传递的实参型别
b. 使用的容器种类
c. 请求插入或置入的容器位置
d. 所持有型别构造函数的异常安全性
e. 还有，对于禁止出现重复的容器（即，std::set,std::map,std::unordered_set和std::unordered_map）而言，容器中是否已经存在要添加的值。

所以，这里适用一般的性能调优建议：欲确定置入或插入哪个运行更快，需对两者实施基准测试。

2.1 emplace系列效率更高的前提

这样的说法当然不尽如人意，所以你肯定会高兴的得知，有一种启发式思路可以帮助确定置入功能在哪些情况下极有可能值得一试。如果下列情况都成立，那么置入将几乎肯定比插入更高效。

• 欲添加的值是以构造而非赋值方式加入容器。本条款第一例（即从xyy出发创建std::string型别对象，并加入std::vector），就能看出该值是被添加到了vs的结尾，该位置尚不存在对象。是故，新值必须以构造方式加入std::vector。若我们修订此例，使得新的std::string型别对象去到某个已被某对象占据的位置，则完全变成另一回事了。考虑如下代码：

  std::vector<std::string>  vs;   //同前
  ...                             //向vs中添加元素
  vs.emplace_back(vs.begin(), "xyy"); //向vs的开头添加`xyy`
  

  对于这代码，很少会有实现是将待添加的std::string在由vs[0]占用的内存中实施构造。这里一般会采用不同的手法，即移动赋值的方式来让该值就位。但既然是移动赋值，总要有个作为源的移动对象，也就是意味着需要创建一个临时对象作为移动的源。由于置入相对于插入的主要优点在于既不会创建也不会析构临时对象，那么当添加的值是经由赋值放入容器的时候，置入的边际效用也就趋于消失了。

  哎，向容器中添加值究竟是通过构造还是赋值，这一般取决于实现者。但是，启发式思维会再一次派上用场。

  基于节点的容器几乎总是使用构造来添加新值，而大多数标准容器都是基于节点的。仅有的一些例外是std::vector,std::deque和std::string(std::array也不基于节点，但它根本不支持插入或置入，所以和这里的讨论不相干)。在非基于节点的容器中，可以可靠的说，emplace_back是使用构造函数非赋值来将新值就位的，而这一点对于std::deque的emplace_front来说也一样成立。

• 传递的实参型别与容器持有物的型别不同。可以再次看出，置入相对于插入的优势通常源于这一个事实，即当传递的实参型别并非容器持有之物的型别时，其接口不要求创建和析构临时对象。当型别为T的对象被添加到container<T>中时，没有理由期望置入的运行速度会比插入快，因为并不需要为了满足插入的接口去创建临时对象。

• 容器不太可能由于出现重复情况而拒绝待添加的新值。这意味着，或者是容器允许重复值，或者所添加的大部分值都满足唯一性。这个因素之所以值得一提，是因为，欲检测某值是否已经在容器中，置入的实现通常会使用该新值创建一个节点，以便将该节点的值与容器的现有节点进行比较。如果待添加的值尚不在容器中，则将节点链入该容器。但是，如果该节点已经存在，则置入就会中止，节点也就会实施析构，这意味着其构造和析构的成本是被浪费掉了。

下述前面已列出的调用语句满足所有的判断准则。它们就比对应的push_back调用要运行的更快。

vs.emplace_back("xyy");     //在容器尾部以构造新值
                            //传递和型别有异于容器持有之物的型别
                            //未使用拒绝重复值的容器
vs.emplace_back(50, 'x');   //同上

2.2 emplace系列在资源管理对象就地构造的时候，最好不要用

在决定是否选用置入函数时，还有其他两个问题值得操心。第一个和资源管理有关。假定你有个持有std::shared_ptr<Widget>型别对象的容器。

std::list<std::shared_ptr<Widget>> ptrs;

而你想向其添加一个需要通过自定义删除器来释放的(参见Item 19) std::shared_ptr。Item 21解释过，只要可行，你就应该使用std::make_shared来创建std::shared_ptr型别的对象，但它同时也认可，在某些情况下你无法这样做。而其中之一，就是需要指定自定义删除器的情况。在此情况下，就必须直接使用new来获取裸指针以备std::shared_ptr加以管理。

如果自定义删除器就是下面这个函数：

void killWidget(Widget* pWidget);

选用了插入函数的代码就应该长成这样：

ptrs.push_back(std::shared_ptr<Widget>(new Widget, killWidget));

也可能长成这样，但意义相同：

ptrs.push_back({ new Widget, killWidget });

不管写成上面两者中的哪样，在调用push_back之前，都会创建一个std::shared_ptr型别的临时对象。push_back的形参是个std::shared_ptr型别的引用，所以必须存在一个std::shared_ptr型别独享来 让该形参指涉到。

如果选用了emplace_back，本可以避免创建std::shared_ptr型别的临时独享，但是在本例的情况下，该临时对象带来的收益远超其成本。考虑下面这个有可能发生的事件序列：

1. 上述两个调用语句无论哪个都会构造一个std::shared_ptr<Widget>型别的临时对象，用以持有从new Widget返回的裸指针。该对象暂称为temp。
2. push_back会按引用方式接受temp。在为链表节点分配内存以持有temp的副本的过程中，抛出了内存不足的异常。
3. 该异常传播到了push_back之外，temp被析构。作为给Widget兜底的、指涉到它并对其施加管理的std::shared_ptr<Widget>型别对象会自动释放该Widget，在本例的情况下，会调用killWidget达成该目的。

即使发生异常，也没有资源泄露。在push_back的调用过程中，从new Widget出发构造的Widget，会在为管理它创建的std::shared_ptr(temp)的析构函数中得到释放，岁月静好。

现在考虑 一下，如果调用的是emplace_back，而不是push_back，会发生什么：

ptrs.emplace_back(new Widget, killWidget);

1. 从new Widget返回的裸指针被完美转发，并运行到emplace_back内为链表节点分配内存的执行点。然而，该内存分配失败，并抛出了内存不足的异常。
2. 该异常传播到了emplace_back之外，作为唯一可以获取堆上Widget的抓手的裸指针，却丢失了。那个Widget(连同他拥有的任何资源)都发生了泄漏。

在这种场景下，岁月不再静好，并且故障不能归罪于std::shared_ptr。即使换用std::unique_ptr的自定义删除器，同样的问题仍然可能会现身。从根本上讲，像std::shared_ptr和std::unique_ptr这样的资源管理类若要发挥作用，前提是资源（比如从new出发的裸指针）会立即传递给资源管理对象的构造函数。std::make_shared和std::make_unique这样的函数会把这一点自动化，这个事实真是为何他们如此重要的原因之一。

在调用持有资源管理对象的容器（例如，std::list<std::shared_ptr<Widget>>）的插入函数时，函数的形参型别通常能确保在资源的获取（例如，运用new）和对资源管理的对象实施构造之间不再有任何其他动作。而在置入函数中，完美转发会推迟资源管理对象的创建，直到他们能够在容器的内存中构造为止。这开了一个“天窗”，其中就会因异常而导致资源泄露。所有的标准容器对此都在劫难逃。在处理持有资源管理对象的容器时，必须小心确保在选用了置入而非插入函数时，不会在提升了一点代码效率的同时，却因异常安全性的削弱而赔的精光。

坦率地说，绝不应该把像new Widget这样的表达式传递给emplace_back、push_back或者大多数其他函数，因为正如Item 21所解释过的，这可能会导致我们刚才所讨论的异常安全问题。要把这扇门关闭，就需要从new Widget中获取指针并将其在独立语句中转交给其他资源管理对象，然后将该对象作为右值传递给你最初想要向其传递new Widget的函数，Item 21涵盖了该技术的更多细节。所以，选用了push_back的代码有应该这样写：

std::shared_ptr<Widget> spw(new Widget, 
                            killWidget);    //构造Widget并用spw管理它
ptrs.push_back(std::move(spw));             //以右值形式添加spw

选用了emplace_back的版本十分类似：

std::shared_ptr<Widget> spw(new Widget, killWidget);
ptrs.emplace_back(std::move(spw));  

无论选用哪个，这个途径都会蝉声了构造和析构spw的成本。考虑选用置入而非插入的动机就在于避免容器所持有之物的型别的临时对象的成本，而这成本正是spw所体现的概念，当你向容器中添加的是资源管理对象，并遵循了正确的做法以确保在资源的获取和将其移交给资源管理对象之间没有任何多余的动作的话，置入函数的性能表现就不太会在此情形下仍然超越插入函数。

2.3 emplace系列在带有explicit声明饰词的构造函数，慎用

置入函数第二个值得一提的方面，是它们与带有explicit声明饰词的构造函数之间的互动。假设你为了表彰C++11对正则表达式的支持，构造了一个正则表达式对象的容器:

std::vector<std::regex>   regexes;

由于别你的同事们为了“每天该上多少次社交网站才最理想”的争论而分了心，你无意间写下了下面这句看似无意义的代码：

regexes.emplace_back(nullptr);  //向持有正则表达式的容器添加了一个nullptr?

你在输入时没有注意到该错误，而编译器也一声不吭地接受了代码，最终你浪费了大把时间来调试，找了半天，你终于发现自己在正则表达式容器中插入了一个空指针。但这怎么可能呢？指针本根不是正则表达式啊，而且如果你试图这样做：

std::regex r = nullptr;         //错误！无法通过编译

编译器会拒绝你的代码。有意思的是，如果你选用的是push_back而非emplace_back，编译器同样也会拒绝你的代码：

regexes.push_back(nullptr);     //错误！无法通过编译

这种令人好奇的行为源自于std::regex对象可以从字符串触发来构造这一事实。这就使得下面这样有用的代码成为合法的：

std::regex  uppperCaseWord("[A-Z]+");

从字符串出发来构造std::regex型别对象，肯定会导致相对较高昂的运行期成本，因此，为了尽可能地减少无意间招致这种开销的可能性，接受const char *指针的std::regex构造函数以explicit饰词声明。这就是为何下面几个语句都通不过编译：

std::regex r = nullptr;         //错误！无法通过编译

regexes.push_back(nullptr);     //错误！无法通过编译

在两种情况下，我们都要求了一次从指针到std::regex的隐式型别转换，而由于该构造函数带有explicit饰词声明，这样的型别转换被阻止了。

然而，在emplace_back的调用过程中，我们却没有声称传递的是个std::regex对象。取而代之的是，我们向std::regex对象传递的是个构造函数实参。这不但不被视作隐式型别转换的请求，反而在编译器看来是等同于写了这样的代码：

std::regex  r(nullptr);         //能编译

如果简短的注释“能编译”暗示着一种无精打采，那是好事，因为这段代码虽然能通过编译，但却有着未定义行为。接受const char*指针的std::regex构造函数要求指涉到的字符串包含一个有意义的正则表达式，而空指针并不符合该要求。如果你编写并编译这样的代码，你能指望的最好结果就是它在运行时崩溃。如果你不那么走运，你和你的调试器可能得亲密好一阵子了。

先把push_back和emplace_back和亲密什么的按下不表，单注意下面几个非常相似的初始化语法如何蝉产生了不同的结果：

std::regex  r1 = nullptr;       //错误！无法通过编译

std::regex r2(nullptr);         //能编译

用标准的官方术语来说，用于初始化r1（采用等号）的语法对应于所谓的复制初始化。相对的，用于初始化r2的语法（使用括号，尽量也可以使用花括号代替）会产生所谓的直接初始化。复制初始化是不允许调用带有explicit声明饰词的构造函数的，但直接初始化就允许。是故，对r1实施初始化的那一行通不过编译，但对r2实施初始化的那一行就可以通过编译。

但是，回过头来再说push_back和emplace_back，或更一般地对插入函数和置入函数作对比。置入函数使用的是直接初始化，所以他们就能够调用带有explicit声明饰词的构造函数。而插入函数使用的是复制初始化，它们就不能调用带有explicit声明饰词的构造函数。因此：

regexes.emplace_back(nullptr);      //能编译，直接初始化允许使用
                                    //接受指针的，带有explicit声明饰词的
                                    //std::regex构造函数

regexes.push_back(nullptr);         //错误！复制初始化禁止使用
                                    //那个构造函数

这里得到的教训是，在使用置入函数时，要特别小心去保证传递了正确的实参，因为即使是带有explicit声明饰词的构造函数也会被编译器纳入考虑范围，因为它会尽力去找到某种方法来解释你的代码以使得它合法。

要点速记

1. 从原理上说，置入函数应该有时比对应的插入函数高效，而不应该有更低效的可能。

2. 从实践上说，置入函数在以下几个前提条件均成立时，极有可能会运行的更快：a. 待添加的值是以构造而非赋值方式加入容器；b. 传递的实参型别与容器持有之物的型别不同；c. 容器不会由于存在重复值而拒绝待添加的值。

3. 置入函数可能会执行在插入函数中被拒绝的型别转换。