STL 关联容器

关联容器的定义
STL中的关联容器有map、multimap、set、multiset。<是默认的比较运算符，但可能有个比较函数参数。这些容器提供了双向迭代器。
Map类存储（键，值）时，他们按照唯一的键来排序。Pair在<utility>中定义。Map的一个有效地功能是可使用运算符[]通过其键来建立下标。由于下标功能在map中提供，所以值可以通过insert函数输入到map中，还可以通过数组类型的赋值来输入，例如下面的语句：Month["December"]=31;
Map类的部分规范如下：

Template<class Key,class T,class Compare=less<Key>>
class map
{
	  public:
		 explicit map(const Compare &cmp=Compare());
		 //Default constructor
		 //Precondition :none
		 //postcondition :the map object is initialized to be empty
		 //the default comparison operator is <
		 //A comparision function object may be supplied

		 template<class InputIter>
		 map(InputIter first,InputIter last,
				 const Compare &comp=Compare());
		 //Constructor :map is initialized with length last-first
		 //and filled with all values from the derefenced
		 //input iterators on the range[first,last].
		 //precondition :none;
		 //Postcondition :the map contains input itertors in the
		 //range[first,last].if a function comp is supplied,it
		 //is used to compare elements of the  map
		 
		 bool empty()const;
		//determines whether the map is empty
		//precondition :none
		//postcondition :Returns true if the map is empty
		//otherwise returns false

		size_type size()const;
	       //Determines the size of the map
	       //the returns type size_type is an integral type
	       //precondition :none;
	       //Postcondition :returns the number of elements
	       
	       Iter insert(const value_type &e);
	       Iter insert(Iter i,const value_type &e);
	       //inserts element pair e into the map if a value_type
	       //with the same key is not already present in the map
	       //Takes an optional iterator parameter as a hint as to
	       //where to insert
	       //precondition :the iterator is initialized;
	       //postcondition :Element e has been inserted into the map
	       //and an iterator to e is returned.
	       Iter erase(Iter i);
	       //removes the map element pointed to by iterator i 
	       //precondition :none
	       //postcondition :return an iterator pointing to the map
	       //element folling by removed pair.
	       //if the pair was the last element ,the value returned by 
	       //end() was returned

	       void erase(Iter first,Iter last);
	       //removes all elements in the range[first,last]
	       //precondition :none
	       //postcondition :the map has no elements in the rang[first,last];

	       Iter find(const Key_value &e)const;
	       //returns an iterator points to the element
	       //equal to e.
	       //precondition :none
	       //postcondition :if the element is in the map ,an iterator
	       //returned pointing to e; otherwise the value returned by
	       //end() was returned

	       size_type count(const Key_value &e)const;
	       //returns number of elements equal to e,
	       //precondition :none
	       //postcondition :returns number of element equal to 
	       //e .since a map has unique keys,count will always
	       //return 1 or 0;

	       Iter lower_bound(const Key_value &e)const;
	       //returns an iterator that points to the first
	       //key that is equal to or greater than e
	       //precondition:none
	       //postcondition :return  the comparison function object for
	       //the set//????

	       Iter upper_bound(const Key_value &e)const;
	       //returns an iterator that points to the first key
	       //that is greater than e;
	       //precondition :none
	       //postcondition :returns the comparison function object for 
	       //the set

	       void swap(map<key,T,Compare> &m);
	       //Exchange maps
	       //precondition :none
	       //postcondition :Exchange the contents of the map
	       //m with current map,*this

	       Iter begin();
	       //returns an iterator to the first element in the map
	       //precondition :none
	       //postcondition :if the map was empty ,the value returned
	       //by end() was returned.
	       Iter end();
	       //returns an iterator to test for the end of the map
	       //precondition :none
	       //postcondition :the value for the end of the map 
	       //was returned.

};

注意关联容器有自己的find和count函数来查找数据项。他们还可以使用lower_bound、
upper_bound 和equal_range函数返回一组相等的数据项。数据项使用insert函数添加到关联容器中。对于map和multimap，元素还可以使用下标运算符[]插入。
Multimap和multiset容器类似于对应的map和set，但他们允许键重复。当键可能有两个与它有关的值时，这是很有效的。下面的程序创建了一个map ，然后创建了一个multimap，把姓名存储为键，电话号码存储为值。multimap可以为一个姓名存储对个电话号码，而map会用同一个键覆盖另一个项目。

#include<utility>
#include<map>
#include<iostream>
#include<string>
using namespace std;
int main()
{
	//declare a map to contain names and  phone numbers
	map<string,string> phoneBook ;
	//declare a map iterator
	map<string ,string>::const_iterator it1;

	string name1="Smith, John";
	string name2="Thonpson, Julia";
	string name3="Johnson, Mary";
	string name4="Little, Carol";
	string name5="Johnson, Mary";
	string phone1="212-555-444";
	string phone2="806-555-6565";
	string phone3="445-555-7111";
	string phone4="745-555-6787";
	string phone5="745-555-7777";
	
	//assign elements to map using subscripts
	phoneBook[name1]=phone1;
	phoneBook[name2]=phone2;
	phoneBook[name3]=phone3;
	phoneBook[name4]=phone4;
	phoneBook[name5]=phone5;

	//print map elements
	for(it1=phoneBook.begin();it1!=phoneBook.end();it1++)
		cout<<it1->first<<"\t"<<it1->second<<endl;

	it1=phoneBook.find(string(name3));
	//display found map element
	if(it1!=phoneBook.end())
		cout<<" search for "<<it1->first<<"--phone numbers"<<
			endl<<it1->second<<endl<<endl;
	//create a multimap to contain names and phone numbers
	//using the mak pair function  insert elements
	multimap<string,string> phoneBook2;
	phoneBook2.insert(make_pair(name1,phone1));
	phoneBook2.insert(make_pair(name2,phone2));
	phoneBook2.insert(make_pair(name3,phone3));
	phoneBook2.insert(make_pair(name4,phone4));
	phoneBook2.insert(make_pair(name5,phone5));
	
	typedef multimap<string,string>::const_iterator Iter;
	Iter it2;

	for(it2=phoneBook2.begin();it2!=phoneBook2.end();++it2)
	{
		cout<<it2->first<<'\t'<<it2->second<<endl;
	}
	//return  map pairs with the same key
	pair<Iter,Iter>phoneNum=phoneBook2.equal_range(name3);

	//display pairs with the same key
	cout<<" Search for"<<name3<<"--phone numbers:"<<endl;

	for(it2=phoneNum.first;it2!=phoneNum.second;++it2)
		cout<<it2->second<<endl;
	return 0;
}