如何使用 C++11 声明静态查找表

Question

我有 C++11 程序，它需要从一系列值中选择一个值。每个范围都有一个指定的值以从中选择一个值。

以下是我的值范围，并为每个值分配了值。

1-10 = 5
11-14 = 13
15-20 = 17
21-28 = 24
29-36 = 31
37-47 = 43
48-52 = 50
53-60 = 53
61-68 = 65

因此，如您所见，如果输入介于 1-10 之间，则 5 应为返回值，如果输入介于 11-14 之间，则应选择 13，依此类推。

上面的要求可以通过下面的程序来实现，其中包含一个很大的 if else 语句的脏列表。

#include <iostream>

// Following are return values to chosen based on which range the input value falls within
// 1-10 = 5
// 11-14 = 13
// 15-20 = 17
// 21-28 = 24
// 29-36 = 31
// 37-47 = 43
// 48-52 = 50
// 53-60 = 53
// 60-68 = 65

unsigned int GetValueBasedOnRange(const int value) {
    int value_picked_from_appropriate_range = 0;

    if (value > 1 && value < 10) {
        value_picked_from_appropriate_range = 5;
    } else if (value > 11 && value < 14) {
        value_picked_from_appropriate_range = 13;
    } else if (value > 15 && value < 20) {
        value_picked_from_appropriate_range = 17;
    } else if (value > 21 && value < 28) {
        value_picked_from_appropriate_range = 24;
    } else if (value > 29 && value < 36) {
        value_picked_from_appropriate_range = 31;
    } else if (value > 37 && value < 47) {
        value_picked_from_appropriate_range = 43;
    } else if (value > 48 && value < 52) {
        value_picked_from_appropriate_range = 50;
    } else if (value > 53 && value < 60) {
        value_picked_from_appropriate_range = 53;
    } else if (value > 61 && value < 68) {
        value_picked_from_appropriate_range = 65;
    } 

    return value_picked_from_appropriate_range;
}

int main() {
    unsigned int value_within_a_range = 42;
    std::cout << GetValueBasedOnRange(value_within_a_range) << std::endl;
}

上面的程序运行良好，但是 if else 语句的大列表很糟糕。此外，如果将来有更多值和范围，它们会影响 if else 逻辑。在 C++ 11 中有没有办法可以设置一个漂亮的静态查找表来实现这一点，而不必编写 if else？我可以在头文件中声明一些静态表，并在其中声明输出值？

在 C++11 中这样做的一些聪明方法？我大概可以试试std::map<std::pair<unsigned int, unsigned int>, unsigned int>? 但是，想知道使用它的好方法或更简单的方法..

PS：我不确定它是否称为查找表或其他东西。但是，为某个值对/范围选择硬编码值的东西。

Answer 1

那么你可以简单地声明你的表

static constexpr int table[] = 
{
    0, // dummy value
    5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
    13, 13, 13, 13,
    17, 17, 17, 17, etc...
};

然后正确访问它。这很繁琐而且容易出错，但它可以工作并让您可以O(1)访问它。

另一种方法是使用c范围。你需要一个table.h：

extern "C" int* table;

和一个table.c文件：

int table[] =
{
    [1 ... 5] = 5,
    etc...
}

主要原因是C++不支持这种初始化，而C99支持，所以需要用普通c编译器编译。

然后你可以像这样使用它：

int main()
{
    int a = table[2] // = 5
    int b = table[11] // = 13
}

并使用您的功能：

unsigned int GetValueBasedOnRange(const int value) {
    assert(value > 0 && value < maxTableSize);
    return table[value];
}

Answer 2

如果索引具有特殊含义，那么这种方法可能会有所帮助。初始化是在编译时完成的，因此在执行期间是 O(1)：

#include <array>

template<typename ARRAY>
constexpr void fill_range(ARRAY& array, int first, int last, int value)
{
    for(int i = first; i <= last; ++i)
        array[i] = value;
}

constexpr std::array<int, 69> make_table()
{
    std::array<int, 69> a {0};
    fill_range(a, 1, 10, 5);
    fill_range(a, 11, 14, 13);
    fill_range(a, 15, 20, 17);
    fill_range(a, 21, 28, 24);
    fill_range(a, 29, 36, 31);
    fill_range(a, 37, 47, 43);
    fill_range(a, 48, 52, 50);
    fill_range(a, 53, 60, 53);
    fill_range(a, 61, 68, 65);
    return a;
}

constexpr auto arr = make_table();

int main()
{
      return arr[65];
}