unordered-map_编程技术问答社区_程序员问答知识库

以下是关于 unordered-map 的编程技术问答

以更快的方式从/向文件读/写std::unordered_map

我正在使用一些非常大的std::unordered_map S(数亿个条目)，需要保存和从文件中保存和加载它们.我目前这样做的方式是通过地图迭代并读取/编写每个密钥和价值对一对: std::unordered_map map; void save(){ std::unordered_map::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 =

0 2023-05-23 编程技术问答社区 algorithm performance c++11 unordered-map

emplace的性能比检查差，其次是emplace。

我有一个没有默认构造函数的 value_type 的std::unordered_map，所以我不能执行以下 auto k = get_key(); auto& v = my_map[k]; 我最终写了一个辅助功能 value_type& get_value(key_type& key) { return std::get(my_map.emplace( std::piecewise_construct, std::forward_as_tuple(key), std::forward_as_tuple(args_to_construct_value) ))->second; } 但是，性能明显更糟糕(即值_type的构造函数以per

4 2023-05-23 编程技术问答社区 c++ performance c++11 unordered-map emplace

unordered_map：find()和count()哪个更快呢？

unordered_map容器是否具有指定键的项目，最快的方法是什么? 解决方案他们将具有相同的性能.您应该使用最能表达您尝试做的事情的算法. 为了详细说明，通常将使用find()实现count().例如，在 libcxx 中，count()被实现为return (find(__k) != end()); 其他解决方案 find()和count()适用于C ++中的许多容器. 对于地图，集合等另一方面， count()具有恒定的执行时间o(e)，其中e是找到提供的键的次数.最坏的情况是所有成员都相同的集合，因此count()可能具有复杂性o(n) map或unordered_map不允许重复，因此它们的渐近运行时间将相同. 选择取决于代码中的语义.如果您只想检查是否存在键，则可以使用count.如果您想检查键是否存在并使用其值，请使用find，因为您已经将迭代器指向该元素. 其他解决方案 C ++ 20通过提供contains方法结束

0 2023-05-23 编程技术问答社区 c++ performance c++11 unordered-map

在实践中，unordered_map真的比map快吗？

当然，unordered_map的查找性能平均是恒定的，并且地图的查找性能为o(logn). 但是，为了在unordered_map中找到一个对象，我们必须: 哈希我们想找到的关键. equality_compare键，每个键在同一桶中. 虽然在地图中，我们只需要更少地将寻求的键与log2(n)键进行比较，其中n是地图中的项目数. 我想知道真正的性能差异是什么，鉴于哈希函数添加了开销和equality_compare并不比sield_than比较便宜. 我没有回答自己的问题，而不是打扰社区，而是写了一个测试. 我已经分享了以下结果，以防其他人发现这种有趣或有用的情况. 如果某人能够并且愿意添加更多信息，则当然会邀请更多答案. 解决方案回答有关与错过搜索数量有关的问题的问题，我已经重构了测试以参数为参数. 示例结果: searches=1000000 set_size= 0 miss= 100% ordere

2 2023-05-23 编程技术问答社区 c++ performance dictionary unordered-map

Unordered_Map查询时间

内置地图和C ++库中的集合(包括unordered_map和multimap)要求查找函数(用于查找特定元素)使用迭代器来遍历元素. C ++参考站点声称，使用这些数据结构查找元素需要平均恒定时间，就像常规哈希表一样.但是，在找到元素之前，迭代器是否不需要穿越整个列表，平均使此o(n)时间限制? 解决方案您的语句不是真的: map，set，multimap和multiset通常以二进制树(例如:在vs中实现为红色黑树)，在这种情况下，查找方法在这种情况下搜索使用该属性的键在一个节点中，left child is less比节点(根据比较)和the right child is greater(根据比较).根据标准的要求，这给出了 o(log n). 在unordered_map和unordered_set的情况下，实施为哈希表，通常以桶集(例如:std::vector)的形式实施，并且将铲斗作为unordered_map元素的集合实现((例如:std:

2 2023-05-23 编程技术问答社区 performance hashmap hashtable unordered-map multimap

为什么std::unordered_map很慢，我可以更有效地使用它来缓解这个问题吗？

我最近发现了一件奇怪的事情.看来，用完全似乎超过2倍 flaster flaster /em>而不是使用std::unordered_map来缓存所有元素. 请注意，我确实从问题中获取了提示是GCC STD: :unordered_map实施缓慢?如果是这样 - 为什么?我试图使用这些知识来使std::unordered_map的性能尽可能地表现(我使用了G ++ 4.6，它的性能比G ++的最新版本更好，我尝试指定声音初始存储桶数，我完全等于地图必须保存的最大元素数). 相比与使用std::unordered_map相比，根本没有缓存，几乎要快40倍. 我是在做错什么还是这个容器慢了，为什么?可以使表现更快吗?也许哈希图本质上无效，应在高性能代码中尽可能避免使用? 有问题的基准是: #include #include #include #include std::

0 2023-05-23 编程技术问答社区 c++ performance c++11 caching unordered-map

在琐碎的键的情况下，使用map比unordered_map有什么优势吗？

最近关于unordered_map unordered_map的讨论使我意识到，由于查找的效率( amortized o(1) vs. o(log n)).大多数时候，我使用地图，将int或std::string用作密钥类型；因此，我对哈希功能的定义没有任何问题.我对它的想法越多，我就越意识到，在使用简单类型的键的情况下，我找不到在std::unordered_map上使用std::map的任何理由 - 我看了界面，并且没有发现会影响我的代码的任何重大差异. 因此，问题:在int和int和std::string的情况下，是否有真正的理由在std::unordered_map上使用std::map? 我是从严格编程的角度询问的 - 我知道它并不完全被视为标准，并且可能在移植方面构成问题. 另外，我希望正确的答案之一可能是"对于较小的数据集更有效" ，因为较小的开销(是真的吗?) - 因此，我想要将问题限制为密钥数量不平整的情况(> 1 024). 编辑: duh，我

2 2023-05-23 编程技术问答社区 c++ performance dictionary unordered-map

C++11：unordered_map/set是否保证遍历顺序为插入顺序？

我写了一些这样的代码: unordered_map uii; uii.insert(make_pair(12,4)); uii.insert(make_pair(3,2)); uii.insert(make_pair(6,1)); uii.insert(make_pair(16,9)); .... 当我使用for loop访问此地图时，它会按照我插入的正确顺序打印键.我测试了unordered_set，结果相同. 所以我的问题是，C ++标准是否将访问顺序保证为插入顺序，就像Java的LinkedHashMap? 一样解决方案否，它是unordered，没有这样的保证. 无序的关联容器中的元素被组织到 Buckets，具有相同哈希的键最终会放在同一桶中.这当容器的尺寸时，桶数会增加增加以保持每个存储桶中的平均元素数量一个值. 重新启用迭代器，可能导致元素为在不同的存储桶中重新安排，但不会使参考无效到元素. 这对于u

12 2023-05-23 编程技术问答社区 c++ c++11 insert unordered-map

OpenMP/__gnu_parallel for an unordered_map

在我的代码中的某个时刻，我必须在unordered_map中的所有元素上进行操作.为了加速此过程，我想使用OpenMP，但是天真的方法不起作用: std::unordered_map hastTable; #pragma omp for for(auto it = hastTable.begin(); it != hastTable.end(); it ++){ //do something } 的原因是，unordered_map的迭代器不是随机访问迭代器. 作为替代方案，我尝试了在for_each上使用的__gnu_parallel指令.但是以下代码 #include #include __gnu_parallel::for_each (hashTable.begin(), hashTable.end(),[](std::pair

2 2023-05-11 编程技术问答社区 c++ openmp unordered-map gnu-parallel

NaN是关联容器的有效键值吗？

考虑在double上键入的C ++中的有序和无序的关联容器. . 是NaN有效的密钥类型? 使用订购的容器，我应该说"不"，因为它不尊重严格的弱点. 有无序的容器，我不知道. 这是GCC 4.6.2中发生的情况: #include #include #include #include #include int main() { typedef std::map map_type; // replace by "unorderd_map" map_type dm; double d = std::acos(5); // a good nan dm[d] = 2; dm[d] = 5; dm[d] = 7; std::cout

0 2023-04-20 编程技术问答社区 c++ dictionary nan unordered-map

std::pair的哈希值，用于unordered_map中。

做 unordered_map, unsigned int> m; 我们得到错误C2338:C ++标准不为此类型提供哈希. 是否有一种内置方法来定义int std::pair的哈希，或者我们需要手动定义它?(在这种情况下，哈希可以只是(第一项字节)(对第二项的字节)胶合在一起). 注意:我正在使用VC ++2013. note2: pair 将作为unordered_map问题的关键没有清楚地解决如何使用两个int s实际创建哈希的问题，如下所示. 解决方案如果您不想使用Boost，那么滚动不应该太难了. 添加了static_assert，以确保维护2个ints拟合1 size_t的假设. using IntPair = std::pair; struct IntPairHash { static_assert(sizeof(int) *

4 2023-04-14 编程技术问答社区 c++ dictionary hashmap unordered-map std-pair

一个保留了插入顺序的C++哈希图

我有以下代码: #include #include "boost/unordered_map.hpp" using namespace std; using namespace boost; int main() { typedef unordered_map 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 first second

2 2023-04-05 编程技术问答社区 c++ unordered-map html-lists multi-index

Visual C++ 2010：unordered_map和移动构造器

我有一个名为Foo的结构，其中包含unique_ptr struct Foo { std::unique_ptr pointer; }; 现在，我正在尝试将Foo的实例存储在unordered_map 中 std::unordered_map myMap; 从技术上讲，这应该是可能的，因为地图不需要复制构造函数，所以只需要移动构造函数. 但是，我无法在地图中插入一个元素: myMap.insert(std::make_pair(3, Foo())); 此行将在Visual C ++ 2010中产生以下错误(由于我的编译器不使用英语，我大致翻译了): error C2248: 'std::unique_ptr::unique_ptr' : unable to access private member declared in 'std::unique_ptr' with [

2 2023-04-01 编程技术问答社区 c++ visual-studio-2010 constructor move unordered-map

std::unordered_map::emplace问题与私有/删除的复制构造函数

以下代码使用GCC 4.7.2(mingw) 编译罚款 #include #include struct test { test() =default; private: test(test const&) =delete; }; int main() { std::unordered_map map; map.emplace( std::piecewise_construct, std::forward_as_tuple('a'), std::forward_as_tuple() ); } 如果我将test中的复制构造函数从test(test const&) =delete;更改为test(test const&) =default;，但是，模板错误呕吐物似乎抱怨const test& co

2 2023-03-28 编程技术问答社区 c++ gcc c++11 mingw unordered-map

我如何实现一个CString哈希函数以用于std::unordered_map？

我想声明: std::unordered_map m_mapMyMap; 但是，当我构建时，我会出现错误，告诉我标准C ++没有为CSTRING提供哈希功能，而CSTRING具有(LPCSTR)操作员. 我如何正确地实现cstring的哈希功能? 解决方案基于std::string的MS STL实现，我创建了以下方法，可用于std::unordered_set>>> and std::unordered_map: namespace std { template struct hash { // hash functor for CString size_t operator()(const CString& _Keyval) const { // hash _Keyval to size_t value by pseudorando

2 2023-03-27 编程技术问答社区 c++ hash mfc unordered-map

计算无序地图占用的内存空间

我有两个无序地图:(在Linux中执行代码) 第一个无序地图: 它由更多至少的65536条目组成.每个条目包括 int unsigned char unsigned char 第二个无序地图: 它由少于65536的肠道组成.每个条目由组成 int int int vector 现在，我想根据上述两个无序地图(字节)占据的内存进行比较.之后，我想计算实现的内存压缩. 请指导我如何找到两个无序地图所占据的记忆? 第二个无序地图的更多详细信息: typedef std::tuple key_t; struct KeyHasher { std::size_t operator()(const key_t& k) const { using boost::hash_value; using boost::hash_combine; // Start with a ha

8 2023-03-25 编程技术问答社区 c++ memory-management unordered-map

std::unordered_map不释放内存

我在MSVC14(VS2015)中观察到std::unordered_map的奇数行为. 考虑以下方案.我创建了一个无序的地图，并用虚拟结构填充它，该结构消耗了大量的内存，可以说1GB，总的100k元素插入.然后，您开始从地图上删除元素.可以说，您已经删除了一半的元素，然后，您希望将一半的记忆释放.正确的?错误的！我看到，当映射中的元素数量通过一些阈值时，记忆是释放的，在我的情况下是1443个元素. 可能会说使用VirtualAllocEx或malloc优化的. >实际上，它没有将内存释放回系统，因为优化决定了策略，并且可能无法调用HeapFree以将来重复使用已分配的内存. 为了消除我对allocate_shared的自定义分配器的消除，它没有解决问题.因此，主要的问题是为什么会发生这种情况以及unordered_map使用的"紧凑"内存可以做什么? 代码 #include #include #include #i

0 2023-03-25 编程技术问答社区 c++ visual-c++ memory-management stl unordered-map

是否有一个BOOST池固定大小的分配器？

我想创建unordered_map(因为我特别想要一张哈希地图).我想在开始时分配其最大大小(根据我的约束). 因此，如果我想分配256个条目，每个条目的大小为1B(只是一个例子.假设1 Byte包括键和值).然后我的unordered_map键 +条目的总大小为256b.我想在分配器中预先分配256b. 然后，当unordered_map将调用allocate()/deallocate()时，allocator将从已经分配的内存中给出1B. typedef boost::unordered::unordered_map, std::equal_to, ??? > > myMap 它存在于增强中吗?还是其他地方? ----编辑---- 正如我所看到的(在这里的答案) - 我的问题有两种解决方案: 实现allocator，该allocator容纳boost::pool.此p

0 2023-03-25 编程技术问答社区 c++ memory-management boost unordered-map allocator

当T是原始类型时，std::vector＜T＞::clear()的复杂性是什么？

我知道，Clear()操作的复杂性在容器的大小上是线性的，因为必须调用攻击器.但是原始类型(和POD)呢?似乎最好的办法是将矢量大小设置为0，以使复杂性是恒定的. 如果可能的话，std :: unordered_map是否也可以? 解决方案似乎最好的办法是将矢量大小设置为0，以使复杂性是恒定的. 通常，将向量调整到零 IS线性在当前存储在vector中的元素数量中.因此，将vector的大小设置为零，与调用clear() - 两者本质上没有任何优势. 然而，至少一个实施(libstdc ++， clear()的实现导航到 bits/stl_construct.h ，执行非平凡的编译时间优化:它使用类型bool的模板参数声明辅助模板类_Destroy_aux.该类具有true的部分专业化和false的显式专业化.这两个专业都定义了一个称为__destroy的单个静态函数.如果模板参数为true，则功能主体为空；如果参数为false，则包含一个循环T的dest

16 2023-03-23 编程技术问答社区 vector complexity-theory unordered-map primitive

c++-unordered_map的复杂性

我需要创建一个查找函数，其中a(x，y)对对应于特定的z值.对此的一个主要要求是，我需要尽可能接近O(1)的复杂性.我的计划是使用unordered_map. 我通常不使用哈希表进行查找，因为查找时间对我从来都不重要.我是否正确地认为，只要我构建了unordered_map没有碰撞，我的查找时间就会是o(1)? 我担心的是，如果键不存在于无序地图中，那么复杂性就会变得什么.例如，如果我使用unordered_map :: find():，例如，要确定我的哈希表中是否存在键，它将如何给我答案?它实际上是否在所有键上迭代? 我非常感谢您的帮助. 解决方案标准或多或少需要使用桶进行碰撞解决方案，这意味着实际查找时间将关于在铲斗，无论该元素是否存在. 可以使其成为O(lg n)，但通常不是这样做的，因为存储桶中的元素数量应该很小，所以如果哈希表正确使用. 确保水桶中的元素数量很小，您必须确保哈希功能有效.什么有效手段取决于被哈希的类型和值. (MS

10 2023-03-23 编程技术问答社区 c++ hashtable complexity-theory unordered-map

首页
<
1
2
3
4
5
6
7
8
>
尾页