代码之家 › 专栏 › 技术社区 › Enlico

对不允许重复的集装箱放置和插入效率不同的困惑

effective-c++ emplace insert c++11 c++

Enlico · 技术社区 · 4 年前

在第41项中 现代C++ ,以下是一种情况,它为安置功能提供了比插入对手更高的性能:

容器不太可能将新值作为重复值拒绝

原因是,鉴于 构造函数的参数 对于试图插入容器中的项目,置换函数必须构造该对象以评估它是否已经存在于容器中,在这种情况下,构造是一种浪费,其次是不可避免的构造浪费。

我在这里已经有些怀疑了。如果我使用插入函数来避免这种情况,那么我将自己构造对象(可能是一个临时对象,将我传递给放置函数的参数传递给它的构造器),并将其传递给插入函数,然后,如果容器中已经有一个相等的值,那么这个临时对象将被销毁。

所以我看不出有什么不同。

此外,提交人补充说

与插入功能相比,为安置功能创建此类节点的频率更高。

如果对象已经在容器中,为什么我用来在容器中插入对象的函数会受到影响?

0 回复 | 直到 4 年前

n314159 4 年前

我不确定这是否以及如何适用于无序容器。但是a std::set 通常在内部由二叉树(通常是红黑树)表示。你可以假设节点看起来有点像这样:

struct Node {
    Node* parent, left_child, right_child;
    value_type value;
}

现在让我们看看放置和插入时会发生什么:

emplace(args...) :现在,我们需要一个 value_type -为了能够进行比较。但我们不会创造一个临时的,我们以后会移动( std::set 不需要 value_type 可移动或可复制!)。我们将直接创建一个 Node a 在堆上构建 value 原地从 args 之后,我们检查 价值 已在集合中。如果是这样,我们删除 a 并且已经完成。否则,我们将调整 Node* 属于 一 把它带进片场。
insert(val) :在这里,我们已经有一个对象(可能是临时的)。因此,我们确定它是否已经在集合中。如果是这样,什么都不会发生,我们就完了。如果它不在集合中,我们现在分配一个 Node 并将val复制/移动到其中 节点 并设置 节点* 把它带进片场。

现在让我们分析一下不同的szenarios。

位置(参数…) :如果 value_type 对象构造自 args... 已经在地图上了。我们将始终分配一个 节点 并使用 value_type(args...) 建设者一次。不得移动,不得复制。如果对象已经存在,我们将 delete 一 节点 从而调用析构函数 value_type .
插入(val) :如果 val 已经存在,我们根本不进行任何建设 insert 如果没有,我们分配一个 节点 复制/移动 瓦尔 如果你建造 瓦尔 从 args。。。 同时将其传递给 插入 (即呼叫 insert(value_type(args...)) )那么,我们当然还有另一个 value_type(参数…) 以及调用此临时文件的析构函数。

所以, emplace 将始终分配 节点 ,而不管值是否存在。 插入(value_type(args…)) 如果值存在,则不会有这个,但如果值不存在,则会有一个额外的移动。

因此,如果你的容器可能会拒绝该对象,那么你将为该对象分配不必要的堆 节点 。这可能比从 插入 此外,你会发现 安置就位 一个已经存在的对象,因为这只会添加 节点 -分配 ^1. 如果它失败了,没有奖金。

1:可能会有另一个超载 emplace(value_type) 不要那样做。我不确定标准库是否这样做。