目录

1 map的介绍

1.1 模板参数

2 pair介绍

3 map的使用

2.1 map的定义

2.2 map的迭代器

2.3 map的空间增长

2.4 map的增删

2.4.1 insert

2.4.2 erase

2.5 map的查找

2.6 map的访问

2.6.1 insert的返回值

2.6.2 原理

2.6.3 功能

4 其他map

---

1 map的介绍

---

#include <map>

• 类模板原型

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

1.1 模板参数

• Key

键所对应的类型

• T

值所对应的类型

• Compare（缺省参数）

比较函数（伪函数/函数对象）。仿函数本质就是一个类重载的 operator（）运算符。库里面默认给的仿函数是less。

less是库里面的一个仿函数，表示类型大的优先级大，按照键的大小进行升序排序

greater是库里面的一个仿函数，表示类型小的优先级大，按照键的大小进行降序排序

• Alloc

set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第三个参数

STL库中的less实现：

template <class T> 
struct less 
{
  bool operator() (const T& x, const T& y) const 
  {
      return x < y;
  }
  typedef T first_argument_type;
  typedef T second_argument_type;
  typedef bool result_type;
};

STL库中的greater实现：

template <class T> 
struct greater 
{
  bool operator() (const T& x, const T& y) const 
  {
      return x > y;
  }
  typedef T first_argument_type;
  typedef T second_argument_type;
  typedef bool result_type;
};

2 pair介绍

---

template <class T1, class T2> struct pair;

可以理解为pair的诞生就是为了服务map，作为map的键值对使用

3 map的使用

---

2.1 map的定义

• 无参构造

//声明
explicit map (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());

//无参构造
map<int, int> m;

• 迭代器区间构造

//声明
template <class InputIterator>
map (InputIterator first, InputIterator last,
     const key_compare& comp = key_compare(),
     const allocator_type& = allocator_type());
      
vector<int> v={1,2,3,4,5,6,7,8,9};
//迭代器区间构造
map<int, int> s(v.begin(), v.end());

• 拷贝构造

//声明
map (const map& x);

map<int, int> m1;
//拷贝构造
map<int, int> m2(m1);

• 使用大括号初始化构造

//声明
map (initializer_list<value_type> il,
     const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type());

//这里的 {} 会进行隐式类型转换为 pair<int, int>
map<int, int> m{{1,2}, {2,3}, {3,4}, {4,5}, {5,6}}; //数组s中有五个元素，容器的长度就为5。

map使用大括号初始化的原理就是，先将其转化为initializer_list容器，然后调用相应的构造函数进行初始化

2.2 map的迭代器

迭代器的主要作用就是让算法能够不用关心底层数据结构。与vector不同的是list的迭代器不单纯是一个指针而是对一个节点的封装，封装的好处就在于可以对其进行运算符重载

map的迭代器为一个双向迭代器，因此map的迭代器可以支持对一个迭代器进行++或者--操作

接口	时间复杂度	接口说明
begin()	O（1）	获取第一个数据位置的iterator/const_iterator
end()	O（1）	获取最后一个数据的下一个位置的iterator/const_iterator
rbegin()	O（1）	获取最后一个数据位置的reverse_iterator
rend()	O（1）	获取第一个数据前一个位置的reverse_iterator

注意： end() 返回的是最后一个元素的后一个位置的地址，不是最后一个元素的地址，所有STL容器均是如此

map<int, int> m{ {1,2}, {2,3}, {3,4}, {4,5}, {5,6} };
//按照键的大小进行升序输出
for (auto it =m.begin(); it != m.end(); it++)
{
    cout << it->first << " " << it->second << endl;
}
//按照键的大小进行降序输出
for (auto it = m.rbegin(); it != m.rend(); it++)
{
    cout << it->first << " " << it->second << endl;
}

2.3 map的空间增长

接口	时间复杂度	接口说明
size()	O（1）	获取数据个数
empty()	O（1）	判断是否为空

