我不确定这是否以及如何适用于无序容器。但是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)
不要那样做。我不确定标准库是否这样做。
