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: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2015-09-14 10:11:17

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.

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.

About the speed, mentioned for Chris. I examined briefly your code, I
didn't understood what do some benchmarks. I will check. If your code is
better, you will have all my support. i will clap the winner. But I need to
examine. Let me some days, and I will say you my oppinion

2015-09-14 15:19 GMT+02:00 Neil Groves <neil_at_[hidden]>:

> > You have Random access iterators with access time O(logN) ( you can run a
> > std::sort over the data structure with good results).
> >
>
> Traversal operations are mandated to be Amortized O(1) for
> random-access iterators. If the traversal is O(log N) it isn't a
> random-access iterator.
> http://en.cppreference.com/w/cpp/concept/RandomAccessIterator
>
> Neil
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>