【C++】map和set的使用（上）

👉关联式容器👈

我们已经接触过 STL 中的部分容器，比如：vector、list、deque、forward_list(C++11) 等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面

存储的是元素本身。序列式容器中存储的数据通常没有什么关系。那什么是关联式容器呢？

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是 <key, value> 结构的键值对，在数据检索时比序列式容器效率更高。

👉键值对👈

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和 value，key代表键值，value 表示与 key 对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

SCI - STL 中关于键值对的定义

template <class T1, class T2>
struct pair
{
  typedef T1 first_type;
  typedef T2 second_type;
  T1 first;
  T2 second;
  pair() : first(T1()), second(T2())
  {}
  pair(const T1& a, const T2& b) : first(a), second(b)
  {}
};

👉树形结构的关联式容器👈

根据应用场景的不同，STL 总共实现了两种不同结构的关联式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树（即红黑树）作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器。

set

1. set 的介绍

1. set 是按照一定次序存储元素的容器。
2. 在 set 中，元素的 value 也标识它(value 就是 key，类型为 T)，并且每个 value 必须是唯一的。 set 中的元素不能在容器中修改(元素总是 const)，但是可以从容器中插入或删除它们。

在内部，set 中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。

set 容器通过 key 访问单个元素的速度通常比unordered_set 容器慢，但它们允许根据顺序对子集进行直接迭代。

set 在底层是用二叉搜索树(红黑树)实现的。

注意：

与 map / multimap 不同，map / multimap 中存储的是真正的键值对 <key, value>，set 中只 value，但在底层实际存放的是由 <value, value> 构成的键值对。

set 中插入元素时，只需要插入 value 即可，不需要构造键值对。

set 中的元素不可以重复（因此可以使用 set 进行去重）。

使用 set 的迭代器遍历 set 中的元素，可以得到有序序列。

set 中的元素默认按照小于来比较。

set 中查找某个元素，时间复杂度为 l o g 2 N

2. set 的使用

1. set 的模板参数列表
2. 
3. T：set 中存放元素的类型，实际在底层存储 <value, value> 的键值对。

Compare：set 中元素默认按照小于来比较，即中序遍历的结果是升序（注：Compare 可以自己写一个仿函数来控制比较的方式）。

Alloc：set 中元素空间的管理方式，使用 STL 提供的空间配置器管理。

2. set 的构造和赋值运算符重载

注：set 的拷贝构造和赋值运算符重载，代价是比较大的！

3. set 的修改操作
4. 
   

注：set 中的元素不允许修改，因为修改元素可能会破坏二叉搜索树的结构。

4. set 的使用举例

