各类map效率比较实用2(151)

1、果然大数据hash表虐红黑树了。


2、但是唯一确定的是unordered_map > hash_map > map,官方也是如此认为的，前面map虽然高效，但是开辟的内存却是更多，也更难使用。（见146使用方法）

3、使用数据，50000存储，2000查询

4、现象，map在上万的查询就各种内存泄露了，cmap依旧需要removeall释放。map性能可能更差，上千未测试map的数据；

下面是代码：++

// test.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <afx.h>
#include <stdio.h>
#include <iostream>
#include <deque>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <hash_map>
#include <xhash>
#include <vector>
#include <stdarg.h>
#include <afxtempl.h>
#include <functional>
#include <algorithm>


using namespace std;

typedef struct TDATA0 {
	int year;
	int month;
	int day;
} *PTDATA0;
typedef struct TDATA1 {
	TDATA1& operator= (TDATA1& t) {
		name = t.name;
		adress = t.adress;
		parents = t.parents;
		brithday = t.brithday;
		return *this;
	}
	CString name;
	CString adress;
	CString parents;
	TDATA0 brithday;
} *PTDATA1;

typedef struct FINDDATA {
	FINDDATA(int in) {
		index = in;
		::CoCreateGuid(&findguid);
	}
	~FINDDATA() {}
	operator int () {
		return index;
	}
	int index;
	GUID findguid;
} *PFINDDATA;

std::wstring GUIDToWstring(GUID* guid) {
	wchar_t guid_string[37];
	swprintf(
		guid_string, sizeof(guid_string) / sizeof(guid_string[0]),
		L"%08x-%04x-%04x-%02x%02x-%02x%02x%02x%02x%02x%02x",
		guid->Data1, guid->Data2, guid->Data3,
		guid->Data4[0], guid->Data4[1], guid->Data4[2],
		guid->Data4[3], guid->Data4[4], guid->Data4[5],
		guid->Data4[6], guid->Data4[7]);
	return guid_string;
}
struct WCharLess : public binary_function<const wchar_t*, const wchar_t*, bool>  
{  
public:  
	result_type operator()(const first_argument_type& _Left, const second_argument_type& _Right) const  
	{  
		return(_wcsicmp(_Left, _Right) < 0 ? true : false);
	}  
};
//struct KeyHasher
//{
//	std::size_t operator()(const CString& k) const
//	{
//		using std::size_t;
//		using std::tr1::hash;
//
//		return (hash<CString>()(k));
//	}
//};
typedef std::queue<FINDDATA> stru_find;
typedef std::map<CString, TDATA1> map_d_type;
typedef stdext::hash_map<CString, TDATA1, stdext::hash_compare<const wchar_t*, WCharLess>> hashmap_d_type;
typedef std::tr1::unordered_map<wstring, TDATA1> unordemap_d_type;
typedef std::vector<std::pair<CString, TDATA1>> vecpair_d_type;
typedef CMap<CString, LPCTSTR, TDATA1, TDATA1&> cmap_d_type;

void createfinddata(stru_find& find) {
	for (int i = 2000; i < 4000; i++)
	{
		find.push(FINDDATA(i));
	}
	find.push(0);
}
size_t loadCmapData(stru_find find, cmap_d_type &test_data) {
	for (int i = 1; i <= 50000; i++)
	{
		GUID guid;
		wchar_t strbuffer[10] = {0};

		_itow(i, strbuffer, 10);

		TDATA1 t ;
		t.name = _T("name");
		t.name += strbuffer;
		t.adress = _T("address");
		t.adress += strbuffer;
		t.parents = _T("parents");
		t.parents += strbuffer;
		t.brithday.year = t.brithday.month = t.brithday.day = i;


		::CoCreateGuid(&guid);
		if (i == find.front()) {
			guid = find.front().findguid;
			find.pop();
		}
		
		CString temp(GUIDToWstring(&guid).c_str());
		test_data.SetAt(temp, t);
	}
	return test_data.GetSize();
}
void printfcmap(stru_find& find, cmap_d_type &test_data) {
	TDATA1 out;
	BOOL b;
	CString temp;

	int n = find.size();
	for (int i = 0; i < n; i++)
	{
		temp.Empty();
		temp.Append(GUIDToWstring(&find.front().findguid).c_str());
		b = test_data.Lookup(temp, out);
		if (b) {
			wcout << endl << L"find count: " << find.size() << "find index:"<< find.front() << endl
				<< "data key :" << temp.GetString()  << endl
				<< L"name :" << out.name.GetString()<< endl
				<< L"address :"<< out.adress.GetString() <<endl
				<< L"parents :"<<out.parents.GetString() << endl
				<< L"birthday :" << out.brithday.year << " "<< out.brithday.month<<" "<<out.brithday.day << endl;
			find.pop();
		}
	}
}

