关联式容器
关联式容器是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
类似,不同之处在于它可以存储重复的键
关联式容器与序列式容器的区别在于元素的顺序。关联式容器内部使用二叉搜索树(如红黑树)实现,因此元素是按照特定的顺序进行存储。而序列式容器内部使用动态数组或链表实现,元素按照插入的顺序进行存储。
pair
pair
是一个模板类,封装了两个成员变量first
,second
,用于存储两个不同类型的值。它被定义在头文件<utility>
中。
template <class T1, class T2>
struct pair
{
T1 first;
T2 second;
};
C++还提供了一个函数make_pair
用于创建pair
对象,需要时直接传入两个参数,分别对应first
和second
,make_pair
内部会自动推演参数类型,返回一个pair
对象。
auto p = make_pair("hello world", 10);
因为pair
可以存储任意两个不同类型的数据,所以任何需要封装两个变量的地方,都可以使用pair
。而我们的key - value
结构,就是需要封装两个变量key
和value
,所以map
和set
的底层都是使用pair
来完成的。
set
set
是一种集合容器。它是基于红黑树实现的,它可以存储不重复的元素,并且会自动按照元素的大小进行排序。
set
的概念和特点:
- 不重复的元素:
set
中的元素是不重复的,每个元素只能出现一次。- 自动排序:
set
中的元素会根据元素的大小进行自动排序。默认情况下,set
按照升序排列。你也可以通过传入自定义的比较函数来进行降序排序。- 红黑树实现:
set
内部使用红黑树(一种自平衡二叉搜索树)来存储元素。这个数据结构保证了素的快速插入、查找和删除,时间复杂度为O(logn)。- 迭代器支持:
set
提供了迭代器,可以用于遍历集合中的元素- 查找和插入的效率高:由于
set
是基于红黑树实现,查找和插入操作的平均时间复杂度为O(logn),效率比较高。- 元素的值是不可修改的:在
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
的默认情况是升序排列。
构造函数
默认构造:
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;
size:
size_type size() const;
swap:
void swap (set& x);
clear:
void clear();
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
节点的迭代器
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
表示插入成功
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
:代表了比较规则的仿函数
特殊接口
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>
:
map<string, int> m;
- 利用匿名对象插入:
m.insert(pair<string, int>("hello", 100));
- 利用多参数默认构造的类型转化:
m.insert({ "hello", 100 });
- 利用
make_pair
进行插入:
m.insert(make_pair("hello", 100));
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( ))
可以看出,这是在利用参数
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的引用。