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: Jeremy Murphy (jeremy.william.murphy_at_[hidden])
Date: 2015-09-15 22:00:55

Without having looked in any detail at the new container in question, the
discussion does remind me of a similar container proposed by Aleksandr
Kupriianov some months ago.

http://lists.boost.org/Archives/boost/2014/07/215224.php

It might be worth justifying why your container is better than that one,
whether we can abstract aspects of both, etc.
We can ask whether it is OK to add these augmented containers one by one as
they are offered or whether it might be better to consider a few at once in
order to design some consistent interface.
Cheers.

Jeremy

On 16 September 2015 at 08:52, Francisco José Tapia <fjtapia_at_[hidden]>
wrote:

> Thanks by your interest.
>
> I think it will be a good idea create a Concept.
>
> About the iterators are similar to the iterators of std::deque as say the
> description in cppreference.com. “As opposed to std::vector
> <http://en.cppreference.com/w/cpp/container/vector>, the elements of a
> deque are not stored contiguously: typical implementations use a sequence
> of individually allocated fixed-size arrays.”
>
> You have an valid iterator before begin (), you can use begin() -1 , if you
> increment this iterator you have the begin iterator. In the same way, if
> you decrement the end() iterator , the iterator obtained pointed to the
> last element.
>
> The iterators can obtain their position in the data structure. The iterator
> begin() - 1 , return the value -1. This is the reason of the signed
> integers in the position of the elements, and the explanations of the “tons
> of warnings” of Mr. Clearwater.
>
> You can add or subtract any value to an iterator, and obtain a new iterator
> in a time proportional to the logarithm of the distance.
>
> The increment or decrement an iterator is a O(1) operation, because the
> average of jumps for to reach the previous or next node is less than 4,
> independent of the size of the tree.
>
>
> I didn't examine in deep the Concepts before now, but after read the
> documentation, I think is an excellent idea.
>
> Thanks by your information
>
> 2015-09-14 16:26 GMT+02:00 Neil Groves <neil_at_[hidden]>:
>
> > 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
> >
> > _______________________________________________
> > Unsubscribe & other changes:
> > http://lists.boost.org/mailman/listinfo.cgi/boost
> >
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>