C++: Maps on Chains(bannalia.blogspot.com)
bannalia.blogspot.com
C++: Maps on Chains
http://bannalia.blogspot.com/2025/07/maps-on-chains.html
22 comments
Why can't you use this for the comparison operator:
better implemented as
tie(x.min, x.max) < tie(y.min, y.max)Or since C++20, just default operator<=>: https://en.cppreference.com/w/cpp/language/default_compariso...
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.
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)
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.
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.
> 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.
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
[deleted]
what did you try to use as a comparison function?
This 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;
});Interesting… 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)
1. std::find last
2. std::iter_swap(first, found)
3. std::sort(front + 1, back)
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.
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.
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/
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.
[deleted]
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.
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.
> internal implementation of std::map
> abusing the ordering function
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).
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).
I agree. This seems very unintuitive and would be a code smell in a review.
The correct way of storing disjoint intervals is to key by min endpoint of each interval and use ordered querying