[HN Gopher] C++: Maps on Chains
___________________________________________________________________
C++: Maps on Chains
Author : signa11
Score : 41 points
Date : 2025-07-11 07:27 UTC (2 days ago)
(HTM) web link (bannalia.blogspot.com)
(TXT) w3m dump (bannalia.blogspot.com)
| gsliepen wrote:
| 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.
| Gupie wrote:
| Why can't you use this for the comparison operator:
| 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; }
| mgaunard wrote:
| better implemented as tie(x.min, x.max) <
| tie(y.min, y.max)
| gsliepen wrote:
| Or since C++20, just default operator<=>: https://en.cpprefer
| ence.com/w/cpp/language/default_compariso...
| Sharlin wrote:
| 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.
| z_open wrote:
| 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)
| gsliepen wrote:
| 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?
| monkeyelite wrote:
| He's just asserting he's using the data structure in the way he
| wants to.
| derriz wrote:
| 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.
| dm270 wrote:
| I agree. This seems very unintuitive and would be a code smell
| in a review.
| monkeyelite wrote:
| > 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.
| AlotOfReading wrote:
| 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/
| monkeyelite wrote:
| That's the same idea as putting intervals in map, an
| ordered tree.
| derriz wrote:
| 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.
| diath wrote:
| 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
___________________________________________________________________
(page generated 2025-07-13 23:01 UTC)