标签: unordered-map
可怜的unordered_map插入性能/哈希函数
我现在一直在编写一个图像处理算法,在某些时候我需要收集一些关于转换像素的统计信息,以便更深入地了解我应该遵循的进一步开发方向.我需要收集的信息格式如下:
key: RGB value
value: int
我做了什么,是我打开转换后的图像并迭代它,保存我需要的值std::unordered_map,具有以下签名:
typedef std::unordered_map<boost::gil::rgb8_pixel_t, unsigned int> pixel_map_t;
在循环中:
for(int y = 0; y < vi.height(); y++) {
SrcView::x_iterator dst_it = src.row_begin(y);
for(int x = 0; x < vi.width(); x++, hits++) {
diff_map.insert(std::make_pair(dst_it[x], /* some uint32 */));
}
我还编写了一个自定义哈希函数(它是一个完美的哈希函数:256^2 x R + 256 x G +
B- 所以无论桶和哈希表的布局如何,冲突都应该是最小的(合理的扩展).
我注意到的是,插入速度非常慢! - 在达到第11次迭代后,插入速度降低约100倍.我发生了大量的碰撞!尽管图像中的重复颜色数量非常少.
之后,我想消除代码中的任何可能的错误,并开始unordered_map使用原始键类型(如int)对STL哈希函数进行基准测试.
该基准的代码是:
std::size_t hits = 0, colls = 0;
for(int y = 0; y < vi.height(); y++) {
SrcView::x_iterator …推荐指数
解决办法
查看次数
C++ unordered_map 导致编译时错误
我有以下几点：
#include<iostream>
#include<unordered_map>
#include<tuple>
using namespace std;
class CTest {
// Properties
public:
unordered_map<const string, tuple<int, int> > Layout;
// Methods
public:
CTest ();
~CTest ();
};
CTest::CTest () {
Layout["XYZ"] = make_tuple (0, 1);
}
CTest::~CTest () {
// Do nothing
}
int main (int argc, char *argv[]) {
CTest Test;
return 0;
}
编译这个简单的程序会出现以下错误：
错误 C2678：二进制“==”：未找到采用“const std::string”类型的左侧操作数的运算符（或没有可接受的转换）
我在 Windows 7 中使用 Visual Studio 2010 Professional。
推荐指数
解决办法
查看次数
在 C++ 中实现 Hashmap :: 模板化数据类型的哈希函数
我最近一直在使用 STL 的 unordered_map ，虽然它似乎工作得很好，但我不太明白散列函数是如何工作的，因为数据类型是作为模板参数给出的。为了更彻底地理解这个数据结构，我用 C++ 实现了我自己的小 Hashmap 类：
哈希表接口：
#ifndef _HASHMAP_H_
#define _HASHMAP_H_
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <vector.h>
//Beginning of Hashmap class definition
template <class Key, class Value>
class Hashmap{
private:
int mappedElementCount;
public:
explicit Hashmap();
virtual ~Hashmap();
virtual void test();
virtual int hash(Key*);
int* getSize();
void putKVPair(Key*,Value*);
void clearMap();
//When we use these methods, we'll want a linear vector of keys and values to
//iterate over, so vector is good here
std::vector<Key>* getKeys(); …推荐指数
解决办法
查看次数
为什么没有C ++ POD结构的默认哈希？
我想将POD结构用作地图中的哈希键，例如
struct A { int x; int y; };
std::unordered_map<A, int> my_map;
但我不能这样做，因为没有哈希函数可自动为此类结构生成。
- 为什么C ++标准不需要POD结构的默认哈希？
- 为什么即使标准没有强制要求，编译器（特别是GCC 4.x / 5.x）也提供这样的哈希值？
- 如何使用模板以可移植的方式为我的所有POD结构生成哈希函数（如果需要，我愿意做出语义假设）？
推荐指数
解决办法
查看次数
如果在地图中找不到键，则返回其他值
我有unordered map：
static unordered_map<int, long> my_map;
auto& result = my_map[i];
如果没有键i，结果就是0. 是否可以返回其他值，例如NULL或-MAXINT？
推荐指数
解决办法
查看次数
STL无序容器的本地迭代器有哪些用途？
在C ++标准表91的第23.2.7节中，无序关联容器[unord.req]描述了STL无序关联容器必须满足的其他要求。在该表中的标准决定了STL无序容器（即，，，和）必须提供作为成员类型和。unordered_setunordered_mapunordered_multisetunordered_multimaplocal_iteratorconst_local_iterator
local_iterator是一个迭代器类型，其类别，值，差，指针和引用类型与无序容器的相同iterator。该迭代器可用于遍历单个存储桶，但不能跨存储桶进行迭代。const_local_iterator是一个迭代器类型，其类别，值，差，指针和引用类型与无序容器的相同const_iterator。该迭代器可用于遍历单个存储桶，但不能跨存储桶进行迭代。
问
这些迭代器有什么用？
c++ unordered-map unordered-set unordered-multiset unordered-multimap
推荐指数
解决办法
查看次数
C++ 中的 Hashmap 等价物
我有一个应用程序（在 C++ 中），其中我需要在字符串和整数之间有一组配对，即：
("david", 0)
("james", 1)
("helen", 2)
...
如果我们使用 java (key, value) 定义，我需要能够 (1) 搜索以查看映射中是否存在一个键 (2) 检索与给定字符串 (key) 关联的值。 java，我发现HashMap类型可以处理我需要的一切。
我想做同样的事情，但在 C++ 中。我做了一些谷歌搜索，发现在 C++ 2011 库中有一个 unordered_map 类型可以复制这个。我很好奇这是否是最好的方法。
在我的应用程序中，我对集合有以下规则
- 整数始终是连续的（如示例所示）并从 0 开始。
- 整数值永远不会改变。
- Map 是在应用程序开始时创建的并且不会改变，即它是不可变的。
- 没有重复的字符串键。
- 创建地图后，我不知道我将需要使用多少个键（以及扩展整数值）。我的应用程序的参数之一是包含要使用的单词列表的文本文件的目录。
- 我不在乎与此相关的启动时间成本。我需要主要任务（即 containsKey(..) 和 get(key) 尽可能快）。它将被称为 A LOT。该应用程序以处理大型文本语料库（即维基百科）和形成单词/文档之间的共现矩阵为中心。
我认为不是同时存储整数和字符串，而是将字符串存储在某种列表类型中，然后返回索引，即 data = { "david", "james", "helen", ... }
然后像 find_Map(data, key) 之类的东西返回它所在的索引（值）。我认为这可以通过首先按升序排序并应用搜索算法来加快速度。但同样，这只是一个猜测。
我确实意识到这是一个常见问题，并且存在许多不同的方法。我将编写一些不同的想法，但我认为最好先询问小组看看你们的想法。
推荐指数
解决办法
查看次数
clang 6 不支持 unordered_map::merge？
通过这个简单的例子，我得到了一个编译错误：
#include <unordered_map>
int main() {
std::unordered_map<int, int> a, b;
a.merge(b);
}
错误：
$ clang++ -std=c++17 merge.cpp
merge.cpp:5:4: error: no member named 'merge' in 'std::__1::unordered_map<int, int, std::__1::hash<int>, std::__1::equal_to<int>, std::__1::allocator<std::__1::pair<const int, int> > >'
a.merge(b);
~ ^
1 error generated.
版本：
$ clang++ --version
clang version 6.0.0 (tags/RELEASE_600/final)
Target: x86_64-apple-darwin17.5.0
Thread model: posix
InstalledDir: /usr/local/opt/llvm/bin
根据 cppreference，从 C++17 开始这应该是合法的。GCC 7 很乐意编译它。
推荐指数
解决办法
查看次数
如何更改 unordered_map 中的键？
我需要使用平均支持恒定时间查找的数据结构。我认为使用 astd::unordered_map是一个很好的方法。我的数据是数字的“集合”。
|115|190|380|265|
这些数字不必按特定顺序排列。我需要O(1)时间来确定这个数据结构中是否存在给定的数字。我有使用 a 的想法std::unordered_map，它实际上是一个哈希表（我说得对吗？）。所以数字将是关键，然后我将只有虚拟值。
所以基本上我首先需要确定数据结构中是否存在匹配给定数字的键，然后我根据该条件运行一些算法。独立于该条件，我还想更新一个特定的键。假设190，我想添加20它，所以现在关键是210。现在数据结构看起来像这样：
|115|210|380|265|
我想这样做的原因是因为我有一个遍历二叉搜索树的递归算法。每个节点都有一个int value, 和两个指向左右节点的指针。当到达叶节点时，我需要在“哈希表”数据结构中创建一个新字段，其中包含current_node->value. 然后当我在递归中返回树时，我需要将每个节点的值依次添加到存储在键中的先前总和上。以及为什么我的数据结构（我建议应该是一个std::unordered_map) 有多个数字字段，因为它们中的每一个都代表从树的叶节点到中间某个节点的唯一路径。我检查从叶子到给定节点的路径上所有节点值的总和是否等于该节点的值。所以基本上每个键都添加了节点的当前值，存储该路径上所有节点的总和。我需要扫描该数据结构以确定是否有任何字段或键等于当前节点的值。另外我想在接近恒定的时间内将新值插入到数据结构中。这是用于竞争性编程，我会犹豫使用std::vector因为查找一个元素并插入一个元素需要线性时间，我认为。那会搞砸我的时间复杂度。也许我应该使用除 a 之外的其他数据结构std::unordered_map？
推荐指数
解决办法
查看次数
C++ unordered_map operator[] vs unordered_map.find() 性能
我正在解决interviewbit.com 上的一个竞争性编程问题，我基本上使用了 unordered_map 来跟踪访问过的数字。当我使用operator[]时，我的代码无法及时执行，但是当我使用find时它通过了所有测试。两者应该具有相同的时间复杂度。
我尝试使用 clock() 对这两个代码进行计时，方法是将它们运行 10 次并平均运行时间，它们都或多或少地给出了相同的时间。我用的是g++ 7.4.0，而网站提供的环境是g++ 4.8.4。这可能是造成这种情况的原因。
int Solution::solve(vector<int> &A) {
unordered_map<long long, int> hashmap;
for(auto a : A)
hashmap[a] = 1;
int res = 0;
for(int i = 0; i < A.size(); ++i){
for(int j = i + 1; j < A.size(); ++j){
// if(hashmap.find((long long)A[i] + A[j]) != hashmap.end())
if(hashmap[(long long)A[i] + A[j]] == 1)
++res;
}
}
return res;
}
问题是在数组中找到总和也存在于数组中的对。当我使用 [] 运算符时，我在大约 900 的数组大小上遇到了“超出时间限制”。
推荐指数
解决办法
查看次数