[c++高阶]map和set系列相关接口详解

1.前言

在前面我们已经学习了二叉搜索树，以及AVL树，相信对于二叉搜索树已经有了一个很深的理解。如果不懂的，可以先阅读下面两篇文章

[c++高阶]二叉搜索树深度剖析-CSDN博客

[c++高阶]AVL树的深度剖析&模拟实现-CSDN博客

 map和set的底层实现原理是一棵红黑树，红黑树的本质也是一棵二叉搜索树，他与AVL树的区别就在于旋转策略的不同。后续再着重讲解红黑树

本章重点：

着重讲解map和set的相关接口函数以及使用方法

2.前期准备知识

在详细介绍map和set之前，先补充两个概念。

1.map和set是关联式容器，和我们之前学的vector,list,string等序列式容器是不一样的。

区别如下：

序列式容器的底层为线性序列的数据结构，里面存储的是元素本身。

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

2.什么是键值对呢？

① 用来表示具有一 一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。

② 比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该单词，在词典中就可以找到与其对应的中文含义。(即：通过我们建立的对应关系快速的检索🔍数据)

SGI-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)
{}
};

它实际上就是封装了两个可以是不同类型的数,它可以用作中英字典,存储pair<string,string>的结构,first存储中文，second存储对应的英文解释,非常好用!

在map中使用的是pair结构，并且pair中key和value是不同的类型，而在set中其实使用的也是pair结构，但是在set中的key和value类型是同一个类型。

pair的三种常见用法：

1.使用pair结构定义对象，然后插入

map<string,string> dict;
pair<string,string> kv1("排序","sort");
pair<string,string> kv2("左边","left");
dict.insert(kv1);
dict.insert(kv2);

2.使用匿名对象进行插入

map<string,string> dict;
dict.insert(pair<string,string>("排序","sort"));
dict.insert(pair<string,string>("左边","left"));

3.使用make_pair进行插入

map<string,string> dict;
dict.insert(make_pair("排序","sort"));
dict.insert(make_pair("左边","left"));

3.set的结构详解

set是key模型,本质是确定一个元素在不在此容器中,也就是说set中存储的是一个单一数据

set的基本介绍

1. set是按照一定次序存储元素的容器(默认从小到大)；
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。
3. set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
4. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。（通过仿函数来进行）
5. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
6. set在底层是用二叉搜索树(红黑树)实现的。

接口如下：

T是类型，Compare看上去是不是很熟悉，他就是仿函数，Alloc暂时不用管。 

相关接口介绍和使用：

1.set的构造函数:

 2.set的迭代器

 使用代码示例：

#include <iostream>
#include <set>

int main ()
{
  int myints[] = {75,23,65,42,13};
  std::set<int> myset (myints,myints+5);

  std::cout << "myset contains:";
  for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;

  std::cout << '\n';

  return 0;
}

 其他几个接口使用方法和上面begin和end是一样的。

3.set的容量函数

#include <iostream>
#include <set>

int main ()
{
  std::set<int> myset;

  myset.insert(20);
  myset.insert(30);
  myset.insert(10);
  std::cout<<myset.size()<<endl;//3
  std::cout << "myset contains:";
   
  while (!myset.empty())
  {
     std::cout << ' ' << *myset.begin();//10,20,30
     myset.erase(myset.begin());
  }
  std::cout << '\n';

  return 0;
}

4.set的插入、删除、查找函数 

插入：

 使用示例：

#include <iostream>
#include <set>