size_t loadMapData(stru_find findata, map_d_type& mapdata) {
	for (int i = 1; i <= 50000; i++)
	{
		GUID guid;
		wchar_t strbuffer[10] = {0};
		_itow(i, strbuffer, 10);

		TDATA1 t ;
		t.name = _T("name");
		t.name += strbuffer;
		t.adress = _T("address");
		t.adress += strbuffer;
		t.parents = _T("parents");
		t.parents += strbuffer;
		t.brithday.year = t.brithday.month = t.brithday.day = i;


		::CoCreateGuid(&guid);
		if (i == findata.front()) {
			guid = findata.front().findguid;
			findata.pop();
		}

		CString temp(GUIDToWstring(&guid).c_str());
		mapdata.insert(map_d_type::value_type(temp, t));
	}
	return mapdata.size();
}

void printfmap(stru_find& find, map_d_type &test_data) {
	
	CString temp;

	int n = find.size();
	for (int i = 0; i < n; i++)
	{
		temp.Empty();
		temp.Append(GUIDToWstring(&find.front().findguid).c_str());
		map_d_type::iterator ifind = test_data.find(temp);
		//map_d_type::iterator ifind ;
		//out = (*ifind).second;
		if (ifind != test_data.end()) {
			wcout << endl << L"left find count: " << find.size() << " find index:"<< find.front() << endl
				<< "data key :" << temp.GetString()  << endl
				<< L"name :" << (*ifind).second.name.GetString()<< endl
				<< L"address :"<< (*ifind).second.adress.GetString() <<endl
				<< L"parents :"<<(*ifind).second.parents.GetString() << endl
				<< L"birthday :" << (*ifind).second.brithday.year << " "<< (*ifind).second.brithday.month<<" "<<(*ifind).second.brithday.day << endl;
			find.pop();
		}
	}
}

size_t loadUnoderMapData(stru_find findata, unordemap_d_type& test_data) {
	test_data.rehash(50000);
	for (int i = 1; i <= 50000; i++)
	{
		GUID guid;
		wchar_t strbuffer[10] = {0};
		_itow(i, strbuffer, 10);

		TDATA1 t ;
		t.name = _T("name");
		t.name += strbuffer;
		t.adress = _T("address");
		t.adress += strbuffer;
		t.parents = _T("parents");
		t.parents += strbuffer;
		t.brithday.year = t.brithday.month = t.brithday.day = i;


		::CoCreateGuid(&guid);
		if (i == findata.front()) {
			guid = findata.front().findguid;
			findata.pop();
		}

		wstring temp(GUIDToWstring(&guid).c_str());

		test_data.insert(unordemap_d_type::value_type(temp, t));
	}
	return test_data.size();
}

