标签: unordered-map

我有以下代码:

#include <iostream>
#include "boost/unordered_map.hpp"

using namespace std;
using namespace boost;

int main()
{

    typedef unordered_map<int, int> Map;
    typedef Map::const_iterator It;

    Map m;
    m[11] = 0;
    m[0]  = 1;
    m[21] = 2;

    for (It it (m.begin()); it!=m.end(); ++it)
        cout << it->first << " " << it->second << endl;

    return 0;
}

但是,我正在寻找保留顺序的东西,以便稍后我可以按照它们插入的相同顺序迭代元素.在我的计算机上,上面的代码不保留订单,并打印以下内容:

 0 1
11 0
21 2

我想也许我可以用一个 boost::multi_index_container

typedef multi_index_container<
    int,
    indexed_by<
        hashed_unique<identity<int> >,
        sequenced<>
    >
> Map;

有人可以告诉我如何使用这个容器(或任何其他适当的容器)实现我的原始代码,以便迭代器遵循插入的顺序？

我最近才开始关注boost和它的容器,我在网上阅读了一些文章,在stackoverflow上,boost :: unordered_map是大型集合中表现最快的容器.所以,我有这个类State,它必须在容器中是唯一的(没有重复),并且容器中将有数百万甚至数十亿个状态.因此,我一直在尝试优化它以实现小尺寸和尽可能少的计算.之前我正在使用boost :: ptr_vector,但是当我在stackoverflow上读到时,只要没有那么多对象,向量就是好的.在我的情况下,状态描述来自机器人的感觉运动信息,因此可能存在大量状态,因此快速查找是最重要的.在unordered_map 的boost文档之后,我意识到我可以做两件事来加快速度:使用hash_function,并使用相等运算符根据hash_function比较状态.因此,我实现了一个私有hash()函数,它接收状态信息并使用boost :: hash_combine,创建一个std :: size_t哈希值.operator ==基本上比较状态的哈希值.所以:

• 是std :: size_t足以覆盖数十亿可能的hash_function组合吗？为了避免重复状态,我打算使用他们的hash_values.

• 在创建state_map时,我应该使用State*或哈希值作为键吗？即:boost::unordered_map<State*,std::size_t> state_map; 或 boost::unordered_map<std::size_t,State*> state_map;

• 使用boost :: unordered_map :: iterator = state_map.find()的查找时间比通过boost :: ptr_vector并比较每个迭代器的键值更快吗？

• 最后,任何关于如何优化这种无序地图以获得速度和快速查找的提示或技巧将不胜感激.

编辑:我已经看到了不少答案,一个不使用boost而是使用C++ 0X,另一个不使用unordered_set,但说实话,我还是想看看boost :: unordered_set如何与hash函数一起使用.我已经按照boost的文档进行了实现,但我仍然无法弄清楚如何使用boost的hash函数和有序集.

昨天我试图使用std::unordered_map,这段代码混淆了我使用了多少内存.

typedef list<string> entityId_list;
struct tile_content {
   char cost;
   entityId_list entities;
};
unordered_map<int, tile_content> hash_map;

for (size_t i = 0; i < 19200; i++) {
   tile_content t;
   t.cost = 1;
   map[i] = t;
}

所有这些代码部分都是在MS VS2010中以调试模式编译的.我在任务管理器中看到的是大约1200 kb的"干净"过程,但填充后hash_map它使用了8124 kb的内存.这是正常的行为unordered_map吗？为什么要使用这么多内存？

我知道C++ STL中的unordered_map是作为散列表实现的,该散列表由对应于散列值的桶组成.插入,删除和元素搜索的时间保证摊销不变.但是我不太明白迭代器如何在这个数据结构上工作.当我增加迭代器时,它如何知道下一个位置在哪里？当我使用迭代器迭代unordered_map时,时间复杂度会是多少？用于查找迭代器常量的下一个位置的时间是多少？我在"C++标准库:一本教程和参考书"中找到了有关unordered_map内部结构的一些信息,但我无法找到问题的答案.希望有人可以帮忙!

谢谢.

我最近发现了boost :: multi_index_container,我对他的性能感到好奇,与我自己实现的基于多级映射的类似容器相比,定义如下:

