Re: [boost] Determining interest in container with efficient random access insert and erase

Subject: Re: [boost] Determining interest in container with efficient random access insert and erase
From: Neil Groves (neil_at_[hidden])
Date: 2015-09-14 10:26:40

On 14 September 2015 at 15:11, Francisco José Tapia <fjtapia_at_[hidden]> wrote:
> The iterators are not like the vector's itertors, but they are not like the
> list iterators. They permit you go directly to a position without travel
> all the previous nodes.
> It's a different type. You can do a std::sort over the data structure with
> good results. Really the ++operator and --operator are O(1), because
> involve a small number of nodes, and don't depend of the tree size.
> The polynomy of any algorith must be multiplied by logN. Then que quicksort
> is  O ( (logN)²).
>
> This new type of iterator was not defined, because until now, it was not
> necessary. But now appear and we must name it, I name as random iterators
> wth access O(logN), If we agree any other name, I will use. It's a semantic
> problem only.
>

I understand the problem. I completely agree that the standard
categories for Iterators are sub-optimal. The separation between
orthogonal concepts such as traversal, dereference type etc. is
frequently problematic. You can define a new Concept, and interfaces.
There is no rational reason to reduce your potential set of actions to
waiting or violating a Concept. You can't sensibly abuse an existing
Concept weakening the guarantees. The standard algorithms such as
std::sort provide complexity guarantees that it simply would not be
able to adhere to with your iterators since the supplied iterators
would be outside of the pre-conditions of calling the algorithm. Often
this would 'work' without breaking. However if code has a side-effect
during dereference operations it is possible that code could go wrong
due to an excessive number of dereference invocations. Even if your
internal iterators were robust against this, if they were wrapped in
iterator adaptors that made an assumption, and forwarded the
random_access guarantee it can go wrong.

Violating Concept conditions is not going to be populate with Boost
developers. I strongly recommend doing what you are doing, but with a
clear new Concept and you will need to make clear calling standard
algorithms for RandomAccessIterators with these is technically
undefined-behaviour. You might even be able to provide some equivalent
non-member functions. I could work with you to make some Boost.Range
extension points to make optimal algorithms selected, but with very
clear, precise and correct complexity guarantees.

> In the same way, the interface of STL set , map , multiset and multimap is
> dangerous in a concurrent environment, because you obtain an iterator to a
> node, and before to access, other thread delete that node , and your
> program crash. We can wait until the C++ standard define a new interface or
> we can propose an interface, and begin to use,  correct the failures, and
> learn with the experience, in order to obtain the best solution. When the
> standard define something, change and adapt.
>

This example is not at all the same since the standard guarantees
nothing about concurrent access in the Concept definition. It
absolutely does guarantee O(1) access. Not specifying something is
very different from specifying a tighter condition you wish to ignore.

Adapt by all means, but please don't violate design contracts for
anything we are to include in Boost.

Please don't misunderstand my intent. I'm trying to help you reach a
proposal that'll be acceptable. I've frequently been tempted, while
developing Boost.Range to do things that work on an implementation
level, loosening Concepts. It has uniformly been an error. Now the
code has extension points, but these are largely done using non-member
functions and overloads and selecting tuned algorithms while retaining
strict conformance for other cases.

Neil Groves