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 ?
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.
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.
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).
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.
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.
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;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With