【C++】关联式容器——map&set的使用（上）

1.关联式容器和键值对

1. 关联式容器

在之前的学习中，我们学习了vector，list，deque等容器，这些容器被统称为序列式容器，因为其底层是线性的数据结构，内部存放的是元素本身，那么关联式容器是什么呢？关联式容器也是用来存放数据的，只是关联式容器中存放数据是以<key,value>键值对的方式存储的，在数据检索的时候效率更高。

其实也可以理解成使用了更高级的数据结构，除了单纯的存储数据外，加上了一些特殊的存储逻辑。比如map和set就使用了二叉搜索树这种高级的数据结构。

STL中一共实现了两种不同类型的关联式容器：树形结构和哈希结构。

其中树形结构的容器有：map、multimap、set、multiset四个。其底层都是使用了**平衡搜索树（红黑树）**实现的，容器中的元素是一个有序的序列。

2. 键值对

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

现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

在SGI- STL中对于键值对pair的定义如下

template <class T1, class T2>
struct pair
{
  typedef T1 first_type;
  typedef T2 second_type;
  T1 first;   //key
  T2 second;  //value
  pair() : first(T1()), second(T2())  //默认构造
  {}
  pair(const T1& a, const T2& b) : first(a), second(b) //构造函数
  {}
};

其中一般使用first表示key，second表示value。

make_pair

按照一般的调用方式，如果我们想创建一个pair的匿对象，需要使用以下代码

pair<string,string>("apple","苹果");

写了这么长一串就是为了创建一个匿名的pair对象多少是有点麻烦的，所以干脆就封装出一个函数模版make_pair,用于快速创建出一个pair对象，使用方式

make_pair("apple","苹果");//调用此函数就返回一个pair对象

在底层，这个函数是这样实现的

template<class T1, class T2>
pair<T1,T2> make_pair(T1 first, T2 second)
{
    return (pair<T1,T2>(first,second));//本质上还是调用了pair的构造函数
}

2. 树形结构的关联式容器——set

首先还是老样子，挂一下set的使用文档

上述的英文看起来可能对某些同学很吃力，所以我们总结一下

1. set是按照特定顺序存储唯一元素的容器，里面不会出现重复的内容（可以用来去重）

1. set虽然是采用了键值对的方式存储数据，但是在set中，key==value，可以对照二叉搜索树中的K模型来看。所以在插入数据时只需要插入value即可，不需要构造键值对。

1. set中的元素一般是const修饰的，不能被修改，但是可以插入或者删除元素

1. set中的数据的排序方式是可以自己传入的，默认使用的是仿函数less<T>。

1. set通常比unordered_set更慢，通过其key访问单个元素，但允许根据其顺序对子集进行直接迭代。

1. set中查找某个元素的时间复杂度为log2n

1. 模版参数列表

接下来我们来看看set的模版参数列表

第一个参数是其内部存放元素类型，实际在其内部存放的是<value,value>键值对；第二个参数看到是Compare就知道是仿函数啦，这是用来决定set中数据的排序方式的，默认按照小于来排序；Alloc是set中元素空间的管理方式，默认使用STL提供的空间配置器。

2. 默认成员函数

1. 构造函数

set的构造方式就非常简洁，一个默认构造，一个迭代器区间构造，还有一个拷贝构造

void Test1()
{
    set<int> s1;//默认构造
    vector<int> v = {1,3,5,2,6,3,5,1};
    set<int> s2(v.begin(), v.end());//迭代器区间构造
    set<int> s3(s2);//拷贝构造
    cout << "s1:";
    for(auto e : s1)
    {
        cout << e << " ";
    }
    cout << endl;
    cout << "s2:";
    for(auto e : s2)
    {
        cout << e << " ";
    }
    cout << endl;
    cout << "s3:";
    for(auto e : s3)
    {
        cout << e << " ";
    }
    cout << endl;
}

2. 析构函数和赋值重载

很显然，在构造set对象的时候有资源申请，所以在析构函数的时候，需要进行资源释放。

析构函数和赋值重载的使用与其他容器非常相似，这里就不赘述了。