container for insert/delete + fast index

Discussion in 'C++' started by ndbecker2@gmail.com, Jul 21, 2006.

  1. Guest

    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, 2006
    #1
    1. Advertising

  2. 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
    Victor Bazarov, Jul 21, 2006
    #2
    1. Advertising

  3. 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
    Thorsten Kiefer, Jul 21, 2006
    #3
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    658
  2. Michele Simionato

    Python is darn fast (was: How fast is Python)

    Michele Simionato, Aug 23, 2003, in forum: Python
    Replies:
    13
    Views:
    558
  3. Juha Nieminen
    Replies:
    22
    Views:
    1,019
    Kai-Uwe Bux
    Oct 12, 2007
  4. Pallav singh

    Container for Look Up to be Fast

    Pallav singh, Aug 13, 2011, in forum: C++
    Replies:
    10
    Views:
    881
    Jorgen Grahn
    Aug 16, 2011
  5. Tomasz Chmielewski

    sorting index-15, index-9, index-110 "the human way"?

    Tomasz Chmielewski, Mar 4, 2008, in forum: Perl Misc
    Replies:
    4
    Views:
    275
    Tomasz Chmielewski
    Mar 4, 2008
Loading...

Share This Page