STL容器之关联容器
FrankGood 2011-07-13
STL是C++的一个类库。STL中的容器有队列容器和关联容器，容器适配器（congtainer adapters：stack,queue，priority queue），位集（bit_set），串包(string_package)等等。
在系列中，我将介绍list,vector，deque等队列容器，和set和multisets,map和multimaps等关联容器，一共7种基本容器类。
队列容器（顺序容器）：队列容器按照线性排列来存储T类型值的集合，队列的每个成员都有自己的特有的位置。顺序容器有向量类型、双端队列类型、列表类型三种。
下面介绍关联容器类。
集和多集（set 和multiset 容器类）：
一个集合（#include<set>）是一个容器，它其中所包含的元素的值是唯一的。这在收集一个数据的具体值的时候是有用的。集合中的元素按一定的顺序排列，并被作为集合中的实例。如果你需要一个键/值对（pair）来存储数据，map（也是一个关联容器，后面将马上要讲到）是一个更好的选择。一个集合通过一个链表来组织，在插入操作和删除操作上比向量（vector）快，但查找或添加末尾的元素时会有些慢。
在集中，所有的成员都是排列好的。
如果先后往一个集中插入：12，2，3，123，5，65
则输出该集时为：2，3，5，12，65，123
集和多集的区别是：set支持唯一键值，set中的值都是特定的，而且只出现一次；而multiset中可以出现副本键，同一值可以出现多次。
Set和multiset的模板参数：
template<class key, class compare, class Allocator=allocator>
第一个参数key是所存储的键的类型，第二个参数是为排序值而定义的比较函数的类型，第三个参数是被实现的存储分配符的类型。在有些编译器的具体实现中，第三个参数可以省略。第二个参数使用了合适形式的迭代器为键定义了特定的关系操作符，并用来在容器中遍历值时建立顺序。集的迭代器是双向，同时也是常量的，所以迭代器在使用的时候不能修改元素的值。
Set定义了三个构造函数：
默认构造函数：
explicit set(const Compare&=compare());
如：
set<int,less<int> > set1;
less<int>是一个标准类，用于形成降序排列函数对象。升序排列是用greater<int>。通过指定某一预先定义的区间来初始化set对象的构造函数：
template<class InputIterator> set(InputIterator, InputIterator,\ const Compare&=compare());
如：
set<int ,less<int> >set2(vector1.begin(),vector1.end());
复制构造函数：
set（const set<Key,Compare&>）;
如：
set<int ,less<int> >set3(set2);
下面我们来看一个简单的集和多集的插入例程：
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> set1;
for(int i=0; i<10; ++i)
set1.insert(i);
for(set<int>::iterator p=set1.begin();p!=set1.end();++p)
cout<<*p<<"";
if(set1.insert(3).second)//把3插入到set1中
//插入成功则set1.insert(3).second返回1，否则返回0
//此例中，集中已经有3这个元素了，所以插入将失败
cout<<"set insert success";
else
cout<<"set insert failed";
int a[] = {4, 1, 1, 1, 1, 1, 0, 5, 1, 0};
multiset<int> A;
A.insert(set1.begin(),set1.end());
A.insert(a,a+10);
cout<<endl;
for(multiset<int>::iterator p=A.begin();p!=A.end();++p)
cout<<*p<<" ";
return 0;
} 映射和多重映射（map 和multimap）
映射和多重映射(#include<map>)基于某一类型Key的键集的存在，提供对T类型的数据进行快速和高效的检索。对map而言，键只是指存储在容器中的某一成员。Map不支持副本键，multimap支持副本键。Map和multimap对象包涵了键和各个键有关的值，键和值的数据类型是不相同的，这与set不同。
set中的key和value是Key类型的，而map中的key和value是一个pair结构中的两个分量。Map支持下表运算符operator[],用访问普通数组的方式访问map，不过下标为map的键。在multimap中一个键可以对应多个不同的值。
下面的例程说明了map中键与值的关系。
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<char,int,less<char> > map1;
map<char,int,less<char> >::iterator mapIter;
//char 是键的类型，int是值的类型
//下面是初始化，与数组类似
//也可以用map1.insert(map<char,int,less<char> >::value_type(''c'',3));
map1['c']=3;
map1['d']=4;
map1['a']=1;
map1['b']=2;
for(mapIter=map1.begin();mapIter!=map1.end();++mapIter)
cout<<" "<<(*mapIter).first<<": "<<(*mapIter).second;
//first对应定义中的char键，second对应定义中的int值
//检索对应于d键的值是这样做的：
map<char,int,less<char> >::const_iterator ptr;
ptr=map1.find('d');
cout<<'\n'<<" "<<(*ptr).first<<" 键对应于值："<<(*ptr).second;
return 0;
} 从以上例程中，我们可以看到map对象的行为和一般数组的行为类似。Map允许两个或多个值使用比较操作符。下面我们再看看multimap:
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
multimap<string,string,less<string> >mulmap;
multimap<string,string,less<string> >::iterator p;
//初始化多重映射mulmap:
typedef multimap<string,string,less<string> >::value_type vt;
typedef string s;
mulmap.insert(vt(s("Tom "),s("is a student")));
mulmap.insert(vt(s("Tom "),s("is a boy")));
mulmap.insert(vt(s("Tom "),s("is a bad boy of blue!")));
mulmap.insert(vt(s("Jerry "),s("is a student")));
mulmap.insert(vt(s("Jerry "),s("is a beatutiful girl")));
mulmap.insert(vt(s("DJ "),s("is a student")));
//输出初始化以后的多重映射mulmap:
for(p=mulmap.begin();p!=mulmap.end();++p)
cout<<(*p).first<<(*p).second<<endl;
//检索并输出Jerry键所对应的所有的值
cout<<"find Jerry :"<<endl;
p=mulmap.find(s("Jerry "));
while((*p).first=="Jerry ")
{
cout<<(*p).first<<(*p).second<<endl;
++p;
}
return 0;
} 