5 ms·

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 de

by derriz 1y ago

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 1y ago
I 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 ago
  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/ https://web.engr.oregonstate.edu/~erwig/diet/
  - monkeyelite 1y ago
    That’s the same idea as putting intervals in map, an ordered tree.
- derriz 1y ago
  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.
  - monkeyelite 1y ago
    > 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).

by derriz 1y ago

dm270 1y ago

I 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 ago
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/ https://web.engr.oregonstate.edu/~erwig/diet/
- monkeyelite 1y ago
  That’s the same idea as putting intervals in map, an ordered tree.
derriz 1y ago
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.
- monkeyelite 1y ago
  > 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).