目录

关联式容器

树形结构的关联式容器

set

set的使用

map

map的使用

multiset和multimap

multiset

multimap

---

关联式容器

在以前我们学到的vector/list/deque等容器，它们只是单纯存储数据，存储的数据和数据之间没什么关联，它们都属于序列式容器。

这篇学习的map和set，叫做关联式容器，一般还可以用来查找数据，存储的数据和数据之间有很强的关联性，这样设计的目的是在数据检索时效率更高。

树形结构的关联式容器

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

set

set的使用

1.set的模板参数列表

T：set存放参数的类型

Compare：set中元素默认按照小于来比较

2.set的构造

函数声明	功能介绍
set(const Compare& comp = Compare(),const Allocator& = Allocator());	构造空的set
set(InputIterator first,InputIterator last,const Compare& comp = Compare(),const Allocator& = Allocator());	用[first,last)区间中的元素构造set

3.set的迭代器

函数声明	功能介绍
iterator begin()	返回set中起始位置元素的迭代器
iterator end()	返回set中最后一个元素后面的迭代器

4.set的修改操作

函数声明	功能介绍
void erase(iterator position)	删除set中position位置上的元素
insert(const value_type& x)	在set中插入元素x

5.set的使用示例

<code>void test_set()

{

//排序+去重

set<int> s1;

s1.insert(9);

s1.insert(4);

s1.insert(2);

s1.insert(7);

s1.insert(4);

s1.insert(8);

s1.insert(6);

set<int>::iterator it = s1.begin();

while (it != s1.end())

{

cout << *it << endl;

++it;

}

vector<int> v = { 5,7,6,12,2,3,5,1,7 };

set<int> s2(v.begin(), v.end());

for (auto e : s2)

{

cout << e << " ";

}

cout << endl;

set<int> s3 = { 4,1,9,3,7,5,6 };

for (auto e : s3)

{

cout << e << " ";

}

cout << endl;

s3.erase(9);

for (auto e : s3)

{

cout << e << " ";

}

cout << endl;

auto pos = s3.find(10);

if (pos != s3.end())

{

cout << *pos << endl;

s3.erase(pos);

}

else

{

cout << "找不到" << endl;

}

}

除了set，还有multiset，但是multiset只有搜索和排序的功能，没有去重的功能。

void test_set()

{

//搜索 排序

multiset<int> s1;

s1.insert(9);

s1.insert(4);

s1.insert(1);

s1.insert(7);

s1.insert(4);

s1.insert(8);

s1.insert(6);

s1.insert(4);

s1.insert(1);

s1.insert(7);

s1.insert(4);

s1.insert(8);

multiset<int>::iterator it = s1.begin();

while (it != s1.end())

{

cout << *it << " ";

++it;

}

cout << endl;

}

那么，在multiset中，如果有相同值，find默认查找的是中序第一个，查找x，查找到x的节点后，这个节点的左子树没有x节点，他就是中序第一个x节点。

map

map的使用

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

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

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

4.map底层是平衡二叉搜索树（红黑树）。

1.map的模版参数说明

key：键值对中key的类型

T：键值对中value的类型

Comapre：比较器类型，缺省情况下按照小于比较，也可以自己显式传递比较规则

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

2.map的迭代器

函数声明	功能介绍
begin()	返回map中起始位置元素的迭代器
end()	返回map中最后一个元素后面的迭代器

3.map的容量与元素访问

函数声明	功能
bool empty() const	检测map中元素是否为空
size_type size() const	返回map中有效元素个数
mapped_type& operator[](const key_type& k)	返回key对应的val

问题：如果key不在map中，通过operator[]获取对应value时会发生什么？

我们先来看一下operator[]的文档说明：

operator[]的实现调用了insert函数，那再看一下insert的文档说明：

总结一下insert的返回值说明：

key存在，插入失败，返回->pair<存在的key所在节点的迭代器，false>

key不存在，插入成功，返回->pair<新插入key所在节点的迭代器，true>

了解了insert的返回值之后，我们来翻译一下上面operator[]中的调用：

我们再来结合operator[]的功能来进一步了解：

总结一下，operator[]给一个key，返回key对应value的引用，如果map之前已经有这个key了，那么返回这个key对应value的引用；如果map之前没有这个key，那么这个value相当于一个缺省值。

4.map中元素的修改

函数声明	功能
pair<iterator,bool> insert(const value_type& x)	在map中插入键值对x，注意x是一个键值对，返回值也是键值对，详见上面，不再赘述
void erase(iterator position)	删除position位置上的元素
iterator find(const key_type& x)	在map中插入key为x的元素，找到返回该元素位置的迭代器，否则返回end
size_type count(const key_type& x)const	返回key为x的键值在map中的个数，由于map中key是唯一的，因此该函数的返回值要么为0，要么为1，因此可以检测一个key是否在map中

上面的count函数为什么不返回bool值而返回个数呢？其实这个函数是和multimap结合的，multimap允许多个key为x的元素存在（允许key冗余）。

multiset和multimap

multiset

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

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

3.multiset中的元素不能修改

multimap

1.multimap中的key是可以重复的

2.multimap中的元素默认将key按照小于来比较

3.multimap中没有重载operator[]操作，这是由于multimap中的key可以重复

4.使用时与map包含的头文件相同