c++ - 构造一个大型多维 vector 数组

Question

现在我有一个 vector std::vector<char> myVector(4)包含一组 char 的任意组合可以说 {@,#,O,*,%,$,!} 可能或多或少但不会多于此，也可能不总是 4 个成员，但对于任何一个实例。

现在我坚持尝试创建一个数据结构，该数据结构可以使用不定数量的这些组合作为索引到另一个 vector 。

在我试图完成的伪代码中:

SomeDataStructure['*']['#']['@']['O'] = someData

(someData 将是一个小类，但这应该无关紧要)

这是一个需要快速运行的关键操作部分，并且会经常运行。

我试图与之推理的一些人是: 一个 4 维数组，但我可以访问那些没有数字索引的数组。也许某种形式的枚举可以解决这个问题。编辑: map 会是执行此操作的一种方式吗？

---

编辑:

我使用 map 解决了这个问题:

std::map<std::vector<char>, someData> myMap;

Answer 1

由于可能的字符数限制为 8 个，因此您可以改用枚举。因此，您只需要 3 位来表示每个“字符”。您可以使用位域 将这些 3 位“字符”中的几个打包成一个短整数。生成的压缩整数成为 vector<SomeData> 的索引.

这个 vector 占用的空间是space_of_SomeData * 2^(3*number_of_spaces) .例如，如果 number_of_spaces是 4，结果是 4096*space_of_SomeData .这可能会导致一些内存空间浪费，但查找和插入应该非常快。

下面是一些示例代码:

#include <vector>

enum CharSet
{
    ampersand,
    pound,
    letterOh,
    percent,
    dollar,
    exclamation
};

struct CompositeIndex
{
    union
    {
        struct // Bitfield
        {
            unsigned c0 : 3; // 3 bits
            unsigned c1 : 3; // 3 bits
            unsigned c2 : 3; // 3 bits
            unsigned c3 : 3; // 3 bits
        } chars;

        unsigned int index;
    };
};

unsigned int lookup(CharSet c0, CharSet c1, CharSet c2, CharSet c3)
{
    CompositeIndex ci;
    ci.chars.c0 = c0;
    ci.chars.c1 = c1;
    ci.chars.c2 = c2;
    ci.chars.c3 = c3;
    return ci.index;
}

typedef int SomeClass;

int main(int argc, char* argv[])
{
    std::vector<SomeClass> vec(100);
    vec[lookup(ampersand, percent, dollar, pound)] = 42;
}

如果您绝对必须使用 char字符，您可以轻松创建一个 256 元素的查找表，快速将 'char' 字符转换为 CharSet值(value)观。

---

正如其他人已经讨论过的，您可以使用 std::map<std::string, SomeData>甚至(可能更快)std::map<char[4], SomeData, Comparitor> .如果已知不同字符序列的大致频率分布，请尝试首先在映射中插入最频繁出现的模式。根据映射的内部实现，这可能会加快查找最常见模式的速度(它们靠近底层二叉搜索树的顶部)。