Using std::set container for range items
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;
}
Your comparison operator is unsuitable.
If you wish to use any container or algorithm based on ordering in C++, the ordering relation needs to be a Strict Weak Ordering Relation. The definition can be found on Wikipedia, in short the following rules must be respected:
- Irreflexivity: For all x in S, it is not the case that x < x.
- Asymmetry: For all x, y in S, if x < y then it is not the case that y < x.
- Transitivity: For all x, y, z in S, if x < y and y < z then x < z.
- Transitivity of Incomparability: For all x, y, z in S, if x is incomparable with y (neither x < y nor y < x hold), and y is incomparable with z, then x is incomparable with z.
Your comparison operator fails, and therefore is unsuitable. In general, a quick way of obtaining a good comparison operator is to do what tuples do:
bool operator<(range const & b) const
{
return std::tie(first, second) < std::tie(b.first, b.second);
}
You want a map, not a set.
In order to solve your problem, you want a map, not a set.
For disjoint intervals, a map from lower-bound to upper-bound is sufficient:
std::map<int, int> intervals;
The .lower_bound
and .upper_bound
operations allow finding the closest key in O(log N) time, and from there containment is quickly asserted.
For non-disjoint intervals, things get trickier I fear, and you'll want to start looking into specialized data-structures (Interval Trees for example).