[数据结构]浅谈C++ STL 的map和set容器

2/22/2017来源:ASP.NET技巧人气:1158

[数据结构]浅谈C++ STL 的map和set容器

    在C++的STL库中,有许多种不同结构、不同用途的容器。容器又可以分为两大类,分别是:    

序列式容器(sequence containers) 关联式容器(associative containers)

其中序列式容器包括vector、queue和list等,本文中的map和set属于关联式容器。   先说说set容器,set的特性是,所有的元素再插入的时候都会根据元素的键值来排序。(默认为升序,需要时可以传入模板参数改为降序排序)。set元素的键值就是实值,实值就是键值,所以set中的值不能修改,只能做插入和删除的操作。set不允许两个元素有相同的键值。       set的底层实现是红黑树,所以set容器的效率非常高。      

set常用成员有(具体用法见SetTest())

1. 迭代器(前向/反向/const迭代器) 2. Insert a. 直接插入一个值(返回pair <K,V>)first->元素位置 second->成功标志 b. 在某位置插入 c. 插入一个区间 3. Erase a. 删除一个有效迭代器所指的位置,否则assert b. 删除一个值 未找到不报错, 找到即删除 c. 删除一个迭代器区间的值 4. Swap 5. Clear 6. Emplace——构造插入,比insert效率高(C++11) 7. Find 8. count——常用于快速判断一个元素是否存在

   容器map的特性是,所有元素都会根据元素的键值自动排序。map的所有元素都是pair,同时拥有实值和键值。pair的第一元素被视为键值,第二元素被视为实值。map同样不允许有两个元素拥有相同的键值,也不能修改元素的键值,不过实值可以修改。map与set相似的是底层也是map容器实现。

map常用成员(测试用例见MapTest)

1. Insert    a. 插入一个pair<Key,Value>() 2. Operator[]    a. 以K值为参数,返回V值引用

#include <iostream> #include <string> #include <set> #include <map> using namespace std; void SetTest() { int i; int a[5]={0,1,2,3,4}; set<int> s(a,a+5); cout<<"Size="<<s.size()<<endl;//size=5; cout<<"3 count="<<s.count(3)<<endl;//3 count=1 s.insert(3); cout<<"Size="<<s.size()<<endl;//size=5; cout<<"3 count="<<s.count(3)<<endl;//3 count=1 s.insert(5); cout<<"Size="<<s.size()<<endl;//size=6; cout<<"3 count="<<s.count(3)<<endl;//3 count=1 s.erase(1); cout<<"Size="<<s.size()<<endl;//size=5; cout<<"3 count="<<s.count(3)<<endl;//3 count=1 cout<<"1 count="<<s.count(1)<<endl;//1 count=0 //insert一个值到set时,可通过insert的返回值来判断 //insert的返回值是一个pair<iterator,bool>类型的值 //若插入成功,iterator值为插入位置的迭代器,bool的值为true //若插入失败,iterator值为已有元素的迭代器,bool的值为false pair<set<int>::iterator,bool> PR=s.insert(8); cout<<"insert 8 pr.first:"<<*pr.first<<"-"<<"pr.second:"<<pr.second<<endl; pr=s.insert(0); cout<<"insert 0 pr.first:"<<*pr.first<<"-"<<"pr.second:"<<pr.second<<endl; s.erase(1);//erase一个不存在的元素,对set无影响 set<int>::iterator is=s.find(1);//未找到元素1 is值为s.end() 即is是一个无效的迭代器; //s.erase(is); //erase一个无效的迭代器会触发assert,所以向erase传入迭代器时要保证其合法性 cout<<"升序排列的is1:"; set<int>::iterator is1=s.begin(); while (is1!=s.end()) { cout<<*is1++<<" "; } cout<<endl; set<int>::iterator is2=s.begin(); //*is2 = 9;//无法通过编译,在set中其底层实现是const_iterator,故不能通过迭代器修改值 //set默认升序排列,也可以通过改变模板参数改为降序排列 set<int,greater<int>> s1; s1.insert(a,a+5); cout<<"降序排列的is3:"; set<int,greater<int>>::iterator is3=s1.begin(); while (is3!=s1.end()) { cout<<*is3++<<" "; } cout<<endl; } void MapTest() { map<string,int> m;//以string为键值,以int为实值 m["[]"]=1;//map内对[]操作符进行重载,以键值为参数,返回值为实值的引用 //相当于(*((insert(value_type(k,T()))).first)).second m.insert(make_pair<string,int>("make_pair",2)); pair<string,int> value("pair",3); pair<map<string,int>::iterator,bool> ret; ret=m.insert(value); cout<<"ret.first:"<<"("<<(ret.first)->first<<","<<(ret.first)->second<<")"<<" "<<"ret.second:"<<ret.second<<endl; map<string,int>::iterator mi=m.begin(); while (mi!=m.end()) { cout<<(*mi).first<<": "<<mi->second<<endl; mi++; } } int main () { cout<<"SetTest()"<<endl; SetTest(); cout<<endl; cout<<endl; cout<<"MapTest()"<<endl; MapTest(); cout<<endl; cout<<endl; return 0; }

运行结果

这里写图片描述