如何使用 C++11 声明静态查找 table
How to declare a static lookup table using C++11
我有一个 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 应该是 return 值，如果输入介于 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 中，我可以设置一个很好的静态查找 table 来实现这一点，而不必编写 if else 吗？我可以在头文件中声明一些静态 table，其中包含输出值？
在 C++11 中执行此操作的一些聪明方法？我大概可以试试std::map<std::pair<unsigned int, unsigned int>, unsigned int>？但是，想知道使用它的好方法或更简单的方法..
PS: 我不确定它是否称为查询 table 或其他。但是，为某个 pair/range 值选择硬编码值的东西。
那么你可以简单地声明你的 table
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];
}
强力方法是用结构对每一行建模：
struct Record
{
int range_minimum;
int range_maximum;
int value;
};
您的查找 table 将如下所示：
static const Record table[] =
{
/* min, max, value */
{ 1, 10, 5},
{11, 14, 13},
{15, 20, 17},
//...
};
const unsigned int quantity_entries =
sizeof(table) / sizeof(table[0]);
您可以编写一个搜索循环：
int search_value = 0;
std::cin >> search_value;
//...
for (unsigned int i = 0; i < quantity_entries; ++i)
{
const int minimum = table[i].range_minimum;
const int maximum = table[i].range_maximum;
if ((search value >= minimum) && (search_value <= maximum))
{
std::cout << "Value is: " << table[i].value << "\n";
break;
}
}
if (i >= quantity_entries)
{
std::cout << "Search value not found in table.\n";
}
此技术允许您添加或删除行或更改 table 中的值，而无需更改代码。只需要测试一次代码。
如果指标有特殊含义，那么这种方法可能会有所帮助。初始化是在编译时完成的，所以在执行过程中是 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];
}
您可以使用 std::lower_bound 选择合适的范围。 “键”是范围内的最大值，“值”是结果。
unsigned int GetValueBasedOnRange(const int value) {
using elem = std::map<int, unsigned>::value_type;
using less = std::map<int, unsigned>::value_compare;
static const std::array<elem, 10> range {
{ 0, 0 },
{ 10, 5 },
{ 14, 13 },
{ 20, 17 },
{ 28, 24 },
{ 36, 31 },
{ 47, 43 },
{ 52, 50 },
{ 60, 53 },
{ 65, 65 },
};
auto it = std::lower_bound(range.begin(), range.end(), value, less{});
return it != range.end() ? it->second : 0;
}
std::map<int, unsigned> 也适用，它的成员 lower_bound.
你不需要比 table 和 STL 更进一步：
#include <array>
#include <algorithm>
#include <limits>
using range_val_t = int;
using answer_val_t = int;
int find(range_val_t value){
using p_t = std::pair<range_val_t,answer_val_t>;
p_t min_placeholder{std::numeric_limits<range_val_t>::min(),answer_val_t()};
// Upper bound of each range
static const p_t table[] = {min_placeholder,{10,5},{14,13},{20,17},{28,24}};
auto comp = [](const p_t& a,range_val_t b){ return a.first<b;};
auto IT = std::lower_bound(std::begin(table),std::end(table),value,comp);
//Out of range error
if(IT==std::begin(table) || IT == std::end(table));
return IT->second;
}
#include <iostream>
int main()
{
std::cout<<find(7)<<'\n'; //5
std::cout<<find(10)<<'\n';//5
std::cout<<find(11)<<'\n';//13
std::cout<<find(14)<<'\n';//13
std::cout<<find(15)<<'\n';//17
std::cout<<find(19)<<'\n';//17
std::cout<<find(20)<<'\n';//17
std::cout<<find(21)<<'\n';//24
}
如果范围应该是不可变的，那么 c99 就足够了（使用 const 而不是 conexpr）：
struct {
int bound, value;
} static constexpr mapping[]={
{1,0},{11,5},{15,13},/*...*/{53,50},{61,53},{69,65}
};
auto getValue(int x){
for(auto m: mapping)
if(x<m.bound)
return m.value;
return -1;
};
您必须断言边界是严格递增的：
#include <type_traits>
for(auto i=0; i<std::extent<decltype(mapping){}-1;++i)
assert((mapping[i].bound<mapping[i+1].bound));
我有一个 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 应该是 return 值，如果输入介于 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 中，我可以设置一个很好的静态查找 table 来实现这一点，而不必编写 if else 吗？我可以在头文件中声明一些静态 table，其中包含输出值？
在 C++11 中执行此操作的一些聪明方法？我大概可以试试std::map<std::pair<unsigned int, unsigned int>, unsigned int>？但是，想知道使用它的好方法或更简单的方法..
PS: 我不确定它是否称为查询 table 或其他。但是，为某个 pair/range 值选择硬编码值的东西。
那么你可以简单地声明你的 table
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];
}
强力方法是用结构对每一行建模：
struct Record
{
int range_minimum;
int range_maximum;
int value;
};
您的查找 table 将如下所示：
static const Record table[] =
{
/* min, max, value */
{ 1, 10, 5},
{11, 14, 13},
{15, 20, 17},
//...
};
const unsigned int quantity_entries =
sizeof(table) / sizeof(table[0]);
您可以编写一个搜索循环：
int search_value = 0;
std::cin >> search_value;
//...
for (unsigned int i = 0; i < quantity_entries; ++i)
{
const int minimum = table[i].range_minimum;
const int maximum = table[i].range_maximum;
if ((search value >= minimum) && (search_value <= maximum))
{
std::cout << "Value is: " << table[i].value << "\n";
break;
}
}
if (i >= quantity_entries)
{
std::cout << "Search value not found in table.\n";
}
此技术允许您添加或删除行或更改 table 中的值，而无需更改代码。只需要测试一次代码。
如果指标有特殊含义，那么这种方法可能会有所帮助。初始化是在编译时完成的，所以在执行过程中是 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];
}
您可以使用 std::lower_bound 选择合适的范围。 “键”是范围内的最大值，“值”是结果。
unsigned int GetValueBasedOnRange(const int value) {
using elem = std::map<int, unsigned>::value_type;
using less = std::map<int, unsigned>::value_compare;
static const std::array<elem, 10> range {
{ 0, 0 },
{ 10, 5 },
{ 14, 13 },
{ 20, 17 },
{ 28, 24 },
{ 36, 31 },
{ 47, 43 },
{ 52, 50 },
{ 60, 53 },
{ 65, 65 },
};
auto it = std::lower_bound(range.begin(), range.end(), value, less{});
return it != range.end() ? it->second : 0;
}
std::map<int, unsigned> 也适用，它的成员 lower_bound.
你不需要比 table 和 STL 更进一步：
#include <array>
#include <algorithm>
#include <limits>
using range_val_t = int;
using answer_val_t = int;
int find(range_val_t value){
using p_t = std::pair<range_val_t,answer_val_t>;
p_t min_placeholder{std::numeric_limits<range_val_t>::min(),answer_val_t()};
// Upper bound of each range
static const p_t table[] = {min_placeholder,{10,5},{14,13},{20,17},{28,24}};
auto comp = [](const p_t& a,range_val_t b){ return a.first<b;};
auto IT = std::lower_bound(std::begin(table),std::end(table),value,comp);
//Out of range error
if(IT==std::begin(table) || IT == std::end(table));
return IT->second;
}
#include <iostream>
int main()
{
std::cout<<find(7)<<'\n'; //5
std::cout<<find(10)<<'\n';//5
std::cout<<find(11)<<'\n';//13
std::cout<<find(14)<<'\n';//13
std::cout<<find(15)<<'\n';//17
std::cout<<find(19)<<'\n';//17
std::cout<<find(20)<<'\n';//17
std::cout<<find(21)<<'\n';//24
}
如果范围应该是不可变的，那么 c99 就足够了（使用 const 而不是 conexpr）：
struct {
int bound, value;
} static constexpr mapping[]={
{1,0},{11,5},{15,13},/*...*/{53,50},{61,53},{69,65}
};
auto getValue(int x){
for(auto m: mapping)
if(x<m.bound)
return m.value;
return -1;
};
您必须断言边界是严格递增的：
#include <type_traits>
for(auto i=0; i<std::extent<decltype(mapping){}-1;++i)
assert((mapping[i].bound<mapping[i+1].bound));