This had bit me in the past with std::sort that made seemingly benign code randomly crash a live service, cppreference has a list of all the standard facilities that need to meet these requirements: https://en.cppreference.com/w/cpp/named_req/Compare.html
That’s fine if you just need any well-defined SWO, but I presume the author needs this specific ordering for some algorithmic reason. Still, it’s pretty ugly for a comparator to be throwing.
I don’t understand the point of this article. There is no requirement stated regarding the properties of the ordering - in fact there is no code at all that depends on the traversing the map elements in a particular order. So you can pick any ordering you want.
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.
This is one of those cases where being able to name the problem helps. It's a discrete interval problem and is typically solved by a discrete interval tree.
That would indeed satisfy std::map, but then the question is, is that a useful ordering for intervals? To answer that, you need to define what you want to use the interval map for. If you want to be able to lookup in which unique interval a given value is, then you shouldn't have overlapping intervals to begin with. If you do allow overlapping intervals, a query could result in multiple intervals. Are lookups by value (not by interval) still O(log N) with that ordering?
This had bit me in the past with std::sort that made seemingly benign code randomly crash a live service, cppreference has a list of all the standard facilities that need to meet these requirements: https://en.cppreference.com/w/cpp/named_req/Compare.html
Why can't you use this for the comparison operator:
That’s fine if you just need any well-defined SWO, but I presume the author needs this specific ordering for some algorithmic reason. Still, it’s pretty ugly for a comparator to be throwing.
better implemented as
Or since C++20, just default operator<=>: https://en.cppreference.com/w/cpp/language/default_compariso...
I don’t understand the point of this article. There is no requirement stated regarding the properties of the ordering - in fact there is no code at all that depends on the traversing the map elements in a particular order. So you can pick any ordering you want.
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.
> 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.
This is one of those cases where being able to name the problem helps. It's a discrete interval problem and is typically solved by a discrete interval tree.
Diets are a particularly clever solution to this:
https://web.engr.oregonstate.edu/~erwig/diet/
That’s the same idea as putting intervals in map, an ordered tree.
I agree. This seems very unintuitive and would be a code smell in a review.
It's a somewhat interesting article, but it doesn't say much. It starts with:
> 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.
Throwing a runtime error seems like an absurd solution compared to changing the comparison operator or using an unordered_map
What's wrong with x.min < y.min || (x. min == y.min && x.max < y. max)
That would indeed satisfy std::map, but then the question is, is that a useful ordering for intervals? To answer that, you need to define what you want to use the interval map for. If you want to be able to lookup in which unique interval a given value is, then you shouldn't have overlapping intervals to begin with. If you do allow overlapping intervals, a query could result in multiple intervals. Are lookups by value (not by interval) still O(log N) with that ordering?
He’s just asserting he’s using the data structure in the way he wants to.