I've been looking for such a container myself, and had a discussion
about it a few years ago in the boost mailing list.  This seems to also
be a "future work" of the boost::multi_index library, so there seem to
be interest in it anyway. (see
http://www.boost.org/libs/multi_index/doc/future_work.html#ranked_indices)

// Peter

Martin Knoblauch Revuelta skrev:

> I've written a sequence container with O(log n) complexity for both
> random access and insertion/removal:
>
> http://sourceforge.net/projects/avl-array
>
> It was after posting to comp.lang.c++.moderated when I discovered this
> other group (comp.std.c++) and the fact that this subject has already
> been discussed years ago in "tree containers in STL". It was not the
> main subject there, but some people suggested creating something like
> this. Well, my idea was not so new after all :-)
>
> IMHO, a container like this would be very useful. What do you think?
> Is this (O(log n) complexity) anti-STL-spirit?
>
> Sorry for the partly/duplicated post.
>
> Regards,
> Martin Knoblauch Revuelta
>
> ---
> [ comp.std.c++ is moderated.  To submit articles, try just posting with ]
> [ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
> [              --- Please see the FAQ before posting. ---               ]
> [ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Gianni Mariani wrote:
> This is very cool.  I was about to say that this is eqivalent to
> std::map<int,T> but that's not what this is at all.

Exactly.

>  It seems like this
> is certainly far better than std::deque

Well, it depends. If you only need to insert/remove elements at ends,
then deque is much better (taking O(1) time where my container takes
O(log N) time).

> One potentially interesting application for this is in the "bring to
> front" compression techniques or an LRU system.

Are you thinking in splay trees?
(http://en.wikipedia.org/wiki/Splay_tree)
My container is not a splay tree, and I guess it will never be better
than a splay tree in these applications. ??

> Would it be easy to support a "splice" method ?

Not too difficult. It will probably be in the next release. But I guess
it shouldn't be called "splice". The splice method in a list takes only
O(1) time, because only the ends of the sublists need to be re-linked.
That's why it is called splice, isn't it?

In my container this will take O(n log N), where n is the number of
nodes to move, and N is the number of nodes in the container. In cases
where n is significant with respect to N, the operation can be
optimized to take just O(N) time.

Best regards,

Martin

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

DeCaf wrote:
> I've been looking for such a container myself, and had a discussion
> about it a few years ago in the boost mailing list.  This seems to also
> be a "future work" of the boost::multi_index library, so there seem to
> be interest in it anyway. (see
> http://www.boost.org/libs/multi_index/doc/future_work.html#ranked_indices)
>
> // Peter

Interesting. I had not seen that part of multi_index documentation, but
I considered for a while if my container should be an extension for
multi_index, instead of a separated library. Now I think it might be
both.

I think it can be useful as a simple container. In some particular
cases, the "Non-Proportional Sequence View" (NPSV) feature can be used
too.

The natural numbers index (or rank) somehow contradicts the nature of
multi_index, because the index of some elements change as others are
inserted/removed. The NPSV goes further: more than one element can have
the same index (or rank).

Though, it might be useful as a multi_index extension, regarded that
the necessary design exceptions (mutant, non-unique indexes) were
somehow integrated.

Best regards,

Martin Knoblauch Revuelta

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

I've written a sequence container with O(log n) complexity for both
random access and insertion/removal:

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

It was after posting to comp.lang.c++.moderated when I discovered this
other group (comp.std.c++) and the fact that this subject has already
been discussed years ago in "tree containers in STL". It was not the
main subject there, but some people suggested creating something like
this. Well, my idea was not so new after all :-)

IMHO, a container like this would be very useful. What do you think?
Is this (O(log n) complexity) anti-STL-spirit?

Sorry for the partly/duplicated post.

Regards,
Martin Knoblauch Revuelta

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]