void printUnoderMap(stru_find findata, unordemap_d_type& test_data) {
	wstring temp;

	int n = findata.size();
	for (int i = 0; i < n; i++)
	{
		//temp.empty();
		temp = (GUIDToWstring(&findata.front().findguid));
		unordemap_d_type::iterator ifind = test_data.find(temp);
		
		if (ifind != test_data.end()) {
			wcout << endl << L"left find count: " << findata.size() << " find index:"<< findata.front() << endl
				<< "data key :" << temp  << endl
				<< L"name :" << (*ifind).second.name.GetString()<< endl
				<< L"address :"<< (*ifind).second.adress.GetString() <<endl
				<< L"parents :"<<(*ifind).second.parents.GetString() << endl
				<< L"birthday :" << (*ifind).second.brithday.year << " "<< (*ifind).second.brithday.month<<" "<<(*ifind).second.brithday.day << endl;
			findata.pop();
		}
	}
}


size_t loadHashMapData(stru_find findata, hashmap_d_type& test_data) {
	test_data.rehash(50000);
	for (int i = 1; i <= 50000; i++)
	{
		GUID guid;
		wchar_t strbuffer[10] = {0};
		_itow(i, strbuffer, 10);

		TDATA1 t ;
		t.name = _T("name");
		t.name += strbuffer;
		t.adress = _T("address");
		t.adress += strbuffer;
		t.parents = _T("parents");
		t.parents += strbuffer;
		t.brithday.year = t.brithday.month = t.brithday.day = i;


		::CoCreateGuid(&guid);
		if (i == findata.front()) {
			guid = findata.front().findguid;
			findata.pop();
		}

		CString temp(GUIDToWstring(&guid).c_str());

		test_data.insert(hashmap_d_type::value_type(temp, t));
	}
	return test_data.size();
}

void printHashMap(stru_find findata, hashmap_d_type& test_data) {
	CString temp;

	int n = findata.size();
	for (int i = 0; i < n; i++)
	{
		temp.Empty();
		temp.Append(GUIDToWstring(&findata.front().findguid).c_str());
		hashmap_d_type::iterator ifind = test_data.find(temp);
		
		if (ifind != test_data.end()) {
			wcout << endl << L"left find count: " << findata.size() << " find index:"<< findata.front() << endl
				<< "data key :" << temp.GetString()  << endl
				<< L"name :" << (*ifind).second.name.GetString()<< endl
				<< L"address :"<< (*ifind).second.adress.GetString() <<endl
				<< L"parents :"<<(*ifind).second.parents.GetString() << endl
				<< L"birthday :" << (*ifind).second.brithday.year << " "<< (*ifind).second.brithday.month<<" "<<(*ifind).second.brithday.day << endl;
			findata.pop();
		}
	}
}
int _tmain(int argc, _TCHAR* argv[])
{
	size_t loadsize = 0;
	string loadtype;

	stru_find finddata;
	map_d_type	test_mapdata;
	cmap_d_type test_cmapdata;
	hashmap_d_type test_hashmapdata;
	unordemap_d_type test_unordermapdata;

	createfinddata(finddata);

	time_t start = clock();
	//loadsize = loadMapData(finddata, test_mapdata);loadtype.empty();loadtype.append("In map type:");
	//loadsize = loadCmapData(finddata, test_cmapdata);loadtype.empty();loadtype.append("In cmap type:");
	//loadsize = loadHashMapData(finddata, test_hashmapdata); loadtype.empty();loadtype.append("In hash_map type:");
	loadsize = loadUnoderMapData(finddata, test_unordermapdata); loadtype.empty();loadtype.append("In unordered_map type:");
	time_t end = clock();
	cout << loadtype << endl << "load "<< loadsize <<" data useing time:" << end - start << "/ms" << endl;
	
	start = clock();
	//printfmap(finddata, test_mapdata);
	//printfcmap(finddata, test_cmapdata);
	//printHashMap(finddata, test_hashmapdata);
	printUnoderMap(finddata, test_unordermapdata);
	end = clock();
	test_mapdata.clear();
	test_cmapdata.RemoveAll();
	cout << endl << "find "<<finddata.size()<<" data using time:" << end - start << "/ms" << endl;
	
	system("pause");
	return 0;
}