STL之(底层红黑树)set、multiset、map、multimap
set、multset容器set/multiset是以rb_tree为底层机构,因此有元素自动排序的特性。排序的依据是key,而set/multiset的value和key合一:value就是key,其中value由key和data组成。set/multiset提供遍历操作和迭代器,按正常规则(++iter)遍历,便能获得排序状态(sorted)我们无法使用set/multiset...
set、multset容器
- set/multiset是以rb_tree为底层机构,因此有元素自动排序的特性。
- 排序的依据是key,而set/multiset的value和key合一:value就是key,其中value由key和data组成。
- set/multiset提供遍历操作和迭代器,按正常规则(++iter)遍历,便能获得排序状态(sorted)
- 我们无法使用set/multiset的迭代器改变元素值(因为key有严谨的排序规则)。
- set/multiset的迭代器是其底部的RB Tree的const-iterator,就是为了禁止用户对元素赋值
- set元素的key必须对一无二,因此其insert()用的是rb_tree的insert_unique().
- multiset元素的key可以重复,因此其insert()用的是rb_tree的insert_equal().
缺省情况下使用递增排序
解析:
a、set的模板类参数有三个:第一个是key(data也是key),第二个是默认比较方法less,第三个是分配器;
b、set中有一个数据t,类型就是底层的红黑树rb_tree;
c、此时rb_tree中的keyofvalue就是identity;
d、在实际使用过程如黄色框过程一样,声明一个int类型的set,就相当于使用了默认的key、比较方法less和identity取key法。
e、对set设置相关函数,就是间接使用rb_tree的相关函数。
f、迭代器是const类型,因此不能修改迭代器,也就是不能对元素赋值。
例子:
int i;
int ia[5]={0,1,2,3,4};
set<int>iset(ia,ia+5);
cout<<"size="<<iset.size()<<endl;//size=5
cout<<"3 count="<<iset.count(3)<<<<endl;//求iset中3的数量
iset.insert(3);//再插入一个3
cout<<"size="<<iset.size()<<endl;//size=5,证明插入失败
cout<<"3 count="<<iset.count(3)<<endl;//count=1
iset.insert(5);
cout<<"size="<<iset.size()<<endl;//size=6
iset.erase(1);
cout<<"1 count="<<iset.count(1)<<endl;//count=0
set<int>::iterator itel=iset.begin();
set<int>::iterator ite2=iset.end();
for(;ite1!=ite2;++ite1)
cout<<*ite1;
cout<<endl;
//使用STL算法find()来搜寻元素,不是好办法,效率不高
ite1=find(iset.begin(),iset.end(),3);
if(ite1!=iset.end())
cout<<"3 found"<<endl;
//面对关联式容器,应使用容器提供的find函数搜寻元素,而不是STL算法
ite1=iset.find(3);
if(ite1!=iset.end())
cout<<"3 found"<<endl;
//企图使用迭代器改变set元素,是不允许的
*ite1=9;//error
map、multimap容器
map的所有元素都是pair,同时拥有键值(key)和实值(value)
pair的第一元素被视为键值,第二元素被视为实值
性质:
- 以rb_tree为底层结构,因此元素有自动排序的特性,排序的依据是key;
- 提供遍历操作和迭代器,正常的++ite遍历,便能得到排序状态;
- 无法使用map/multimap来改变元素的key,但可以用来改变元素的data。
- map元素的key必须独一无二,因此insert()使用的是rb_tree的insert_unique();
- multimap元素的key可以重复,因此inset()使用的是rb_tree的insert_equal().
解析:
a、map模板类参数有4个,比set多了第二个参数,它是key和data的结合;
b、map中有一个数据t,它就是红黑树rb_tree类型;
c、此rb_tree默认的第三个模板参数是selectlst表示得到传入key和data中的key;
d、声明一个map<int,string>类型的map,就如上黄色图过程所示。其中Rb tree中的value参数用标准库中的pair<const int, string>表示。
e、注意pair模板参数中是cont int,表示map中的key值是不可以改变的。
f、最后注意一点,map是可以用[ ]来进行元素插入,而multiset则不可以。
g、与set一样,几乎所有的map操作行为,都是转调用红黑树的操作行为。
例子:
#include<map>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
map<string,int>simap;//以string为键值,以int为实值
//验证下标操作符[]的特性
simap[string("jjhou")]=1;//第一对内容是("jjhou",1)
simap[string("jerry")]=2;//第二对内容是("jerry",2)
simap[string("jason")]=5;
simap[string("jimmy")]=4;
pair<string,int>value(string("david"),5);
//验证insert的特性
pair<map<string,int>::iterator,bool>pair1;
pair1=simap.insert(value);
map<string,int>::iterator ite=pair1.first;
cout<<ite->second<<endl;//5
map<string,int>::iterator simap_iter=simap.begin();
for(;simap_iter!=simap.end();++simap_iter)
cout<<simap_iter->first<<" "<<simap_iter->second<<endl;//按照键值顺序输出5,2,4,1
int number=simap[string("jjhou")];
cout<<number<<endl;//1
map<string,int>::iterator ite1;
//对于关联式容器,使用其提供的find来提供搜索元素
ite1=simap.find(string("jerry"));
if(ite1==simap.end())
cout<<"mchen not found"<<endl;
//可以通过map迭代器修改“value”
ite1->second=9;
cout<<ite1->second<<endl;//9
system("pause");
}
1、map的insert函数
pair<iterator,bool> insert(const value_type& x)
{return t.insert_unique(x);}
注意其返回值类型是一个pair,bool表示插入成功与否,如果成功,iterator指向被插入的元素。
如上例中15-18行
2、map容器独有的operator[]
mapped_type& operator[] (const key_type& Key)
map的下标运算符[]的作用是:若key存在,则返回相应的value;若key不存在,则对该key对应的value赋一个对应value类型数据的默认值并返回。
例:
map<string, string> imap
if ("kevin" == imap["name"])
{
imap["name"] = "man";
}
cout << imap["name"] << endl;
上面代码的目的是,判断imap["name"]的值是否为"kevin",如果是则修改imap["name"]的值为"man",最后输出imap["name"]的值。代码看似没有问题,但是输出却永远为空,原因就是在判断语句里面对map的下标运算符[]的错误使用。
在上面的代码中,对于if ("kevin" == ["name"])这行代码,首先会判断imap中关键字为name的项是否存在,此时程序发现没有该项,因此会在imap中插入一项("name", ""),此时imap["name"]的值就为空字符串,这就导致了if判断的结果永远都为false,进不了if代码块里面修改数据。
例2:
class Obj
{public:
//...
};
map<string, Obj*> imap;
Obj *ptr = imap["abc"]; //ptr等于NULL
上面代码中,map的key是string类型,而value则是Obj*类型,即Obj类型的指针,而imap中并不在关键字为"abc"的项,对于imap["abc"],程序会自动插入一项("abc", NULL),此时关键字为"abc"的项对应的值是一个空指针,若不小心使用到这个之后指针访问数据时,就会出现Segmentation fault了。不同编译器对于指针赋的默认值是不一样的,当map的value类型是指针的时候,就要注意野指针或空指针问题了。
因此当需要判断map中是否存在指定的key值时,就不能直接使用map的下标运算符了,这时候可以使用find函数,如下面代码所示:
bool isexist(const string&s)
{
return imap.find(s) != imap.end();
}
更多推荐
所有评论(0)