map、hash_map、unordered

#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 = ; i< L.size(); i++)

   dictL[L[i]] += ;

删除元素： 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 = ;                              // 键值

    const unsigned int NUM_RANGE = 0xffffff;        // 随机数范围的最大值

    int* szNumA = new int[NUM_COUNT];

    int* szNumB = new int[NUM_COUNT];

    srand(::GetTickCount());

    for (unsigned int uiNum = ; uiNum < NUM_COUNT; ++uiNum)

    {

        szNumA[uiNum] = (rand() * rand()) % NUM_RANGE;

        szNumB[uiNum] = szNumA[uiNum];

    }

    for (unsigned int uiNum = ; 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 = ; uiNum < NUM_COUNT; ++uiNum)

    {

        mapNum.insert(std::map<int, int>::value_type(szNumA[uiNum], ));

    }

    dwMap = ::GetTickCount() - dwMap;

    dwHMap = ::GetTickCount();

    for (unsigned int uiNum = ; uiNum < NUM_COUNT; ++uiNum)

    {

        hMapNum.insert(std::hash_map<int, int>::value_type(szNumA[uiNum], ));

    }

    dwHMap = ::GetTickCount() - dwHMap;

    dwUnMap = ::GetTickCount();

    for (unsigned int uiNum = ; uiNum < NUM_COUNT; ++uiNum)

    {

        unMapNum.insert(std::unordered_map<int, int>::value_type(szNumA[uiNum], ));

    }

    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 = ; uiNum < NUM_COUNT; ++uiNum)

    {

        mapNum.find(szNumB[uiNum]);

    }

    dwMap = ::GetTickCount() - dwMap;

    dwHMap = ::GetTickCount();

    for (unsigned int uiNum = ; uiNum < NUM_COUNT; ++uiNum)

    {

        hMapNum.find(szNumB[uiNum]);

    }

    dwHMap = ::GetTickCount() - dwHMap;

    dwUnMap = ::GetTickCount();

    for (unsigned int uiNum = ; 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 = ; uiNum < NUM_COUNT; ++uiNum)

    {

        mapNum.erase(szNumB[uiNum]);

    }

    dwMap = ::GetTickCount() - dwMap;

    dwHMap = ::GetTickCount();

    for (unsigned int uiNum = ; uiNum < NUM_COUNT; ++uiNum)

    {

        hMapNum.erase(szNumB[uiNum]);

    }

    dwHMap = ::GetTickCount() - dwHMap;

    dwUnMap = ::GetTickCount();

    for (unsigned int uiNum = ; 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 ;

}

巴特西

map、hash_map、unordered_map 的思考

最新文章

热门文章