网站开发文档模板下载,google推广方式和手段有哪些,郑州网站推广优化,上海网络推广营销C#xff1a;STL - set map 关联式容器pairset模板参数typedef的类型构造函数迭代器常规接口特殊接口 multisetmap模板参数typedef的类型常规接口特殊接口 multimap 关联式容器
关联式容器是C标准库提供的一种数据结构#xff0c;用于存储操作键值对#xff08;key-v… CSTL - set map 关联式容器pairset模板参数typedef的类型构造函数迭代器常规接口特殊接口 multisetmap模板参数typedef的类型常规接口特殊接口 multimap 关联式容器
关联式容器是C标准库提供的一种数据结构用于存储操作键值对key-value。每个键值对都包含一个键和一个关联的值。关联式容器提供了通过键快速查找和访问值的功能。
C98标准库提供了四种树形结构的关联式容器set、multiset、map和multimap。 setset是一个无序集合存储唯一的元素。内部实现使用红黑树因此元素是按照特定的顺序进行存储。查找和插入操作的平均时间复杂度为O(log n)。 multisetmultiset和set类似不同之处在于它可以存储重复的元素。 mapmap是一个键值对的集合其中的键是唯一的。内部实现也是使用红黑树。查找和插入操作的平均时间复杂度为O(log n)。 multimapmultimap和map类似不同之处在于它可以存储重复的键。
后续C11又提供了哈希结构的关联式容器此博客不做讲解。
关联式容器与序列式容器的区别在于元素的顺序。关联式容器内部使用二叉搜索树如红黑树实现因此元素是按照特定的顺序进行存储。而序列式容器内部使用动态数组或链表实现元素按照插入的顺序进行存储。 pair
在讲解map与set之前我们要先了解一个类pair。
pair是一个模板类封装了两个成员变量firstsecond用于存储两个不同类型的值。它被定义在头文件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为xsecond为y。
pair类还支持拷贝构造函数、移动构造函数和赋值运算符重载以及比较运算符重载。
使用pair类可以方便地将两个不同类型的值组合在一起便于传递和操作。例如
pairint, string p1(1, hello);
cout p1.first p1.second endl;pairdouble, 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和secondmake_pair内部会自动推演参数类型返回一个pair对象。
auto p make_pair(hello world, 10);此时make_pair就会推演对象的类型为pairconst 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 lessT 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()
{setint, compint s1;return 0;
}其中s1通过仿函数comp完成了逆序排列而set的模板参数有缺省值Compare lessT所以set的默认情况是升序排列。 typedef的类型
类型含义缺省值key_type第一个模板参数T的类型即value的类型value_type第一个模板参数T的类型即value的类型key_compare第二个模板参数的类型即用于比较的仿函数的类型lesskey_typevalue_compare第二个模板参数的类型即用于比较的仿函数的类型lessvalue_type
由于在set中key和value是一致的所以以上表格中key_type和value_type是一致的key_compare与value_compare是一致的。
而key_compare与value_compare的缺省值是 lesskey_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)。
pairiterator,bool insert (const value_type val);这是最常用的插入其用于直接插入一个val值的节点但是其返回值比较特别pairiterator,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中所以每一个节点都是一个pairkey, value。 模板参数
set的模板如下
template class Key, class T, class Compare lessKey class map其有三个模板参数 Key代表key值的类型 T代表value值的类型 Compare代表了比较规则的仿函数 同样的map也可以在模板参数中定义仿函数与set相似。 typedef的类型
类型含义缺省值key_type第一个模板参数Key的类型即key的类型mapped_type第二个模板参数T的类型即value的类型value_type将key与value封装后 pairconst key_type,mapped_type的类型key_compare第二个模板参数的类型即用于比较的仿函数的类型lesskey_type
在map中value的类型是mapped_type而value_type却是pairconst key_type,mapped_type的类型这是值得注意的。 常规接口
由于map的很多接口和set一致这里就用一张表格概括
函数声明 功能注意事项迭代器 begin , end等 遍历map走中序遍历得到有序数据emptybool empty() const;判空-sizesize_type size() const;返回元素个数-erasevoid erase (iterator position);删除迭代器指向的节点迭代器必须有效size_type erase (const key_type k);删除key值的节点 key值可以不存在void erase (iterator first, iterator last);删除迭代器区间-swapvoid swap (map x);交换两棵树根节点指针-clearvoid clear();清空map-key_compkey_compare key_comp() const;得到比较key的仿函数-value_compvalue_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是一致的但是不一样的是我们需要插入pairkey, value所以此处拿出来额外讲解。
重点看到以下insert的重载
pairiterator,bool insert (const value_type val);其插入的值val的类型时候value_type而我们先前说明过value_type就是pairkey, value的类型。也就是说我们要构造出一个pair插入进去。 现在我们有mapstring, int
mapstring, int m;现在我们对其进行插入
利用匿名对象插入
m.insert(pairstring, int(hello, 100));以上代码我们利用pairstring, 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的类型来调用默认构造。这样我们最后就得到了一个pairkey, value。 第二层
this-insert( )上一层我们构造了一个pairkey, value然后它被作为参数传入到这个insert中相当于把刚刚构造的节点插入进map中。map的插入后不论成功与否都会返回一个pairiterator, booliterator用于指向key的迭代器bool用于标识插入是否成功。所以这一层最后得到了一个pair分别存储了指向key的迭代器和bool。 第三层
( ).first上一层中我们得到了pairiterator, bool这一层访问它的first也就是访问了iterator所以这一层得到了指向key值的迭代器。 第四层
(*( )).second我们上一层拿到了指向key的迭代器这一层先对迭代器解引用*( )此时就得到了一个map的节点。而map的节点是pairkey, value所以我们解引用得到了一个pair随后通过( ).second访问pairkey, value的second也就是value。最后返回这个value的引用。 所以我们最后得到了key对应的value的引用。那么这有什么用呢
假设我们有一个mapstring, 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相同的节点不过多赘述了。
