命名空间
变体
操作

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

来自 cppreference.cn
< cpp‎ | 容器‎ | 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) 将 value 插入到尽可能接近 pos 紧前位置处。
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 移动；否则，它保留对元素的拥有权。该元素插入到尽可能接近 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) 就地构造到 set 中。此重载仅当限定 ID 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) 就地构造到 set 中。此重载仅当以下条件成立时才参与重载决议：这些条件共同允许在不构造 Key 实例的情况下调用此函数。

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

目录

[编辑] 参数

pos - 指向新元素将插入位置之前的迭代器
value - 要插入的元素值
first, last - 定义要插入的元素源范围的迭代器对
ilist - 要从中插入值的初始化列表
nh - 兼容的节点句柄
x - 可与键透明比较的任何类型的值
类型要求
-
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-8, 9, 10

[编辑] 复杂度

1,2) 对容器大小呈对数，O(log(size()))。
3,4) 如果插入发生在 pos 紧后(C++11 前)前(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) 通常实现为一个循环，该循环使用 end() 作为提示调用重载 (3)；它们针对追加已排序序列（例如另一个 std::set），其最小元素大于 *this 中的最后一个元素进行了优化。

特性测试宏 值 标准 特性
__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++ 标准。

缺陷报告 应用于 发布时的行为 正确的行为
LWG 233 C++98 pos 只是一个提示，它可能被完全忽略 插入要求
尽可能接近
pos 紧前位置
LWG 264 C++98 如果范围 [first, last) 根据 Compare 排序，则重载 (5) 的复杂度要求为线性
范围 [first, last) 根据 Compare 排序		 在此特殊情况下
取消线性要求
LWG 316 C++98 在重载 (1) 的返回值中，未指定
哪个布尔值表示成功插入		 成功由
true 表示

[编辑] 另请参阅

(C++11)
 就地构造元素
(公共成员函数) [编辑]
(C++11)
 使用提示就地构造元素
(公共成员函数) [编辑]
 创建从参数推断类型的std::insert_iterator
(函数模板) [编辑]
取自“https://cppreference.cn/mwiki/index.php?title=cpp/container/set/insert&oldid=180855”