stl - searching for elements in containers

[Raven Arkadon]

i have somthing like

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.

[Prelude]

std::set defines its own find member function. All you have to do is make sure that your class overloads operator<.

[Raven Arkadon]

#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]

[hk_mp5kpdw]

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.

#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]

[Raven Arkadon]

>> 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