如果集合中已存在临时元素,是否允许“[unordered_]set::emplace()”不构造临时元素?

Hol*_*Cat 5 c++ language-lawyer

这个答案指出了一些有趣的事情:

天真的实现比给定容器中已存在的类型的对象std::unordered_set<T>::emplace()要慢,因为可以检测到并立即退出,但天真的会首先分配一个节点,构造元素,然后检查唯一性,如果存在则销毁并释放它已经存在。insert()Tinsert()emplace()

emplace当给定参数时肯定是这种情况!= 1,因为如果不调用构造函数就无法理解它们。但也许可以优化 1 个参数的情况。

std::set<T>::emplace()想必所有这些也适用。那么,两个问题:

  1. 标准是否允许emplace()在这种情况下不构造对象?即,如果只传递一个参数,并且remove_cvref_t<argument-type>与元素类型匹配,是否可以直接emplace()应用==// <hash 参数,而无需构造新对象?

    • 那么透明比较器呢?如果 的参数emplace与元素类型可比较,是否可以直接比较,而不构造完整元素?
  2. 现代的实现实际上在实践中进行了这种优化吗?

use*_*522 2

标准是否允许 emplace() 在这种情况下不构造对象?

不,[associative.reqmts][unord.req](分别用于std::setstd::unordered_set)仅要求参数 是emplaceCpp17EmplaceConstructible容器中的,并且没有额外的语义要求。emplace还指定与将插入到容器中的对象的键进行比较。

[container.requriments.general]/16.5 Cpp17EmplaceConstructible中所指定,仅需要分配器感知容器根据[container.requirements.general]/3std::allocator_traits::construct将对象构造到容器中所需的表达式的有效性。

对于标准分配器std::allocatorconstruct将简单地使用参数列表中相应的直接初始化来构造对象。这通常不会对构造对象的值与原始对象的关系施加任何要求。它甚至不需要导致对复制或移动构造函数的调用。对于其他分配器,construct仅需要构造预期类型的​​对象,没有任何语义要求(请参阅[allocator.requirements.general]/2)。

因此,不要求将插入的元素的键与传递的对象的键相等,因此优化通常无效。(但是假设规则当然仍然适用。)

对于insert规范要求Cpp17CopyInsertableCpp17MoveInsertable代替。这些特别强制要求在容器中构造的对象相当于根据[container.requirements.general]/16.3 和 16.4传递的对象,并且规范insert还要求与传递的对象的键进行比较,而不是与将要传递的对象的键进行比较。构建在容器中。