STL Map中使用Vector作为键

Question

我正在处理一些二进制数据，这些数据存储在长度任意的无符号整数数组中。我发现数据有重复，并且希望短期忽略重复项并消除长期造成重复的错误。我计划将每个数据集插入到一个映射中存储，但前提是在映射中没有找到该数据集。我最初的想法是使用memcpy函数将整数强制转换为字符数组，并将其复制到字符串中存储，但这种方法失败了，因为我的许多数据包含在相关数据前面有多个字节的0（又名NULL），因此大部分真实数据被丢弃了。我的下一个尝试计划是使用std::map, int>，但是我意识到我不知道map插入函数是否会起作用。即使这可能并不明智，但这是可行的吗？或者有更好的方法来解决这个问题吗？

修改： 所以有人指出我没有清楚地说明我在做什么，所以这里有一个更好的描述。我正在生成一棵最小生成树，假设我有许多包含我正在使用的实际终节点的树。目标是选择覆盖所有端节点且共享最多一个节点并且都连接的树的选择，其长度最短。我基于二叉决策树的思路进行操作，但是我做出了一些更改，以便实现更大程度的并行性。我选择使用无符号整数制作每个数据集的位向量，其中位位置的1表示包含相应的树。例如，如果一个5个树的数据集中只包含树0，则从此处开始：00001。从这里我可以生成：00011、00101、01001和10001。

每个单独的树（00010，00100等等）都可以并行处理，因为它们之间没有依赖关系。我对所有的单独树都这样处理，应该能够生成范围在（0，2^n）内所有值仅一次。

我开始注意到许多数据集需要完成的时间比我预期的要长，于是启用了调试输出来查看所有生成的结果。经过一个快速的Perl脚本后，确认我有多个进程生成相同的输出。从那时起，我一直在努力解决重复项的来源，但是很少成功，希望这能够足够好地工作，让我验证正在生成的结果，而不需要等待计算时间长达3天的情况。

- jthecie

---

你为什么不尝试一下呢？ - Kerrek SB

如果您只需要独一无二的元素，可以考虑使用 std::set。 - brendanw

Answer 1

你不需要担心这个问题，因为std::vector提供了"==", "<" 和 ">" 运算符： http://zh.cppreference.com/w/cpp/container/vector/operator_cmp

- Renan Greinert

---

但是你需要一个小于运算符作为 map 中的键。不过我猜你可以将比较函数作为模板参数传递进去。 - Brian Neal

向量还提供了这个功能，就像链接中所示。我会编辑我的回答使其更清晰。感谢您的观察。 - Renan Greinert

Answer 2

std::map键的要求已经被std::vector满足，所以你可以这样做。听起来像是一个好的临时解决方案（易于编码，最小化麻烦）--但你知道他们说的话：“没有比暂时更永久的东西了”。

- Jon

---

我真正希望看到的是，在添加这个之后，我是否仍然会得到重复的结果。这将把搜索范围缩小到我无意中存储或提取重复项，而不是生成它们。 - jthecie

Answer 3

根据Renan Greinert所说，“vector<>”符合被用作“map”键的要求，因此应该可以运行。

你还说：

“我想先将每个数据集插入到一个map中再存储，但前提是在map中没有找到它。”

通常情况下，这不是你想做的，因为这将涉及在map上进行一次查找，如果没有找到，则执行插入操作。这两个操作实际上需要执行两次查找。最好就是尝试将项目插入地图中。如果键已经存在，则操作会按定义失败。因此，您的代码将如下所示：

#include <vector>
#include <map>
#include <utility>

// typedefs help a lot to shorten the verbose C++ code
typedef std::map<std::vector<unsigned char>, int> MyMapType;

std::vector<unsigned char> v = ...; // initialize this somehow
std::pair<MyMapType::iterator, bool> result = myMap.insert(std::make_pair(v, 42));
if (result.second)
{
   // the insertion worked and result.first points to the newly 
   // inserted pair
}
else
{
   // the insertion failed and result.first points to the pair that
   // was already in the map
}

- Brian Neal

---

我已经更新了原始问题，并提供了更多关于我的操作的详细信息，希望这有助于澄清我的动机。老实说，我并没有意识到可以像这样跳过查找，感谢STL中可用的新功能。 - jthecie

糟糕，我刚刚修复了“键已存在于映射中”的注释。如果键已经存在于映射中，则result.second将为false，而result.first将指向现有的键和值对。 - Brian Neal

Answer 4

为什么你需要一个std::map呢？也许我错过了一些点，但是使用find算法和std::vector结合起来怎么样，就像这里所解释的那样？

这意味着，你将unsigned int附加到向量中，然后稍后搜索它，例如：

std::vector<unsigned int> collector; // vector that is substituting your std::map
for(unsigned int i=0; i<myInts.size(); ++i) {  // myInts are the long ints you have
    if(find(collector.begin(), collector.end(), myInts.at(i)==collector.end()) {
         collector.push_back(myInts.at(i));
    }
}

- ezdazuzena

---

如果我可以将所有内容都放入一个unsigned int中，那么这很好用。问题是，一旦我得到足够大的输入，我就必须开始溢出到多个整数，并且必须将它们作为整个集合保留以进行搜索。我真的希望在不实际制作结构来处理此问题的情况下完成此操作，因为它希望是一个非常临时的hack。 - jthecie