C++ : suitable Data Structure for this given scenario

Question

我想知道哪种数据结构适合我的情况。请指导我。以下是要求。如下图所示，基于三个值 A、B 和 C(其中 A 为整数值，B、C 为字符)。左边的表都有唯一的条目。我想存储两个接受规则编号和真/假的值。因此，对于 A、B 和 C 的每个唯一值，我想存储与它们对应的两个值(接受规则编号和真/假)。一个重要的事情是接受规则编号可以是一个或多个(大小不固定)。其次，表长可达65025以上。

P.S:我之前问过这类问题，但这次情况略有不同。

Answer 1

让我们检查一下我们的基础知识，好吗。

您基本上想要三元组(数字、字符、字符)和由两个元素组成的一对之间的关​​联:一组接受规则数字和一个 bool 值(注意:在您的示例中， bool 值与以下事实相关:是否为接受规则编号)。

所以，我们取 this answer关于如何最好地选择一个标准库容器并愚蠢地遵循它的问题:

1. 联想？是的
   1. 订购了吗？否 => unordered_
   2. 单独的 key ？是 => map
   3. 多个值？否(单一结构)=> 否 multi

就这样，你想要一个 unordered_map 从您的 key (三元组)到您的值(对)。

对于无序 map ，我们需要 5 个模板参数:

• Key (关键)
• T (值(value))
• Hash : 计​​算键哈希值的谓词，默认为 std::hash<Key>如果正确实现
• Equal :一个比较器，用于检查具有相同散列的两个键的幂等性，因为散列不是单射的，它默认为 std::equal<Key> (即使用 operator== )
• Allocator : 容器从中获取内存的内存分配器，默认为 std::allocator

所以，假设我们的 Key可以散列和比较是否相等，我们只需要提供一个 Key和相关的值(value)。虽然很少有键是可散列的，因此我们将自己提供散列器。

struct TableKey {
    int A;
    char B;
    char C;
};

struct TableKeyHasher {
    size_t operator()(TableKey const& tk) const {
        return hash<int>(tk.A) ^ hash<char>(tk.B) ^ hash<char>(tk.C);
    }
};

bool operator==(TableKey const& left, TableKey const& right) {
    return std::tie(left.A, left.B, left.C) == std::tie(right.A, right.B, right.C);
}

bool operator!=(TableKey const& left, TableKey const& right) {
    return not (left == right);
}

struct TableValue {
    std::unordered_set<int> acceptingRules;
    bool someBooleanWithoutName;
};

最后:

using MySuperTable = std::unordered_map<TableKey, TableValue, TableKeyHasher>;