STL and finding objects by name
Matthew Bucknall
Apologies if the answer to this is obvious, I have spent quite some time
trying to come up with a solution. I would like to use some sorted STL
container (maybe a set ?) to hold a bunch of named objects, that is,
objects that posses their own name. I then want to search for objects in
the container by name. Here is an example:
class Thing
{
public:
Thing(const std::string& name):
m_name(name)
{}
std::string get_name() const { return m_name; }
bool operator< (const Thing& rhs) const
{
return m_name < rhs.m_name;
}
private:
const std::string m_name;
};
std::set<Thing> things;
std::set<Thing>::iterator find_thing(const std::string& name)
{
// this won't work of course, but this hopefully illustrates
// what I want to do
return things.find(name);
}
My question is, how can named objects (such as Thing) be stored in an
STL container such that they can then be efficiently found by name?
Note, I want named objects to have direct access to their name so
storing objects in a std::map<std::string, Thing> is no good IMHO
because items contained in the map don't have access to their keys.
Regards,
Matt.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Daniel Krügler
> Apologies if the answer to this is obvious, I have spent quite some time
> trying to come up with a solution. I would like to use some sorted STL
> container (maybe a set ?) to hold a bunch of named objects, that is,
std::set would be one possible choice, yes.
> objects that posses their own name. I then want to search for objects in
> the container by name. Here is an example:
>
> class Thing
> {
> public:
>
> Thing(const std::string& name):
> m_name(name)
> {}
>
> std::string get_name() const { return m_name; }
>
> bool operator< (const Thing& rhs) const
> {
> return m_name < rhs.m_name;
> }
>
> private:
>
> const std::string m_name;
> };
Instances of this class cannot be used in std containers, because
they are not Assignable (due to the const data member m_name).
You have to remove the const qualifier.
> std::set<Thing> things;
>
> std::set<Thing>::iterator find_thing(const std::string& name)
> {
> // this won't work of course, but this hopefully illustrates
> // what I want to do
>
> return things.find(name);
> }
Except for the failure that Thing is not Assignable, the code should
work.
It works, because Thing has an implicit c'tor accepting a std:string,
so
the code above does the "correct" thing by invoking
things.find(Thing(name));
If this too expensive for you, you should consider to use a cheap-
to-create ThingProxy instead of Thing in the set. This would mean that
the
actual data (e.g. the string member) is stored in an external
container.
In this case you have to ensure careful life-time control between the
set and the actual data container.
> My question is, how can named objects (such as Thing) be stored in an
> STL container such that they can then be efficiently found by name?
This is one possible choice. You can also use a (manually) sorted
sequence container, like std::vector<Thing>.
If Thing::operator< is not a natural sorting for Thing, you should
consider to separate the predicate from the value type:
struct ThingByName {
bool operator()(const Thing& lhs, const Thing& rhs) const
{
return lhs.get_name() < rhs.get_name();
}
};
typedef std::set<Thing, ThingByName> ThingSet;
You might consider to return a const reference in get_name(),
if invoking the predicate shows to be a performance blocker.
HTH & Greetings from Bremen,
Daniel Krügler
Lance Diduck
as is.
I think what you wanted to say was "How to I make a container of Thing
sorted by the name of Thing, without having to replicate the name for
each entry, nor having to create a Thing object to search by?"
There is no direct answer. My solution uses a level of indirection:
class Thing
{
public:
explicit Thing(const std::string& name):
m_name(name)
{}
std::string get_name() const { return m_name; }
std::string m_name;
//lots more stuff....
friend struct ThingWrapper;
};
typedef boost::shared_ptr<Thing> ThingPtr;
struct ThingWrapper{
ThingWrapper(std::string const& arg):m_name(arg){}
ThingWrapper(ThingPtr const& arg):m_thing(arg){}
bool operator< ( ThingWrapper const& rhs) const
{
if(m_thing )
if(rhs.m_thing)
return m_thing->m_name < rhs.m_thing->m_name;
else
return m_thing->m_name < rhs.m_name;
return m_name<rhs.m_name;
}
std::string get_name()const{
if(m_thing)return m_thing->m_name;
return m_name;
}
ThingPtr get_thing()const{
return m_thing;
}
private:
std::string m_name;
ThingPtr m_thing;
};
std::set<ThingWrapper> things;
ThingPtr find_thing(const std::string& name)
{
std::set<ThingWrapper>::iterator f
=things.find(ThingWrapper(name));
if(f!=things.end())return f->get_thing();
return ThingPtr();
}
void foo(){
ThingPtr tmp(new Thing("C++"));
things.insert(ThingWrapper(tmp));
things.insert(ThingWrapper(ThingPtr(new Thing("Java"))));
things.insert(ThingWrapper(ThingPtr(new Thing("Ruby"))));
things.insert(ThingWrapper(ThingPtr(new Thing("Erlang"))));
ThingPtr tmp2=find_thing("C++");
assert(tmp->get_name()==tmp2.get_name());
}
So what is really being searched and sorted are ThingWrappers, and it
know when there is just a string or the full object.
Lance
Alberto Ganesh Barbati
>
> class Thing
> {
> public:
>
> Thing(const std::string& name):
> m_name(name)
> {}
>
> std::string get_name() const { return m_name; }
>
> bool operator< (const Thing& rhs) const
> {
> return m_name < rhs.m_name;
> }
>
> private:
>
> const std::string m_name;
> };
>
>
> std::set<Thing> things;
>
>
> std::set<Thing>::iterator find_thing(const std::string& name)
> {
> // this won't work of course, but this hopefully illustrates
> // what I want to do
>
> return things.find(name);
> }
>
> My question is, how can named objects (such as Thing) be stored in an
> STL container such that they can then be efficiently found by name?
> Note, I want named objects to have direct access to their name so
> storing objects in a std::map<std::string, Thing> is no good IMHO
> because items contained in the map don't have access to their keys.
>
Unfortunately, std::set is not very friendly in this scenario. The only
way to do proper lookup is to create an instance of Thing, for example
like this:
std::set<Thing>::iterator find_thing(const std::string& name)
{
return things.find(Thing(name));
}
If Thing is an heavy weight object, you could add a function set_name()
to change an object name, making it private to avoid involuntarily
breaking the std::set invariant, but making it a friend of find_thing so
that it can re-use one Thing instance:
std::set<Thing>::iterator find_thing(const std::string& name)
{
static Thing key;
key.set_name(name);
return things.find(key);
}
(not the most elegant code, I know.)
As a last resort, you could avoid using std::set entirely and rely on
smarter containers, for example Boost.MultiIndex
http://www.boost.org/doc/libs/1_35_0/libs/multi_index/doc/index.html
HTH,
Ganesh
Barry
> Hello,
>
> Apologies if the answer to this is obvious, I have spent quite some time
> trying to come up with a solution. I would like to use some sorted STL
> container (maybe a set ?) to hold a bunch of named objects, that is,
> objects that posses their own name. I then want to search for objects in
> the container by name. Here is an example:
>
> class Thing
> {
> public:
>
> Thing(const std::string& name):
> m_name(name)
> {}
>
> std::string get_name() const { return m_name; }
// return const reference to avoiding copying.
std::string const& get_name() const { return m_name; }
>
> bool operator< (const Thing& rhs) const
> {
> return m_name < rhs.m_name;
> }
// provide operator== to meet the requirement of set
bool operator== (Thing const& rhs) const { return m_name ==
rhs.m_name; }
>
> private:
>
> const std::string m_name;
// remove const, to make Thing Assignable to meet the
requirement for container.
// as long as you don't provide modifier, the class remains
immutable.
std::string m_name;
>
> };
>
> std::set<Thing> things;
>
> std::set<Thing>::iterator find_thing(const std::string& name)
> {
> // this won't work of course, but this hopefully illustrates
> // what I want to do
>
> return things.find(name);
>
> }
>
a test case
#include <iostream>
int main()
{
things.insert(Thing("hello"));
things.insert(Thing("world"));
std::set<Thing>::iterator i = find_thing("hello");
if (i != things.end())
std::cout << i->get_name() << std::endl;
}
output:
hello
> My question is, how can named objects (such as Thing) be stored in an
> STL container such that they can then be efficiently found by name?
> Note, I want named objects to have direct access to their name so
> storing objects in a std::map<std::string, Thing> is no good IMHO
> because items contained in the map don't have access to their keys.
I guess you meant bidirectional map,
check out Boost.Bimap, which is newly added into boost_1.35.0
HTH.
--
Best Regards
Barry
Mateusz Adamczyk
> std::set<Thing> things;
>
> std::set<Thing>::iterator find_thing(const std::string& name)
> {
> // this won't work of course, but this hopefully illustrates
> // what I want to do
>
> return things.find(name);
>
> }
If You write:
std::set<Thing>::iterator find_thing(const std::string& name)
{
// this won't work of course, but this hopefully illustrates
// what I want to do
return things.find(Thing(name));
}
it should work. But You must remember, that in set all object are key!
So You can't change object stored in set. You have to erased it and
after
modifications insert it again.
Regards,
Mateusz Adamczyk
Bart van Ingen Schenau
> On Apr 4, 9:37 pm, Matthew Bucknall <m...@mattbucknall.com> wrote:
>> Hello,
>>
>> Apologies if the answer to this is obvious, I have spent quite some
>> time trying to come up with a solution. I would like to use some
>> sorted STL container (maybe a set ?) to hold a bunch of named
>> objects, that is, objects that posses their own name. I then want to
>> search for objects in the container by name. Here is an example:
>>
>> class Thing
>> {
<snip>
>> bool operator< (const Thing& rhs) const
>> {
>> return m_name < rhs.m_name;
>> }
>
> // provide operator== to meet the requirement of set
> bool operator== (Thing const& rhs) const { return m_name ==
> rhs.m_name; }
Which requirement of set demands that you provide an operator== ?
The equality (or rather, equivalence) of two elements is given by the
relation (!(a<b) && !(b<a)).
std::set is purely defined in terms of a less-than operator.
>
> HTH.
>
> --
> Best Regards
> Barry
>
>
Bart v Ingen Schenau
--
a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq
c.l.c FAQ: http://c-faq.com/
c.l.c++ FAQ: http://www.parashift.com/c++-faq-lite/
Barry
wrote:
> Barry wrote:
>
> > // provide operator== to meet the requirement of set
> > bool operator== (Thing const& rhs) const { return m_name ==
> > rhs.m_name; }
>
> Which requirement of set demands that you provide an operator== ?
> The equality (or rather, equivalence) of two elements is given by the
> relation (!(a<b) && !(b<a)).
> std::set is purely defined in terms of a less-than operator.
>
I was so wrong, thanks for pointing that out.
--
Best Regards
Barry
--
Seungbeom Kim
>
> My question is, how can named objects (such as Thing) be stored in an
> STL container such that they can then be efficiently found by name?
> Note, I want named objects to have direct access to their name so
> storing objects in a std::map<std::string, Thing> is no good IMHO
> because items contained in the map don't have access to their keys.
This is a situation that occurs very frequently: having an object in
an associative container, where the object itself provides the key.
For the sake of explanation below, let's assume Whole = Key + Extra.
std::set<Whole> is bad because it doesn't allow you to look up by Key
alone, and you have to construct a Whole object when all you want is
just to look up by Key, as described in the problem. You may not even
be able to construct a Whole object just from Key, without Extra.
std::map<Key, Extra> is bad because Extra doesn't have access to Key.
Boost.Bimap, a variation on this, is a good library and I'm glad to see
it, but it adds extra complication and it's not often what you want,
either; having a map where you can look up Key by Extra is one thing,
and having Key right inside an object is another. Many operations of
Extra, including even construction, may require Key at hand. Providing
an ordering between Extra objects may be another difficulty/impossibility.
std::map<Key, Whole> solves most of the problems and is easy to use,
but duplicates Key and results in a wasted space (and time).
This situation shows a deficiency in the 'set or map' classification
of the associative containers currently in the standard library.
std::set<V> requires key_type (V) to be the same as value_type (V),
whereas std::map<K, M> requires key_type (K) to be separate from
mapped_type (M), but there's no container that allows something in
between. I think a new container that allows arbitrary mapping from
value_type to key_type, via parametrization, would be helpful:
template <class V, class K, class ToKey,
class Comp = std::less<K>,
class Alloc = std::allocator<V> >
class associative
// Stores nodes of V. Uses ToKey(...)(V) to get K.
{
public:
typedef V value_type;
typedef K key_type;
// ...
};
// the current standard library associative container equivalences:
struct identity
{
template <class T>
const T& operator()(const T& t) const { return t; }
};
struct get_first
{
template <class T1, class T2>
const T1& operator()(const std::pair<T1, T2>& p) const
{ return p.first; }
};
template <class V>
using set = associative<V, V, identity>;
template <class K, M>
using map = associative<std::pair<const K, M>, K, get_first>;
Then the OP's problem can be solved by the following:
struct get_name
{
const std::string& operator()(const Thing& t) const
{ return t.get_name(); }
};
typedef associative<Thing, std::string, get_name> map;
What do you think?
--
Seungbeom Kim