2.4 map的增删

接口	时间复杂度	接口说明
insert()	O（ logN ）	插入数据
erase()	O（ logN ）	删除数据
clear()	O（ N ）	删除容器中所有数据
swap()	O（ 1 ）	交换两个容器的数据

map插入接⼝，插⼊的pair键值对数据，跟set所有不同，但是查和删的接⼝只⽤关键字key跟set是完全类似的，不过find返回iterator，不仅仅可以确认key在不在，还找到key映射的value，同时通过迭代还可以修改value

2.4.1 insert

• 添加元素的方式

int main()
{
    map<int, int> m;
    
    //创建对象+插入
    pair<int, int> e(1, 1);
    m.insert(e);
    //匿名对象插入
    m.insert(pair<int, int>(1, 1));
    //插入元素构造键值对
    m.insert(make_pair(1, 1));
    
    //operator [ ] 插入
    m[1] = 1;
    //隐式类型转换插入——常用
    m.insert({ 1,1 });
    return 0;
}

map容器中存储的是pair键值对，在容器内部对pair进行了类型重定义为 value_type。这个与其他容器不一样

• 单个数据插入

//声明
pair<iterator,bool> insert (const value_type& val);

// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
map<int, int> s;
s.insert({1, 1});

• 列表插入

//声明
void insert (initializer_list<value_type> il);

// 列表插⼊，已经在容器中存在的值不会插⼊
map<int, int> m;
s.insert({{1,2}, {2,3}, {3,4}, {4,5}, {5,6}});

• 迭代器区间插入

//声明
template <class InputIterator>
void insert (InputIterator first, InputIterator last);

vector<int> v={1,2,3,4,5,6,7,8,9};
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
map<int, int> m;
s.insert(v.begin(), v.end());

2.4.2 erase

• 删除一个迭代器位置值

//声明
iterator erase (const_iterator position);

// 删除⼀个迭代器位置的值
map<int, int> m{{1,2}, {2,3}, {3,4}, {4,5}, {5,6}};
auto it = s.find(1);
s.erase(it);

• 删除一个指定的值

//声明
size_type erase (const value_type& val);

// 删除val，val不存在返回0，存在返回1
map<int, int> m{{1,2}, {2,3}, {3,4}, {4,5}, {5,6}};
s.erase(1);

• 删除一段迭代器区间的值

//声明
iterator erase (const_iterator first, const_iterator last);

// 删除⼀段迭代器区间的值
map<int, int> m{{1,2}, {2,3}, {3,4}, {4,5}, {5,6}}; 
s.erase(s.begin(), s.end());

2.5 map的查找

//声明
//mapped_type对应的是第二个模板参数 (T)
mapped_type& operator[] (const key_type& k);

接口	时间复杂度	接口说明
find()	O（ logN ）	返回键为key的映射的迭代器
count()	O（ logN ）	查看元素是否存在，因为map中键是唯一的，所以存在返回1，不存在返回0
lower_bound()	O（ logN ）	返回一个迭代器，指向键值>= key的第一个元素
upper_bound()	O（ logN ）	返回一个迭代器，指向键值> key的第一个元素

2.6 map的访问

接口	时间复杂度	接口说明
operator [ ]	O（ logN ）	返回key所对应的value的引用

//声明
//mapped_type对应的是第二个模板参数 (T)
mapped_type& operator[] (const key_type& k);

2.6.1 insert的返回值

//声明
pair<iterator,bool> insert (const value_type& val);

2.6.2 原理

2.6.3 功能

int main()
{
    map<int, int> m;
    //插入
    m[1];
    
    //插入+修改
    m[2] = 2;
    
    //修改
    m[1] = 100;
    
    //查找key所对应的值
    cout << m[1] << endl;//100
    return 0;
}

4 其他map

---

multimap	元素可以重复，且元素有序
unordered_map	元素无序且只能出现一次
unordered_multimap	元素无序可以出现多次

以上容器与map容器的使用基本完全类似