set和map

set和map

关联式容器

在之前我们接触了许多容器如：vector、list等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身

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

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

键值对

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

SGI-STL中关于键值对的定义：

template 
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)
    {}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

set

set的模板由一个数据类型、一个仿函数、一个空间配置器组成

set的特点：

• set里面存放的不是键值对。set中只放value，但在底层实际存放的是由构成的键值对

• set中每个数据都是唯一的，因此可以用来去重

• set的数据无法被修改，但可以插入或删除

  无法被修改的原因：set的普通 迭代器也是const迭代器

  

• set的数据是有序的，其顺序比较方式是由仿函数决定，默认是升序

set的使用

循环遍历

可以看出：迭代器遍历的底层应该是中序遍历

查找find

iterator find (const value_type& val) const;

如果找到了就返回该数据所处位置的迭代器，没找到就返回end

set的find与标准库中的find的差异在于–效率。set中的find的效率是O(logN)，而标准库中的find是暴力查找，效率是O(N)

count函数

size_type count (const value_type& val) const;

功能：传入val，返回这个val在set中出现了几次。

由于set中每个值最多出现一次。因此count的返回值不是1就是0。

因此count也可以像find一样，用来判断val在不在set中。但要注意两者的返回值不同

不过set中并不常用count，multiset会常用，后面会讲

lower_bound和upper_bound

lowerbound找左边界，所找到的值是大于等于参数值的

upperbound找右边界，所找的值是大于参数值的

看下面样例理解：

为什么右边界是大于呢？为什么没有等于呢？假如有等于，那么itup正好是60.但在erase时迭代器区间为左闭右开，并不能将60也删除

multiset

模板上，multiset和set是一样的

multiset与set的区别在于：multiset中的元素可以重复

multiset使用时，头文件还是#include

而在接口上的区别表现在如下接口：

对于前四个接口的区别很好理解，这里说一下equal_range

其中equal_range和count都是专门为multiset准备的

equal_range

pair equal_range (const value_type& val) const;

功能：返回一个范围的边界，该范围包括容器中与val等价的所有元素

该接口的返回值是两个迭代器。假设val=7，那么第一个迭代器是multiset中第一个7的位置，第二个迭代器是multiset中最后一个7的下一个位置

如果参数不存在则会返回一个不存在的区间

运用示例：

可以看出利用这个函数配合erase，可以很方便的删除multiset中所有同一val的数据

map

模板中的T就是value。

map的特点：

• map中的key是唯一的，不可重复的，但value是可以重复的。即一个value可以对应多个key

• map的key是不可被修改的，但value可以被修改

• map是有序的，其顺序是由key决定的，与value无关

• map中存储的数据是键值对。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:

  typedef pair value_type;

map的使用

插入insert

map的所插入值的类型为pair

针对单个数据的插入给出如下不同写法：（重点掌握第二种和第三种）

• 外部定义出个pair。此写法不常用

• 利用make_pair函数

  

  传入两个参数，返回pair类型

• 隐式类型的转换。此方法C++11才开始支持

  

  C++11后，利用{}可以实现构造函数的多参数的隐式类型转换

  c++98只支持单参数的构造函数的隐式类型转换

  

使用实例如下：

从上述可以看出：

• 当容器中存储的数据是一个结构时（如pair、vector等），就可以用->
• pair的第一个值即key是不可以被修改的；第二个值即value是可以被修改的

map的插入，当即将插入的数据的key已存在时：则该数据不会被插入。这也说明在插入过程中只比较key，value是否相同无所谓

insert的返回值

我们只看这个insert接口的返回值：

可以看到，返回值类型为pair，其中第一个元素是迭代器，第二个元素是bool值

bool：插入成功返回true，插入失败返回false

iteratro：插入成功则指向最新插入的那个元素，否则就指向已经存在的那个元素

即：

删除erase

从上面可以看出：给个key就可以进行删除，不需要给pair

operator[]

mapped_type& operator[] (const key_type& k);

功能：返回所传入key的对应的value

例如：

深入理解：operator[]的实现相当于如下：

mapped_type就是value

将括号细分：

• 第一部分：调用insert函数

  (this->insert(make_pair(k, mapped_type()))

  得到pair类型的返回值，记为A

• 对A解引用，得到A的第一个值，是一个迭代器位置，记为B

  *(A).first)

• 对刚刚所得的迭代器，再解引用得到一个map元素，并获取这个元素的第二个值

  (B).second

  至此就获得了传入的k所对应的value

简化后如下：

V就是mapped_type

这里的V()是匿名对象。如果value是int，那它就是0；如果是指针那就是nullptr；如果是结构，那就会调用其默认构造函数

并且由于map的insert不会覆盖，所以即使key已经存在，后面的V()也不会产生影响

多种功能

map的[]可以实现多种功能：

• 读
• 插入
• 修改

一种情况

当key不在map中时，通过operator获取对应value时会发生什么问题

在元素访问时，有一个与operator[]类似的操作at()(该函数不常用)函数，都是通过key找到与key对应的value然后返回其引用，不同的是：当key不存在时，operator[]用默认value与key构造键值对然后插入，返回该默认value，at()函数直接抛异常

一道例题

统计水果出现次数：

以前的写法：

void Test()
{
	// 统计水果出现的次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
   "苹果", "香蕉", "苹果", "香蕉" };
	map countmap;
	for (const auto& str : arr)
	{
		auto ret = countmap.find(str);
		if (ret == countmap.end())
		{
			countmap.insert(make_pair(str, 1));
		}
		else
		{
			ret->second++;
		}
	}

	for (const auto& e : countmap)
	{
		cout << e.first << ":" << e.second << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

运用map的[]：

void Test1()
{
	// 统计水果出现的次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
   "苹果", "香蕉", "苹果", "香蕉" };
	map countmap;

	for (const auto& str : arr)
	{
		countmap[str]++;
	}

	for (const auto& e : countmap)
	{
		cout << e.first << ":" << e.second << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

countmap[str]++;

• 当str不在countmap中时，会进行插入，初始值为0，再返回value并++
• 当str在countmap中时，则会直接对value进行++

multimap

multimap与map的唯一区别在于：multimap中的key可以重复

也因为如此：

• multimap中没有operator[]

• 

  插入的返回值也不同了。少了bool，因为插入永远成功