关联式容器
关联式容器是C++标准库提供的一种数据结构,用于存储操作键值对(key-value)。每个键值对都包含一个键和一个关联的值。关联式容器提供了通过键快速查找和访问值的功能。
C++98标准库提供了四种树形结构的关联式容器:set、multiset、map和multimap。
set
:set
是一个无序集合,存储唯一的元素。内部实现使用红黑树,因此元素是按照特定的顺序进行存储。查找和插入操作的平均时间复杂度为O(log n)。multiset
:multiset
和set
类似,不同之处在于它可以存储重复的元素。map
:map
是一个键值对的集合,其中的键是唯一的。内部实现也是使用红黑树。查找和插入操作的平均时间复杂度为O(log n)。multimap
:multimap
和map
类似,不同之处在于它可以存储重复的键。
后续C++11又提供了哈希结构的关联式容器,此博客不做讲解。
关联式容器与序列式容器的区别在于元素的顺序。关联式容器内部使用二叉搜索树(如红黑树)实现,因此元素是按照特定的顺序进行存储。而序列式容器内部使用动态数组或链表实现,元素按照插入的顺序进行存储。
pair
在讲解map
与set
之前,我们要先了解一个类:pair
。
pair
是一个模板类,封装了两个成员变量first
,second
,用于存储两个不同类型的值。它被定义在头文件<utility>
中。
pair
类的定义如下:
template <class T1, class T2> struct pair { T1 first; T2 second; };
pair
类有两个模板参数T1
和T2
,分别表示两个值的类型。
pair
类有两个成员变量first
和second
,分别表示两个值。
pair
类的构造函数有多个重载形式,可以根据需要来创建pair
对象。其中,最常用的是以下几种:
- pair():默认构造函数,创建一个
pair
对象,默认初始化first
和second
。 - pair(const T1& x, const T2& y):构造函数,初始化
first
为x
,second
为y
。
pair
类还支持拷贝构造函数、移动构造函数和赋值运算符重载,以及比较运算符重载。
使用pair类可以方便地将两个不同类型的值组合在一起,便于传递和操作。例如:
pair<int, string> p1(1, "hello"); cout << p1.first << " " << p1.second << endl; pair<double, char> p2; p2.first = 3.14; p2.second = 'a'; cout << p2.first << " " << p2.second << endl;
输出结果为:
1 hello 3.14 a
另外的,C++还提供了一个函数make_pair
用于创建pair
对象,需要时直接传入两个参数,分别对应first
和second
,make_pair
内部会自动推演参数类型,返回一个pair
对象。
auto p = make_pair("hello world", 10);
此时make_pair就会推演对象的类型为pair<const char*, int>。
因为pair可以存储任意两个不同类型的数据,所以任何需要封装两个变量的地方,都可以使用pair。而我们的key - value结构,就是需要封装两个变量key和value,所以map和set的底层都是使用pair来完成的。
set
set
是一种集合容器。它是基于红黑树实现的,它可以存储不重复的元素,并且会自动按照元素的大小进行排序。
下面是一些set
的概念和特点:
- 不重复的元素:
set
中的元素是不重复的,每个元素只能出现一次。 - 自动排序:
set
中的元素会根据元素的大小进行自动排序。默认情况下,set
按照升序排列。你也可以通过传入自定义的比较函数来进行降序排序。 - 红黑树实现:
set
内部使用红黑树(一种自平衡二叉搜索树)来存储元素。这个数据结构保证了素的快速插入、查找和删除,时间复杂度为O(logn)。 - 迭代器支持:
set
提供了迭代器,可以用于遍历集合中的元素。 - 查找和插入的效率高:由于
set
是基于红黑树实现,查找和插入操作的平均时间复杂度为O(logn),效率比较高。 - 元素的值是不可修改的:在
set
中,元素的值是不可修改的。如果需要修改元素的值,需要先删除旧的元素,然后插入新的元素。
接下来我们讲解set
的接口使用以及注意事项。
模板参数
set
的模板如下:
template < class T, class Compare = less<T>> class set;
其有两个模板参数:
T
:代表value
值的类型
Compare
:代表了比较规则的仿函数
也就是说,我们在定义set
的时候,可以在模板参数中传入仿函数,用于制定规则:
template <class T> struct comp { bool operator()(const T& t1, const T& t2) const { return T1 > T2; } }; int main() { set<int, comp<int>> s1; return 0; }
其中,s1
通过仿函数comp
完成了逆序排列,而set
的模板参数有缺省值Compare = less<T>
,所以set
的默认情况是升序排列。
typedef的类型
类型 | 含义 | 缺省值 |
key_type |
第一个模板参数T 的类型,即value 的类型 |
value_type |
第一个模板参数T 的类型,即value 的类型 |
|
key_compare |
第二个模板参数的类型,即用于比较的仿函数的类型 | less<key_type> |
value_compare |
第二个模板参数的类型,即用于比较的仿函数的类型 | less<value_type> |
由于在set中,key和value是一致的,所以以上表格中,key_type和value_type是一致的,key_compare与value_compare是一致的。
而key_compare与value_compare的缺省值是 less<key_type>,即升序排序的仿函数。
构造函数
默认构造:
explicit set (const key_compare& comp = key_compare());
迭代器区间构造:
template <class InputIterator> set (InputIterator first, InputIterator last, const key_compare& comp = key_compare());
通过一个迭代器区间来构造set
,由于是模板,所以可以是其它容器的迭代器。
迭代器
set
的迭代器用法与其它容器一致,就是通过begin
和end
来进行遍历,或者说使用反向迭代器。值得注意的是容器set
的迭代器走中序遍历,得到的是有序的数据。
常规接口
empty:
bool empty() const;
即返回这个set
是否为空,如果为空返回true
,不为空返回false
。
size:
size_type size() const;
返回当前set
存储的节点个数。
swap:
void swap (set& x);
交换两个set
的根节点指针。
clear:
void clear();
清空当前set
。
key_comp 与 value_comp:
key_compare key_comp() const; value_compare value_comp() const;
可以看到,两者的返回类型分别是key_compare 与value_compare ,也就是比较key与value的仿函数,这两个函数的功能就是返回当前比较set的仿函数。
find:
iterator find (const value_type& val) const;
find
函数用于查找val
值的节点,如果找到了,返回指向val
的迭代器;如果没找到,则返回end()
处的迭代器。
count:
size_type count (const value_type& val) const;
count
函数用于检测set
中存在几个val
值的节点,但是由于set
不可以存在重复的元素,所以这个函数的返回值只有可能是1或0。返回类型为size_type
即size_t
无符号整型。
特殊接口
lower_bound 与 upper_bound:
iterator lower_bound (const value_type& val) const; iterator upper_bound (const value_type& val) const;
两者都传入一个val
值,返回值一个iterator
迭代器,它们的功能如下:
lower_bound
:返回第一个>=val
节点的迭代器
upper_bound
:返回第一个>val
节点的迭代器
在STL设计中,都是利用左闭右开的区间特性,而迭代器也利用了此特性,我们可以使用lower_bound 与upper_bound配合得到一个一开一闭的迭代器区间,从而进行遍历,删除等等操作。
比如现在我们想遍历一个set
中[3, 20]
的闭区间,你会如何查找迭代器?
假设我们有一个名为s1
的set
,看一段代码:
auto it1 = s1.find(3); auto it2 = s2.find(21); while(it1 != it2) { cout << *it1 << endl; ++it1; }
请问这个代码正确吗?
以上代码存在两个问题:
在s1
中可能不存在值为3
或者21
的节点,find
有可能是失败的,此时我们就无法遍历到[3, 20]
了。
- 由于我们要遍历
[3, 20]
,迭代器遵循左闭右开的特性,所以我们找了一个比20
大的迭代器21
来遍历。但是如果我们的set
存储的是float
类型的数据,20
与21
之间可能还会存在其它节点,此时我们可能就会多遍历到其它节点。
因此我们可以利用lower_bound
与upper_bound
配合来得到迭代器:
auto it1 = s1.lower_bound(3); auto it2 = s2.upper_bound(21); while(it1 != it2) { cout << *it1 << endl; ++it1; }
以上代码中lower_bound(3)可以得到第一个>=3节点的迭代器,这样就不怕3节点不存在的情况了,如果3存在,此函数得到3,如果不存在,就得到大于3的下一个节点。
而upper_bound(21)则是得到第一个>21节点的迭代器,如果我们存储了float类型的数据,而刚好存储了一个21.0001的数据,那么此时upper_bound(21)就刚刚好返回这个只大21一点点的节点。
通过两者配合,我们就可以得到一个等效的左闭右开迭代器区间,后续方便操作。
erase:
set
的erase
存在三个重载:
void erase (iterator position);
这个erase
用于删除迭代器指向的节点,迭代器必须有效。
void erase (iterator first, iterator last);
这个erase
用于删除整个迭代器区间[first, last)
,迭代器必须有效。
size_type erase (const value_type& val);
这个erase
用于删除val
值的节点,val
值可以不存在,删除后返回删除节点的个数。在set
中,由于不存在重复节点,所以返回值只可能是0或1。
insert:
set
的insert
也存在三个重载:
iterator insert (iterator position, const value_type& val);
这个重载用于提高插入效率,如果迭代器position
位于插入val
值的节点之前,那么此次插入val
的效率会提高,但是如果迭代器position
与插入val
节点无关,那么与一般的插入一致。
template <class InputIterator> void insert (InputIterator first, InputIterator last);
这个重载用于插入一整个迭代器区间[first, last)
。
pair<iterator,bool> insert (const value_type& val);
这是最常用的插入,其用于直接插入一个val值的节点,但是其返回值比较特别:pair<iterator,bool>
如果原先val存在,此时iterator指向原先的val节点,bool值返回false表示插入失败
如果原先val不存在,此时iterator指向新插入的val节点,bool值返回true表示插入成功
但是函数不能一次性返回两个值,于是把iterator和bool两个值封装进pair中返回。这样我们就既可以得到迭代器,又可以检测是否插入成功了。
multiset
multiset
是一个允许存在重复元素的set
,其它的效果与set
完全一致。
但是有几个接口还是值得注意:
find:
对multiset
使用find
时,由于一个val
可能有多个节点,此时返回中序遍历的第一个节点。
count:
对于set
而言,count
用于返回某个val
值的个数,由于set
不能重复,所以这个count
接口没有多大意义。而对于multiset
才有用,可以检测val
的个数。
map
map
是一种关联容器,用于存储键-值对(key-value)。map
中的每个元素都由一个键和一个与之关联的值组成,键和值可以是任意类型。其将key
和value
封装进了pair
中,所以每一个节点都是一个pair<key, value>
。
模板参数
set
的模板如下:
template < class Key, class T, class Compare = less<Key> >class map
其有三个模板参数:
Key
:代表key
值的类型
T
:代表value
值的类型
Compare
:代表了比较规则的仿函数
同样的,map
也可以在模板参数中定义仿函数,与set
相似。
typedef的类型
类型 | 含义 | 缺省值 |
key_type |
第一个模板参数Key 的类型,即key 的类型 |
|
mapped_type |
第二个模板参数T 的类型,即value 的类型 |
|
value_type |
将 |
|
|
第二个模板参数的类型,即用于比较的仿函数的类型 |
less<key_type> |
在map
中,value
的类型是mapped_type
,而value_type
却是pair<const key_type,mapped_type>
的类型,这是值得注意的。
常规接口
由于map
的很多接口和set
一致,这里就用一张表格概括:
函数 | 声明 | 功能 | 注意事项 |
迭代器 | begin , end等 | 遍历map | 走中序遍历,得到有序数据 |
empty | bool empty() const; | 判空 | - |
size | size_type size() const; | 返回元素个数 | - |
erase | void erase (iterator position); | 删除迭代器指向的节点 | 迭代器必须有效 |
size_type erase (const key_type& k); | 删除key值的节点 | key值可以不存在 | |
void erase (iterator first, iterator last); |
删除迭代器区间 |
- |
swap | void swap (map& x); | 交换两棵树根节点指针 | - |
clear | void clear(); | 清空map | - |
key_comp | key_compare key_comp() const; | 得到比较key的仿函数 | - |
value_comp | value_compare value_comp() const; | 得到比较value的仿函数 | - |
find | iterator find (const key_type& k); | 得到key位置的迭代器 | 如果没有找到,返回end()等效的迭代器 |
count | size_type count (const key_type& k) const; | 返回值为key的节点个数 | - |
lower_bound | iterator lower_bound (const key_type& k); | 返回第一个>=key值节点的迭代器 | - |
upper_bound | iterator upper_bound (const key_type& k); | 返回第一个>key值节点的迭代器 | - |
特殊接口
insert:
对于map
而言,insert
的功能其实和set
是一致的,但是不一样的是我们需要插入pair<key, value>
,所以此处拿出来额外讲解。
重点看到以下insert
的重载:
pair<iterator,bool> insert (const value_type& val);
其插入的值val
的类型时候value_type
,而我们先前说明过,value_type
就是pair<key, value>
的类型。也就是说,我们要构造出一个pair
插入进去。
现在我们有map<string, int>
:
pair<iterator,bool> insert (const value_type& val);
现在我们对其进行插入:
- 利用匿名对象插入:
m.insert(pair<string, int>("hello", 100));
以上代码,我们利用pair<string, int>("hello", 100)
这种语法构造了一个匿名对象,然后进行插入。
- 利用多参数默认构造的类型转化:
m.insert({ "hello", 100 });
由于pair
具有一个多参数的默认构造,具有类型转化的功能,所以我们可以利用隐式类型转化进行传参。而我们有多个参数,所以要把这些参数用{}
括起来。
- 利用
make_pair
进行插入:
m.insert(make_pair("hello", 100));
即利用make_pair
函数,让其自动推导类型构造pair
。
operator[ ]:
map
还重载了[]
,这个重载比较复杂,但是非常有用,我们先看到声明:
mapped_type& operator[] (const key_type& k);
其接收一个key_type
类型的参数,也就是接受一个key
,然后返回一个mapped_type&
,也就是一个value
的引用。其功能为:接受一个key
值,然后返回这个key
对应的value
的引用。
其等效于下面的代码:
(*((this->insert(make_pair(k,mapped_type()))).first)).second
现在我们来解读以上代码,我们将其拆解为四个部分:make_pair(k, mapped_type( )) + this->insert( ) + ( ).first + (*( )).second,我们一层层解析。
第一层:
make_pair(k, mapped_type( ))
可以看出,这是在利用参数k
,通过make_pair
构造一个pair
,而这个pair
的value
使用了mapped_type( )
(mapped_type
就是value
的类型)来调用默认构造。这样我们最后就得到了一个pair<key, value>
。
第二层:
this->insert( )
上一层我们构造了一个pair<key, value>,然后它被作为参数,传入到这个insert中,相当于把刚刚构造的节点插入进map中。map的插入后,不论成功与否,都会返回一个pair<iterator, bool>,iterator用于指向key的迭代器,bool用于标识插入是否成功。所以这一层最后得到了一个pair,分别存储了指向key的迭代器和bool。
第三层:
( ).first
上一层中我们得到了pair<iterator, bool>
,这一层访问它的first
,也就是访问了iterator
,所以这一层得到了指向key
值的迭代器。
第四层:
(*( )).second
我们上一层拿到了指向key的迭代器,这一层先对迭代器解引用*( ),此时就得到了一个map的节点。而map的节点是pair<key, value>,所以我们解引用得到了一个pair,随后通过( ).second访问pair<key, value>的second,也就是value。最后返回这个value的引用。
所以我们最后得到了key对应的value的引用。那么这有什么用呢?
假设我们有一个map<string, string>类型的字典dict,通过这个来展示operator[ ]的功能:
- 插入一个key值:
dict["left"];
以上语句在dict
中插入了一个key = "left"
但是没有value
的节点 - 插入一对
key - value
:dict["left"] = "左边";
由于operator[ ]
返回的是对应的引用,因此我们可以直接给返回值赋值,此时我们就插入了一个节点key = "left" - value = "左边"
- 修改
key
对应的value
:dict[“coffe”] = "咖啡";
如果我们的dict
原先就存在key = "coffe"
的节点,以上代码可以修改这个key
的value
值
- 得到
key
对应的value
:cout << dict["coffe"] << endl;
由于我们拿到的是value
的引用,我们也可以把它作为一个值赋值给别人或者输出
可以看到,operator[]
的功能非常丰富,整体来说还是一个很好用的重载。
multimap
原本的map
同一个key
只能存在一个value
,而multimap
则可以存在多个key
相同的节点,不过多赘述了。