c - 当索引不连续时，设置查找表的最佳方法是什么？

Question

我有两个这样定义的枚举

enum foo {
    foo_a = 0x1,
    foo_b = 0x2,
    foo_c = 0x4,
    foo_d = 0x8,
    foo_e = 0x10,
    ..etc..
}

和

enum bar {
    bar_a = 0x1,
    bar_b = 0x2,
    bar_c = 0x4,
    bar_d = 0x8,
    bar_e = 0x10,
    ..etc..
}

现在，foo_[az] 和 bar_[az] 之间存在 1 对 1 的映射关系，我想快速查找一下。这样做的明显方法是做一些声明像

int table[][] = {
    [foo_a] = bar_c,
    [foo_b] = bar_a,
    [foo_c] = bar_b,
    ..etc..
}

并使用result = table[(enum foo)temp]. 但是由于这些枚举是按位声明的，所以的大小table呈指数增长。

有没有更简单的方法可以在编译时进行设置？

我考虑过的一件事是

int table[][] = {
    [LOG(foo_a)] = bar_c,
    [LOG(foo_b)] = bar_a,
    [LOG(foo_c)] = bar_b,
    ..etc..
}

这将减少内存占用，但我不知道无论如何要在编译时计算 LOG。

还有其他建议吗？

我唯一的限制如下，无论如何我都不能修改枚举，因为更改它们会导致二进制不兼容。

编辑：首选编译时解决方案

score 3 · Accepted Answer

是的，只要参数是 2 的幂，您就可以“在编译时计算日志”：

#define LOG2P2(m) (((m)-1)/(((m)-1)%255+1) / 255%255*8 + 7-86/(((m)-1)%255+12))

这适用于m高达 2**2040 左右的值（比实际 C 实现中的任何类型都大得多），并且在以下问题的答案中，有一个版本适用于更大的值，我从中得到了这个值：

score 1 · Accepted Answer

只需制作一个配对表：

int table[2][] = {
  { foo_a, bar_c },
  { foo_b, bar_a },
  /* ... */
};

现在对其进行排序，如果需要，将其复制到按第二个值排序的第二个表中以进行反向查找。如果表只有十几个元素，则进行线性搜索，或者bsearch()如果它很大，则使用。

score 0 · Accepted Answer

如果您知道所有枚举的值，那么您可以计算所有枚举的日志并将它们存储在缓冲区中。或者，您可以写入所有日志。文件中的值（您将要使用）并读取该文件以生成表；这样，您将计算对数。值仅是第一次。

3 回答 3