container for insert/delete + fast index

N

ndbecker2

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?
 
V

Victor Bazarov

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
 
T

Thorsten Kiefer

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top