Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > container for insert/delete + fast index

Reply
Thread Tools

container for insert/delete + fast index

 
 
ndbecker2@gmail.com
Guest
Posts: n/a
 
      07-21-2006
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?

 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      07-21-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) 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


 
Reply With Quote
 
 
 
 
Thorsten Kiefer
Guest
Posts: n/a
 
      07-21-2006
(E-Mail Removed) 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


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
sorting index-15, index-9, index-110 "the human way"? Tomasz Chmielewski Perl Misc 4 03-04-2008 05:01 PM
Copy elements from one STL container to another STL container Marko.Cain.23@gmail.com C++ 4 02-16-2006 05:03 PM
std::transform container => std::abs(container) Steven T. Hatton C++ 4 12-05-2004 07:10 AM
STL: container's values setup by another container Maitre Bart C++ 2 02-11-2004 12:11 AM
std::container::iterator vs std::container::pointer Vivi Orunitia C++ 11 02-04-2004 08:09 AM



Advertisments