I see some behaviour in std::unordered_set that I need to understand better.
I created a struct that also provides a "hash" function and an "equality" function. The struct contains values for an interval, the lower and upper bound. I use the struct in the std::unordered_set definition also as the "hash" and "equal_to" template argument. Many will not like it, but for the MRE it is OK. No need to write separate functors.
I want to add only disjoint intervals to a std::unordered_set. So, I use a selfmade disjoint-function and consider 2 intervals to be equal, if they overlap.
I have written some test function (MRE) below.
Why can I insert intervals [1,5] and [2,3] although they overlap and are considered to be equal?
Maybe becuase of the different hash values and the nature of the underlying hash table in the std::unordered_set? Please kindly confirm.
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_set>
struct Interval {
int left{};
int right{};
bool isDisjoint(const Interval& other) const {
return left < other.right && right < other.left;
}
// Hash function
std::size_t operator()(const Interval& i) const {
std::size_t result = static_cast<std::size_t>(i.left) + (static_cast<std::size_t>(i.right) << 16);
return result;
}
// Comparison for equality
bool operator ()(const Interval& lhs, const Interval& rhs) const {
bool result = not lhs.isDisjoint(rhs);
return result;
}
//bool operator== (const Interval& other) const {
// bool result = not isDisjoint(other);
// return result;
//}
// Simple output
friend std::ostream& operator << (std::ostream& os, const Interval& i) {
return os << '[' << i.left << ','<< i.right << ']';
}
};
std::vector<Interval> intervals{ {1,5},{2,3},{1,10},{5,10},{6,8} };
int main() {
std::unordered_set< Interval, Interval, Interval> disjointIntervals{};
// Special test for first 2 intervals
std::cout << ((not intervals[0].isDisjoint(intervals[1]))?"[1,5] is equal to [2,3]": "[1,5] is NOT equal to [2,3]") << '\n';
for (const auto& i : intervals) {
// Test for hash values. They are all different
std::cout << "Interval: " << (static_cast<std::size_t>(i.left) + (static_cast<std::size_t>(i.right) << 16)) << " \tHash: " << (i.left + (i.right << 16)) << '\n';
disjointIntervals.insert(i);
}
for (const auto& i : disjointIntervals)
std::cout << i << '\n';
}