Namespaces
Variants

std::map<Key,T,Compare,Allocator>:: insert

From cppreference.net
std:: pair < iterator, bool > insert ( const value_type & value ) ;
(1)
template < class P >
std:: pair < iterator, bool > insert ( P && value ) ;
(2) (自 C++11 起)
std:: pair < iterator, bool > insert ( value_type && value ) ;
(3) (自 C++17 起)
(4)
iterator insert ( iterator pos, const value_type & value ) ;
(C++11 前)
iterator insert ( const_iterator pos, const value_type & value ) ;
(自 C++11 起)
template < class P >
iterator insert ( const_iterator pos, P && value ) ;
(5) (自 C++11 起)
iterator insert ( const_iterator pos, value_type && value ) ;
(6) (自 C++17 起)
template < class InputIt >
void insert ( InputIt first, InputIt last ) ;
(7)
void insert ( std:: initializer_list < value_type > ilist ) ;
(8) (自 C++11 起)
insert_return_type insert ( node_type && nh ) ;
(9) (自 C++17 起)
iterator insert ( const_iterator pos, node_type && nh ) ;
(10) (自 C++17 起)

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

1-3) 插入 value
重载 (2) 等价于 emplace ( std:: forward < P > ( value ) ) ,且仅当 std:: is_constructible < value_type, P && > :: value == true 时参与重载决议。
4-6) value 插入到尽可能接近 pos 之前位置的位置。
重载 (5) 等价于 emplace_hint ( pos, std:: forward < P > ( value ) ) ,且仅当 std:: is_constructible < value_type, P && > :: value == true 时参与重载决议。
7) 插入范围 [ first , last ) 中的元素。若范围中存在多个键值比较等效的元素,则插入哪个元素是未指定的(待解决 LWG2844 )。
8) 从初始化列表 ilist 插入元素。如果范围内多个元素的键比较等价,则未指定具体插入哪个元素(待解决 LWG2844 )。
9) nh 为空 节点句柄 ,则无操作。否则,若容器中尚未包含与 nh. key ( ) 等效键的元素,则将 nh 所拥有的元素插入容器。若 nh 非空且 get_allocator ( ) ! = nh. get_allocator ( ) ,则行为未定义。
10) nh 为空 节点句柄 ,则不执行任何操作并返回结束迭代器。否则,若容器中尚未包含与 nh. key ( ) 等价的键对应的元素,则将 nh 所拥有的元素插入容器,并返回指向具有等价于 nh. key ( ) 键的元素的迭代器(无论插入成功与否)。若插入成功,则 nh 被移走;否则其仍保留元素的所有权。该元素会尽可能插入到紧邻 pos 之前的位置。若 nh 非空且 get_allocator ( ) ! = nh. get_allocator ( ) ,则行为未定义。

不会使任何迭代器或引用失效。 若插入成功,则通过节点句柄持有的元素所获取的指针和引用会失效,而该元素被提取之前所获取的指针和引用将变为有效。 (C++17 起)

目录

参数

pos - 指向新元素将插入位置之前的迭代器
value - 要插入的元素值
first, last - 定义要插入元素范围的迭代器对
ilist - 要从中插入值的初始化列表
nh - 兼容的节点句柄
类型要求
-
InputIt 必须满足 LegacyInputIterator 的要求。

返回值

1-3) 返回一个由迭代器和布尔值组成的对:迭代器指向被插入元素(或阻止插入的元素),布尔值当且仅当插入成功时被设为 true
4-6) 指向被插入元素的迭代器,或指向阻止插入的元素的迭代器。
7,8) (无)
9) 一个 insert_return_type 类型的对象,其成员按以下方式初始化:
  • 如果 nh 为空,则 inserted false position end ( ) ,且 node 为空。
  • 否则如果插入成功,则 inserted true position 指向被插入的元素,且 node 为空。
  • 如果插入失败,则 inserted false node 保留 nh 先前的值,且 position 指向一个键与 nh. key ( ) 等效的元素。
10) nh 为空则为尾迭代器,若插入发生则指向被插入元素的迭代器,若插入失败则指向具有与 nh. key ( ) 等价键的元素。

异常

1-6) 若任何操作抛出异常,则插入操作无效。

