命名空间
变体
操作

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

来自 cppreference.cn
< 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) (since C++11)
(3)
iterator insert( iterator pos, const value_type& value );
 (until C++11)
iterator insert( const_iterator pos, const value_type& value );
 (since C++11)
iterator insert( const_iterator pos, value_type&& value );
 (4) (since C++11)
template< class InputIt >
void insert( InputIt first, InputIt last );
 (5)
void insert( std::initializer_list<value_type> ilist );
 (6) (since C++11)
insert_return_type insert( node_type&& nh );
 (7) (since C++17)
iterator insert( const_iterator pos, node_type&& nh );
 (8) (since C++17)
template< class K >
std::pair<iterator, bool> insert( K&& x );
 (9) (since C++23)
template< class K >
iterator insert( const_iterator pos, K&& x );
 (10) (since C++23)

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

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

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

目录

[编辑] 参数

pos - 新元素将插入的位置之前的迭代器
value - 要插入的元素值
first, last - 定义要插入元素的源范围的迭代器对
ilist - 要从中插入值的初始化列表
nh - 兼容的 节点句柄
x - 任何可以与键透明比较的类型的值
类型要求
-
InputIt 必须满足 LegacyInputIterator 的要求。

[编辑] 返回值

1,2) 一个由指向插入元素的迭代器（或阻止插入的元素）和 bool 值组成的对，当且仅当发生插入时，该值设置为 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 为空，则为 End 迭代器；如果发生插入，则为指向插入元素的迭代器；如果插入失败，则为指向具有与 nh.key() 等效键的元素的迭代器。
9) 一个由指向插入元素的迭代器（或阻止插入的元素）和 bool 值组成的对，当且仅当发生插入时，该值设置为 true。
10) 指向插入元素的迭代器，或指向阻止插入的元素的迭代器。

[编辑] 异常

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

[编辑] 复杂度

1,2) 对数复杂度，与容器大小成对数关系，O(log(size()))。
3,4) 如果插入发生在 pos 之后(until C++11)之前(since C++11) 的位置，则为分摊常数时间复杂度；否则为对数复杂度，与容器大小成对数关系。
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 前一个位置
LWG 264 C++98 如果范围 (5) 的复杂度被要求是线性的，则
范围 [first, last) 根据 Compare 排序		 删除了线性要求
在这种特殊情况下
LWG 316 C++98 在重载 (1) 的返回值中，未指定
哪个 bool 值指示插入成功		 成功由
指示 true

[编辑] 参见

(C++11)
 就地构造元素
(public member function) [编辑]
(C++11)
 使用提示就地构造元素
(public member function) [编辑]
 创建从参数推断类型的 std::insert_iterator
(function template) [编辑]
Retrieved from "https://cppreference.cn/mwiki/index.php?title=cpp/container/set/insert&oldid=180855"