Best C++ STL way to map ranges to values?

Question

Want to know the most efficient way to map ranges of values in C++

When for example:

I have a bunch of objects differentiated by integer key ranges, e.g.

0-10 -> object a
11-20 -> object b
21-30 -> object c

Where objects are a particular class with a few variables of their own inside. There should be a thousand objects in this scenario.

I was wondering what is the best/fastest way in C++ STL to lookup an object based on an input key. e.g.

lookup(13) -> object b

Note that the ranges are not fixed and may not be of equal size.

Thanks

Answer 1

Easily accomplished with std::map and it's upper_bound function.

Use the lower end of each range as the key into a map. The corresponding value of the map type is a triple of {lower bound, upper bound, and item}. Then to lookup an object based on a specific value, invoke map::upper_bound and to find the the item in the map that is "one past" the matching item. Then "go back 1" and test to see if it's a match.

#include <algorithm>
#include <iostream>
#include <map>

template <typename T>
struct RangeAndValue
{
    int low;
    int high;
    T value;
};

template <typename T>
struct RangeTable
{
    std::map<int, RangeAndValue<T>> table;
    void Insert(int low, int high, const T& t)
    {
        table[low] = {low, high, t};
    }

    bool Lookup(int value, T& t)
    {
        auto itor = table.upper_bound(value);
        if (itor != table.begin())
        {
            itor--;
            if ((value >= itor->second.low) && (value <= itor->second.high))
            {
                t = itor->second.value;
                return true;
            }
        }
        return false;
    }
};

Proof of concept (using your sample ranges of 0-10 maps to a, 11-20 maps to b, and 21-30 maps to c)

int main()
{
    RangeTable<std::string> rangeTable;

    rangeTable.Insert(0, 10, "a");
    rangeTable.Insert(11,20, "b");
    rangeTable.Insert(21,30, "c");

    for (int i = -1; i < 32; i++)
    {
        std::string s;
        bool result = rangeTable.Lookup(i, s);
        std::cout << i << " : " << (result ? s : "<not found>") << std::endl;
    }

    return 0;
}

Produces expected results when run:

$ g++ main.cpp -o testapp
$ ./testapp
-1 : <not found>
0 : a
1 : a
2 : a
3 : a
4 : a
5 : a
6 : a
7 : a
8 : a
9 : a
10 : a
11 : b
12 : b
13 : b
14 : b
15 : b
16 : b
17 : b
18 : b
19 : b
20 : b
21 : c
22 : c
23 : c
24 : c
25 : c
26 : c
27 : c
28 : c
29 : c
30 : c
31 : <not found>

Answer 2

Same idea as @selbie's answer, but using a transparent comparator to avoid wrapping the map in your own class:

#include <compare>
#include <iostream>
#include <map>
#include <string>

template <typename T>
struct Range
{
    T begin{}, end{};

    friend constexpr auto operator<=>(const Range &, const Range &) = default;
    friend constexpr std::weak_ordering operator<=>(const Range &a, T b)
    {
        if (b < a.begin)
            return std::weak_ordering::greater;
        else if (b > a.end)
            return std::weak_ordering::less;
        else
            return std::weak_ordering::equivalent;
    }
};

int main()
{
    std::map<Range<int>, std::string, std::less<>> m = {
        {{0, 5}, "A"},
        {{6, 10}, "B"},
        {{11, 15}, "C"},
    };

    auto check = [&](int n)
    {
        auto it = m.find(n);
        if (it != m.end())
            std::cout << n << " -> " << it->second << '\n';
        else
            std::cout << n << " not in the map\n";
    };

    check(0); // A
    check(1); // A
    check(5); // A
    check(6); // B
    check(-1); // not in the map
    check(16); // not in the map
}

First, we use std::less<> (without the template argument - the transparent version), which makes .find() a template, accepting any type comparable with the key type.

Next we make a range class that overloads comparison operators (using C++20) with itself and with its element type.

You could do the same thing with std::pair and with a custom transparent comparator (add using is_transparent = void;) that compares it with the numbers in the correct way.