C++ Primer 学习笔记：关联容器入门 set && map

叁歲伎倆 2022-06-02 03:41 185阅读 0赞

\#\#关联容器  
标准库提供8个关联容器，这8个容器间的不同体现在三个维度上：每个容器  
（1）或者是一个set，或者是一个map；  
（2）或者要求不重复的关键字，或者允许重复关键字；  
（3）按顺序保存元素，或无序保存。  
允许重复关键字的容器的名字中都包含单词multi；  
不保持关键字按顺序存储的容器的名字都以单词unordered开头。

类型map和multimap定义在头文件map中；set和multiset定义在头文件set中；无序容器则定义在头文件unordered\_map和unordered\_set中。

关联容器类型  
按关键字有序保存元素

map	关联数组；保存关键字-值对
    set	关键字即值，即只保存关键字的容器
    multimap	关键字可重复出现的map
    multiset	关键字可重复出现的set

无序集合

unordered_map	用哈希函数组织的map
    unordered_set	用哈希函数组织的set
    unordered_multimap	哈希组织的map；关键字可以重复出现
    unordered_multiset	哈希组织的set；关键字可以重复出现

set内部使用平衡二叉树来实现的，那么可以获取最小值（set的begin()）和最大值(set的rbegin())，set中不可以直接使用end()-1来获取最大值，所以要使用反向指针。

使用set做遍历其实是平衡二叉树的中序遍历，获得是一个有序的序列，要是使用unordered的set，它是没有rbegin()函数的

\#\#自定义比较函数

一般情况下我们使用基本类型的set和map，但是假如我们需要使用自定义的类型去存储呢》这个时候我们应该定义一个比较函数，来做两个元素的判断，遮掩刚才可以在set中插入到正确的位置，如下面的例子：

bool cmp(ClassA a,ClassA b)
    {
    	return a.x < b.x;
    }
    int main()
    {
    	set<ClassA,decltype(cmp)*> ss(cmp);
    	map<int, int,decltype(cmp)*> mmp(cmp);
    }

首先顶一个了一个ClassA的比较函数cmp，然后在声明定义set的时候需要告诉它函数指针的类型，注意我们这里通过decltype来获取函数指针的类型，这个时候需要添加一个\*号，表明我们需要的是函数类型的指针，然后使用cmp来初始化set，这样表明我们每当插入元素的时候都需要调用cmp函数来做比较，从而插入到正确的位置。

对于map也是同样的做法，

还有下面几个成员函数需要注意：

map::lower\_bound(key):返回map中第一个大于或等于key的迭代器指针  
map::upper\_bound(key):返回map中第一个大于key的迭代器指针

关于map中的count和find函数的区别：  
使用count，返回的是被查找元素的个数。如果有，返回1；否则，返回0。注意，map中不存在相同元素，所以返回值只能是1或0。使用find，返回的是被查找元素的位置，没有则返回map.end()。