std::map find和count效率测试

1、简介
  在使用标准模板库中的map容器且遇到键值对的值为自定义struct或class类型时，考虑到特殊场景（即不能确保key自始至终唯一），若插入新元素（new 对象），在程序执行结束释放内存时会造成内存泄露（重复的key对应的value所申请的内存空间）。
  因此在插入新元素前需要判断key是否已经存在，若存在则考虑删除之前的键值后再进行新元素的插入，或者直接忽略此次插入操作。此时可以使用find及count函数进行判断，find(x)功能是在map中搜索键为x的元素，若找到则返回迭代器（位置），否则返回迭代器为map::end（即容器末尾元素）；count(x)功能是在map中搜索键为x的元素，并返回具有该键的元素个数，因为map容器不允许重复键，函数实际上只返回0或1。
  下面通过代码来分析下两个函数在map中判断元素是否存在的效率差异。

2、代码

#include <iostream>
#include <sstream>
#include <Windows.h>
#include <ctime>
#include <map>
#include <string>
using namespace std;

#define MAX_NUM 500000

int main()
{
	time_t tBegin, tEnd;//时间戳，计算代码段执行时间

	//键值为int类型的map
	map<int, int> mapInt;
	for(int i=0; i<MAX_NUM; i++)
	{
		mapInt.insert(make_pair(i, i));
		//或mapInt[i] = i; 区别为遇到重复键时，insert不会覆盖值，[]会覆盖值
	}
	
	map<int, int>::iterator iterInt;
	tBegin = clock();
	for(int i=0; i<MAX_NUM; i++)
	{
		iterInt = mapInt.find((MAX_NUM/2));
	}
	tEnd = clock();
	cout << "int-find  耗时" << (tEnd-tBegin) << "毫秒" << endl;

	int nRtn = 0;
	tBegin = clock();
	for(int i=0; i<MAX_NUM; i++)
	{
		nRtn = mapInt.count((MAX_NUM/2));
	}
	tEnd = clock();
	cout << "int-count 耗时" << (tEnd-tBegin) << "毫秒" << endl << endl;

	//键值为string类型的map
	map<string, string> mapString;
	for(int i=0; i<MAX_NUM; i++)
	{
		stringstream ss;
		ss << i; 
		string str = ss.str();
		str = "string" + str;
		mapString[str] = str;//或mapString.insert(make_pair(str, str));
	}

	map<string, string>::iterator iterStr;
	tBegin = clock();
	for(int i=0; i<MAX_NUM; i++)
	{
		iterStr = mapString.find("string250000");
	}
	tEnd = clock();
	cout << "string-find  耗时" << (tEnd-tBegin) << "毫秒" << endl;

	tBegin = clock();
	for(int i=0; i<MAX_NUM; i++)
	{
		nRtn = mapString.count("string250000");
	}
	tEnd = clock();
	cout << "string-count 耗时" << (tEnd-tBegin) << "毫秒" << endl;

	getchar();
	return 0;
}

3、运行结果
  运行环境：Win10-64位 + VS2010-Win32

图1 debug模式

图2 release模式

4、总结
  通过运行结果可以看出find函数比count执行时间短，效率快了约一倍。