命名空间
变体
操作

std::unordered_set<Key,Hash,KeyEqual,Allocator>::insert

来自 cppreference.com
< cpp‎ | 容器‎ | 无序集合
 
 
 
 
std::pair<iterator,bool> insert( const value_type& value );
(1) (自 C++11)
std::pair<iterator,bool> insert( value_type&& value );
(2) (自 C++11)
iterator insert( const_iterator hint, const value_type& value );
(3) (自 C++11)
iterator insert( const_iterator hint, value_type&& value );
(4) (自 C++11)
template< class InputIt >
void insert( InputIt first, InputIt last );
(5) (自 C++11)
void insert( std::initializer_list<value_type> ilist );
(6) (自 C++11)
insert_return_type insert( node_type&& nh );
(7) (自 C++17)
iterator insert( const_iterator hint, node_type&& nh );
(8) (自 C++17)
template< class K >
std::pair<iterator, bool> insert( K&& obj );
(9) (自 C++23)
template< class K >
iterator insert( const_iterator hint, K&& obj );
(10) (自 C++23)

如果容器中不存在具有等效键的元素,则将元素(s)插入到容器中。

1,2) 插入 value.
3,4) 插入 value,使用 hint 作为搜索应从何处开始的非绑定建议。
5) 插入范围 [firstlast) 中的元素。如果范围中的多个元素具有比较等效的键,则未指定插入哪个元素(待定 LWG2844)。
6) 插入来自初始化列表 ilist 的元素。如果范围中的多个元素具有比较等效的键,则未指定插入哪个元素(待定 LWG2844)。
7) 如果 nh 是一个空的 节点句柄,则不执行任何操作。否则,如果容器中不存在具有与 nh.key() 等效的键的元素,则将 nh 拥有的元素插入到容器中。如果 nh 不为空且 get_allocator() != nh.get_allocator(),则行为未定义。
8) 如果 nh 是一个空的 节点句柄,则不执行任何操作并返回结束迭代器。否则,如果容器中不存在具有与 nh.key() 等效的键的元素,则将 nh 拥有的元素插入到容器中,并返回指向具有与 nh.key() 等效的键的元素的迭代器(无论插入是否成功)。如果插入成功,则从 nh 中移动元素,否则它将保留元素的所有权。 hint 用作搜索应从何处开始的非绑定建议。如果 nh 不为空且 get_allocator() != nh.get_allocator(),则行为未定义。
9) 如果 *this 已经包含一个透明地与 obj 比较等效的元素,则不执行任何操作。否则,使用 std::forward<K>(obj) 构造一个 value_type 类型的对象 u,然后将 u 插入到 *this 中。如果 equal_range(u) != hash_function()(obj) || contains(u)true,则行为未定义。value_type 必须从 std::forward<K>(obj)EmplaceConstructibleunordered_set 中。只有当 Hash::is_transparentKeyEqual::is_transparent 有效且分别表示一个类型时,此重载才会参与重载解析。这假设这样的 Hash 可以使用 KKey 类型进行调用,并且 KeyEqual 是透明的,这共同允许在不构造 Key 实例的情况下调用此函数。
10) 如果 *this 已经包含一个透明地与 obj 比较等效的元素,则不执行任何操作。

否则,使用value_type构造一个名为u的对象,其值为std::forward<K>(obj),然后将u插入*thisTemplate:hint 用作非绑定建议,表示搜索应从何处开始。 如果equal_range(u) != hash_function()(obj) || contains(u)true,则行为未定义。 value_type 必须能够从std::forward<K>(obj)EmplaceConstructibleunordered_set中。 只有当以下条件满足时,此重载才参与重载解析:

  • std::is_convertible_v<K&&, const_iterator>std::is_convertible_v<K&&, iterator> 都为false,以及
  • Hash::is_transparentKeyEqual::is_transparent 有效,并且分别表示一个类型。 假设此类Hash 可以同时使用KKey 类型进行调用,并且 KeyEqual 是透明的,
这意味着可以在不构造 Key 实例的情况下调用此函数。

如果操作后,新元素数量大于旧的max_load_factor() * bucket_count(),则会进行重新哈希。
如果发生重新哈希(由于插入),则所有迭代器都会失效。 否则(没有重新哈希),迭代器不会失效。 如果插入成功,则在节点句柄中保存元素期间获得的指向该元素的指针和引用将失效,而之前在提取该元素之前获得的指向该元素的指针和引用将变为有效。(自 C++17 起)

内容

[编辑] 参数

