How to declare a static lookup table using C++11

Question

I have C++11 program which needs to pick a value from a range of values. Each of the ranges have an assigned value to pick a value from.

Following is my range of values with assigned values for each.

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

So, as you can see above 5 should be return value if the input falls between 1-10, 13 should be chosen if the input falls between 11-14 and so on.

Above requirement could be acheived with the following program with a big dirty list of if else statements.

#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;
}

Above program works fine but the big if else list of statements is bad. Also, if there are more values and ranges coming in future, they affect the if else logic. Is there way in C++ 11 that I could set up a nice static look up table to achieve this without having to write if else? Some static table that I could declare in a header file with the output values in there?

Some smart way of doing this in C++11? I can probably try an std::map<std::pair<unsigned int, unsigned int>, unsigned int>? But, wondering of a nice way using that or an even simpler approach..

PS: I am not sure if its called a look up table or something else. But, something that picks a hard coded value for a certain pair/range of values.

Answer 1

Well you could simply declare your 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...
};

And then accessing it correctly. This is tideous to do and prone to errors but it works and gives you a O(1) access to it.

Another way would be to use c range. You would need a table.h:

extern "C" int* table;

and a table.c file:

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

The main reason is that this initialization is not supported in C++ but is supported in C99, so you need to compile it using a regular ccompiler.

You can then use it like this:

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

and using your function:

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

Answer 2

If the indicies have special meaning then this approach may be helpful. The initialization is done in the compile time, so during execution it is 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];
}

Answer 3

The brute-force method would be to model each row with a structure:

struct Record
{
    int range_minimum;
    int range_maximum;
    int value;
};

Your lookup table would look like this:

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]);

You could write a search loop:

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";
}

This technique allows you to add or remove rows or changing the values in the table without having to change the code. Only need to test the code once.

Answer 4

You do not need to go further than a table and 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
}

Answer 5

You can use std::lower_bound to pick the right range. The "key" is the highest value in the range, and the "value" is the result.

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> also works, with it's member lower_bound.

Answer 6

If the range is supposed to be immutable, then c99 would suffice (use const instead of consexpr):

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;
 };

You've got to assert that the bounds are strictly increasing:

#include <type_traits>
for(auto i=0; i<std::extent<decltype(mapping){}-1;++i)
      assert((mapping[i].bound<mapping[i+1].bound));