map系列

• 1.map
• • 原理：
  • 常用接口：
• 2.unordered_map
• • 原理：
  • 常用接口：
• 3.multimap
• • 原理：
  • 常用接口：

1.map

原理：

map內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能。
map内部实现了一个红黑树，该结构具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素，因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作，故红黑树的效率决定了map的效率。

常用接口：

1.插入元素：

map<int, string> mapStudent;
 
// 第一种 用insert函數插入pair
mapStudent.insert(pair<int, string>(000, "student_zero"));

// 第二种 用insert函数插入value_type数据
mapStudent.insert(map<int, string>::value_type(001, "student_one"));
 
// 第三种 用"array"方式插入
mapStudent[123] = "student_first";

• 使用insert时，当map中有这个关键字时，insert操作是不能在插入数据的。

2. 查找元素

当所查找的关键key出现时，它返回数据所在对象的位置，如果沒有，返回iter与end函数的值相同。

// find 返回迭代器指向当前查找元素的位置否则返回map::end()位置
iter = mapStudent.find("123");

3. 刪除与清空元素

//迭代器刪除
iter = mapStudent.find("123");
mapStudent.erase(iter);

4…

• begin() 返回指向map头部的迭代器

  clear(） 删除所有元素

  count() 返回指定元素出现的次数, (帮助评论区理解： 因为key值不会重复，所以只能是1 or 0)

  empty() 如果map为空则返回true

  end() 返回指向map末尾的迭代器

  equal_range() 返回特殊条目的迭代器对

  erase() 删除一个元素

  find() 查找一个元素

  get_allocator() 返回map的配置器

  insert() 插入元素

  key_comp() 返回比较元素key的函数

  lower_bound() 返回键值>=给定元素的第一个位置

  max_size() 返回可以容纳的最大元素个数

  rbegin() 返回一个指向map尾部的逆向迭代器

  rend() 返回一个指向map头部的逆向迭代器

  size() 返回map中元素的个数

  swap() 交换两个map

  upper_bound() 返回键值>给定元素的第一个位置

  value_comp() 返回比较元素value的函数

2.unordered_map

原理：

unordered_map: unordered_map内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的
常用函数：

常用接口：

• =迭代器=========
  begin 　　返回指向容器起始位置的迭代器（iterator）
  end 　　 返回指向容器末尾位置的迭代器
  cbegin　 返回指向容器起始位置的常迭代器（const_iterator）
  cend 　　 返回指向容器末尾位置的常迭代器
  =Capacity
  size 　　 返回有效元素个数
  max_size 返回 unordered_map 支持的最大元素个数
  empty 判断是否为空
  =元素访问=
  operator[] 　　 访问元素
  at 　　 　　　　访问元素
  =元素修改=
  insert 　　插入元素
  erase　　 删除元素
  swap 　　 交换内容
  clear　　 清空内容
  emplace 　构造及插入一个元素
  emplace_hint 按提示构造及插入一个元素
  操作=========
  find 　　　　　　通过给定主键查找元素,没找到：返回unordered_map::end
  count 　　　　　返回匹配给定主键的元素的个数
  equal_range 　　返回值匹配给定搜索值的元素组成的范围
  Buckets======
  bucket_count 　　　返回槽（Bucket）数
  max_bucket_count 返回最大槽数
  bucket_size 　　　 返回槽大小
  bucket 　　　　　　返回元素所在槽的序号
  load_factor　　　　 返回载入因子，即一个元素槽（Bucket）的最大元素数
  max_load_factor 　 返回或设置最大载入因子
  rehash　　　　　　 设置槽数
  reserve 　　　　　 请求改变容器容量

3.multimap

原理：

multimap容器保存的是有序的键/值对，但是可以保存重复的元素。multimap中会出现具有相同键值的元素序列。multimap大部分成员函数的使用方式和map相同。因为重复键的原因，multimap有一些函数的使用方式和map有一些区别。

常用接口：

1.find()
multimap 的成员函数 find() 可以返回一个键和参数匹配的元素的迭代器。
2.equal_range()
如果我们想访问给定键对应的所有元素。成员函数 equal_range() 就可以做到这一点。它会返回一个封装了两个迭代器的 pair 对象，这两个迭代器所确定范围内的元素的键和参数值相等。

auto pr = people.equal_range("Ann");
if(pr.first != std::end(people))
{
    for (auto iter = pr.first ; iter != pr.second; ++iter)
        std:cout << iter->first << " is " << iter->second << std::endl;
}

3. lower_bound()和 upper_bound()
   multimap 的成员函数 lower_bound() 会返回一个迭代器，它指向键值相等或大于参数的第一个元素，或者指向结束迭代器。upper_bound() 也返回一个迭代器，它指向键值大于函数参数的第一个元素，如果这样的元素不出现的话，它就是一个结束迭代器。所以，当存在一个或多个相等键时，这些函数会返回一个开始迭代器和一个结束迭代器，它们指定了和参数匹配的元素的范围，这和 equal_range() 返回的迭代器是相同的。

auto iter1 = people.lower_bound("Ann");
auto iter2 = people.lower_bound("Ann");
if(iter1 != std::end(people))
{
    for(auto iter = iterl ; iter != iter2; ++iter)
        std::cout << iter->first << " is " << iter->second << std::endl;
}

4.count()
通过调用 multimap 的成员函数 count() 可以知道有多少个元素的键和给定的键相同。

5.erase()
multimap 的成员函数 erase() 有 3 个版本：

• 以待删除兀素的迭代器作为参数，这个函数没有返回值；
• 以一个键作为参数，它会删除容器中所有含这个键的元素，返回容器中被移除元素的个数；
• 接受两个迭代器参数，它们指定了容器中的一段元素，这个范围内的所有元素都会被删除，这个函数返回的迭代器指向最后一个被删除元素的后一个位置。