5 ms·
C++: Maps on Chains
- gsliepen 1y agoIt'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 1y agoWhy 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 1y agobetter implemented as tie(x.min, x.max) < tie(y.min, y.max)
- gsliepen 1y agoOr since C++20, just default operator<=>: https://en.cppreference.com/w/cpp/language/default_comparisons.html https://en.cppreference.com/w/cpp/language/default_compariso...
- Sharlin 1y agoThat’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 1y agoThrowing 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 1y agoThat 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 1y agoHe’s just asserting he’s using the data structure in the way he wants to.
- derriz 1y agoI 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 1y agoI agree. This seems very unintuitive and would be a code smell in a review.
- monkeyelite 1y ago> 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.
- deleted 1y ago[deleted]
- AlotOfReading 1y agoThis 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/ https://web.engr.oregonstate.edu/~erwig/diet/
- diath 1y agoThis 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 https://en.cppreference.com/w/cpp/named_req/Compare.html
- deleted 1y ago[deleted]
- monkeyelite 1y agowhat did you try to use as a comparison function?
- diath 1y agoThis was the original sort function (it was meant to force "last" to be first on the list after the sort which obviously violated the requirement): 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; });
- monkeyelite 1y agoInteresting… I’m sure you resolved this. But the textbook solution is: 1. std::find last 2. std::iter_swap(first, found) 3. std::sort(front + 1, back)
- delifue 1y agoThe correct way of storing disjoint intervals is to key by min endpoint of each interval and use ordered querying