Ryfujk

I'd like to store a bunch of range items in std::set container.

This data structure should provide fast decision whether a specific input range contained by one of the ranges that the set currently holds, by overloading the comparison of std::set in order use the set::find method to check one of the items in set contain the input range argument.

It should also support range item that represents a single point (start_range == end_range).

Here's my implementation :

#include <iostream>

#include <map>

#include <set>

using std::set;

using std::map;



class range : public std::pair<int,int>

{

public:

    range(int lower, int upper)

    {

        if (upper < lower)

        {

           first = upper;

           second = lower;

        }

        else

        {

           first = lower;

           second = upper;

        }

    }

    range(int val)

    {

        first = second = val;

    }

    bool operator<(range const & b) const

    {

        if (second < b.first)

        {

            return true;

        }

        return false;

    }

};

And here's how I test my data structure:

int main(int argc, const char * argv[])

{

    std::map<int, std::set<range>> n;



    n[1].insert(range(-50,-40));

    n[1].insert(range(40,50));

    n[2].insert(range(-30,-20));

    n[2].insert(range(20,30));

    n[3].insert(range(-20,-10));

    n[3].insert(range(10,20));



    range v[] = {range(-50,-41), range(30,45), range(-45,-45), range(25,25)};

    int j[] = {1,2,3};

    for (int l : j)

    {

        for (range i : v)

        {

            if (n[l].find(i) != n[l].end())

            {

                std::cout << l << "," << i.first << ","  << i.second << " : " 

                          << n[l].find(range(i))->first  << " "

                          << n[l].find(range(i))->second << std::endl;

            }

        }

    }

}

and here are the results I get:

1,-50,-41 : -50 -40 --> good 

1,30,45 : 40 50     --> bad

1,-45,-45 : -50 -40 --> good

2,30,45 : 20 30     --> bad

2,25,25 : 20 30     --> good

So as you can see, my code does support perfectly well single point range (-45 is contained by range (-50,-40) and 25 is contained by by range (20,30))

However, as for wider ranges, my current operator < is capable of finding the contained relationship which is equal for the set terminology (meaning that for ranges a and b a<b && a<b.

Is there anyway to change this operator to make it work ?

Your operator < defines partial order:
(30,45) < (40, 50) == false and simultaneously (40, 50) < (30, 45) == false so in terms of std::set and std::map they are equal. That is why you got these results.

There is a paper about partial order: https://en.wikipedia.org/wiki/Partially_ordered_set

You might want use std::unordered_map or define somehow total order for your ranges.

I suggest operator < that compares the arithmetical mean of range bounds, i.e.
(a, b) < (c, d) if and only if (a+b)/2 < (c+d)/2 for total order. Note that you might want use float for arithmetical mean.

For testing I suggest the following code draft (I write here from scratch and didn't tested it). -1 meanst that are no range that contains this

int range::firstContainsMe(const std::vector<range> rangesVec)

{

    for (size_t i = 0; i < rangesVec; i++) {

        if (lower >= rangesVec[i].lower && upper <= rangesVec[i].upper) {

            return i;

        }

    }

    return -1;

}

Sounds like a perfect match for using Boost Interval Container Library. In short, you can

#include <boost/icl/interval_set.hpp>



// Helper function template to reduce explicit typing:

template <class T>

auto closed(T&& lower, T&& upper)

{

   return boost::icl::discrete_interval<T>::closed(std::forward<T>(lower),

        std::forward<T>(upper));

}



boost::icl::interval_set<int> ranges;



ranges.insert(closed(1, 2));

ranges.insert(closed(42, 50));



std::cout << contains(ranges, closed(43, 46)) << "n"; // true

std::cout << contains(ranges, closed(42, 54)) << "n"; // false

This should easily be pluggable into your std::map and be usable without further adjustments.