471,311 Members | 1,761 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,311 software developers and data experts.

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 3900
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
reply views Thread by rosydwin | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.