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.

Telegu

Unrelated: your ranges in the if-else conditions don't seem to overlap. Is that intentional? Or did you mean to use <= instead of <? – Donndonna

Did you mean for 60 to be included in two different ranges? – Shrivel

Yes. The ranges are non overlapping. That is intentional. – Telegu

I corrected the issue with 60. Sorry that was a mistake which I corrected – Telegu

Using a std::map would be difficult because your map key is a range. The std::map likes to have keys that are constant. – Ravish

Prefer to use math (algebra), to determine a relationship between the ranges or search value and the result value. This would be the most efficient and simplest. – Ravish

In general, an if ... else if .. ladder is more readable if it's clear that the ranges are contiguous. (not to mention more likely to be correct) The code in the question, if it properly implemented what's described in the text, has redundant tests. Do it like this: if (value < 1) picked = 0; else if (value < 11) picked = 5; else if (value < 15) picked = 13; etc.. – Wingo

Answer 1

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

Bradlybradman

constexpr auto arr = make_table() should be declared as const auto arr = make_table(). Otherwise it does not compile. But other than that this C++11 technique works great! – Telegu

Lots of good answers. But this is the one felt the simplest for me. If there were multiple answers, I could have chosen, I would have accepted more than one answer. All answers are really good and and great learning for me! – Telegu

Answer 2

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

Varick

Perfect, except that you need a dummy entry at the start of the array to account for zero-indexing. – Shrivel

How to access this table? Do you mind writing your logic in the sample program I used in my question? – Telegu

I am forced write C++ 11 code. You constexpr technique looks interesting to me. – Telegu

Well it's the same, it's just that you really need to be careful to write the table correctly! The constexpr isn't really necessary but allow you to use your table in constexpr functions. – Varick

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.

Ravish

Answer 4

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.

Potentiality

Answer 5

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
}

Argentiferous

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

Counsellor