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

2019-11-08 19:25:26

字体：大中小

来源：转载

供稿：网友

[数据结构]浅谈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. Swap5. Clear6. Emplace——构造插入，比insert效率高（C++11）7. Find8. 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;}

运行结果

这里写图片描述