int main ()
{
  std::set<int> myset;
 

  // set some initial values:
  for (int i=1; i<=5; ++i) myset.insert(i*10);    // set: 10 20 30 40 50

  myset.insert (25);               
  myset.insert (24);               
  myset.insert (26);                 

  int myints[]= {5,10,15};              // 10 already in set, not inserted
  myset.insert (myints,myints+3);

  std::cout << "myset contains:";
  for (it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

 删除:

删除上面已经使用过了，就不过多进行介绍了。 

 查找：

 返回的是找到的那个值所在位置的迭代器

#include <iostream>
#include <set>

int main ()
{
  std::set<int> myset;
  std::set<int>::iterator it;

  // set some initial values:
  for (int i=1; i<=5; i++) myset.insert(i*10);    // set: 10 20 30 40 50

  it=myset.find(20);
  myset.erase (it);
  myset.erase (myset.find(40));

  std::cout << "myset contains:";
  for (it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

5.Set的注意事项

（1）Set的底层使用红黑树来实现的，只不过在使用红黑树时，键值对为(key,key)。
（2）Set最大的功能就是去重

示例如下：

#include <iostream>
#include <set>

int main ()
{
  std::set<int> myset;
  std::set<int>::iterator it;

  // set some initial values:
  for (int i=1; i<=5; i++) myset.insert(i*10);    // set: 10 20 30 40 50

  myset.insert(20);
  std::cout << "myset contains:";
  for (it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';  //10 20 30 40 50

  return 0;
}

4.map的结构详解

介绍map时就不跟介绍set难么详细了，大部分接口都是一样的，这里只给出重要的相关接口且set里面没有介绍过的。

1.结构如下：

解释：

Key :键值中key的类型

T：键值中value的类型

Compare:仿函数比较类型。一般都是按照Key的类型来进行比较的，不显示传递的话就默认使用升序比较。

Alloc:通过空间配置器来申请空间，这里不做过多的解释。有兴趣的可以自行了解。

2.operator[]和at函数

mapped_type其实就是第二个参数类型T，key_type是第一个参数类型Key

 含义如下：

1.如果k在容器中，那么返回的就是第二个类型的引用

2.如果k与容器中任何元素的键不匹配，则该函数用该键插入一个新元素，并返回对其映射值的引用。注意，这总是将容器的大小增加1，即使没有将映射值赋给元素（映射值元素是使用其默认构造函数构造的）。

使用方法如下：

#include <iostream>
#include <map>
#include <string>

int main ()
{
  std::map<char,std::string> mymap;

  mymap['a']="an element";
  mymap['b']="another element";
  mymap['c']=mymap['b'];

  std::cout << "mymap['a'] is " << mymap['a'] << '\n';
  std::cout << "mymap['b'] is " << mymap['b'] << '\n';
  std::cout << "mymap['c'] is " << mymap['c'] << '\n';
  std::cout << "mymap['d'] is " << mymap['d'] << '\n';

  std::cout << "mymap now contains " << mymap.size() << " elements.\n";

  return 0;
}

 结果：

 在这里d这个key是不在容器中的，但是使用了[]进行插入，没有给出他对应的value值，所以就是用了value的默认构造函数，给value进行赋值。

 at函数接口

 含义如下：

返回对以键k标识的元素的映射值的引用。
如果k与容器中任何元素的键不匹配，则该函数抛出out_of_range异常。

 两者的区别就是在没有的时候，一个是插入，另一个是直接抛异常。

使用方法：

#include <iostream>
#include <string>
#include <map>

int main ()
{
  std::map<std::string,int> mymap = {
                { "alpha", 0 },
                { "beta", 0 },
                { "gamma", 0 } };

  mymap.at("alpha") = 10;
  mymap.at("beta") = 20;
  mymap.at("gamma") = 30;
   mymap.at("hello")=0;//抛异常，报错

  for (auto& x: mymap) {
    std::cout << x.first << ": " << x.second << '\n';
  }

  return 0;
}

 Map的方括号设计的十分巧妙,它的传递参数是pair中的first,返回值是pair中的second,并且它返回的是引用,因此我们就可以根据first修改second，它可以用来计数,请看如下demo代码:

统计水果的数量：

string arr[]={"苹果","西瓜","香蕉","苹果","西瓜","西瓜","西瓜","苹果"};
map<string,int> countmap;
for(auto str : arr)
{
	countmap[str]++;
}

3.map的插入，查找，删除函数

插入：

查找：

 删除：

 前面在讲set的时候做了详细的介绍，这里就不过叙述了。

5.mutiset和mutimap

map和set的遍历是有序并且去重的也就是说里面没有相同的元素,但是
STL提供了multimap和multiset它们允许存在相同的元素!

他们也会进行排序，但是他们不会对重复元素进行去重。

Mutimap中由于不进行去重，所以无法支持[]的操作。 

结构如下：

mutiset:

mutimap: 

 有兴趣的可以详细的阅读下面文章来对比他们与set和map的区别和联系

<map> - C++ Reference (cplusplus.com)

<set> - C++ Reference (cplusplus.com)

6.总结与拓展

map和set在实际中用的其实不是很多，但是我们也要熟练的掌握map和set的相关接口，后续用的更多的是Unordered_map和Unordered_set。后续会进行详细的介绍。但是map和set既然存在，存在的话一定是有对应的使用的场景的，因此还是很有必要学习的。

                                             坚持学下来，明天一定会更好的。