typedef int      Data;
typedef uint64_t MainKey;
typedef uint64_t SecondaryKey;

typedef std::unordered_map<SecondaryKey, Data>       SecondaryMap;
typedef std::unordered_map<PrimaryKey, SecondaryMap> PrimaryMap;

密钥排序并不重要.快速查找很重要,为此我使用的是:

// find primaryKey=10 and secondaryKey=30
PrimaryMap m;
....
auto i1 = m.find( 10);
if ( i1 != m.end())
{
    auto& secondary = i1->second;
    auto i2 = secondary.find( 30);
    if ( i2 != secondary.end())
    {
        found = true;
        ....
    }
}

我想知道会是什么

• boost :: multi_index_container最接近的配置,以匹配我的实现
• 按主键和辅助键搜索的最快方法.

我试图配置模板,但我不确定这是否是最佳解决方案:

struct RecordKey
{
    MainKey         mainKey;
    SecondaryKey    secondaryKey;

    RecordKey( const MainKey mainKey, SecondaryKey secondaryKey): …

我正试图找到一个可能是一个非常微不足道的问题的解决方案.我想const unordered_map在类初始化列表中初始化我.但是我还没有找到编译器(GCC 6.2.0)将接受的语法.代码链接在这里.

#include <unordered_map>

class test {
 public:
    test()
      : map_({23, 1345}, {43, -8745}) {}

 private:
   const std::unordered_map<long, long> map_;
 };

错误:

main.cpp: In constructor 'test::test()':
main.cpp:6:36: error: no matching function for call to 'std::unordered_map<long int, long int>::unordered_map(<brace-enclosed initializer list>, <brace-enclosed initializer list>)'
  : map_({23, 1345}, {43, -8745}) {}
                                ^

复制常量是否不允许在初始化列表中初始化？或者语法必须不同？

我已经阅读了有关std::unordered_map使用cppreference的 C++ 17中的演绎指南.

然后尝试运行以下示例,该示例是从cppreference复制的.

#include <unordered_map>
int main() {
// std::unordered_map m1 = {{"foo", 1}, {"bar", 2}}; // Error: braced-init-list has no type
                                                     // cannot deduce pair<const Key, T> from
                                                     // {"foo", 1} or {"bar", 2}
   std::unordered_map m1 = std::initializer_list<
                        std::pair<char const* const, int>>({{"foo", 2}, {"bar", 3}}); // guide #2
   std::unordered_map m2(m1.begin(), m1.end()); // guide #1
}

但是,编译器会出错.

main.cpp: In function 'int main()':
main.cpp:7:84: error: class template argument deduction failed:
                         std::pair<char const* const, int>>({{"foo", 2}, {"bar", 3}}); …

我正在处理一些非常大std::unordered_map的(数亿条目),需要将它们保存到文件中并从文件中加载它们.我目前这样做的方法是迭代地图并一次读取/写入每个键和值对:

std::unordered_map<unsigned long long int, char> map;

void save(){
    std::unordered_map<unsigned long long int, char>::iterator iter;
    FILE *f = fopen("map", "wb");
    for(iter=map.begin(); iter!=map.end(); iter++){
        fwrite(&(iter->first), 8, 1, f);
        fwrite(&(iter->second), 1, 1, f);
    }
    fclose(f);
}

void load(){
    FILE *f = fopen("map", "rb");
    unsigned long long int key;
    char val;
    while(fread(&key, 8, 1, f)){
        fread(&val, 1, 1, f);
        map[key] = val;
    }
    fclose(f);
}

但是有大约6.24亿条记录,从文件中读取地图需要9分钟.写入文件速度更快但仍需要几分钟.有更快的方法吗？

为什么我不能有一个std::set或std::unordered_set的std::functionS'

有什么方法可以让它工作吗？

我std::unordered_map想要添加一个键值对.如果密钥尚不存在,那么我希望它与给定值一起添加.如果密钥已存在,那么我希望更新该值.

这里的标准建议似乎是使用operator[].但是这需要地图的值类型是默认可构造的.我希望避免提供默认构造函数.我该怎么办？