C++set和map的简单使用

C++中的STL模板库的功能可谓相当强⼤。今天我们来简单说⼀下set和map的使⽤⽅法。1.pair

我们先来说⼀下pair。pair定义在头⽂件中，其本⾝相当于⼀个已经重定义过的，有两个元素的结构体。它始终以前⼀个元素（first）为第⼀关键字，后⼀个元素（second）为第⼆关键字。在set或是其他STL容器中使⽤的时候⾃动进⾏按此排序。pair的定义很简单，定义如下：

pair q;

当然⾥⾯的数据类型可以改变，后⾯的变量名也可以任意改变。或者你可以使⽤make_pair来新建⼀个pair，⽐如：

make_pair(s,t);

在新建pair的时候可以直接赋值，有两种⽅法，第⼀种如下：

pair p1(0,\"Hello\");

就是在定义的pair的名称后⾯打上括号，⾥⾯直接把值传进去。第⼆种如下：

pair p2 = make_pair(1,\"World\");

这样的话就是使⽤⼀次makepair来对pair赋初值了。

看起来很简单。这样我们就可以在STL中使⽤pair这种数据结构类型，以进⾏各种复杂的操作……⽽在向⾥⾯压⼊pair元素的时候，只要加⼀个make_pair就可以了。2.map

map本⾝是键值（key）和映射值（value）的⼀个映射。其中key和value可以选择任意数据类型。（1）创建⼀个map

这⾥使⽤最简单的⼀种⽅法，就是直接定义⼀个map，在⾥⾯写上key和value的类型，再定义map的名字。

map mp;

（2）向map中添加元素

第⼀种是直接使⽤map的下标进⾏添加，就像使⽤数组⼀样。⽐如：

for（int i = 1;i <= n;i++） mp[i] = i * 100;

第⼆种是使⽤insert函数，将⼀个pair元素进⾏插⼊。⽐如：

for(int i = 1;i <= 10;i++) mp.insert(make_pair(i,i*100));

以及还有许多神奇的添加⽅式，在这⾥不⼀⼀讲述了……（3）在map中查找元素

如果要直接查找元素在map中出现过多少次，那么可以使⽤count函数，⽐如：

map mp;

rep(i,0,19) mp.insert(make_pair(i,i*100)); if(mp.count(1)) printf(\"Yes\\n\");

注意这⾥的count是直接查找键值（key）。

⽽且因为map中会⾃动对相同键值去重……所以count相当于只会告诉你这个元素是否有出现过。如果想使⽤count计算元素出现次数可以使⽤multimap。

map还有find（）函数，可以返回指向所查找元素的迭代器，如果没有此元素就返回指向map尾部的迭代器。⽐如：

map :: iterator itf; itf = mp.find(19);

if(itf != mp.end()) itf->second = 20;

注意因为itf是⼀个迭代器（实际上是指针），所以我们使⽤了->,如果不愿意使⽤的话，也可以写成：（*itf）.second

最暴⼒的⽅式就是直接在map中⽤迭代器遍历，⽐如这样：

map :: iterator it;

for(it = mp.begin();it != mp.end();it++) printf(\"%d->%d\\n\",it->first,it->second);

因为在map中元素的地址是相连的，所以直接it++即可。如果不愿意⽤->就使⽤上⾯的写法。

还有⾮常强劲的查找⽅式，那就是直接使⽤lowerbound和upperbound。这⾥要提⼀下map⾥⾯的排序，他是⾃动按key值从⼩到⼤排序，也就是说不可以对map使⽤sort。

lowerbound和upperbound与平时在数组上的⽤法都是⼀样的，⼀般来说⽀持key值查找（value作为第⼆关键字可不可⾏我还不知道……）⼀般来讲，我们映射都是⼀⼀映射，所以key值应该都是唯⼀的，直接在key值上查找就可以了。特别的，如果lower/upperbound找不到元素的话，返回指向容器末尾的迭代器。（返回的类型如果你开了代码补全可以看到……不过很影响码速）（4）map中删除元素

删除元素⼀般来说有三种操作。第⼀种是直接使⽤erase函数往⾥⾯传实际值，⽐如：

mp.erase(0);

第⼆种就是向⾥⾯传⼀个迭代器，⽐如：

mp.erase(mp.begin());//显然begin函数返回的是⼀个迭代器！！

第三种就是传两个迭代器，注意这样删除的是⼀个左闭右开的区间，⽐如：

map mp;

rep(i,0,19) mp.insert(make_pair(i,i)); map :: iterator itf; itf = mp.upper_bound(15); mp.erase(mp.begin(),itf);

这样删完之后，你会发现元素还剩15~19,（15没有被删去），⽤upperbound的话就是16~19了。

这些操作已经基本够⽤了……还有⼀个很厉害的swap。这⾥的swap函数直接交换的是两个map容器，⽽不是元素。（下⾯代码是偷来的）

#include

using namespace std;

int main( ){

map m1, m2, m3; map ::iterator m1_Iter;

m1.insert ( pair ( 1, 10 ) ); m1.insert ( pair ( 2, 20 ) ); m1.insert ( pair ( 3, 30 ) ); m2.insert ( pair ( 10, 100 ) ); m2.insert ( pair ( 20, 200 ) ); m3.insert ( pair ( 30, 300 ) );

cout << \"The original map m1 is:\";

for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ ) cout << \" \" << m1_Iter->second; cout << \".\" << endl;

// This is the member function version of swap

//m2 is said to be the argument map; m1 the target map m1.swap( m2 );

cout << \"After swapping with m2, map m1 is:\";

for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ ) cout << \" \" << m1_Iter -> second; cout << \".\" << endl;

cout << \"After swapping with m2, map m2 is:\";

for ( m1_Iter = m2.begin( ); m1_Iter != m2.end( ); m1_Iter++ ) cout << \" \" << m1_Iter -> second; cout << \".\" << endl;

// This is the specialized template version of swap swap( m1, m3 );

cout << \"After swapping with m3, map m1 is:\";

for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ ) cout << \" \" << m1_Iter -> second; cout << \".\" << endl;

system(\"pause\");}

就是这样啦！3.set

set即集合，内部是使⽤红⿊树实现的（这么强劲的数据结构蒟蒻学不会QAQ）。不过set的操作还是⾮常值得学⼀学的。（1）创建⼀个set。

set q;

这是最简单的写法，⾥⾯的变量类型是任意的，⽐如什么pair啦或者是⾃⼰定义的结构体。注意set在你没有进⾏重载运算符之前，默认是⼀个⼩根堆，⽽且会⾃动去重。（2）向set⾥⾯插⼊元素

插⼊元素好像有好多好多奇妙的⽅法……不过我还是说最简单的吧，就是直接使⽤insert函数（set可不再⽀持⽤下标插⼊函数了）⽐如：

q.insert(3);//这是int版本的

q.insert((node){a,b,c})//如果你⾃定义⼀个结构体，就可以这么传（和平时往队列⾥⾯压⼀样）

（3）在set中查找元素

这⾥⾯好多函数在map中都介绍过了，⽽且在set中的⽤法和在map中基本⼀样，⽐如count，find等等。不过，我们可以对结构体进⾏运算符重载，之后就可以愉悦的使⽤lowerbound对你想要的东西进⾏查找。⽀持多关键字，多种排序⽅式，我们举个例⼦。

#include#include#include#include#include#include#include#include#include

#define rep(i,a,n) for(int i = a;i <= n;i++)#define per(i,n,a) for(int i = n;i >= a;i--)#define enter putchar('\\n')

struct node{

int sum,val;

bool operator < (const node &g)const {

if(sum == g.sum) return val > g.val; return sum < g.sum; }}

set q;int main(){

for(int i = 1;i <= n;i++) q.insert((node){a,b,c}); set :: iterator it;

it = q.lower_bound((node){1,2,3}); //这样就可以查找了 return 0; }

⾮常强⼒的查找⽅式。然后……注意重载运算符只能重载⼩于号。

注意lowerbound返回第⼀个⼤于等于查找键值的元素，⽽upperbound返回的是最后⼀个⼤于等于查找键值的元素。（4）在set中删除元素

这些函数的⽤法和map基本是⼀样的，不加以赘述。

具体的操作也就是这些了……set同样是需要⽤迭代器来加以访问。

希望能帮助到⼤家。