std::list question

This is a discussion on std::list question within the C++ Programming forums, part of the General Programming Boards category; Just a quickie I'm not sure about. If I did a linear search (t'is linear, right?) like this: Code: /* ...

  1. #1
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709

    std::list question

    Just a quickie I'm not sure about.
    If I did a linear search (t'is linear, right?) like this:

    Code:
    /* GetItemByName
     */
    Item* ItemManager::GetItemByName( const std::string& name ) const
    {
        std::list<Item*>::const_iterator  it = items.begin();
    
        for ( ; it != items.end(); it++ )
        {
            Item* i = (*it);
            if ( i->name == name ) return i;
        }
    
        return 0;   // Doesn't exist
    }
    How does that compare to the std::find() function? Or is it (std::find()) implementation specific?
    Last edited by cboard_member; 06-21-2006 at 01:07 PM.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  2. #2
    Registered User
    Join Date
    Nov 2001
    Posts
    1,348
    linear not difference

    Kuphryn

  3. #3
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    What?

    EDIT: I mean, explain. Evidence.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  4. #4
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,412
    I'm not sure how it compares. I'm sure performance wise, find() will be faster. However, list implements a linear (or sequential) search too.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  5. #5
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    Actually nevermind, I did some profiling.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    And what did you find? They should be roughly the same, although the fact that you are storing pointers might make it more difficult to use find(). I would prefer the algorithm, though, if you can use it.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295

    Lightbulb

    std::find exists for a reason. For starters it's shorter, and less likely to have a bug than hand-rolled code.

    Though if you ever find yourself coding a linear search, then there is a very very good chance that you're not using the best container for the job.

  8. #8
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    I assume std:: list is implemented as doubly linked list and I think that your search and find algorithm will have same performace (both will be linear- O(N)),.
    Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
    It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem

  9. #9
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    They were both roughly the same after getting past some difficulties as Daved said. I'm pretty sure I'm using the wrong container: it took about 4 seconds to find the 9999th item (or was it 99999th. Can't remember).

    Which would be more appropriate (in case I don't get around to reading it up today)?
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  10. #10
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Maybe it is better to use map/multimap container when inserting elements. Searching will be logarithmic since internally map is a Balanced Binary Tree. So if search/find operation is often use I suggest multimap container.
    Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
    It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem

  11. #11
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    Multimap it is. First, I've got to learn how to use it.
    To arms!
    Or google.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  12. #12
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,452
    http://www.sgi.com/tech/stl/
    It also tells you for most things what the O(n) complexity of the various things are.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  13. #13
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    Thankies.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  14. #14
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    If you are doing all your insertions at once in the beginning, and then searching afterwards, then a vector would probably be even better than a map/multimap/set/multiset. Fill the vector with all your data, then sort it, then use binary_search, lower_bound, and/or upper_bound to find what you are looking for. This will be even better than the map solutions because those keep the data sorted as you are inserting which is a bit slower than sorting it once at the end. In addition, the vector uses less memory overhead than the map solutions.

    Another option is the unordered_map/unordered_multimap that will be part of the next standard. You can find an implementation from boost if your library doesn't have one. They're basically hashed maps, which have even faster lookups than the regular map or binary_search.

  15. #15
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    You should put the call to items.end() outside the for loop for best results, i.e.

    Code:
        std::list<Item*>::const_iterator  it = items.begin();
        std::list<Item*>::const_iterator end = items.end();
        for ( ; it != end; it++ ) {
    
        }
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Debugging question
    By o_0 in forum C Programming
    Replies: 9
    Last Post: 10-10-2004, 05:51 PM
  2. Question about pointers #2
    By maxhavoc in forum C++ Programming
    Replies: 28
    Last Post: 06-21-2004, 12:52 PM
  3. std::list question
    By void_main in forum C++ Programming
    Replies: 5
    Last Post: 11-10-2003, 12:21 PM
  4. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 12:47 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21