dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6

Thread: fast access to container element

  1. #1
    Join Date
    Aug 2005
    Location
    southampton, UK
    Posts
    1,320

    fast access to frequently used container element

    I want to store a collection of objects. I will frequently access this collection, however, it is highly likely that the last object i accessed in the collection will be the one i want to access the next time.

    What would be an efficient way to go about finding an element in the collection where the first element is likely to be the correct element, and what container do i need?

    I thought about creating a static counter variable in the class, and have each object have a count variable, which gets populated at contruction from an iterated static counter, i.e.

    Code:
    static int counter;
    int count;
    
    // ctor
    count = counter++;
    and then store the objects in a set where i create a comparison function which compares the count data members, with the object having the greatest count being the first element in the set.

    Then when i want to find my object in the set, i will first check to see if the first element is the object i want, and if not, will use set.find.

    Anyone have a better way of doing this?

    thanks
    Last edited by dave2k; March 31st, 2008 at 11:51 AM.
    With sufficient thrust, pigs fly just fine. However, this is not
    necessarily a good idea. It is hard to be sure where they are going to
    land, and it could be dangerous sitting under them as they fly
    overhead. -- RFC 1925

  2. #2
    Join Date
    Oct 2004
    Posts
    296

    Re: fast access to container element

    however, it is highly likely that the last object i accessed in the collection will be the one i want to access the next time.

    What would be an efficient way to go about finding an element in the collection where the first element is likely to be the correct element, and what container do i need?
    YourObject coll[1];

  3. #3
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: fast access to container element

    You want a splay tree. I don't think the STL has a container for this, but I'm certain there's a free splay tree implementation somewhere on the 'net. And it isn't too hard to code yourself if it comes down to it.

    Essentially, it's a binary tree which rearranges itself on every access (via a set of very simple rules) so that the selected element becomes the root.
    Last edited by Lindley; March 31st, 2008 at 12:44 PM.

  4. #4
    Join Date
    May 2007
    Posts
    811

    Re: fast access to container element

    Here is cool flow chart to help you choose the most appropriate stl container.

  5. #5
    Join Date
    Aug 2005
    Location
    southampton, UK
    Posts
    1,320

    Re: fast access to container element

    cheers guys
    With sufficient thrust, pigs fly just fine. However, this is not
    necessarily a good idea. It is hard to be sure where they are going to
    land, and it could be dangerous sitting under them as they fly
    overhead. -- RFC 1925

  6. #6
    Join Date
    Jan 2004
    Location
    Düsseldorf, Germany
    Posts
    2,401

    Re: fast access to container element

    My suggestion would be to just wrap a std::set and a set iterator into a class. The class's interface should have all (or most) functions that std::set provides and execute them on the std::set. Upon insert, the iterator is set to the element that was just inserted. Upon find, comparison is first done with the element the iterator points to and if that is not correct the set is searched. Upon erase (and construction) the iterator is set to set::end().
    More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason - including blind stupidity. --W.A.Wulf

    Premature optimization is the root of all evil --Donald E. Knuth


    Please read Information on posting before posting, especially the info on using [code] tags.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)