Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Using std::set container for range items

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 ?

like image 862
Irad K Avatar asked Mar 05 '19 08:03

Irad K


People also ask

How do you check if an element exists in a set C++?

set find() function in C++ STL The set::find is a built-in function in C++ STL which returns an iterator to the element which is searched in the set container. If the element is not found, then the iterator points to the position just after the last element in the set.

What is the difference between set and Vector in C++?

Vector is faster for insertion and deletion of elements at the end of the container. Set is faster for insertion and deletion of elements at the middle of the container.

Is std::set ordered?

Yes, std::set stores its elements in such a way that iterating over the elements will be done in sorted order (and the call to std::adjacent_find is to show that std::set stores unique items as well).

How do you add values to a set in C++?

insert() function is an inbuilt function in C++ STL, which is defined in <set> header file. This function is used to insert elements in the set container. when we insert the element the size of the container is increased by the number of the elements inserted.


2 Answers

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.

like image 150
lubgr Avatar answered Oct 08 '22 10:10

lubgr


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;
}
like image 42
Michael Lukin Avatar answered Oct 08 '22 10:10

Michael Lukin