magfr@comp.std.cpp.magfr.user.lysator.liu.se (Magnus Fromreide) wrote in message news:<874r35lak0.fsf@comp.std.cpp.magfr.user.lysator.liu.se>...
[stuff deleted]

> I want to be able to have
>
> genset<foo, mem_fun_t<int, foo> > gs(mem_fun(foo::getb));
>
> and then write
>
> gs.find(17);
>
> in my code, not having to fight with something like
>
> gs.find(foo(0, 17))
>
> since that temporary foo provides me nothing, but this is what I will
> end up with if I use std::set and some specialized comparision
> function.
>
> Now, I could get this effect with a map where the key is a reference
> into the value but then I have to store this useless reference and
> that is a cost I shouldn't need to pay.
>
> ---
> [ comp.std.c++ is moderated.  To submit articles, try just posting with ]
> [ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
> [              --- Please see the FAQ before posting. ---               ]
> [ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

I recently uploaded to the Files section of Boost a preliminary
version of an associative container supporting multiple keys, much
in the same way as a relational table. Among other goodies, it
supports lookup by fields (i.e. not requiring a complete element
to be passed in find and related functions). You can take a look
at it at:

http://groups.yahoo.com/group/boost/files/multiindex.zip

Regards,

Joaqu   n M L   pez Mu   oz
Telef   nica, Investigaci   n y Desarrollo

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

I think it would be good if it was possible to use any member part of
an object in a set as a key and would thus suggest that two new
associative containers, genset and multigenset, are introduced. The
difference between those and normal sets are that they take an extra
template parameter, KeyOfValue, providing a unary_function that takes
the value as argument and returns a key that this container is sorted
on.

Thus the main problem this solves is making containers where the key
is a part of the value that is accessible from the value. There is
still the requirement that the key part of the value isn't changed
while the object is in the map but this is something that the user of
the genset have to solve.

With this set becomes, with the addition of std::identity, see below,

template <class Value, class Compare = less<Value>,
          class Allocate = allocate<Value> >
class set : public genset<Value, identity<Value>, Compare, Allocate>
{
public:
        // typedefs and trivial constructors moving things down from
        // the parent class.
};

map becomes, with the addition of std::select_first, see below,

template <class Key, class Value, class Compare = less<const Key>,
          class Allocate = allocate<pair<const Key, Value> > >
class set : public genset<Value, select_first<pair<const Key, Value> >,
                          Compare, Allocate>
{
public:
        // typedefs and trivial constructors moving things down from
        // the parent class.
        typedef Value mapped_type;
        Value& operator [] (const Key&);
};

identity is a functor that returns it's argument -

template <class T>
class identity : public unary_function<T, T> {
public:
        T operator()(T t) { return t; }
};

select_first is a functor that returns the first part of a pair

template <class T> class select_first;

template <class T, class U>
class select_first<pair<T, U> > : public unary_function<pair<T, U>, T> {
public:
        T operator()(pair<T, U> p) { return p.first; }
};

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Magnus Fromreide wrote:
> I think it would be good if it was possible to use any member part of
> an object in a set as a key and would thus suggest that two new
> associative containers, genset and multigenset, are introduced. The
> difference between those and normal sets are that they take an extra
> template parameter, KeyOfValue, providing a unary_function that takes
> the value as argument and returns a key that this container is sorted
> on.

You can already do what you want by providing your own comparison function.
Look at the second template parameter and/or at the compare parameter to the
different constructor forms.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Edward Diener wrote:

> You can already do what you want by providing your own comparison function.
> Look at the second template parameter and/or at the compare parameter to the
> different constructor forms.

Yes, but the problem then is that all of the lookup members still
require a complete instance of the value type while I wish to need
only the key part in order to find my value.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Edward Diener" <eldiener@earthlink.net> wrote:
> Magnus Fromreide wrote:
>> I think it would be good if it was possible to use any member part of
>> an object in a set as a key and would thus suggest that two new
>> associative containers, genset and multigenset, are introduced. The
>> difference between those and normal sets are that they take an extra
>> template parameter, KeyOfValue, providing a unary_function that takes
>> the value as argument and returns a key that this container is sorted
>> on.

> You can already do what you want by providing your own comparison function.

AND declaring all fields that are not used in the comparison finction
as mutable. Whether it is ugly or smart is in the eyes of the beholder.
For what it's worth, std::map could have been implemented as
std::set<std::pair<Key, mutable Value> >, if "mutable" was a full-fledged
cv-like modifier. Too bad it is not.

 Leo

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Magnus Fromreide wrote:
> Edward Diener wrote:
>
>> You can already do what you want by providing your own comparison
>> function. Look at the second template parameter and/or at the
>> compare parameter to the different constructor forms.
>
> Yes, but the problem then is that all of the lookup members still
> require a complete instance of the value type while I wish to need
> only the key part in order to find my value.

Your instance can be a reference ( or pointer ). What is the problem with
passing a reference to the class of your lookup member functor against which
the comparison is made ?

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

xleobx@qmailcomq.com wrote:
> "Edward Diener" <eldiener@earthlink.net> wrote:
>> Magnus Fromreide wrote:
>>> I think it would be good if it was possible to use any member part
>>> of
>>> an object in a set as a key and would thus suggest that two new
>>> associative containers, genset and multigenset, are introduced. The
>>> difference between those and normal sets are that they take an extra
>>> template parameter, KeyOfValue, providing a unary_function that
>>> takes
>>> the value as argument and returns a key that this container is
>>> sorted
>>> on.
>
>> You can already do what you want by providing your own comparison
>> function.
>
> AND declaring all fields that are not used in the comparison finction
> as mutable.

Why should this be needed ? A comparison function is comparing, not changing
anything.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Edward Diener wrote:

> Magnus Fromreide wrote:
> > Edward Diener wrote:
> >
> >> You can already do what you want by providing your own comparison
> >> function. Look at the second template parameter and/or at the
> >> compare parameter to the different constructor forms.
> >
> > Yes, but the problem then is that all of the lookup members still
> > require a complete instance of the value type while I wish to need
> > only the key part in order to find my value.
>
> Your instance can be a reference ( or pointer ). What is the problem
> with passing a reference to the class of your lookup member functor
> against which the comparison is made ?

Are we talking past each other?

I have

class foo
{
public:
  foo(int a, int b) : a_(a), b_(b) { }
  int geta() const { return a_; }
  int getb() const { return b_; }
private:
  int a_, b_;
};

I want to be able to have

genset<foo, mem_fun_t<int, foo> > gs(mem_fun(foo::getb));

and then write

gs.find(17);

in my code, not having to fight with something like

gs.find(foo(0, 17))

since that temporary foo provides me nothing, but this is what I will
end up with if I use std::set and some specialized comparision
function.

Now, I could get this effect with a map where the key is a reference
into the value but then I have to store this useless reference and
that is a cost I shouldn't need to pay.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Edward Diener" <eldiener@earthlink.net> wrote:
> xleobx@qmailcomq.com wrote:
>> "Edward Diener" <eldiener@earthlink.net> wrote:
>>> Magnus Fromreide wrote:
>>>> I think it would be good if it was possible to use any member part
>>>> of
>>>> an object in a set as a key and would thus suggest that two new
>>>> associative containers, genset and multigenset, are introduced. The
>>>> difference between those and normal sets are that they take an extra
>>>> template parameter, KeyOfValue, providing a unary_function that
>>>> takes
>>>> the value as argument and returns a key that this container is
>>>> sorted
>>>> on.
>>
>>> You can already do what you want by providing your own comparison
>>> function.
>>
>> AND declaring all fields that are not used in the comparison finction
>> as mutable.

> Why should this be needed ? A comparison function is comparing, not changing
> anything.

Because, AFAIU, the idea is to be able to modify the non-key parts of the objects,
unless Magnus is more concerned with the cost of construction of those
parts before calling find(), which is also a good point not dismissed
by providing a comparison function. What if the default constructor
for the non-key parts is expensive?

 Leo

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Magnus Fromreide wrote:
> Edward Diener wrote:
>
>> Magnus Fromreide wrote:
>>> Edward Diener wrote:
>>>
>>>> You can already do what you want by providing your own comparison
>>>> function. Look at the second template parameter and/or at the
>>>> compare parameter to the different constructor forms.
>>>
>>> Yes, but the problem then is that all of the lookup members still
>>> require a complete instance of the value type while I wish to need
>>> only the key part in order to find my value.
>>
>> Your instance can be a reference ( or pointer ). What is the problem
>> with passing a reference to the class of your lookup member functor
>> against which the comparison is made ?
>
> Are we talking past each other?
>
> I have
>
> class foo
> {
> public:
>   foo(int a, int b) : a_(a), b_(b) { }
>   int geta() const { return a_; }
>   int getb() const { return b_; }
> private:
>   int a_, b_;
> };
>
> I want to be able to have
>
> genset<foo, mem_fun_t<int, foo> > gs(mem_fun(foo::getb));
>
> and then write
>
> gs.find(17);
>
> in my code, not having to fight with something like
>
> gs.find(foo(0, 17))
>
> since that temporary foo provides me nothing, but this is what I will
> end up with if I use std::set and some specialized comparision
> function.

OK, I see your point, even if I never considered the cost of creating a foo
to be expensive, especially as you have already created a number of them to
put in your associative container. I was responding originally to your
notion of not being able to search on a part of your object as opposed to
the entire value. I am not dismissing the idea of being able to use part of
a key value so that one doesn't have to create an entire object. Maybe there
is room for such a concept and a new container which allows what you want. I
would say that if you are really interested in developing this idea, or have
others develop it possibly with you, you might want to look at Boost at
http:://www.boost.org. For my own part, I usually use keys which are
lightweight to begin with so that the cost of creating such a key, as well
as having the ability to use one's own comparison functionality, seems good
enough in these days of nearly gigabytes of memory and gigahertz of speed.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]