STL之set和map
set
set的特性是,所有元素都会根据元素的键值自动排序,set的键值就是实值,实值就是键值。set不允许两个元素相同。不能通过set的迭代器改变set的元素值,因为set元素值就是其键值,关系到set元素的排列规则。set<T>::iterator被定义为底层RB-TREE的const_iterator。
set和list拥有某些相同的性质:当客户端对它进行元素新增操作或删除操作时,操作之前的所有迭代器,在操作完成之后都亦然有效。
由于RE-tree是一种平衡二叉树,自动排序效果不错,所以标准STL set即以RB-tree为底层机制。
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
intmain()
{
int ia[5] = {0,1,2,3,4};
set<int> iset(ia, ia+5);
set<int>::iterator ite1 = iset.begin();
set<int>::iterator ite2 = iset.end();
//使用STL算法find()来搜索元素,可以有效运作,但效率低
ite1= find(iset.begin(), iset.end(), 3);
if(ite1 != iset.end())
cout<< "3 found" << endl;
//面对关联式容器,应该使用其所提供的find函数来搜寻元素,
//这样会比使用STL算法find()更有效率。因为STL算法find()
//只是循序搜寻,而关联式容器提供的find()利用了红黑树的性质
ite1= iset.find(3);
if(ite1 != iset.end())
cout << "3found" << endl;
return 0;
}
map
map的特性是,所以元素都会根据元素的键值自动被排序。map的所有元素都是pair,同时拥有实值和键值。Pair的第一元素被视为键值,第二元素被视为实值。Map不允许两个元素拥有相同的键值。
我们可以用map的迭代器修改元素的实值,但不能修改键值。因此map的迭代器既不是constant iterator,也不是一种mutable iterator。
map和list拥有某些相同的性质:当客户端对它进行元素新增操作或删除操作时,操作之前的所有迭代器,在操作完成之后都亦然有效。
标准STL map即以RB-tree为底层机制。
multiset
multiset的特性和set有完全相同,唯一差别在于它允许键值冲重复,因为它的插入操作采用的是底层机制rb-tree的insert_equal(),而非insert_unique()。
multimap
multimap的特性和set有完全相同,唯一差别在于它允许键值冲重复,因为它的插入操作采用的是底层机制rb-tree的insert_equal(),而非insert_unique()。
hash_table
以上关联式容器除了可以用红黑树实现外,还可以用hash_table实现。
区别主要有两点:
1.在于hash_table这种结果在插入、删除、搜寻等操作上具有常数平均时间,这种表现是以统计为基础,不需要元素的随机性。而红黑树具有对数平均时间,且这样的表现构造在一个假设上:输入数据具有足够的随机性。
2.基于hash_table实现的容器没有自动排序功能,而基于rb_tree具有自动排序功能。
分享到:
相关推荐
学习STL MAP, STL SET之数据结构基础
可以在windbg导出stl map和set的插件,使用方法参考我csdn的博客http://blog.csdn.net/yichigo/article/details/38232511
STL基础栈链表map set 的ppt 额 看看就知道
STL 中的常用的Vector Map Set Sort用法
学习STL+MAP%2C+STL+SET之数据结构基础.
map和set的异同map和set的异同map和set的异同map和set的异同
C++STL vector list map set dqueue 等应用举例及PPT讲解示例,代码演示
用AVL-tree数据结构作为底层机制,以STL底层空间配置器和iterator_traits编程技法实作出一个独立的关联式容器(map, set, multimap, multiset),并对外提供接口实现和STL完全兼容的容器。
非常实用的STL容器讲解学习,内容全,讲解详细 包括Vector、Vector、String、Deque、sort、set、map,绝对有用!!
vector list map pair stl 标准模板库 c++ 程序示例
在STL的map或set容器中,当使用类作为key时,需要的类结构
源码之前了无秘密,你将看到vector的实现、list的实现、heap的实现、deque的实现、Red Black tree的实现、hash table的实现、set/map的实现;你将看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现;你...
STL中的set和map都是自动排序的,但是如何修改其排序准则呢?本文档给出了修改思路和具体的实现代码。对于STL编程爱好者而言,实在是不可多得的好资料啊。
在使用 list、set 或 map遍历删除某些元素时可以这样使用,如下所示
C语言版的STL,包含set,list,map等基本数据结构和算法.zip
第6次课第4章STL1(vector-set-map-pair).pptx
STL中map、set的数据结构及底层实现.pdf
c程序必备的辅导材料,新手必需品,详细介绍了map,set的用法