在 C++ 中存储和检索多个密钥

Question

我有一些检索值所需的整数键。基于键存储和检索值的最有效方法是什么？

目前，我正在将三个键转换并组合成一个字符串，并将键值对存储在映射中。但是，我认为应该有一种更有效的方法来仅基于整数值来执行此操作，例如基于三个键生成单个键。对此有什么想法吗？

谢谢。

Answer 1

几乎可以肯定，您可以比转换为字符串做得更好（这通常是一个相当慢的操作）。如果您的三个项目的范围足够小，您可以进行一些移位和添加，将它们组合成一个具有更大范围的整数。

如果缺少这一点，您可以创建一个包含三个整数的结构，并定义 operator< 以合理的方式比较它们：

class key { 
    int a, b, c;
public:
    bool operator<(key const &other) { 
        if (a < other.a)
            return true;
        if (a > other.a)
            return false;
        if (b < other.b)
            return true;
        if (b > other.b)
            return false;
        if (c < other.c)
            return true;
        return false;
    }
};

编辑：对于那些关心它的人，使用 (std | tr1 | boost) ::tuple 不会改变答案的特征太多，但会消除大部分代码。元组与 std::pair 非常相似，不同之处在于它支持任意数量的项目而不是仅两个。对于上面的示例，您可以使用类似的内容：

#include <tuple>

namespace stdx = std::tr1;    // or stdx=boost::tr1, etc.

typedef stdx::tuple<int, int, int> key_t;

std::map<key_t, whatever> my_map;

tuple 自动定义比较运算符，假设类型是可比较的（即，用于比较具有相同元素数量的两个元组，并且相应元素的类型是可比较的）。在这种情况下，它进行字典比较（即，比较的结果是第一对不相等的相应元素的结果——如果不存在这样的元素，则两个比较相等）。

Answer 2

Jerry Coffin 的建议很好，它可以扩展到任意数量的任意宽度的键。

然而，在实践中，有很多情况可以采用以下有效方法。如果键的大小使其总和适合本机类型，那么我们可以按如下方式组合键。

假设我们有三个关键部分：

a, 16-bit,
b, 32-bit
c, 16-bit

按重要性顺序列出以进行比较。 （与 Jerry Coffin 的示例相同。）

然后，我们可以

class key {
  private:
    uint64_t key_rep_;  // internal key representation
};

通过 key_rep_ 的以下底层解释

AAAABBBBBBBBCCCC

获得一个值上面的每个字母都是一个半字节，并显示了它所代表的关键部分。

将此方法与直接方法进行比较：

• 在键中读取和写入键部分较慢
• 比较两个键更快

在映射或集合中，键的比较比读/写更频繁，因此此方法在适用时可以实现整体效率。

Answer 3

您可以使用映射将带有键的向量映射到值，并对映射使用字典顺序。如果键的数量是恒定的，您甚至可以使用相同的顺序映射 int 数组

Answer 4

你正在做的事情听起来不错。您可能会想到的另一种方法是使用从三个整数子项生成的哈希码来通过类似 unordered_map。

如果 std::map 适合您并且不需要 O(1) 查找时间，那么迁移到基于哈希的容器可能会导致哈希代码生成变得复杂（不容易做好） ）这让它带来的麻烦超过了它的价值。