首页 > 代码库 > map、hash_map、unordered_map 的思考

map、hash_map、unordered_map 的思考

2024-07-14 22:54:16   221人阅读

#include <map>

map<string,int> dict;

map是基于红黑树实现的，可以快速查找一个元素是否存在，是关系型容器，能够表达两个数据之间的映射关系。

dict.insert(make_pair("abc",1));

dict.count("mn"); 看看dict中含有 mn的个数，因为元素是唯一的，所以这个返回值只有两种情况，0或者1. (multi_map就不是这样啦)

dict.find("mn");如果不存在就返回 dict.end(),如果存在就返回指向该元素的 iterator

dict["pq"]++ 相当于取出 value 来进行 ++ 再存回去，下标访问不存在的元素，将导致在map中添加一个新的元素，新的键就是该下标， value的值为默认值。

所以建立一个map的时候可以：

vector<string> L;
unordered_map<string,int> dictL;for(int i = 0; i< L.size(); i++)   dictL[L[i]] += 1;

删除元素： dict.eraser("abc"); 返回值为删除元素的个数

               dict.eraser(itr); 删除 itr 指向的元素，并且 itr 所指向元素必须是存在的，不能是 dict.end(). 这种形式的返回值为 void

遍历： for(map<string, int>::iterator itr = dict.begin(); itr != dict.end(); itr++)

               cout<< itr->first <<"  " << itr->second <<endl;

map中的元素是按照健，有序的.

 

#include<unordered_map>

unordered_map是基于hash实现的。

unordered_map的插入、删除、查找 性能都优于 hash_map 优于 map，所以首选为 unordered_map.

它的缺陷是元素是无序的，当使用时候需要元素是有序的时候，不可以用它。

性能比较参考：http://keary.cn/?p=779

下面是它比较的代码

#include <iostream>#include <stdlib.h>#include <Windows.h>#include <map>#include <hash_map>#include <unordered_map>#include <algorithm>bool MapTest(){    const unsigned int NUM_COUNT = 0xffffff;        // 数组长度    const int DEFAULT_VALUE = http://www.mamicode.com/0;                              // 键值    const unsigned int NUM_RANGE = 0xffffff;        // 随机数范围的最大值    int* szNumA = new int[NUM_COUNT];    int* szNumB = new int[NUM_COUNT];    srand(::GetTickCount());    for (unsigned int uiNum = 0; uiNum < NUM_COUNT; ++uiNum)    {        szNumA[uiNum] = (rand() * rand()) % NUM_RANGE;        szNumB[uiNum] = szNumA[uiNum];    }    for (unsigned int uiNum = 0; uiNum < NUM_COUNT; ++uiNum)    {        std::swap(szNumB[uiNum], szNumB[(rand() * rand()) % NUM_COUNT]);    }    std::map<int, int> mapNum;    std::hash_map<int, int> hMapNum;    std::unordered_map<int, int> unMapNum;    DWORD dwMap, dwHMap, dwUnMap;    // 插入测试    dwMap = ::GetTickCount();    for (unsigned int uiNum = 0; uiNum < NUM_COUNT; ++uiNum)    {        mapNum.insert(std::map<int, int>::value_type(szNumA[uiNum], 0));    }    dwMap = ::GetTickCount() - dwMap;    dwHMap = ::GetTickCount();    for (unsigned int uiNum = 0; uiNum < NUM_COUNT; ++uiNum)    {        hMapNum.insert(std::hash_map<int, int>::value_type(szNumA[uiNum], 0));    }    dwHMap = ::GetTickCount() - dwHMap;    dwUnMap = ::GetTickCount();    for (unsigned int uiNum = 0; uiNum < NUM_COUNT; ++uiNum)    {        unMapNum.insert(std::unordered_map<int, int>::value_type(szNumA[uiNum], 0));    }    dwUnMap = ::GetTickCount() - dwUnMap;    std::cout << "insert time of map is :" << dwMap << "ms" <<std::endl;    std::cout << "insert time of hash_map is :" << dwHMap << "ms" <<std::endl;    std::cout << "insert time of unordered_map is :" << dwUnMap << "ms" <<std::endl << std::endl;    // 查找测试    dwMap = ::GetTickCount();    for (unsigned int uiNum = 0; uiNum < NUM_COUNT; ++uiNum)    {        mapNum.find(szNumB[uiNum]);    }    dwMap = ::GetTickCount() - dwMap;    dwHMap = ::GetTickCount();    for (unsigned int uiNum = 0; uiNum < NUM_COUNT; ++uiNum)    {        hMapNum.find(szNumB[uiNum]);    }    dwHMap = ::GetTickCount() - dwHMap;    dwUnMap = ::GetTickCount();    for (unsigned int uiNum = 0; uiNum < NUM_COUNT; ++uiNum)    {        unMapNum.find(szNumB[uiNum]);    }    dwUnMap = ::GetTickCount() - dwUnMap;    std::cout << "search time of map is :" << dwMap << "ms" <<std::endl;    std::cout << "search time of hash_map is :" << dwHMap << "ms" <<std::endl;    std::cout << "search time of unordered_map is :" << dwUnMap << "ms" <<std::endl << std::endl;    // 删除测试    dwMap = ::GetTickCount();    for (unsigned int uiNum = 0; uiNum < NUM_COUNT; ++uiNum)    {        mapNum.erase(szNumB[uiNum]);    }    dwMap = ::GetTickCount() - dwMap;    dwHMap = ::GetTickCount();    for (unsigned int uiNum = 0; uiNum < NUM_COUNT; ++uiNum)    {        hMapNum.erase(szNumB[uiNum]);    }    dwHMap = ::GetTickCount() - dwHMap;    dwUnMap = ::GetTickCount();    for (unsigned int uiNum = 0; uiNum < NUM_COUNT; ++uiNum)    {        unMapNum.erase(szNumB[uiNum]);    }    dwUnMap = ::GetTickCount() - dwUnMap;    std::cout << "delete time of map is :" << dwMap << "ms" <<std::endl;    std::cout << "delete time of hash_map is :" << dwHMap << "ms" <<std::endl;    std::cout << "delete time of unordered_map is :" << dwUnMap << "ms" <<std::endl << std::endl;    delete [] szNumA;    delete [] szNumB;    return true;}int main(int argc, char* argv[]){    MapTest();    system("pause");    return 0;}

 


联系
我们