C++: Maps on Chains

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

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.

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.

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

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)