stl - searching for elements in containers

This is a discussion on stl - searching for elements in containers within the C++ Programming forums, part of the General Programming Boards category; i have somthing like Code: class MyClass { std::string id; /* other members */ }; now i want to store ...

  1. #1
    Registered User
    Join Date
    Aug 2001
    Posts
    244

    stl - searching for elements in containers

    i have somthing like
    Code:
    class MyClass {
      std::string id;
    
       /* other members */
    };
    now i want to store many instances of this in a container.
    because i want to be able to do a quick lookup based on the id i would chose either std::map or std::set (or the hashed versions).

    now,
    actually i want to be able to map ids to the MyClass-instances - thus map,

    on the otherhand the MyClass needs its id internally so somthing like std::map<std::string, MyClass> would duplicate the id - and thats not good - since the id is constant anyway and it would be just a waste of memory.

    so i guess i want a std::set<MyClass>.
    but i need to lookup the MyClass instances by id - and of course by binary search.

    so whats the best way to do this?

    i mean: do i have to write my own binsearch function - or is there some template part of the stl? i need an iterator as a search result.
    Last edited by Raven Arkadon; 03-24-2005 at 05:51 AM.
    signature under construction

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    std::set defines its own find member function. All you have to do is make sure that your class overloads operator<.
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    Code:
    #include <iostream>
    
    #include <set>
    
    
    class Declaration {
    protected:
      const std::string id;
    
    public:
    
      Declaration(const std::string &r_id) :
        id(r_id)
      {
      }
    
      bool operator < (const std::string &r_str) const {
        if(0 > id.compare(r_str))
          return true;
    
        return false;
      }
    
      operator const std::string () const {
        return id;
      }
    
    };
    
    
    int main()
    {
      typedef std::set< Declaration > decset_t;
      decset_t decset;
    
      decset.insert(Declaration(std::string("1")));
      decset.insert(Declaration(std::string("2")));
      decset.insert(Declaration(std::string("3")));
      decset.insert(Declaration(std::string("4")));
    
      decset_t::iterator it = decset.find(std::string("7"));
      if(it != decset.end())
        std::cout << "success\n";
      else
        std::cout << "failure\n";
    
    
      return 0;
    }

    this is my solution which seems to work:
    i defined the operator < which works with the keytype - and a conversion from the object to its keytype. is that the way its usually done?

    [edit]
    what i am not sure about: when Declaration is converted to std::string still a copy of the id is made (but only temporarily - so its not as bad as having all keys duplicated) - can i get rid of even that?

    a reference to the id doesnt work because of 2 reasons:
    .) the object might move - thus the reference might point to an invalid location.
    .) and the main reason: the stl uses references internally - and references to references are illegal

    [/edit]
    Last edited by Raven Arkadon; 03-24-2005 at 09:24 AM.
    signature under construction

  4. #4
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,794
    Make the less than operator compare two Declaration objects with each other. The find function would need to accept a Declaration object instead of a string.

    Code:
    #include <iostream>
    
    #include <set>
    
    
    class Declaration {
    protected:
      const std::string id;
    
    public:
    
      Declaration(const std::string &r_id) :
        id(r_id)
      {
      }
    
      friend bool operator< (const Declaration&, const Declaration&);
    
      operator const std::string () const {
        return id;
      }
    
    };
    
    bool operator< (const Declaration &lhs, const Declaration &rhs)
    {
        return lhs.id < rhs.id;
    }
    
    
    int main()
    {
      typedef std::set< Declaration > decset_t;
      decset_t decset;
    
      decset.insert(Declaration(std::string("1")));
      decset.insert(Declaration(std::string("2")));
      decset.insert(Declaration(std::string("3")));
      decset.insert(Declaration(std::string("4")));
    
      decset_t::iterator it = decset.find(Declaration(std::string("7")));
      if(it != decset.end())
        std::cout << "success\n";
      else
        std::cout << "failure\n";
    
    
      return 0;
    }
    [edit]Don't really think you need the () operator in this case.[/edit]
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  5. #5
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    >> The find function would need to accept a Declaration object instead of a string.

    thats the point: i DONT want find to accept Declaration object - it should accept a string.

    but true: inserting a second compare funtion that compares two Declaration objects directly makes sense - though it doesnt have to be friend.

    in my case all declarations would first be converted to strings and then passed to the compare function

    edit: cool! the conversion member isnt even needed anymore.
    seems that find is a template itself
    signature under construction

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Noob STL question about Containers.
    By Swerve in forum C++ Programming
    Replies: 2
    Last Post: 03-15-2009, 12:02 PM
  2. stl containers allocation in heap or stack?
    By sawer in forum C++ Programming
    Replies: 9
    Last Post: 08-06-2006, 03:08 PM
  3. C++ std routines
    By siavoshkc in forum C++ Programming
    Replies: 33
    Last Post: 07-28-2006, 12:13 AM
  4. Visual C++ 2005 linking and file sizes
    By Rune Hunter in forum C++ Programming
    Replies: 2
    Last Post: 11-12-2005, 09:41 PM
  5. STL multimaps / searching
    By Codulation in forum C++ Programming
    Replies: 7
    Last Post: 01-05-2004, 05:28 PM

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