RobbEr's Blog

Welcome

STL-map

发表于 更新于 分类于 ， 阅读次数： Valine：
本文字数： 2.6k 阅读时长 ≈ 2 分钟

简介

map 直译为图，为有序键值对 （key - value）容器，它提供一对一的数据处理能力（key不能重复，对应的value可以重复），可以修改 value 值，而不能修改 key 值

map 内部自建一颗红黑树，具有自动排序的能力，

map为关联式容器，其底层为红黑树（RB-Tree）

类模板

1
2
3
4
5
6
7
template<
    class Key,                      //key的数据类型
    class T,                        //value的数据类型
    class Compare = std::less<Key>, //依据key的排序方法
    //分配器
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

成员函数

由于 map 以 RB-Tree 为底层，又由于 map 开放的所有操作接口，RB-Tree 也都提供了，所以所有的 map 操作行为，都只是转调用 RB-Tree 的操作行为而已

迭代器

  1. begin() - 返回指向 map 个元素的迭代器
  2. end() - 返回指向 map 中最后一个元素之后的理论元素的迭代器
  3. rbegin() - 返回指向 map 中最后一个元素的反向迭代器（反向开始）
  4. rend() – 返回一个反向迭代器，指向 map 中第一个元素之前的理论元素
  5. cbegin() - 返回指向 map 中第一个元素的const迭代器
  6. cend() - 返回一个const迭代器，指向 map 中最后一个元素之后的理论元素
  7. crbegin() – 返回指向 map 中最后一个元素的const反向迭代器（反向开始）
  8. crend() - 返回指向 map 中第一个元素之前的理论元素的const反向迭代器

容量相关

  1. size() - 返回 map 中元素数 O(1)
  2. max_size() - 返回 map 可以容纳的最大元素数 O(1)
  3. empty() - 当前 map 是否为空 O(1)

元素访问相关

  1. [g] - 返回对 map 位置 g 处的引用 O(log2(n))
  2. at(g) - 返回对 map 位置 g 处的引用，同时进行越界检查 1. [g] - 返回对 map 位置 g 处的引用 O(log2(n))

修改器相关

  1. clear() - 清空所有元素，size()置 0
  2. insert() - 插入一个或多个元素到指定位置 O(log2(n))
  3. erase() - 删除指定位置元素 O(log2(n))
  4. swap() - 交换元素
  5. emplace() - 插入一个元素到指定位置，调用构造函数 (C++11)
  6. emplace_hint() - 插入新元素到容器中尽可能接近于恰在 hint 前的位置，调用构造函数 (C++11)
  7. extract() - 从另一容器释出结点 (C++17)
  8. merge() - 从另一容器接合结点 (C++17)
  9. insert_or_assign() - 插入元素，或若键已存在则赋值给当前元素 (C++17)
  10. try_emplace() - 若键不存在则原位插入，若键存在则不做任何事 (C++17)

元素查找相关

  1. count() - 返回匹配特定键的元素数量 O(1)
  2. find() - 寻找带有特定键的元素
  3. equal_range() - 返回匹配特定键的元素范围
  4. lower_bound() - 返回指向首个不小于给定键的元素的迭代器
  5. upper_bound() - 返回指向首个大于给定键的元素的迭代器
  6. contains() - 检查容器是否含有带特定键的元素 (C++20)

map迭代器详解

map的所有迭代器都是双向迭代器

const迭代器

map 所返回的迭代器都是 const 迭代器，类型为 pair ,只能对其操作，可以更改其指向的 value 值，但不能修改 key 值即：

1
2
3
4
5
6
7
map<int, int> v;
v.insert(make_pair(1, 2));
auto i = v.begin();
int f = i->first;	//f = 1
int s = i->second;	//s = 2
i->first = 2;		//error!
i->second = 3;		//ok

map的一些特性

1. try_emplace

不同于 insert 和 implace ，若不发生插入，则这些函数不从右值参数移动

简而言之，当执行try_emplace(Key， Val)，且容器中已经含有等价的Key时，函数并不进行参数构造，而如果是执行emplace(Key， Val)，那么无论何种情况总是会调用std::pair的构造函数，这导致程序产生了大量的垃圾数据，并浪费了很多时间

详细可查看此处

2. operator[]与insert()

先说结论，推荐使用operator[]。再来分析

从目前 map 源码（msvc10.0.19041.0）中，两个函数分别如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// operator[]
mapped_type& operator[](const key_type& _Keyval) {
    return _Try_emplace(_Keyval).first->_Myval.second;
}
mapped_type& operator[](key_type&& _Keyval) { // find element matching _Keyval or insert value-initialized value
    return _Try_emplace(_STD move(_Keyval)).first->_Myval.second;
}

// insert 过多，只挑选两个

iterator insert(const value_type& _Val) {
    return iterator(_Emplace(_Val).first, _Get_scary());
}
pair<iterator, bool> insert(value_type&& _Val) {
    const auto _Result = _Emplace(_STD move(_Val));
    return {iterator(_Result.first, _Get_scary()), _Result.second};
}
...

当访问元素时，使用operator[]是肯定的；

而当插入时，对比一下使用的函数，operator[]使用的为try_emplace，当元素存在时，不用调用构造函数进行构造再销毁，又回到了上一个问题。