标签: unordered-map

我想要有类似的东西

 unordered_set<vector<pair<int,int>>> us;

但即使没有配对:

#include <vector>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<vector<int>> um;
}

它失败:

In file included from /usr/include/c++/4.8/bits/hashtable.h:35:0,
                 from /usr/include/c++/4.8/unordered_set:47,
                 from prog.cpp:2:
/usr/include/c++/4.8/bits/hashtable_policy.h: In instantiation of ‘struct std::__detail::_Hash_code_base<std::vector<int>, std::vector<int>, std::__detail::_Identity, std::hash<std::vector<int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>’:
/usr/include/c++/4.8/bits/hashtable_policy.h:1402:10:   required from ‘struct std::__detail::_Hashtable_base<std::vector<int>, std::vector<int>, std::__detail::_Identity, std::equal_to<std::vector<int> >, std::hash<std::vector<int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, true, true> >’
/usr/include/c++/4.8/bits/hashtable.h:174:11:   required from ‘class std::_Hashtable<std::vector<int>, std::vector<int>, std::allocator<std::vector<int> >, std::__detail::_Identity, std::equal_to<std::vector<int> >, std::hash<std::vector<int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >’
/usr/include/c++/4.8/bits/unordered_set.h:96:18:   required from …

我们知道基于哈希表的容器实现就像std::unordered_map使用了很多内存但我不知道多少是多少？

除了空间复杂性表示法,并且不考虑容器元素是否是指向更大对象的指针:

有没有办法弄清楚这样的容器在运行时使用了多少字节？

有没有办法在运行时告诉任何容器使用多少内存？

当我想确保我想要使用的条目存在时,我通常会这样做.

#include <unordered_map>

struct type { int member; };
std::unordered_map<type> map;

if (map.find(key) != map.end())
    map[key].member = 42;

但是,我认为它key在哈希映射中执行两次查找.这会缓存查找.

#include <unordered_map>

struct type { int member; };
std::unordered_map<type> map;

auto find = map.find(key);
if (find != map.end())
    find->second.member = 42;

第一种选择感觉更具表现力.它真的慢吗？

如何unordered_map按顺序排序？我需要打印unordered_map按键排序.

我理解clear()操作的复杂性在容器的大小上是线性的,因为必须调用析构函数.但原始类型(和POD)呢？似乎最好的做法是将矢量大小设置为0,这样复杂性就是不变的.

如果可以,std :: unordered_map也可以吗？

我想使用的元组组成的int,char,char在我的unordered_map.我这样做:

#include <string>
#include <unordered_map>
#include <cstring>
#include <iostream>
#include <tuple>

using namespace std;

tuple <int,char,char> kk;
unordered_map<kk,int> map;

int main()
{
    map[1,"c","b"]=23;
    return 0;
}

但这给了我以下错误:

map.cpp:9:21: error: type/value mismatch at argument 1 in template parameter list     for ‘template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> class    std::unordered_map’
map.cpp:9:21: error:   expected a type, got ‘kk’
map.cpp:9:21: error: template argument 3 is invalid
map.cpp:9:21: error: template argument 4 is invalid …

我的问题是安全问题.我搜索了cplusplus.com和cppreference.com,他们似乎缺乏std :: move期间的迭代器安全性.具体来说:使用已移动对象的迭代器调用std :: unordered_map :: erase(iterator)是否安全？示例代码:

#include <unordered_map>
#include <string>
#include <vector>
#include <iostream>
#include <memory>

class A {
public:
    A() : name("default ctored"), value(-1) {}
    A(const std::string& name, int value) : name(name), value(value) { }
    std::string name;
    int value;
};
typedef std::shared_ptr<const A> ConstAPtr;

int main(int argc, char **argv) {
    // containers keyed by shared_ptr are keyed by the raw pointer address
    std::unordered_map<ConstAPtr, int> valued_objects;

    for ( int i = 0; i < 10; ++i ) {
        // …

问题

对于用户定义类型的std :: unordered_map或std :: unordered_set的第三个模板参数,std :: hash有什么好的特殊性,所有成员数据类型都已经具有良好的std :: hash特性？

对于这个问题,我将"好"定义为易于实现和理解,合理有效,并且不太可能产生哈希表冲突.商品的定义不包括任何有关安全性的陈述.

什么是谷歌的状态

目前,两个StackOverflow问题是Google搜索"std hash specialization"的第一个问题.

第一个,如何在无序容器中为用户定义的类型专门化std :: hash :: operator()？,解决了打开std命名空间和添加模板特化是否合法的问题.

第二个,如何专门化来自其他库的类型的std :: hash,基本上解决了同样的问题.

这留下了当前的问题.鉴于C++标准库的实现为标准库中的基本类型和类型定义了散列函数,为用户定义的类型专门化std :: hash的简单有效方法是什么？有没有一种很好的方法来组合标准库实现提供的哈希函数？

(编辑感谢dyp.)StackOverflow的另一个问题是如何组合一对哈希函数.

谷歌的其他结果没有任何帮助.

这篇 Dobbs博士的文章指出,两个令人满意的哈希的XOR将产生一个新的令人满意的哈希值.

这篇文章似乎是从知识中说出并暗示了很多东西,但却注重细节.它与第一个例子中的简短评论中的Dr. Dobbs文章相矛盾,称使用XOR组合散列函数会产生一个弱的结果散列函数.

因为XOR应用于任何两个相等的值导致0,我可以看出为什么XOR本身很弱.

元问题

一个很好的理由回答解释为什么这个问题无效且一般无法回答也是受欢迎的.

当然,unordered_map的查找性能平均是常量,并且映射的查找性能是O(logN).

但是当然为了在unordered_map中找到一个对象,我们必须:

1. 哈希我们想要找到的密钥.
2. equality_compare键与同一个桶中的每个键.

而在地图中,我们只需要将所搜索的密钥与log2(N)密钥进行比较,其中N是地图中的项目数.

我想知道真正的性能差异是什么,假设散列函数增加了开销并且equality_compare不比less_than比较便宜.

我写了一个测试,而不是用一个我可以自己回答的问题打扰社区.

我已经分享了下面的结果,以防其他人发现这个有趣或有用.

如果有人能够并且愿意添加更多信息,当然会邀请更多答案.

在std :: unordered_map上运行基于范围的for循环时,似乎循环变量的类型不使用引用类型:

std::unordered_map<int, int> map = { {0, 1}, {1, 2}, {2, 3} };
for(auto&[l, r] : map)
    static_assert(std::is_same_v<decltype(r), int&>);

MSVC 2017,gcc 8.2和clang 7.0.0都报告了一个失败的断言.将此反对到std :: vector,其中断言不会失败,正如人们所期望的那样:

std::vector<int> vec = { 1, 2, 3 };
for(auto& r : vec)
    static_assert(std::is_same_v<decltype(r), int&>);

然而,在MSVC 2017和gcc 8.2上,修改局部变量r的循环将具有可观察到的副作用:

#include <iostream>
#include <type_traits>
#include <unordered_map>
#include <vector>

int main() {
    std::unordered_map<int, int> a = { {0, 1}, {1, 2}, {2, 3} };
    for(auto[l, r] : a)
        std::cout << l << "; " << …