复杂度

1-3) 与容器大小成对数关系, O(log(size()))
4-6) 若插入发生在 after (until C++11) before (since C++11) pos 位置则为均摊常数复杂度,否则与容器大小成对数关系。
7,8) O(N·log(size() + N)) ,其中 N 为待插入元素的数量。
9) 与容器大小成对数关系, O(log(size()))
10) 若插入发生在 pos 正前方 位置,则摊还常数时间复杂度;否则与容器大小成对数关系。

注释

提示插入 ( ( 4-6 ) ( 10 ) ) 不返回布尔值,这是为了与顺序容器(如 std::vector::insert )的位置插入操作保持签名兼容。这使得创建通用插入器(如 std::inserter )成为可能。检查提示插入是否成功的一种方法是比较插入前后的 size() 值。

示例

#include <iomanip>
#include <iostream>
#include <map>
#include <string>
using namespace std::literals;
template<typename It>
void print_insertion_status(It it, bool success)
{
    std::cout << "插入 " << it->first
              << (success ? " 成功\n" : " 失败\n");
}
int main()
{
    std::map<std::string, float> heights;
    // 重载 3:从右值引用插入
    const auto [it_hinata, success] = heights.insert({"Hinata"s, 162.8});
    print_insertion_status(it_hinata, success);
    {
        // 重载 1:从左值引用插入
        const auto [it, success2] = heights.insert(*it_hinata);
        print_insertion_status(it, success2);
    }
    {
        // 重载 2:通过转发到 emplace 插入
        const auto [it, success] = heights.insert(std::pair{"Kageyama", 180.6});
        print_insertion_status(it, success);
    }
    {
        // 重载 6:从右值引用插入(带位置提示)
        const std::size_t n = std::size(heights);
        const auto it = heights.insert(it_hinata, {"Azumane"s, 184.7});
        print_insertion_status(it, std::size(heights) != n);
    }
    {
        // 重载 4:从左值引用插入(带位置提示)
        const std::size_t n = std::size(heights);
        const auto it = heights.insert(it_hinata, *it_hinata);
        print_insertion_status(it, std::size(heights) != n);
    }
    {
        // 重载 5:通过转发到 emplace 插入(带位置提示)
        const std::size_t n = std::size(heights);
        const auto it = heights.insert(it_hinata, std::pair{"Tsukishima", 188.3});
        print_insertion_status(it, std::size(heights) != n);
    }
    auto node_hinata = heights.extract(it_hinata);
    std::map<std::string, float> heights2;
    // 重载 7:从迭代器范围插入
    heights2.insert(std::begin(heights), std::end(heights));
    // 重载 8:从初始化列表插入
    heights2.insert({{"Kozume"s, 169.2}, {"Kuroo", 187.7}});
    // 重载 9:插入节点
    const auto status = heights2.insert(std::move(node_hinata));
    print_insertion_status(status.position, status.inserted);
    node_hinata = heights2.extract(status.position);
    {
        // 重载 10:插入节点(带位置提示)
        const std::size_t n = std::size(heights2);
        const auto it = heights2.insert(std::begin(heights2), std::move(node_hinata));
        print_insertion_status(it, std::size(heights2) != n);
    }
    // 打印最终映射
    std::cout << std::left << '\n';
    for (const auto& [name, height] : heights2)
        std::cout << <a

缺陷报告

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

缺陷报告 适用标准 发布行为 正确行为
LWG 233 C++98 pos 仅作为提示,可能被完全忽略 要求插入位置尽可能接近
pos 之前的位置
LWG 264 C++98 重载 ( 7 ) 在区间 [ first , last )
Compare 排序时要求线性复杂度
移除此特殊场景下的
线性复杂度要求
LWG 316 C++98 未明确重载 ( 1 ) 返回值中
哪个 bool 值表示插入成功
成功由
true 表示
LWG 2005 C++11 重载 ( 2 ) ( 5 ) 的描述不清晰 改进了描述

参见

(C++11)
原地构造元素
(公开成员函数)
使用提示原地构造元素
(公开成员函数)
插入元素,若键已存在则赋值给当前元素
(公开成员函数)
创建从参数推断类型的 std::insert_iterator
(函数模板)