C++: Maps on Chains

http://bannalia.blogspot.com/2025/07/maps-on-chains.html

by signa11 • 1 year ago

47 20 1 year ago

bannalia.blogspot.com

gsliepen3• 1 year ago

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• 1 year ago

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• 1 year ago

better implemented as

    tie(x.min, x.max) < tie(y.min, y.max)

gsliepen3• 1 year ago

Or since C++20, just default operator<=>: https://en.cppreference.com/w/cpp/language/default_compariso...

Sharlin• 1 year ago

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• 1 year ago

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)

gsliepen3• 1 year ago

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?

monkeyelite6• 1 year ago

He’s just asserting he’s using the data structure in the way he wants to.

derriz2• 1 year 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• 1 year ago

I agree. This seems very unintuitive and would be a code smell in a review.

monkeyelite6• 1 year 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.

AlotOfReading• 1 year 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/

derriz2• 1 year 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.

diath2• 1 year ago

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

monkeyelite6• 1 year ago

what did you try to use as a comparison function?

diath2• 1 year ago

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;
  });

delifue• 1 year ago

The correct way of storing disjoint intervals is to key by min endpoint of each interval and use ordered querying

C++: Maps on Chains

Related Stories