STL—multimap

multimap 是属于关联容器的一个（其它三个是map、set、multiset），关联容器的插入、删除和查找时间都相同，为O( log(N) 。在学习 multimap 之前最好得先对 map 和 pair 有一定的了解。

multimap是一个允许有多个同键元素的map。其接口与map接口基本相同，只有以下几点改变：

multimap 没有提供operator[ ]。由于一个键可能对应多个元素，所以这个操作符没有意义。
multimap上的插入总会成功。因此，多映射（multimap）insert（）增加一个元素时，并不需要返回 iterator 和 bool 的 pair 。它只返回 iterator 。

tips: multimaps 允许插入相同的键/值对。如果想避免这种冗余性，必须在插入新元素之前先显式做检查。

multimap 最难得部分是查找元素。不能使用operator [ ] ，因为没有提供这个操作符。find（）不是特别有用，因为它返回的 iterator 会指示有给定键值的任何元素（不一定是有该键的第一个元素）。

幸运的是，multimap 会把所有带相同键的元素存储在一起，而且提供了一些方法来得到容器中同键元素子区间的相应 iterator。lower_bound( ) 和 upper_bound( ) 都返回一个 iterator ，分别指示第一个元素和越过最后元素的“元素”。如果不存在与该键匹配的元素，则 lower_bound( ) 和 upper_bound( ) 返回的 iterator 相等。

如果不想分别调用两个方法来得到界定给定键元素的 iterator ，multimap 还提供了一个 equal_range( ) 方法，它会返回 lower_bound( ) 和 upper_bound( ) 所返回两个 iterator 的一个 pair。

下面的例子展示了这些方法的使用。

tips：lower_bound( )、upper_bound( ) 和 equal_range( ) 方法在 map 中也有，但是用途很有限。

多映射示例：好友列表

大多数在线聊天程序允许用户有一个“好友列表”或朋友列表。聊天程序会对好友列表中列出的用户授予特权，如允许他们向用户主动发送消息。

为在线聊天程序实现好友列表的一种方法是把信息存储在一个 multimap 中。一个 multimap 可以存储所有用户的好友列表。容器中的每一项存储对应一个用户的好友。键是用户，值是好友。例如，“张三”和“李四”都在对方的好友列表中，那么就会有形式如下的两项:"张三"映射至“李四“和”李四“映射至”张三“。multimap 允许同一个键有多个值，因此一个用户可以有多个好友。以下是 BuddyList 类定义。

#include<map>
#include<string>
#include<list>

using std::multimap;
using std::string;
using std::list;

class BuddyList
{
public:
	BuddyList();

	//adds buddy as a friend of name 
    void addBuddy(const string& name,const string& buddy);

	//removes buddy as a friend of name 
	void removeBuddy(const string& name ,const string& buddy);

	//returns true if buddy is a friend of name,otherwise returns false
	bool isBuddy(const string& name,const string& buddy);

	//retrieves a list of all the friends name
	list<string> getBuddies(const string& name) const;
	
protected:
	multimap<string, string> mBuddies;

private:
	BuddyList(const BuddyList& src);
	BuddyList& operator=(const BuddyList&rhs);
};

以下是实现。它展示了 lower_bound( )、upper_bound( ) 和 equal_range( ) 的使用。

#include "BuddyList.h"
using namespace std;

BuddyList::BuddyList()
{

}

void BuddyList::addBuddy(const string& name,const string& buddy)
{
	//make sure this buddy isn't already there,we don't want to insert a identical copy of the key/value pair.
	if(!isBuddy(name,buddy))
	{
		mBuddies.insert(make_pair(name, buddy));
	}
}

void BuddyList::removeBuddy(const string& name ,const string& buddy)
{
	//declare two iterators into the map.
	multimap<string, string>::iterator start, end;

	//obtain the beginning and end of the range of elements with key name.
	//use both lower_bound() and upper_bound() to demonstrate their use.
	//otherwise, could just call equal_range().
	//lower_bound()和upper_bound()都返回一个iterator,分别指示第一个元素和越过最后元素的“元素”。
	start = mBuddies.lower_bound(name);
	end = mBuddies.upper_bound(name);

	//iterate through the elements with key name looking for a value buddy
	for(start; start !=end; ++start)
	{
		//we found a match! remove it from the map
		if(start->second == buddy)
		{
		   mBuddies.erase(start);
		   break;
		}
	}
}

bool BuddyList::isBuddy(const string& name,const string& buddy)
{
	//declare two iterators into the map.
	multimap<string, string>::iterator start, end;

	//obtain the beginning and end of the range of elements with key name.
	//use both lower_bound() and upper_bound() to demonstrate their use.
	//otherwise, could just call equal_range().
	start =mBuddies.lower_bound(name);
	end = mBuddies.upper_bound(name);

	//iterate through the element with key name looking for a value buddy. if there
	//are no elements whit key name,start equals end,so the loop body doesn't execute.
	for(start; start!=end;++start)
		if(start->second ==buddy)
			//we found a match!
			return true;
		//no matchs
		return false;
}

list<string> BuddyList::getBuddies(const string& name) const
{
	//create a variable to store the pair of iterators.
	pair<multimap<string,string>::const_iterator,multimap<string,string>::const_iterator> its;

	//obtain the pair of iterators marking the range containing elements with key name.
	its = mBuddies.equal_range(name);

	//create a list with all the names in the range
	//(all the buddies of name)
	list<string> buddies;
	for(its.first; its.first !=its.second; ++its.first)
	{
		buddies.push_back((its.first)->second);
	}

	return buddies;
}

要注意，removeBuddy( ) 不能只是使用 ”完全删除“ 版本的 erase ( )，即把有给定键的所有元素都删除，因为它应当只删除给定键的一个元素，而非全部。还有注意，getBuddies( )不能使用 list 的 insert( ) 在 equal_range( ) 返回的区间内插入元素，因为 multimap iterator 指示的元素是键/值对，而不是 string 。getBuddies( ) 必须显式地迭代处理 list ，从各个键/值抽取出 string ，并将其压入到待返回的新 list 中。

以下是BuddyList 的一个简单测试。

#include "BuddyList.h"
#include<iostream>
using namespace std;

int main()
{
	BuddyList buddies;

	buddies.addBuddy("Harry Potter","Ron Weasley");
	buddies.addBuddy("Harry Potter","Hermione Granger");
	buddies.addBuddy("Harry Potter","Hagid");
	buddies.addBuddy("Harry Potter","Draco Malfoy");

	//That's not right! remove Draco
	buddies.removeBuddy("Harry Potter","Draco Malfoy");
	
	buddies.addBuddy("Hagrid","Harry Potter");
	buddies.addBuddy("Hagrid","Ron Weasley");
	buddies.addBuddy("Hagrid","Hermione Granger");

	list<string> harryBuds = buddies.getBuddies("Harry Potter");

	cout<<"Harry's friends:\n";
	for(list<string>::const_iterator it = harryBuds.begin();
	it != harryBuds.end(); ++it)
	{
		cout<<"\t"<<*it<<endl;
	}

	return 0;

}

运行结果如下：

以上代码下载链接：http://download.csdn.net/detail/chaoyuan899/5476205