名稱空間
變體
操作

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

來自 cppreference.com
< cpp‎ | 容器‎ | 無序集合
 
C++
 
容器庫
 
std::unordered_set
成員型別
成員函式
非成員函式
(until C++20)
推導指南 (C++17起)
 
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 起)

如果容器中尚不包含具有等效鍵的元素，則將元素插入容器中。

1,2) 插入 value。
3,4) 插入 value，使用 hint 作為搜尋起始位置的非繫結建議。
5) 插入範圍 [first, last) 中的元素。如果範圍中有多個元素的鍵比較等價，則插入哪個元素是未指定的（等待 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) 就位構造（EmplaceConstructible）到 unordered_set 中的型別。此過載僅在 Hash::is_transparent 和 KeyEqual::is_transparent 有效且各自表示一個型別時才參與過載決議。這假定此類 Hash 可用 K 和 Key 型別呼叫，並且 KeyEqual 是透明的，這共同允許在不構造 Key 例項的情況下呼叫此函式。
10) 如果 *this 已包含一個與 obj 進行透明比較“等價”的元素，則不執行任何操作。

否則，使用 std::forward<K>(obj) 構造一個 value_type 物件 u，然後將 u 插入到 *this 中。Template:hint 用作搜尋起始位置的非繫結建議。如果 equal_range(u) != hash_function()(obj) || contains(u) 為 true，則行為未定義。value_type 必須是可從 std::forward<K>(obj) 就位構造（EmplaceConstructible）到 unordered_set 中的型別。此過載僅在以下條件滿足時才參與過載決議：

  • std::is_convertible_v<K&&, const_iterator> 和 std::is_convertible_v<K&&, iterator> 都為 false，並且
  • Hash::is_transparent 和 KeyEqual::is_transparent 有效且各自表示一個型別。這假定此類 Hash 可用 K 和 Key 型別呼叫，並且 KeyEqual 是透明的，
這共同允許在不構造 Key 例項的情況下呼叫此函式。

如果操作後新元素數量大於舊的 max_load_factor() * bucket_count()，則會發生重新雜湊（rehashing）。
如果發生重新雜湊（由於插入），所有迭代器都將失效。否則（未發生重新雜湊），迭代器不會失效。如果插入成功，則在節點控制代碼中持有時獲取的元素指標和引用將失效，並且在提取前獲取的該元素的指標和引用將變為有效。(C++17 起)

目錄

[編輯] 引數

hint - 迭代器，用作插入內容的建議位置
value - 要插入的元素值
first, last - 定義要插入的元素源範圍的迭代器對
ilist - 要從中插入值的初始化列表
nh - 相容的節點控制代碼
obj - 可與鍵透明比較的任何型別的值
型別要求
-
InputIt 必須滿足 LegacyInputIterator 的要求。

[編輯] 返回值

1,2) 一個對，包含一個指向已插入元素（或阻止插入的元素）的迭代器，以及一個布林值，當且僅當插入發生時設定為 true。
3,4) 指向插入元素的迭代器，或指向阻止插入的元素的迭代器。
5,6) (無)
7) 一個 insert_return_type 物件，其成員初始化如下：
  • 如果 nh 為空，則 inserted 為 false，position 為 end()，且 node 為空。
  • 否則，如果插入發生，則 inserted 為 true，position 指向插入的元素，且 node 為空。
  • 如果插入失敗，則 inserted 為 false，node 具有 nh 的前一個值，且 position 指向一個鍵與 nh.key() 等價的元素。
8) 如果 nh 為空，則返回末尾迭代器；如果插入發生，則返回指向已插入元素的迭代器；如果插入失敗，則返回指向鍵與 nh.key() 等價的元素的迭代器。
9) 一個對，包含一個指向已插入元素（或阻止插入的元素）的迭代器，以及一個布林值，當且僅當插入發生時設定為 true。
10) 一個指向已插入元素或阻止插入的元素的迭代器。

[編輯] 異常

1-4) 如果任何操作丟擲異常，則插入無效。
本節不完整
原因：情況 5-10

[編輯] 複雜度

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()。

特性測試宏 值 標準 特性
__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
(函式模板) [編輯]
取自“https://cppreference.tw/mwiki/index.php?title=cpp/container/unordered_set/insert&oldid=180862”