C++: Maps on Chains
(bannalia.blogspot.com)41 points by signa11 3 days ago
41 points by signa11 3 days ago
Or since C++20, just default operator<=>: https://en.cppreference.com/w/cpp/language/default_compariso...
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.
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.
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:
That’s the same idea as putting intervals in map, an ordered tree.
Unless you know about the internal implementation of std::map, then abusing the ordering function (which is expected be a total order according to the std::map documentation - i.e. capable of comparing any two elements of the key space) to throw exception when the API for std::map is used in a way you want to block - is not a robust solution. This will probably work but there’s nothing that constrains std::map to be implemented as a RB tree.
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.
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