Thread: stl list find

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    630

    stl list find

    Hello.. Im new to stl..

    Whats the best way to find data in the list by the string?
    Last edited by l2u; 09-05-2006 at 01:56 PM.

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    It depends. If you will have a lot of data and be doing a lot of lookups by the string, you should use a map or a set instead of a vector or list. The set and map classes are also standard library containers, so you shouldn't have too much trouble learning them. What they provide is logarithmic time lookup, which is much faster than linear that a list would use.

    Another option if you are using a vector, and all your objects will be added in the very beginning, is to add the objects first, then sort the vector using std::sort, and then use std::binary_search to find the data.

    If, however, you only have a few items to store, then a linear search is fine. The best way to do this is to use the list.find() method, or if you are using a vector use the std::find algorithm.

  3. #3
    Registered User
    Join Date
    May 2006
    Posts
    630
    Hey Daved, you're very helpful.. Can I use vector inside the map?

  4. #4
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    Yes you can, although in general you'll want to use a std::vector only as the data, not the key.

    Something like this: std::map<std::string, std::vector<std::string> >

    is a map that looks up based on a string key, and has a vector of strings as the data.

    (You NEED a space between the last two > > or it will think it's supposed to be the operator >>).
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  5. #5
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    Quote Originally Posted by Cat
    Yes you can, although in general you'll want to use a std::vector only as the data, not the key.

    Something like this: std::map<std::string, std::vector<std::string> >

    is a map that looks up based on a string key, and has a vector of strings as the data.

    (You NEED a space between the last two > > or it will think it's supposed to be the operator >>).
    that's one of the nasty 'gotcha's of C++. when creating containers of containers, I prefer to use something like
    Code:
    typedef std::vector<std::string> vec_string;
    std::map< std::string, vec_string > my_map;
    just to be on the safe side

  6. #6
    Registered User
    Join Date
    May 2006
    Posts
    630
    Quote Originally Posted by Bench82
    that's one of the nasty 'gotcha's of C++. when creating containers of containers, I prefer to use something like
    Code:
    typedef std::vector<std::string> vec_string;
    std::map< std::string, vec_string > my_map;
    just to be on the safe side
    Why would that be more safe?

  7. #7
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Bench82 is just referring to the fact that you have to put a space between the two > characters, so using the typedef just means you won't need to put two > characters together and so you won't forget to put the space. It doesn't actually make the code safer from run-time errors.

    BTW, that will be fixed in the next standard, so at some point soon compilers will allow the >> without the space.

  8. #8
    Registered User
    Join Date
    May 2006
    Posts
    630
    The map only supports two types of data, am I right with that?

  9. #9
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    It depends on what you mean. A map holds a key-value pair. You can use whatever type you want for the key as long as you make it sortable if it isn't already. So an int, double, string or instance of your own class that implements operator< are all examples of valid key types. You then use whatever type you want for the value, as long as it is copyable. Again, the examples above for keys would also work as values. A vector would also work as a value.

    If you have multiple datatypes that you want to store as the value, you generally combine them into a struct or class and then use the class as the value type.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  4. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM