[C/C++標准庫]_[初級]_[map的查找函數分析]

[C/C++標准庫]_[初級]_[map的查找函數分析]

場景:

1. map在查找非數值索引(數值非重復索引可以使用vector)的對象時是高效率的,因為用的紅黑樹的實現,查找和插入都是logarithmic time 效率很高.

2.map可以說是很實用的數據結構.

3.使用multimap可以存儲重復key,使用場景就是1對多的情況,比如一個聯系人對應多個分組.

void TestMap()
{
	//map一般是通過紅黑樹來實現.http://en.cppreference.com/w/cpp/container/map
	//multimap也一樣的
	//這裡提示下map的優點是key是自動排序的,當然可以設置key的排序方式.在map的構造函數裡.
	//1.判斷map裡是否包含某個key.可以使用count和find.
	//find是找到第一個之後可以直接使用,count只是統計個數.兩個的時間其實是一樣的,
	//硬要說的話是find找到第一個之後直接結束,對於map這種只有唯一key的速度是一樣的,時間復雜度是 logarithmic time
	typedef map TMap;
	typedef multimap TTMap;
	TMap m;
	m[1] = 8;
	m[2] = 10;
	m[5] = 11;
	
	TTMap mm;
	mm.insert(pair(1,8));
	mm.insert(pair(2,10));
	mm.insert(pair(1,11));
	mm.insert(pair(1,12));

	//count
	int count = 0;
	if(count = m.count(1))
	{
		//1.如果要使用,還是得使用[]查找一次.
		//輸出: m.count(1): 1
		cout << "m.count(1): " << count << endl;
	}

	if(count = mm.count(1))
	{
		//1.如果要使用,還是得使用equal_range查找一次.
		//multimap沒有[]操作符重載,因為key不是唯一.
		//輸出 mm.count(1): 3
		cout << "mm.count(1): " << count << endl;
	}

	//查看下count的實現,是使用equal_range來實現的.
	//equal_range是獲取所有等於key的value組成一個連續的iterator,
	//其中pair第一個是匹配key的第一個iterator,第二個是大於key的第一個iterator.
	//map
	pair values =  m.equal_range(1);
	TMap::iterator b = values.first;
	//輸出 map equal_range: 8
	while(b != values.second)
	{
		cout << "map equal_range: " << (*b).second << endl;
		++b;
	}

	//multimap
	pair valuess =  mm.equal_range(1);
	TTMap::iterator bs = valuess.first;
	
	
	//輸出:
	//multimap equal_range: 8
	//multimap equal_range: 11
	//multimap equal_range: 12
	while(bs != valuess.second)
	{
		cout << "multimap equal_range: " << (*bs).second << endl;
		++bs;
	}

	//Find,找到匹配key的第一個iterator,不能找到第二個,如果需要找第二個,使用equal_range
	//Find 使用lower_bound來實現查找,lower_bound 查找大於或等於key的第一個元素.
	//與之類似的upper_bound來實現查找,它查找大於key的第一個元素.
	TMap::iterator ite = m.find(1);
	if(ite != m.end())
	{
		//1.直接使用iterator即可
		//輸出: m.find 8
		cout << "m.find " << (*ite).second << endl;;
	}
	ite = m.lower_bound(3);
	if(ite != m.end())
	{
		//輸出 m.lower_bound key 5 m.lower_bound 11
		cout << "m.lower_bound key " << (*ite).first << " m.lower_bound " << (*ite).second << endl;
	}
	//multimap
	bs = mm.lower_bound(1);
	if(ite != m.end())
	{
		//輸出: mm.lower_bound key 1 mm.lower_bound 8
		cout << "mm.lower_bound key " << (*bs).first << " mm.lower_bound " << (*bs).second << endl;
	}
	bs = mm.upper_bound(1);
	if(ite != m.end())
	{
		//輸出: mm.upper_bound key 2 mm.upper_bound 10
		cout << "mm.upper_bound key " << (*bs).first << " mm.upper_bound " << (*bs).second << endl;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	TestMap();

	return 0;
}

標准庫的源碼:

	size_type count(const key_type& _Keyval) const
		{	// count all elements that match _Keyval
		_Paircc _Ans = equal_range(_Keyval);
		size_type _Num = 0;
		_Distance(_Ans.first, _Ans.second, _Num);
		return (_Num);
		}


	iterator find(const key_type& _Keyval)
		{	// find an element in mutable sequence that matches _Keyval
		iterator _Where = lower_bound(_Keyval);
		return (_Where == end()
			|| _DEBUG_LT_PRED(this->comp,
				_Keyval, this->_Key(_Where._Mynode()))
					? end() : _Where);
		}