C++:STL - set & map

简介: C++:STL - set & map

关联式容器

关联式容器是C++标准库提供的一种数据结构,用于存储操作键值对(key-value)。每个键值对都包含一个键和一个关联的值。关联式容器提供了通过键快速查找和访问值的功能。


C++98标准库提供了四种树形结构的关联式容器:set、multiset、map和multimap。

  1. setset是一个无序集合,存储唯一的元素。内部实现使用红黑树,因此元素是按照特定的顺序进行存储。查找和插入操作的平均时间复杂度为O(log n)。
  2. multisetmultisetset类似,不同之处在于它可以存储重复的元素。
  3. mapmap是一个键值对的集合,其中的键是唯一的。内部实现也是使用红黑树。查找和插入操作的平均时间复杂度为O(log n)。
  4. multimapmultimapmap类似,不同之处在于它可以存储重复的键。

后续C++11又提供了哈希结构的关联式容器,此博客不做讲解。

关联式容器与序列式容器的区别在于元素的顺序。关联式容器内部使用二叉搜索树(如红黑树)实现,因此元素是按照特定的顺序进行存储。而序列式容器内部使用动态数组或链表实现,元素按照插入的顺序进行存储。


pair

在讲解mapset之前,我们要先了解一个类:pair

pair是一个模板类,封装了两个成员变量firstsecond,用于存储两个不同类型的值。它被定义在头文件<utility>中。

pair类的定义如下:

template <class T1, class T2>
struct pair
{
    T1 first;
    T2 second;
};

pair类有两个模板参数T1T2,分别表示两个值的类型。

pair类有两个成员变量firstsecond,分别表示两个值。

pair类的构造函数有多个重载形式,可以根据需要来创建pair对象。其中,最常用的是以下几种:

  • pair():默认构造函数,创建一个pair对象,默认初始化firstsecond
  • pair(const T1& x, const T2& y):构造函数,初始化firstxsecondy

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对象,需要时直接传入两个参数,分别对应firstsecondmake_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的概念和特点:

  1. 不重复的元素:set中的元素是不重复的,每个元素只能出现一次。
  2. 自动排序:set中的元素会根据元素的大小进行自动排序。默认情况下,set按照升序排列。你也可以通过传入自定义的比较函数来进行降序排序。
  3. 红黑树实现:set内部使用红黑树(一种自平衡二叉搜索树)来存储元素。这个数据结构保证了素的快速插入、查找和删除,时间复杂度为O(logn)。
  4. 迭代器支持:set提供了迭代器,可以用于遍历集合中的元素。
  5. 查找和插入的效率高:由于set是基于红黑树实现,查找和插入操作的平均时间复杂度为O(logn),效率比较高。
  6. 元素的值是不可修改的:在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的迭代器用法与其它容器一致,就是通过beginend来进行遍历,或者说使用反向迭代器。值得注意的是容器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_typesize_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]的闭区间,你会如何查找迭代器?

假设我们有一个名为s1set,看一段代码:

auto it1 = s1.find(3);
auto it2 = s2.find(21);

while(it1 != it2)
{
  cout << *it1 << endl;
  ++it1;
}

请问这个代码正确吗?

以上代码存在两个问题:

s1中可能不存在值为3或者21的节点,find有可能是失败的,此时我们就无法遍历到[3, 20]了。

  1. 由于我们要遍历[3, 20],迭代器遵循左闭右开的特性,所以我们找了一个比20大的迭代器21来遍历。但是如果我们的set存储的是float类型的数据,2021之间可能还会存在其它节点,此时我们可能就会多遍历到其它节点。

因此我们可以利用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:

seterase存在三个重载:

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:

setinsert也存在三个重载:

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中的每个元素都由一个键和一个与之关联的值组成,键和值可以是任意类型。其将keyvalue封装进了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

keyvalue封装后 pair<const key_type,mapped_type>的类型


key_compare

第二个模板参数的类型,即用于比较的仿函数的类型

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,而这个pairvalue使用了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[ ]的功能:

  1. 插入一个key值:
    dict["left"];
    以上语句在dict中插入了一个key = "left"但是没有value的节点
  2. 插入一对key - value
    dict["left"] = "左边";
    由于operator[ ]返回的是对应的引用,因此我们可以直接给返回值赋值,此时我们就插入了一个节点key = "left" - value = "左边"
  3. 修改key对应的value
    dict[“coffe”] = "咖啡";
    如果我们的dict原先就存在key = "coffe"的节点,以上代码可以修改这个keyvalue
  1. 得到key对应的value
    cout << dict["coffe"] << endl;
    由于我们拿到的是value的引用,我们也可以把它作为一个值赋值给别人或者输出

可以看到,operator[]的功能非常丰富,整体来说还是一个很好用的重载。


multimap

原本的map同一个key只能存在一个value,而multimap则可以存在多个key相同的节点,不过多赘述了。

相关文章
|
3天前
|
算法 前端开发 Linux
【常用技巧】C++ STL容器操作:6种常用场景算法
STL在Linux C++中使用的非常普遍,掌握并合适的使用各种容器至关重要!
31 10
|
5天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
15 4
|
5天前
|
存储 缓存 编译器
【C++进阶】深入STL之list:模拟实现深入理解List与迭代器
【C++进阶】深入STL之list:模拟实现深入理解List与迭代器
8 0
|
5天前
|
C++ 容器
【C++进阶】深入STL之list:高效双向链表的使用技巧
【C++进阶】深入STL之list:高效双向链表的使用技巧
8 0
|
5天前
|
编译器 C++ 容器
【C++进阶】深入STL之vector:深入研究迭代器失效及拷贝问题
【C++进阶】深入STL之vector:深入研究迭代器失效及拷贝问题
10 0
|
6天前
|
编译器 数据安全/隐私保护 C++
c++primer plus 6 读书笔记 第十三章 类继承
c++primer plus 6 读书笔记 第十三章 类继承
|
2天前
|
数据安全/隐私保护 C++
C++ 中的类是一种用户定义的数据类型,用于表示具有相似特征和行为的对象的模板。
C++ 中的类是一种用户定义的数据类型,用于表示具有相似特征和行为的对象的模板。
|
2天前
|
C++
C++ 是一种面向对象的编程语言,它支持对象、类、继承、多态等面向对象的特性
C++ 是一种面向对象的编程语言,它支持对象、类、继承、多态等面向对象的特性
|
5天前
|
编译器 C++
【C++初阶】—— 类和对象 (下)
【C++初阶】—— 类和对象 (下)
8 2
|
5天前
|
存储 编译器 C++
【C++初阶】—— 类和对象 (中)
【C++初阶】—— 类和对象 (中)
12 3