void SetTest1()
{
  // 排序+去重
  set<int> s = { 1, 2,1,6,3, 8,5,9 }; // C++11的列表初始化
  set<int>::iterator it = s.begin();
  while (it != s.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
}

void SetTest2()
{
  // greater的该文件是functional
  set<int, greater<int>> s = { 1, 2,1,6,3, 8,5,9 }; // C++11的列表初始化
  set<int>::iterator it = s.begin();
  while (it != s.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
}

void SetTest3()
{
  int arr[] = { 1,2,1,6,3,8,5,9 };
  // 迭代器区间初始化
  set<int, greater<int>> s(arr, arr + sizeof(arr) / sizeof(arr[0]));  
  for (auto e : s)
  {
    cout << e << " ";
  }
  cout << endl;
  s.erase(3);
  for (auto e : s)
  {
    cout << e << " ";
  }
  cout << endl;
  auto it = s.find(2);
  if (it != s.end())
  {
    s.erase(it);
    for (auto e : s)
    {
      cout << e << " ";
    }
    cout << endl;
  }
}

注：find 函数如果没有找到指定的 key 值，会返回 end()；如果找到了，会返回该 key 值的迭代器位置。所以如果要通过迭代器位置来删除元素，需要判断该迭代器位置是否为 end()。而通过 key 值来删除的话，容器中没有指定 key 值的话，就返回 0；如果有的话，就返回 1。（注：这里的 0 和 1 是 key 值在容器 set 中的个数）

void SetTest4()
{
  set<int> myset;
  set<int>::iterator itlow, itup;
  for (int i = 1; i < 10; i++) 
    myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
  itlow = myset.lower_bound(30);  // 返回大于等于val的第一个元素的迭代器位置     
  itup = myset.upper_bound(60);   // 返回大于val的第一个元素的迭代器位置
  myset.erase(itlow, itup);                     // 10 20 70 80 90
  std::cout << "myset contains:";
  for (auto it = myset.begin(); it != myset.end(); ++it)
    std::cout << ' ' << *it;
  cout << endl;
}

void SetTest5()
{
  std::set<int> myset;
  for (int i = 1; i <= 5; i++) myset.insert(i * 10);   // myset: 10 20 30 40 50
  std::pair<std::set<int>::const_iterator, std::set<int>::const_iterator> ret;
  // equal_range的返回值是键值对pair<iterator,iterator>
  ret = myset.equal_range(30);  // x <= val < y
  std::cout << "the lower bound points to: " << *ret.first << '\n';
  std::cout << "the upper bound points to: " << *ret.second << '\n';
}

multiset

1. multiset 的介绍

multiset 是按照特定顺序存储元素的容器，其中元素是可以重复的。

在 multiset 中，元素的 value 也会识别它（因为multiset 中本身存储的就是 <value, value> 组成的键值对，因此 value 本身就是 key，key 就是 value，类型为 T）。multiset 元素的值不能在容器中进行修改（因为元素总是 const 的），但可以从容器中插入或删除。

在内部，multiset 中的元素总是按照其内部比较规则（类型比较）所指示的特定严格弱排序准则进行排序。

multiset 容器通过 key 访问单个元素的速度通常比unordered_multiset 容器慢，但当使用迭 代器遍历时会得到一个有序序列。

multiset 的底层结构为二叉搜索树（红黑树）。

注意：

multiset 中在底层中存储的是 <value, value> 的键值对。

mtltiset的插入接口中只需要插入即可。

与 set 的区别是 multiset 中的元素可以重复，set 是中value 是唯一的。

使用迭代器对 multiset 中的元素进行遍历，可以得到有序的序列。

multiset 中的元素不能修改。

在 multiset 中找某个元素，时间复杂度为O ( l o g 2 N ) O(log_2 N)O(log

2

N)。

multiset 的作用是可以对元素进行排序。

2. multiset 的使用

void MultisetTest1()
{
  int arr[] = { 1, 2,1,8,5,7,6,2,9 };
  multiset<int> s(arr, arr + sizeof(arr) / sizeof(arr[0]));
  for (auto e : s)
  {
    cout << e << " ";
  }
  cout << endl;
  cout << s.count(1) << endl;
  auto pos = s.find(2);
  while (pos != s.end())
  {
    cout << *pos << " ";
    ++pos;
  }
  cout << endl;
  s.erase(2);
  for (auto e : s)
  {
    cout << e << " ";
  }
  cout << endl;
}

注：find 返回的是中序遍历中第一个 key 值的迭代器位置，通过 key 值来调用 erase 函数是会删除所有的 key 值的。

map

1. map 的介绍

map 是关联容器，它按照特定的次序（按照 key 来比较）存储由键值 key 和值 value 组合而成的元素。

在 map 中，键值 key 通常用于排序和唯一地标识元素，而值 value 中存储与此键值 key 关联的内容。键值 key 和值 value 的类型可能不同。在 map 的内部，key 与value 通过成员类型 value_type 绑定在一起，为其取别名称为 pair：typedef pair<const key, T> value_type;

在内部，map 中的元素总是按照键值 key 进行比较排序的。

map 中通过键值访问单个元素的速度通常比unordered_map 容器慢，但 map 允许根据顺序对元素进行直接迭代（即对 map 中的元素进行迭代时，可以得到一个有序的序列)。

map 支持下标访问符，即在[]中放入key，就可以找到与 key 对应的 value。

map 通常被实现为二叉搜索树(更准确地说，是平衡二叉搜索树(红黑树))。

2. map 的使用

1. map 的模板参数说明
2. 
3. key：键值对中 key 的类型

T：键值对中 value 的类型

Compare：比较器的类型，map 中的元素是按照 key 来比较的，缺省情况下按照小于来比较。一般情况下，该参数（内置类型）不需要传递，如果无法比较时（自定义类型），需要用户自己显式传递比较规则（一般情况下按照函数指针或者仿函数来传递）。

Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器。

注意：在使用 map 时，需要包含头文件。

map 的修改操作和 set 的修改操作基本是相同的，就是 map 比 set 多了一个 value 值。

注：make_pair 是一个函数模板，其通常被定义成内联函数，其头文件是 utility，通过会被间接包含。