Prev: Is it allowed that std::map equal_range returns more than 1 elements?
Next: template args
From: Matthew Bucknall on 3 Apr 2008 22:37
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; }

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

From: Daniel Krügler on 4 Apr 2008 04:22
On 4 Apr., 15:37, Matthew Bucknall <m...(a)mattbucknall.com> wrote:
> 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



--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Lance Diduck on 4 Apr 2008 04:25
On Apr 4, 9:37 am, Matthew Bucknall <m...(a)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
> {
> 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.
Actually the answer is far from obvious. And actually your code works
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; }
private:
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





--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Barry on 4 Apr 2008 04:32
On Apr 4, 9:37 pm, Matthew Bucknall <m...(a)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
> {
> 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




--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Alberto Ganesh Barbati on 4 Apr 2008 04:33
Matthew Bucknall ha scritto:
>
> 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

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 |  Next  |  Last
Pages: 1 2
Prev: Is it allowed that std::map equal_range returns more than 1 elements?
Next: template args