set、map、multiset、multimap的用法简介

2017-06-12 00:11 阅读 523 次 评论 0 条

RB-tree是一种平衡二叉搜索树,自动排序效果很不错,所以标准的STLsetmap即以RB-tree作为底层的数据结构,set与map所开放的各种操作接口,RB-tree基本上都提供了,因此set、map都只是调用红黑树的方法对外层的一次封装而已。

STL::set特性

1)set的元素的键值就是实值,实值就是键值,即仅有一个值。

2)set不允许出现两个元素拥有相同的键值。

3)set所有的元素的键值都会自动被排序(默认升序)。

4)set iterators是一种constant itertors(相对于mutable iterators)。

5)set使用红黑树作为底层的数据结构。

下面是set一些常用的接口,对于set的底层实现不多说明,感兴趣的可以去看源码:

STL::map特性

1)map的所有元素都是pair,同时拥有键值key与实值value。

2)map不允许两个元素拥有相同的键值。

3)map的所有元素通过键值自动排序(默认升序)。

4)map的键值是不能被修改的,但是实值是可以被修改的。

5)map的使用红黑树作为底层的数据结构。

6)map重载了[],查询速度快。

下面是map一些常用的接口,对于set的底层实现不多说明,感兴趣的可以去看源码:

STL::multiset特性

multiset的特性以及用法与set基本相同,两点差别在于:

1)multiset允许键值重复,它的插入动作调用的是insert_equal。

2)multiset的删除是删除所有值为key的元素。

源码这里不一一列举,感兴趣可以查看C++ reference手册,这里只验证一些区别:

STL::multimap特性

multimap的特性以及用法与map基本相同,差别如下:

1)允许重复键值的元素插入容器(使用了RB-Tree的insert_equal函数) 。

2)键值key与元素value的映射关系是多对多的关系。

3)没有重载[]操作运算。

4)删除key即删除键值为key的所有元素。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:set、map、multiset、multimap的用法简介 | 术与道的分享
分类:编程素养 标签:, , ,
1024do.com导航_术与道导航平台

发表评论


表情