std::unordered_set insert() 方法

自 C++17 起

// (1) Non const version only
std::pair<iterator, bool> insert( const value_type& value );

// (2) Non const version only
std::pair<iterator, bool> insert( value_type&& value );

// (3) Non const version only
iterator insert( const_iterator hint, const value_type& value );

// (4) Non const version only
iterator insert( const_iterator hint, value_type&& value );

// (5) Non const version only
template< class InputIt >
void insert( InputIt first, InputIt last );

// (6) Non const version only
void insert( std::initializer_list<value_type> ilist );

// (7) Non const version only
insert_return_type insert( node_type&& nh );

// (8) Non const version only
iterator insert( const_iterator hint, node_type&& nh );

C++17 之前

// (1) Non const version only
std::pair<iterator, bool> insert( const value_type& value );

// (2) Non const version only
std::pair<iterator, bool> insert( value_type&& value );

// (3) Non const version only
iterator insert( const_iterator hint, const value_type& value );

// (4) Non const version only
iterator insert( const_iterator hint, value_type&& value );

// (5) Non const version only
template< class InputIt >
void insert( InputIt first, InputIt last );

// (6) Non const version only
void insert( std::initializer_list<value_type> ilist );

将元素插入到容器中，如果容器中还没有包含具有等效键的元素。

• (1-2) 插入值。

• (3-4) 插入值，使用提示作为非强制性建议来指示搜索应从何处开始。

• (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()，则行为未定义。

自 C++17 起

失效

如果插入成功，则在节点句柄中持有时获得的指向元素的指针和引用将失效，并且在提取之前获得的指向该元素的指针和引用将变为有效。

C++17 之前

失效

如果由于插入而发生重新散列，则所有迭代器都将失效。否则，迭代器不受影响。

引用不会失效。重新散列仅在新元素数量大于 max_load_factor()*bucket_count() 时发生。

参数

• hint - 迭代器，用作插入内容的建议位置
• value - 要插入的元素值
• first, last - 要插入的元素范围
• ilist - 要从中插入值的初始化列表
• nh - 兼容的节点句柄

类型要求

• (5) - InputIt 必须满足 LegacyInputIterator 的要求。

返回值

• (1-2) - 返回一个对，包含指向插入元素的迭代器（或指向阻止插入的元素的迭代器）和一个布尔值，表示插入是否发生（true表示插入发生，false表示未发生）。
• (3-4) - 返回指向插入元素的迭代器，或指向阻止插入的元素的迭代器。
• (5-6) - (无)
• (7) - 返回一个insert_return_type，其成员按以下方式初始化
  • 如果 nh 为空，则 inserted 为 false，position 为 end()，node 为 empty。
  • 否则，如果插入发生，则 inserted 为 true，position 指向已插入元素，node 为 empty。
  • 如果插入失败，则 inserted 为 false，node 具有 nh 的先前值，position 指向一个键与 nh.key() 等效的元素。
• (8) - 如果nh为空，则为结束迭代器；如果插入发生，则为指向插入元素的迭代器；如果插入失败，则为指向与nh.key()等效的键的元素的迭代器。

复杂度

• (1-4)
  平均情况：O(1)。
  最坏情况：O(size())。

• (5-6)
  平均情况：O(N)（其中 N 是要插入的元素数量）。
  最坏情况：O(N * size()+N)。

• (7-8)
  平均情况：O(1)。
  最坏情况：O(size())。

异常

• (1-4) 如果任何操作抛出异常，插入无效。

重要

本节需要改进。您可以通过编辑此文档页面来帮助我们。

备注

带有提示的插入(3-4)不返回布尔值，以便与顺序容器（如std::vector::insert()）上的位置插入签名兼容。这使得创建通用插入器成为可能，例如std::inserter()。检查带有提示的插入是否成功的一种方法是比较插入前后的size()。

示例

Main.cpp

#include <unordered_set>
#include <iostream>
#include <array>
 
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 << "Initially: " << nums;
  auto p = nums.insert (1); // insert element
  std::cout << "'1' was inserted: " << std::boolalpha << p.second << '\n';
  std::cout << "After insertion: " << nums;
 
  nums.insert (p.first, 0); // insert with hint
  std::cout << "After insertion: " << nums;
 
  std::array<int, 4> a  = {10, 11, 12, 13};
  nums.insert (a.begin (), a.end ()); // insert range
  std::cout << "After insertion: " << nums;
 
  nums.insert ({20, 21, 22, 23}); // insert initializer_list
  std::cout << "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
  std::cout << "After insertion: " << nums;
 
  node = other_nums.extract (other_nums.find (43));
  nums.insert (nums.begin (), std::move (node)); // insert node with hint
  std::cout << "After insertion: " << nums;
}::cout << " " << p.first << " => " << p.second << '\n';

可能输出

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