Prev: Is it allowed that std::map equal_range returns more than 1 elements?
Next: template args
From: Mateusz Adamczyk on 4 Apr 2008 05:13
On 4 Kwi, 15:37, Matthew Bucknall <m...(a)mattbucknall.com> wrote:
> 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

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

From: Bart van Ingen Schenau on 5 Apr 2008 04:32
Barry wrote:

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

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

From: Barry on 6 Apr 2008 00:06
On Apr 6, 3:32 am, Bart van Ingen Schenau <b...(a)ingen.ddns.info>
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



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

From: Seungbeom Kim on 12 Apr 2008 03:13
Matthew Bucknall wrote:
>
> 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

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

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