468,513 Members | 1,799 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,513 developers. It's quick & easy.

container for insert/delete + fast index

I'm looking for an stl-style container that has good performance for
insertion and deletion of elements as well as very fast index
operation.

I'm thinking an stl::list would be good if an external index was
maintained.

I could of course write this, but I wonder if something suitable
already exists?

Jul 21 '06 #1
2 3762
nd*******@gmail.com wrote:
I'm looking for an stl-style container that has good performance for
insertion and deletion of elements as well as very fast index
operation.

I'm thinking an stl::list would be good if an external index was
maintained.

I could of course write this, but I wonder if something suitable
already exists?
Nothing's perfect. If you don't need isertions or deletetions in the
middle, use 'deque'. If you do need insertion/deletions all over the
container, you're better off rolling your own indexing with 'list',
as you already mentioned. Beware, though, that 'list' is a memory hog.

As always, to judge performance you need to measure, not guess.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Jul 21 '06 #2
nd*******@gmail.com wrote:
I'm looking for an stl-style container that has good performance for
insertion and deletion of elements as well as very fast index
operation.

I'm thinking an stl::list would be good if an external index was
maintained.

I could of course write this, but I wonder if something suitable
already exists?
You can try out std::map<int,...:
Access-Time : log N
Remove : constant
Insert : log N

The backraw is the access time of log N (but better than N) and that it uses
more memory on the one hand cause of the tree-structure and on the other
hand for the index.

Regards
Thorsten
Jul 21 '06 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

41 posts views Thread by AngleWyrm | last post: by
7 posts views Thread by William Payne | last post: by
16 posts views Thread by Philip Boonzaaier | last post: by
5 posts views Thread by Robert Oschler | last post: by
3 posts views Thread by alex.fishman | last post: by
18 posts views Thread by Hunk | last post: by
1 post views Thread by fmendoza | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.