std::set insert() 方法

自 C++17 起

// (1) Non const version only
std::pair<iterator, bool> insert( 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++11 起

// (1) Non const version only
std::pair<iterator, bool> insert( 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 );

直到 C++11

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

// (3) Non const version only
iterator insert( iterator hint, const 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)

  自 C++11 起

  在尽可能接近提示的位置插入值，就在提示之前。

  直到 C++11

  在尽可能接近提示的位置插入值。

• (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) 返回一个对，包含指向已插入元素（或阻止插入的元素）的迭代器以及一个表示插入是否发生的 bool 值（如果插入发生则为 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-2) 与容器大小呈对数关系 - O(log size())。

• (3-4)

  自 C++11 起

  如果插入发生在 hint 之前的位置，则分摊常量时间 - O(1)。
  否则，与容器大小呈对数关系 - O(log size())。

  直到 C++11

  如果插入发生在 hint 之后的位置，则分摊常量时间 - O(1)。
  否则，与容器大小呈对数关系 - O(log size())。

• (5-6) O(N * log(size() + N))，其中 N 是要插入的元素数量。

• (7) 容器大小的对数时间 - O(log size())。

• (8)
  如果插入发生在 hint 之前的位置，则分摊常量时间 - O(1)；否则为容器大小的对数时间 - O(log size())。

异常

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

重要

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

备注

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

重载 (5-6) 通常实现为循环调用重载 (3)，并将 end() 作为提示；它们针对追加已排序序列（例如另一个集合），其最小元素大于 *this 中的最后一个元素进行了优化。

示例

Main.cpp

#include <set>
#include <cassert>
#include <iostream>
 
int main()
{
  std::set<int> set;
 
  auto result_1 = set.insert(3);
  assert(result_1.first != set.end()); // it's a valid iterator
  assert(*result_1.first == 3);
  if (result_1.second)
    std::cout << "insert done\n";
 
  auto result_2 = set.insert(3);
  assert(result_2.first == result_1.first); // same iterator
  assert(*result_2.first == 3);
  if (!result_2.second)
    std::cout << "no insertion\n";
}

可能输出

insert done
no insertion