1

我需要在我的 C++ 程序中使用静态表来查找组合。

这是一个简单的例子（我的表会大 3-4 倍）：

int TABLE[3][3] = {
           /*2*/ /*4*/ /*8*/ 
    /*2*/   {4,    8,    16},
    /*4*/   {8,    16,   32},
    /*8*/   {16,   32,   64}
};

我喜欢这种表，因为它很容易从索引中查找组合，也很容易看到组合。

但是，我不喜欢“键”仅在似乎错误的注释中定义的事实。

有没有人在代码中定义了类似的表，有没有一般性的建议？

编辑：我的表无法计算。这是程序特定的“设置”。

4

4 回答 4

3

由于您还标记了您的问题，您始终可以使用 a std::unordered_mapinside another std::unordered_map：

std::unordered_map<int, std::unordered_map<int, int>> TABLE = {
    { 2, { { 2,  4 }, { 4,  8 }, { 8, 16 } } },
    { 4, { { 2,  8 }, { 4, 16 }, { 8, 32 } } },
    { 8, { { 2, 16 }, { 4, 32 }, { 8, 64 } } }
//    ^      ^   ^
//    |      |   |
//    |      |   value at [row][column]
//    |      |
//    |      column
//    row
};

// ...

std::cout << TABLE[1][5] << '\n';  // Outputs `0`
std::cout << TABLE[4][6] << '\n';  // Outputs `0`
std::cout << TABLE[4][4] << '\n';  // Outputs `16`

在纯 C 中，如果不填充数组，就无法在特定“键”处获得特定值：

int TABLE[9][9] = {
    {  0,  0,  0,  0,  0,  0,  0,  0,  0 },
    {  0,  0,  0,  0,  0,  0,  0,  0,  0 },
    {  0,  0,  4,  0,  8,  0,  0,  0, 16 },
    {  0,  0,  0,  0,  0,  0,  0,  0,  0 },
    {  0,  0,  8,  0, 16,  0,  0,  0, 32 },
    {  0,  0,  0,  0,  0,  0,  0,  0,  0 },
    {  0,  0,  0,  0,  0,  0,  0,  0,  0 },
    {  0,  0,  0,  0,  0,  0,  0,  0,  0 },
    {  0,  0, 16,  0, 32,  0,  0,  0, 64 }
};

但是，您应该注意不要超出索引，因为您将索引超出范围。

于 2013-05-30T09:24:21.477 回答
3

如果您需要恒定的查找时间，并且不想使用unordered_map（例如，因为您可以轻松避免哈希计算），您可以将编码与查找分开。

  1. 将数据编码为易于键入和读取的结构，包括元数据：

    struct TableElement {
    int row;
    int col;
    int val;
} raw_table[] = {
    {2, 2,  4}, {2, 4,  8}, {2, 8, 16},
    {4, 2,  8}, {4, 4, 16}, {4, 8, 32},
    {8, 2, 16}, {8, 4, 32}, {8, 8, 64} };

    （你也许可以通过一些工作让一些东西更漂亮）

  2. 从此开始快速查找（一次，在启动时）。这可能是：

    • 一个用于无索引计算的稀疏数组，如 Joachim 答案的后半部分，
    • 用于更好缓存行为的密集阵列
    • 甚至unordered_map使用自定义哈希函数
于 2013-05-30T10:10:45.413 回答
1

在 C++11 中：

#include <vector>

int main()
{
  using std::vector;
  vector<vector<int>> table = {
       /*2*/ /*4*/ /*8*/ 
       /*2*/   {4,    8,    16},
       /*4*/   {8,    16,   32},
       /*8*/   {16,   32,   64} };
}

对于std::array，这可以解决问题：

#include <array>

int main()
{
  using std::array;
  array<array<int,3>,3> table = {{
       /*2*/ /*4*/ /*8*/ 
       /*2*/   {4,    8,    16},
       /*4*/   {8,    16,   32},
       /*8*/   {16,   32,   64} }};
}

还要考虑不使用多维数组，而是使用带有索引技巧的一维数组。

于 2013-05-30T09:16:54.150 回答
1

如果你只是讨厌这些评论，最简单的方法肯定是宏。

#define _(x)

int TABLE[3][3] = {
          _(2)  _(4)  _(8) 
    _(2)   {4,    8,    16},
    _(4)   {8,    16,   32},
    _(8)   {16,   32,   64}
};

^_^

于 2013-05-30T09:35:14.460 回答