 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Martin Knoblauch Revuelta
Guest
|
 Posted: Fri Oct 20, 2006 4:45 pm Post subject: Sequence container with fast random access and fast insertio |
 |
|
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 ] |
|
| Back to top |
|
 |
DeCaf
Guest
|
| Posted: Mon Oct 30, 2006 5:46 pm Post subject: Re: Sequence container with fast random access and fast inse |
|
|
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:
| Quote: | 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 ] |
|
| Back to top |
|
|
Gianni Mariani
Guest
|
| Posted: Mon Oct 30, 2006 11:44 pm Post subject: Re: Sequence container with fast random access and fast inse |
|
|
Martin Knoblauch Revuelta wrote:
| Quote: | 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.
|
Hi Martin,
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. It seems like this
is certainly far better than std::deque and I would support it's use.
My humble vote would go to adding it.
Probably the best thing is to see if the boost people want to add it to
the boost library.
One potentially interesting application for this is in the "bring to
front" compression techniques or an LRU system.
Would it be easy to support a "splice" method ?
/G
---
[ 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 ] |
|
| Back to top |
|
|
Martin Knoblauch Revuelta
Guest
|
| Posted: Tue Oct 31, 2006 12:49 am Post subject: Re: Sequence container with fast random access and fast inse |
|
|
Gianni Mariani wrote:
| Quote: | 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.
| Quote: | 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).
| Quote: | 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. ??
| Quote: | 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 ] |
|
| Back to top |
|
|
Martin Knoblauch Revuelta
Guest
|
| Posted: Tue Oct 31, 2006 12:51 am Post subject: Re: Sequence container with fast random access and fast inse |
|
|
DeCaf wrote:
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 ] |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