hint - 迭代器,用作插入内容的建议位置
value - 要插入的元素值
first, last - 要插入的元素范围
ilist - 用于插入值的初始化列表
nh - 兼容的节点句柄
obj - 任何可以与键透明比较的类型的值
类型要求
-
InputIt 必须满足LegacyInputIterator 的要求。

[编辑] 返回值

1,2) 一个由指向已插入元素(或阻止插入的元素)的迭代器和一个bool 值组成的对,该值仅在插入发生时才设置为true
3,4) 指向已插入元素或阻止插入的元素的迭代器。
5,6) (无)
7) insert_return_type 的一个对象,其成员初始化如下:
  • 如果nh 为空,则 insertedfalsepositionend()node 为空。
  • 否则,如果插入发生,则 insertedtrueposition 指向已插入的元素,node 为空。
  • 如果插入失败,则 insertedfalsenode 具有nh 的先前值,position 指向一个键与nh.key() 相同的元素。
8) 如果nh 为空,则为结束迭代器;如果插入发生,则为指向已插入元素的迭代器;如果失败,则为指向键与nh.key() 相同的元素的迭代器。
9) 一个由指向已插入元素(或阻止插入的元素)的迭代器和一个bool 值组成的对,该值仅在插入发生时才设置为true
10) 指向已插入元素或阻止插入的元素的迭代器。

[编辑] 异常

1-4) 如果任何操作抛出异常,则插入将无效。

[编辑] 复杂度

1-4) 平均情况:O(1),最坏情况:O(size())
5,6) 平均情况:O(N),其中 N 是要插入的元素数量。 最坏情况:O(N * size() + N)
7-10) 平均情况:O(1),最坏情况:O(size())

[编辑] 说明

暗示插入(3,4) 不返回布尔值,以便与顺序容器(如 std::vector::insert)上的位置插入兼容。 这使得创建通用插入器(如 std::inserter)成为可能。 检查暗示插入是否成功的其中一种方法是在之前和之后比较 size()

功能测试 Std 功能
__cpp_lib_associative_heterogeneous_insertion 202311L (C++26) 用于 有序无序 关联 容器 中其余成员函数的异构重载。 (9,10)

[编辑] 示例

#include <array>
#include <iostream>
#include <unordered_set>
 
std::ostream& operator<<(std::ostream& os, std::unordered_set<int> const& s)
{
    for (os << '[' << s.size() << "] { "; int i : s)
        os << i << ' ';
    return os << "}\n";
}
 
int main ()
{
    std::unordered_set<int> nums{2, 3, 4};
 
    std::cout << "1) Initially: " << nums << std::boolalpha;
    auto p = nums.insert(1); // insert element, overload (1)
    std::cout << "2) '1' was inserted: " << p.second << '\n';
    std::cout << "3) After insertion: " << nums;
 
    nums.insert(p.first, 0); // insert with hint, overload (3)
    std::cout << "4) After insertion: " << nums;
 
    std::array<int, 4> a = {10, 11, 12, 13};
    nums.insert(a.begin(), a.end()); // insert range, overload (5)
    std::cout << "5) After insertion: " << nums;
 
    nums.insert({20, 21, 22, 23}); // insert initializer_list, (6)
    std::cout << "6) After insertion: " << nums;
 
    std::unordered_set<int> other_nums = {42, 43};
    auto node = other_nums.extract(other_nums.find(42));
    nums.insert(std::move(node)); // insert node, overload (7)
    std::cout << "7) After insertion: " << nums;
 
    node = other_nums.extract(other_nums.find(43));
    nums.insert(nums.begin(), std::move(node)); // insert node with hint, (8)
    std::cout << "8) After insertion: " << nums;
}

可能的输出

1) Initially: [3] { 4 3 2 }
2) '1' was inserted: true
3) After insertion: [4] { 1 2 3 4 }
4) After insertion: [5] { 0 1 2 3 4 }
5) After insertion: [9] { 13 12 11 10 4 3 2 1 0 }
6) After insertion: [13] { 23 22 13 12 11 10 21 4 20 3 2 1 0 }
7) After insertion: [14] { 42 23 22 13 12 11 10 21 4 20 3 2 1 0 }
8) After insertion: [15] { 43 42 23 22 13 12 11 10 21 4 20 3 2 1 0 }

[编辑] 另请参阅

就地构造元素
(公共成员函数) [编辑]
使用提示就地构造元素
(公共成员函数) [编辑]
创建根据参数推断的类型的 std::insert_iterator
(函数模板) [编辑]