项目中要对一些数据结构进行存取,而项目本身对时间延时比较敏感,在使用vector还是map上着实纠结了一番,主要某些数据量比较小,才有此纠结。
而且想搞明白,到底大到什么数据量该用map?做了一些简单的测试,见下。
首先,不管是vector还是map,请尽量存取指针,否则在存取时会有数据拷贝带来不必要的时间损失。通常用int和string做key的场景比较普遍(我的项目即如此),能用int作key就用int作key,效率比string高。
测试方法:
给vector和map容器中分别塞入1,000,000个数据(顺序插入,有序的),然后设定一个查找目标,vector顺序遍历查找,map用key查找,对比查找时间。使用高精度定时器计时。
基本结论:
1、unordered_map比map快
2、vector查找14次,基本和unordered_map查找一次耗时相当(int和string做key差别不大)
3、string作key,vector查询100次,基本和map查询一次耗时相当;int作key,vector查询28次,基本和map查询一次耗时相当
4、boost的unordered_map和map与STL的效率基本相同
因此:抛弃map,用unordered_map吧。如果明确数据量小,比如小于14个,就用vector或数组,效率更高。
unordered_map<string,...>
unordered_map<int,...>
map<string, ...>
map<int,...>
测试代码:
- #include <windows.h>
- #include <string>
- #include <iostream>
- #include <iomanip>
- #include <map>
- #include <unordered_map>
- #include <boost/unordered_map.hpp>
- #include <boost/interprocess/containers/map.hpp>
- #include <algorithm>
- using namespace std;
- struct MyStruct
- {
- MyStruct() {}
- MyStruct(int x, string s) : i(x), str(s) {}
- int i;
- string str;
- };
- #define VECTOR_TEST_DEF std::vector<MyStruct*>
- //#define STRING_KEY
- #define MAP_TYPE std::map
- //#define MAP_TYPE std::unordered_map
- //#define MAP_TYPE boost::unordered_map
- //#define MAP_TYPE boost::interprocess::map
- #define MAP_TYPE_STR "std::map"
- //#define MAP_TYPE_STR "std::unordered_map"
- //#define MAP_TYPE_STR "boost::unordered_map"
- //#define MAP_TYPE_STR "boost::interprocess::map"
- #ifdef STRING_KEY
- #define MAP_TEST_DEF MAP_TYPE<string, MyStruct*>
- #define TARGET_VAL "100"
- #else
- #define MAP_TEST_DEF MAP_TYPE<int, MyStruct*>
- #define TARGET_VAL 28
- #endif
- #define DATA_COUNT 1000000
- #define LOOP_COUNT 10000
- LARGE_INTEGER m_counterFreq;
- MyStruct* vectorRet;
- MyStruct* mapRet;
- string ToString(int d)
- {
- char szBuf[8];
- sprintf_s(szBuf, "%d", d);
- return string(szBuf);
- }
- LONGLONG GetMicroSecCounter()
- {
- LARGE_INTEGER counter = { 0 };
- QueryPerformanceCounter(&counter);
- return counter.QuadPart * 1000000 / m_counterFreq.QuadPart;
- }
- string GetTimeDiffMillSecStr(LONGLONG microCounterBegin, LONGLONG micoCounterEnd)
- {
- double dblDiff = (micoCounterEnd - microCounterBegin) / (double)1000;
- char szBuf[32];
- sprintf_s(szBuf, "%.3fms", dblDiff);
- return szBuf;
- }
- void TestVectorMap()
- {
- VECTOR_TEST_DEF vecTest;
- MAP_TEST_DEF mapTest;
- QueryPerformanceFrequency(&m_counterFreq);
- vecTest.resize(DATA_COUNT);
- for (int i = 0; i < DATA_COUNT; i++)
- {
- string str = ToString(i);
- MyStruct* t = new MyStruct(i, str);
- vecTest[i] = t;
- #ifdef STRING_KEY
- mapTest[str] = t;
- #else
- mapTest[i] = t;
- #endif // STRING_KEY
- }
- LONGLONG t1 = HighPreciseTickCounter::GetMicroSecCounter();
- VECTOR_TEST_DEF::iterator iterVec;
- for (int i = 0; i < LOOP_COUNT; i++)
- {
- iterVec = vecTest.begin();
- for (; iterVec != vecTest.end(); iterVec++)
- {
- #ifdef STRING_KEY
- if (!strcmp((*iterVec)->str.c_str(), TARGET_VAL))
- #else
- if ((*iterVec)->i == TARGET_VAL)
- #endif // STRING_KEY
- {
- vectorRet = *iterVec;
- break;
- }
- }
- }
- LONGLONG t2 = HighPreciseTickCounter::GetMicroSecCounter();
- MAP_TEST_DEF::iterator iterMap;
- for (int i = 0; i < LOOP_COUNT; i++)
- {
- #ifdef STRING_KEY
- iterMap = mapTest.find(TARGET_VAL);
- #else
- iterMap = mapTest.find(TARGET_VAL);
- #endif // STRING_KEY
- if (iterMap != mapTest.end())
- mapRet = iterMap->second;
- }
- LONGLONG t3 = HighPreciseTickCounter::GetMicroSecCounter();
- #ifdef STRING_KEY
- string keyType = "<string, MyStruct*>";
- #else
- string keyType = "<int, MyStruct*>";
- #endif // STRING_KEY
- std::cout << setiosflags(ios::left);
- std::cout << setw(20) << "Find Target Val: " << TARGET_VAL << std::endl;
- std::cout << setw(20) << "Find Loop Count: " << LOOP_COUNT << std::endl;
- std::cout << setw(20) << "Find Cost Vector: " << GetTimeDiffMillSecStr(t1, t2) << std::endl;
- std::cout << setw(20) << "Find Cost Map: " << GetTimeDiffMillSecStr(t2, t3) << " " << MAP_TYPE_STR << keyType << std::endl;
- cout << setw(20) << "Vector Find: " << vectorRet->str << endl;
- cout << setw(20) << "Map Find: " << mapRet->str << endl;
- for (int i = 0; i < DATA_COUNT; i++)
- {
- MyStruct* t = vecTest[i];
- delete t;
- }
- }
Find Target Val: 50098
Find Vector(Int) Cost : 0.053ms //因为int比较很快,所以仅查找int肯定是vector胜出,因此以此为基准对比
Find Vector(Str) Cost : 3.872ms //不知道是不是因为小编的编译器问题,字符串对比非常慢,此处将查找次数改成了100,否则根本无法使用
Find Map(Int) Cost : 0.241ms //Map的Int查找还可以,为基准的5倍
Find Map(String) Cost : 0.748ms //Map的string查找为基准的15倍,但比vector查找字符串要快的多
UnorderMap(Int) Cost : 0.083ms //Unordered Map果然速度优秀,int索引仅为基准的1.6倍,速度基本没差
UnorderMap(Str) Cost : 0.107ms //Unordered Map的字符串搜索也非常优秀,仅为基准的2倍,和int相差无几,证明hash表搜索堪称极速
Index Vector Cost : 0.002ms
Index Vector(at) Cost : 0.001ms
Index Vector(it) Cost : 0.066ms
(进程 16768)已退出,代码为 0。
要在调试停止时自动关闭控制台,请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .