std::hash_mapの使用

std::hash_mapの使用(VC 2010ベース)
 
一. std::hash_mapの定義
// std::hash_mapの定義

template >,	//      (            )
	class _Alloc = allocator > >	//      
	class hash_map : public _Hash<_hmap_traits _ty="" _tr="" _alloc="" false=""> >	//   (  )
{
......
}

二. std::hash_mapのハッシュ比較器
// std::hash_mapのハッシュ比較器
//ハッシュ比較器はハッシュアルゴリズムに関連するはず
//ハッシュ比較器にはstd::mapと同じデフォルトのless比較器が使用されています.

template >
class hash_compare
{	// traits class for hash containers
public:
	enum
	{	// parameters for hash table
		bucket_size = 1		// 0 < bucket_size
	};
	
	// construct with default comparator
	hash_compare() : comp()
	{}
	
	// construct with _Pred comparator
	hash_compare(_Pr _Pred) : comp(_Pred)
	{}

	// Hash function
	//           (           ,     ),      
	size_t operator()(const _Kty& _Keyval) const
	{	// hash _Keyval to size_t value by pseudorandomizing transform
		long _Quot = (long)(hash_value(_Keyval) & LONG_MAX);
		ldiv_t _Qrem = _CSTD ldiv(_Quot, 127773);

		_Qrem.rem = 16807 * _Qrem.rem - 2836 * _Qrem.quot;
		if (_Qrem.rem < 0)
			_Qrem.rem += LONG_MAX;
		return ((size_t)_Qrem.rem);
	}

	bool operator()(const _Kty& _Keyval1, const _Kty& _Keyval2) const
	{	// test if _Keyval1 ordered before _Keyval2
		return (comp(_Keyval1, _Keyval2));					//          less   
	}

protected:
	_Pr comp;	// the comparator object
};

 
三.使用
//使用コードを見る

#include "stdafx.h"
#include 
#include 

//     std::map   
typedef std::string* PSTDString;

template
struct PLess	
{
	// functor for operator<
	bool operator()(const _Ty& pLeft, const _Ty& pRight) const
	{
		// apply operator< to operands
		return (*pLeft) < (*pRight);		//                 
	}
};

int _tmain(int argc, _TCHAR* argv[])
{
	//       std::hash_map std::hash_compare.   
	// std::hash_compare                .
	std::hash_map > > PStringToIntMap1;

	//       std::map  
	std::string str1 = "1";
	std::string str2 = "2";
	std::string str3 = "3";
	PStringToIntMap1[&str1] = 3;
	PStringToIntMap1[&str2] = 2;
	PStringToIntMap1[&str3] = 1;

	return 0;
}

四.std::mapとの比較
std::hash_mapの時間複雑度はO(1)--O(N):不安定であるがmapより速い.
std::mapの時間複雑度はO(log 2 N):比hash_mapは遅いが安定している.あなたの使用場面を見てください.STLでの使用上は完全に互いに置き換えることができる.