关联容器

分类：set, multiset, map, multimap

特点：内部元素有序排列，新元素插入的位置取决于它的值，查找速度快。

常用函数：

find: 查找等于某个值 的元素(x小于y和y小于x同时不成立即为相等)
lower_bound : 查找某个下界
upper_bound : 查找某个上界
equal_range : 同时查找上界和下界
count :计算等于某个值的元素个数(x小于y和y小于x同时不成立即为相等)
insert: 用以插入一个元素或一个区间

set

特点：

1.set是数学上集合的抽象，是一个不包含重复元素的集合，并且最多包含一个 null 元素。

2.set可以对序列可以进行查找，插入，删除元素，而完成这些操作的时间同这个序列中元素个数的对数成比例关系，

并且当游标指向一个已删除的元素时，删除操作无效。

3.更加实际的定义应该是：一个集合(set)是一个容器，它其中所包含的元素的值是唯一的。这在收集一个数据的具体

值的时候是有用的。集合中的元素按一定的顺序排列，并被作为集合中的实例。

4.一个集合通过一个链表来组织，在插入操作和删除操作上比向量(vector)快，但查找或添加末尾的元素时会有些

慢，具体实现采用了红黑树的平衡二叉树的数据结构。

成员函数

构造函数

template<class Key, class Pred = less<Key>,

class A = allocator<Key> >

class set { … }                                  //默认的顺序是less<T>

set <int> s0;  set <int, less<int> > s1;      set <int, greater<int> > s2;set <int> s4( s1 );set <int> s5( s1.begin( ), s1.begin( )+2 );

访问set中的元素

插入set中已有的元素时，忽略插入。

举例：

1.

#include <set>#include <iostream>using namespace std;int main( ){	set<int> s1;	set<int>::iterator siter1;	s1.insert(10);	s1.insert(20);	s1.insert(30);	s1.insert(90);	s1.insert(31);	cout<<"执行find(20)后，使用迭代器返回值是 ：";	siter1=s1.find(20);	cout<<*siter1<<"\n";   //20	pair<set<int>::const_iterator,set<int>::const_iterator> p1;	p1=s1.equal_range(30);	cout<<"执行equal_range(30)，后返回值情况 ："<<"\n";	cout<<"p1.first :";		cout<<*p1.first<<"\n";  //30	cout<<"p1.second :";	    cout<<*p1.second<<"\n"; //31	return 0;}

2.

#include "stdafx.h"#include <set>#include <iostream>using namespace std;int main() {	set<int> s1;	set<int>::iterator siter1;	s1.insert(10);	s1.insert(20);	s1.insert(30);	s1.insert(40);	cout<<"当值是25时  ";	cout<<"upper_bound(25)的返回值 ：";	siter1=s1.upper_bound(25);	cout<<*siter1<<"  ";                    //30	cout<<"lower_bound(25)的返回值 ：";	siter1=s1.lower_bound(25);              //30	cout<<*siter1<<"  ";    cout<<"\n";	cout<<"当值是30时  ";	cout<<"upper_bound(30)的返回值 ：";	siter1=s1.upper_bound(30);              //40	cout<<*siter1<<"  ";	cout<<"lower_bound(30)的返回值 ：";	siter1=s1.lower_bound(30);	cout<<*siter1<<"  ";                    //30    cout<<"\n";	getchar();	return 0;}

multiset

特点：

1.set和multiset的区别是：set插入的元素不能相同，但是multiset可以相同。

2.删除：如果删除元素a,那么在定义的比较关系下和a相等的所有元素都会被删除

3.count( a )：set能返回0或者1，multiset是有多少个返回多少个。

map

特点：

1.map提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的

值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。

2.这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自

动排序的功能，所以在map内部所有的数据都是有序的。

3.映射和多重映射基于某一类型Key的键集的存在，提供对T类型的数据进行快速和高效的检索。

4.对map而言，键只是指存储在容器中的某一成员。

5.map不支持副本键，multimap支持副本键。map和multimap对象包涵了键和各个键有关的值，键和值的数据类

型是不相同的，这与set不同。set中的key和value是Key类型的，而map中的key和value是一个pair结构中的两个分

量。

成员函数

构造函数

template<class Key, class T, class Pred = less<Key>,class A = allocator<T> > class map {     ….    typedef pair<const Key, T> value_type;     …….};

map 中的元素都是pair模板类对象。关键字(first成员变量)各不相同。元素按照关键字从小到大排列，缺省情况下用

less<Key>,即“<” 定义“小于”。

   map <int, int> m0;   map <int, int, less<int> > m1;   map <int, int, greater<int> > m2;   map <int, int> m4( m1 );   map <int, int> m5(m1.begin( ), m1.begin( )+2);

访问map中的元素

举例：

#include "stdafx.h"#include <map>#include <iostream>using namespace std;int main(){	map<int,float> map1;	map1.insert(map<int,float>::value_type(1,1.1f));	map1.insert(pair<int,float>(2,2.1f));	map1[3]=3.3f;	map<int,float>::iterator miter;	miter=map1.begin();	cout<<"通过(*miter)访问，begin()的返回值 :";	cout<<(*miter).first<<"   "<<(*miter).second;	cout<<"\n";                                    // 1   1.1	cout<<"通过miter->访问，begin()的返回值 :";	cout<<miter->first<<"    "<<miter->second;     // 1   1.1	getchar();	return 0;}

multimap

特点：

1.multimap中的元素由 <关键字,值>组成，每个元素是一个pair对象，关键字就是first成员变量,其类型是Key

2.multimap 中允许多个元素的关键字相同。

3.元素按照first成员变量从小到大排列，缺省情况下用 less<Key> 定义关键字的“小于”关系。

举例

#include "stdafx.h"#include <map>#include <iostream>using namespace std;int main(  ){	map<int,float> map1;	map1.insert(map<int,float>::value_type(1,1.1f));	map1.insert(pair<int,float>(1,2.1f));	map1.insert(pair<int,float>(2,2.1f));	map1[3]=3.3f;	cout<<"map1 :"<<"\n";	map<int,float>::iterator miter;	for(miter=map1.begin();miter!=map1.end();miter++)	cout<<(*miter).first<<"   "<<(*miter).second<<"\n";	cout<<"\n";	cout<<"\n";         	multimap<int,float> map2;	map2.insert(map<int,float>::value_type(1,1.1f));	map2.insert(pair<int,float>(1,2.1f));	map2.insert(pair<int,float>(2,2.1f));	cout<<"map2 :"<<"\n";	multimap<int,float>::iterator miter1;	for(miter1=map2.begin();miter1!=map2.end();miter1++)	cout<<(*miter1).first<<"   "<<(*miter1).second<<"\n";	getchar();	return 0;}

输出：