C++: Maps on Chains
bannalia.blogspot.com
bannalia.blogspot.com
bool operator<(const interval& x, const interval& y)
{
if x.min < y.min return true;
if x.min > y.min return false;
return x_max < y.max;
} tie(x.min, x.max) < tie(y.min, y.max)What's wrong with x.min < y.min || (x. min == y.min && x.max < y. max)
> Suppose we want to have a C++ map where the keys are disjoint
And then we do something that goes against the whole point of such a map:
> But what happens if we try to insert an interval which is not disjoint with those already in the map?
And the solution is:
> Implementation-wise, we just have to [throw an exception if we are] comparing partially overlapping intervals
Much more interesting would be to show how to implement a proper interval map.
std::sort(entries.begin(), entries.end(), [&last] (const auto &a, const auto &b) {
if (last && last->getID() == a.id) {
return true;
}
return a.time < b.time;
});1. std::find last
2. std::iter_swap(first, found)
3. std::sort(front + 1, back)
If the requirement is “use std::map to store items but prevent adding items to the map if they have a particular relationship to existing map keys”, then this is a terrible solution - std::map like maps and dictionaries in all programming language is not designed for this - it should never be an error to add a value associated with a key to a map instance. Hacking the ordering to implement a requirement like this is brittle, obscure and strange.
If this were proposed as a solution to the problem “design a data structure to store values keyed by intervals that prevents overlapping intervals”, then I would mark it very low.
What would you do differently?
I would also assert if any overlapping intervals were inserted - it’s an invariant.
If it was static I would just sort and binary search, but with inserts this seems like a fine way to reuse the std::map.
Std templates are designed for this kind of thing - make a custom comparator, document why it works, wrap it in a typedef.
Diets are a particularly clever solution to this:
Nor is it intuitive - given it relies on understanding how balanced trees are typically implemented.
An “optimized” implementation of std::map should be entitled, for example, to cache results of previous comparisons and exploit the transitive rule for total orders to avoid unnecessarily performing comparisons. Then this solution breaks.
I know whining about downvotes is frowned upon here but I’m surprised to having lost karma here. I’m making what I believe is a good faith argument and am happy to debate my position.
That's the thing about C++. It's not abuse - any strict weak ordering is valid. You are follow the rules and it's guaranteed mathematically to produce correct results.
> capable of comparing any two elements of the key space
You get to define the domain of keys which is almost always a restriction of the possible bits of the key. For example, you can use floats as keys even though nan would break.
> Nor is it intuitive
Intuitive too often means "I haven't seen it before" which is a bias to not learn new approaches of programming. All sufficiently technical knowledge is unintuitive.
- it relies on understanding how balanced trees are typically implemented.
No it doesn't. It's documented API.
> exploit the transitive rule for total orders to avoid unnecessarily performing comparisons
Yes, the comparison must satisfy transitivity. This doesn't violate that.
> I know whining about downvotes is frowned upon here
I downvote low-quality, not to disagree (I did not downvote).