Re: Sequence container with fast random access and fast insertion/removal (wherever)

From:

Alberto Ganesh Barbati <AlbertoBarbati@libero.it>

Newsgroups:

comp.lang.c++.moderated

Date:

20 Oct 2006 21:19:17 -0400

Message-ID:

<_hb_g.11318$Fk1.23097@twister2.libero.it>

comocomocomo ha scritto:

I've written an STL-like sequence container for those cases where list
and vector/deque are slow due to intensive use of _both_ random access
and insertion/removal (at ends or wherever):

http://sourceforge.net/projects/avl-array

Both random access and insertion/removal have O(log n) complexity. It
is implemented wit an AVL tree, but it is _not_ a map. It is a sequence
container: it respects the order of elements, and the 'keys' are
integers ranging always from 0 to size-1, apparently changing 'by
magic' on insertion/removal. Well, there are no keys at all - it is not
a map ;-)

Is this anti-STL-spirit?

Why do you ask? It's just a container, if it has good iterators and a
reasonable interface, how could it be anti-STL?

Do you think it is useful?

Sure it may be. Maybe you should propose it on the Boost mailing list.
But before posting your code there, you should definitely get rid of the
non-portable macros OFFSET_OF and OWNER. The former is actually not
needed, you can use the standard and portable macro offsetof instead.
The latter is just too hack-ish to be even considered for a respectable
library code.

HTH,

Ganesh

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]