Re: noverlay branch

["Gerd Möllmann" <gerd.moellmann@gmail.com>]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> to allow C++.  With std::multimap/std::multiset, we would have a
>> ready-made complete solution for the tree, tested by a gazillion of
>> users.  Just dreaming :-))
>
> I'm not familiar with C++ libs: does this `multiset` lib offer something
> similar to the lazy update of buffer positions that Andreas's code uses
> (via the `offset` field together with the `interval_tree_inherit_offset`
> function)?

No, just the tree-part, or better said not the tree directly.  These
implement an abstraction of an ordered set, or multiset (containing an
element more than once), or map of (key, value) pairs, or multimap
(multiple (key, value) pairs with the same key.

Because of the complexities that the C++ standard guarantees, libstc++
uses rb-trees for the implmentation.  There are also unordered forms of
these concepts, using hash-tables under the hood.

https://cplusplus.com/reference/stl/

The rest would have to be built on top, using that.
std::multimap::iterator for example, would be an in-order iteration over
the key or (key, value) pairs.  C++ iterators are modelled after
pointers (++, --, *).

And there are a number of algorithms defined in C++ like lower_bound,
equal_range, upper_bound and so on that work on pointer-like iterators,
or real C pointers for that matter.

https://en.cppreference.com/w/cpp/algorithm

That's probably not a good explanation, sorry :-/.