命名空间
变体
操作

std::set<Key,Compare,Allocator>::insert

来自 cppreference.com
< cpp‎ | container‎ | set
 
C++
 
容器库
 
std::set
 
std::pair<iterator, bool> insert( const value_type& value );
 (1)
std::pair<iterator, bool> insert( value_type&& value );
 (2) (自 C++11 起)
(3)
iterator insert( iterator pos, const value_type& value );
 (直到 C++11)
iterator insert( const_iterator pos, const value_type& value );
 (自 C++11 起)
iterator insert( const_iterator pos, value_type&& value );
 (4) (自 C++11 起)
template< class InputIt >
void insert( InputIt first, InputIt last );
 (5)
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 pos, node_type&& nh );
 (8) (自 C++17 起)
template< class K >
std::pair<iterator, bool> insert( K&& x );
 (9) (自 C++23 起)
template< class K >
iterator insert( const_iterator pos, K&& x );
 (10) (自 C++23 起)

如果容器中不存在与键等效的元素，则将元素插入容器。

1,2) 插入 value。
3,4) 在尽可能靠近 pos 之前的元素位置插入 value。
5) 从范围 [first, last) 插入元素。如果范围中的多个元素具有比较等效的键，则插入哪个元素是不确定的（待定 LWG2844）。
6) 从初始化列表 ilist 插入元素。如果范围中的多个元素具有比较等效的键，则插入哪个元素是不确定的（待定 LWG2844）。
7) 如果 nh 是一个空 节点句柄，则不做任何操作。否则，将 nh 所拥有的元素插入容器，如果容器中不存在与 nh.key() 等效的键的元素。如果 nh 不为空且 get_allocator() != nh.get_allocator()，则行为未定义。
8) 如果 nh 是一个空 节点句柄，则不做任何操作并返回结束迭代器。否则，将 nh 所拥有的元素插入容器，如果容器中不存在与 nh.key() 等效的键的元素，并返回指向与 nh.key() 等效的键的元素的迭代器（无论插入成功与否）。如果插入成功，则从 nh 中转移元素，否则它将保留对元素的所有权。元素尽可能靠近 pos 之前的元素位置插入。如果 nh 不为空且 get_allocator() != nh.get_allocator()，则行为未定义。
9) 如果 *this 中已经包含一个与 x 透明比较等效的元素，则不做任何操作。否则，使用 std::forward<K>(x) 构造 value_type 的一个对象 u，然后将 u 插入 *this 中。如果 equal_range(u) == equal_range(x) 为 false，则行为未定义。value_type 必须从 std::forward<K>(x) EmplaceConstructible 到 set 中。只有当限定标识符 Compare::is_transparent 有效并表示一个类型时，此重载才会参与重载解析。它允许在不构造 Key 实例的情况下调用此函数。
10) 如果 *this 中已经包含一个与 x 透明比较等效的元素，则不做任何操作。否则，使用 std::forward<K>(x) 构造 value_type 的一个对象 u，然后将 u 插入 *this 中，尽可能靠近 pos 之前的元素位置。如果 equal_range(u) == equal_range(x) 为 false，则行为未定义。value_type 必须从 std::forward<K>(x) EmplaceConstructible 到 set 中。只有当 这允许在不构造 Key 实例的情况下调用此函数。

没有迭代器或引用失效。 如果插入成功，则在元素保存在节点句柄中时获得的元素的指针和引用将失效，在元素被提取之前获得的指向该元素的指针和引用将变为有效。(自 C++17 起)

内容

[编辑] 参数

pos - 指向将插入新元素之前的位置的迭代器
value - 要插入的元素值
first, last - 要插入的元素范围
ilist - 用于插入值的初始化列表
nh - 一个兼容的 节点句柄
x - 任何类型的值，可以透明地与键进行比较
类型要求
-
InputIt 必须满足 LegacyInputIterator 的要求。

[编辑] 返回值

1,2) 一个包含指向已插入元素（或阻止插入的元素）的迭代器以及一个 bool 值的 pair，该值仅当插入发生时才设置为 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) 一个包含指向已插入元素（或阻止插入的元素）的迭代器以及一个 bool 值的 pair，该值仅当插入发生时才设置为 true。
10) 指向已插入元素的迭代器，或指向阻止插入的元素的迭代器。

[编辑] 异常

1-4) 如果任何操作抛出异常，则插入无效。
本节内容不完整
原因：情况 5-8、9、10

[编辑] 复杂度

1,2) 对容器大小的对数，O(log(size()))。
3,4) 如果插入发生在紧邻 之后(直到 C++11)之前(自 C++11 起) pos 的位置，则为均摊常数；否则，为对容器大小的对数。
5,6) O(N·log(size() + N))，其中 N 是要插入的元素数量。
7) 对容器大小的对数，O(log(size()))。
8) 如果插入发生在紧邻 之前 pos 的位置，则为均摊常数；否则，为对容器大小的对数。
9) 对容器大小的对数，O(log(size()))。
10) 如果插入发生在紧邻 之前 pos 的位置，则为均摊常数；否则，为对容器大小的对数。

[编辑] 注释

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

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

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

[编辑] 示例

运行此代码
#include <cassert>
#include <iostream>
#include <set>
 
int main()
{
    std::set<int> set;
 
    auto result_1 = set.insert(3);
    assert(result_1.first != set.end()); // it is 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

[编辑] 缺陷报告

以下行为更改缺陷报告被追溯应用于之前发布的 C++ 标准。

DR 应用于 发布的行为 正确行为
LWG 233 C++98 pos 只是一个提示，它可以完全被忽略 插入要求
尽可能接近
紧邻 pos 之前的
位置 C++98 LWG 264
重载 (5) 的复杂度要求为线性，如果		 范围 [first, last)
根据 Compare 排序
删除了线性要求 C++98 在这种特殊情况下
LWG 316		 在重载 (1) 的返回值中，未指定
哪个 bool 值表示插入成功

成功由

(C++11)
 [编辑] 另请参阅
emplace
(C++11)
 (公有成员函数) [编辑]
emplace_hint
 (公有成员函数) [编辑]
inserter
创建一个根据参数推断类型的 std::insert_iterator