wrote:
> ""Richard Peters"" <r.a.peters@student.tue.nl> wrote in message
> news:b20i35$451$1@news.tue.nl...
>> James Kanze wrote:
>>> r.a.peters@student.tue.nl ("Richard Peters") wrote in message
>>> news:<b1qnpq$311$1@news.tue.nl>...
>>>
>>>> I would like to see a libary extension to std::set
>>>> Making the std::set::find templated, so that it can search for any
>>>> kind of key would solve my problem.
>>>> My question is: Is this extension already discussed, or
>>>> is there an official extension request?
>>>
>>> If you want a map, use a map:-).
>>
>> I don't want a map :) A map is intended to go from one thing to
>> another thing, not from one thing to that same thing. (At least,
>> that's how I see it)
>> I have a collection of one kind of items, there are no duplicates. It
>> just sounds very wrong to put it in a map, which is clearly intended
>> for two seperate things: a key and an associated value.
>
> What about std::set and the standard std::find_if function:
>
>   std::set< my_type > s;
>   std::find_if( s.begin(), s.end(), std::mem_fun( &my_type::name ) );

std::find_if has the wrong complexity. I want to search for elements fast,
it shouldn't take O(s.size()) comparisons.

>>> Seriously, most of the time, there is absolutely nothing wrong with
>>> duplicating the key field.  You're copying the entire object anyway
>>> each time you insert ; you might as well copy the key field too.
>>
>> I'm not too concerned with speed and memory consumption. It just
>> doesn't look pretty, and a templated find member would make it
>> pretty, while it doesn't violate the ideas behind a set being a
>> collection of items sorted in a specific way.
>
> Why should it be a member?  It only needs to use the public interface
> of the class, and unless the search comparator is related to the
> set's comparator, there's no efficiency gain in directly accessing
> the implementation.  Even if the search comparator *is* related to
> the set's comparator, I don't see how the compiler can know that,
> except in a few very specific forms.

If it isn't a member, then the find function can't make use of the fact that
the set has an internal tree structure, and as std::set provides
bidirectional iterators, you can't use binary search. A non-member function
would thus have O(std::set::size()) complexity. If it is a member, and it
has as precondition that the set is sorted with respect to the search
criterion, then that member can make use of the internal tree structure,
just as the member function std::set::find does now, so it has
O(log(std::set::size())) complexity. For hash_sets, the difference between
member and non-member functions would be O(std::hash_set::size()) and O(1).
(Though with hash_sets, you wouldn't be able to just use a subkey of the
key, but only the whole key of an object.)

>>> If the objects involved are complex, to the point where the copying
>>> becomes a burden, I would use something along the lines of:
>>>
>>>     std::map< smart_ptr<T>, smart_ptr<T>, CompareKeys >
>>
>> Then I still would have to construct a complete object in order to
>> get a smart_ptr<T> to pass to map::find.
>
> It sounds to me that you want to get at the underlying tree structure.
> Typically set and map will be implemented in terms of a single tree
> class that might look something like:
>
>   template < typename NodeType, typename Accessor,
>              class Comparator, class Allocator >
>   class tree;
>
>   // Set implementation
>   //
>   template <class T> struct identity {
>     T const& operator(T const&t) const { return t; }
>   };
>
>   template < class ValueType, class Comparator, class Allocator >
>   class set
>     : tree< ValueType, identity<ValueType>,
>             Comparator, Allocator >
>   { ... };
>
>   // Map implementation
>   //
>   template <class T> struct get1st {
>     typename T::first_type const& operator(T const&t) const { return
> t.first; }
>   };
>
>   template < typename KeyType, typename MappedType,
>              class Comparator, class Allocator >
>   class map
>     : tree< pair< const KeyType, MappedType >,
>             get1st< pair< const KeyType, MappedType > >,
>             Comparator, Allocator >
>   { ... };
>
> Maybe it would be helpful if the next version of the standard
> provided such a tree class.  Depending on the exact specification of
> tree, it might even be possible to make set and map typedef templates
> of tree (assuming the next standard permits such things).
>
> It would allow you to create an "intelligent" map structure such as
> the one you want by passing
>
>   std::mem_fun( &my_type::name )
>
> as the accessor.

Yes, this would be possible. It would however be a lot more work and I doubt
that the exposal of internals would be accepted, unless there is a great
advantage in doing so. Making the std::set::find member a template member
involves not much work, both in specification and implementation.

Richard Peters



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

""Richard Peters"" <r.a.peters@student.tue.nl> wrote in message
news:b20i35$451$1@news.tue.nl...
> James Kanze wrote:
> > r.a.peters@student.tue.nl ("Richard Peters") wrote in message
> > news:<b1qnpq$311$1@news.tue.nl>...
> >
> >> I would like to see a libary extension to std::set
> >> Making the std::set::find templated, so that it can search for any
> >> kind of key would solve my problem.
> >> My question is: Is this extension already discussed, or
> >> is there an official extension request?
> >
> > If you want a map, use a map:-).
>
> I don't want a map :) A map is intended to go from one thing to another
> thing, not from one thing to that same thing. (At least, that's how I
> see it)
> I have a collection of one kind of items, there are no duplicates. It
> just sounds very wrong to put it in a map, which is clearly intended for
> two seperate things: a key and an associated value.

What about std::set and the standard std::find_if function:

  std::set< my_type > s;
  std::find_if( s.begin(), s.end(), std::mem_fun( &my_type::name ) );

> > Seriously, most of the time, there is absolutely nothing wrong with
> > duplicating the key field.  You're copying the entire object anyway
> > each time you insert ; you might as well copy the key field too.
>
> I'm not too concerned with speed and memory consumption. It just doesn't
> look pretty, and a templated find member would make it pretty, while it
> doesn't violate the ideas behind a set being a collection of items
> sorted in a specific way.

Why should it be a member?  It only needs to use the public interface of the
class, and unless the search comparator is related to the set's comparator,
there's no efficiency gain in directly accessing the implementation.  Even
if the search comparator *is* related to the set's comparator, I don't see
how the compiler can know that, except in a few very specific forms.


> > If the objects involved are complex, to the point where the copying
> > becomes a burden, I would use something along the lines of:
> >
> >     std::map< smart_ptr<T>, smart_ptr<T>, CompareKeys >
>
> Then I still would have to construct a complete object in order to get a
> smart_ptr<T> to pass to map::find.

It sounds to me that you want to get at the underlying tree structure.
Typically set and map will be implemented in terms of a single tree class
that might look something like:

  template < typename NodeType, typename Accessor,
             class Comparator, class Allocator >
  class tree;

  // Set implementation
  //
  template <class T> struct identity {
    T const& operator(T const&t) const { return t; }
  };

  template < class ValueType, class Comparator, class Allocator >
  class set
    : tree< ValueType, identity<ValueType>,
            Comparator, Allocator >
  { ... };

  // Map implementation
  //
  template <class T> struct get1st {
    typename T::first_type const& operator(T const&t) const { return
t.first; }
  };

  template < typename KeyType, typename MappedType,
             class Comparator, class Allocator >
  class map
    : tree< pair< const KeyType, MappedType >,
            get1st< pair< const KeyType, MappedType > >,
            Comparator, Allocator >
  { ... };

Maybe it would be helpful if the next version of the standard provided such
a tree class.  Depending on the exact specification of tree, it might even
be possible to make set and map typedef templates of tree (assuming the next
standard permits such things).

It would allow you to create an "intelligent" map structure such as the one
you want by passing

  std::mem_fun( &my_type::name )

as the accessor.

--
Richard Smith




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

To the moderators: I already posted this post, after three days it got
approved but it didn't show up.

Howard Hinnant wrote:
> In article <b1qnpq$311$1@news.tue.nl>, Richard Peters
> <r.a.peters@student.tue.nl> wrote:
>
>> I would like to see a libary extension to std::set
>> Making the std::set::find templated, so that it can search for any
>> kind of key would solve my problem. STLport already provides this
>> extension. My question is: Is this extension already discussed, or
>> is there an official extension request?
>
> I do not believe it has been proposed.  I agree that it would make a
> valuable addition.  Although the Metrowerks std::set does not offer
> this extension, our underlying tree has had this interface for about 3
> years and I find it very handy (especially in implementing
> map/multimap).
>
> Indeed, the pattern is handy for more than just find.  All members
> that take a key and perform a lookup can benefit from being templated
> on the key:

I'd like to add to this that while all elements stored in a set are unique,
the elements don't need to be unique with respect to a certain (sub)key
type: consider a set of struct MyStruct { int a; int b } sorted first on a,
then on b. Searching (or any other operation) for an object of MyStruct
would match at most one object. If the set is provided with the right
value_compare, searching for an int would only compare the int to
MyStruct::a, and could match more than one object. I'd like to allow this,
as long as the following holds, for a, b an object of MyStruct, and x a
subkey of a: If a < b then x <= b, if a = b then x = b if a > b then x >= b.

> find

Taken the idea of subkeys into account, when one or more objects held by the
container match a subkey, find returns an iterator to one of them. Why not
return an iterator to the first of them: I think this version could be made
more efficient, and if you really want the first, you can use lower_bound.

> erase

Erases all objects that match the subkey. The semantics of the other
functions are pretty straigtforward.

> count
> lower_bound
> upper_bound
> equal_range
>
> When coupled with a value_compare that can accept several types of
> objects, this essentially becomes a rewrite of the "extract key from
> value" logic (used in many map implementations), but is much more
> elegant.

Yes, this was what I intended.

One final note why I prefer the value_compare accepting several types of
objects over providing an additional template parameter to set, as proposed
by Philippe Mori: With this approach, you can both search for the complete
object or only the key part of the object, and this approach supports
subkeys of the primary key.
Does this sound good enough to provide formal wording? btw, most of this
also applies to map, multi_map, multi_set, and the hash_ variants of these.

Best regards,

Richard Peters


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

kanze@gabi-soft.de (James Kanze) writes:

> If the objects involved are complex, to the point where the copying
> becomes a burden, I would use something along the lines of:
>
>     std::map< smart_ptr<T>, smart_ptr<T>, CompareKeys >
>
> (If you want to use boost::shared_ptr for this, be very careful.  The
> boost::shared_ptr only works if all your pointers to the object are of
> that type.  In this case, I would definitly prefer an invasive smart
> pointer.)

This is not true. boost::shared_ptr works quite happily with pointers of
different type to the same object, and indeed there are functions such as
boost::shared_dynamic_cast designed explicitly to obtain a shared_ptr of a
different type pointing to the same object.

Anthony
--
Anthony Williams
Senior Software Engineer, Beran Instruments Ltd.
Remove NOSPAM when replying, for timely response.

---
[ 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 would like to see a libary extension to std::set (The same would
> > apply to hash_set). First I'll give an introduction to a problem I
> > have.  I have a lot of objects, stored in a container. The objects
> > contain a name, address, and various other members. I want to retrieve
> > the object by searching for the name. Storing the objects in a
> > std::map would duplicate the name field, and is therefore a quite ugly
> > sollution. I could store it in a std::set, but then, when I want to
> > search for a name, I have to construct a whole object. Making the
> > std::set::find templated, so that it can search for any kind of key
> > would solve my problem. STLport already provides this extension. My
> > question is: Is this extension already discussed, or is there an
> > official extension request?
>
> If you want a map, use a map:-).
>

I would also like that extension... but in fact I think that it would
have been a better idea if set would have a template argument that
would allows to give the key part of an object.

template <typename T>
T & KeyOf(T &whole_object) { return whole_object; }

and a set would be define in a way like that:

template <
    typename T,
    typename Compare = less<T>,
    typename GetKey = KeyOf<T>
> class set;

Note that it may also be a new class "set_with_key" that would
be usable has a set and as a map...


On the other hand, most of the time a map would do... and if
memory is the main constraint, then a container like a vector
may be preferable anyway (if the content is essentially fixed).


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

In article <b1qnpq$311$1@news.tue.nl>, Richard Peters
<r.a.peters@student.tue.nl> wrote:

| I would like to see a libary extension to std::set (The same would apply to
| hash_set). First I'll give an introduction to a problem I have.
| I have a lot of objects, stored in a container. The objects contain a name,
| address, and various other members. I want to retrieve the object by
| searching for the name. Storing the objects in a std::map would duplicate
| the name field, and is therefore a quite ugly sollution. I could store it in
| a std::set, but then, when I want to search for a name, I have to construct
| a whole object. Making the std::set::find templated, so that it can search
| for any kind of key would solve my problem. STLport already provides this
| extension. My question is: Is this extension already discussed, or is there
| an official extension request?

I do not believe it has been proposed.  I agree that it would make a
valuable addition.  Although the Metrowerks std::set does not offer
this extension, our underlying tree has had this interface for about 3
years and I find it very handy (especially in implementing
map/multimap).

Indeed, the pattern is handy for more than just find.  All members that
take a key and perform a lookup can benefit from being templated on the
key:

find
erase
count
lower_bound
upper_bound
equal_range

When coupled with a value_compare that can accept several types of
objects, this essentially becomes a rewrite of the "extract key from
value" logic (used in many map implementations), but is much more
elegant.

--
Howard Hinnant
Metrowerks

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

r.a.peters@student.tue.nl ("Richard Peters") wrote in message
news:<b1qnpq$311$1@news.tue.nl>...

> I would like to see a libary extension to std::set (The same would
> apply to hash_set). First I'll give an introduction to a problem I
> have.  I have a lot of objects, stored in a container. The objects
> contain a name, address, and various other members. I want to retrieve
> the object by searching for the name. Storing the objects in a
> std::map would duplicate the name field, and is therefore a quite ugly
> sollution. I could store it in a std::set, but then, when I want to
> search for a name, I have to construct a whole object. Making the
> std::set::find templated, so that it can search for any kind of key
> would solve my problem. STLport already provides this extension. My
> question is: Is this extension already discussed, or is there an
> official extension request?

If you want a map, use a map:-).

Seriously, most of the time, there is absolutely nothing wrong with
duplicating the key field.  You're copying the entire object anyway each
time you insert ; you might as well copy the key field too.

If the objects involved are complex, to the point where the copying
becomes a burden, I would use something along the lines of:

    std::map< smart_ptr<T>, smart_ptr<T>, CompareKeys >

(If you want to use boost::shared_ptr for this, be very careful.  The
boost::shared_ptr only works if all your pointers to the object are of
that type.  In this case, I would definitly prefer an invasive smart
pointer.)

--
James Kanze                           mailto:jkanze@caicheuvreux.com
Conseils en informatique orient   e objet/
                    Beratung in objektorientierter Datenverarbeitung

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

In news:d6651fb6.0302060143.42473731@posting.google.com,
James Kanze <kanze@gabi-soft.de> typed:

> (If you want to use boost::shared_ptr for this, be very careful.  The
> boost::shared_ptr only works if all your pointers to the object are of
> that type.  In this case, I would definitly prefer an invasive smart
> pointer.)

James, I really wish you'd stop propagating this myth.  It hasn't been true
for over a year now (http://tinyurl.com/5hiv).  In fact, many other things
you mightn't expect to work "magically" work right with boost shared_ptr,
including passing them across DLL boundaries where the libraries have
separate heaps, and upcasting to a smart pointer to a base without a virtual
destructor.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com


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

James Kanze wrote:
> r.a.peters@student.tue.nl ("Richard Peters") wrote in message
> news:<b1qnpq$311$1@news.tue.nl>...
>
>> I would like to see a libary extension to std::set
>> Making the std::set::find templated, so that it can search for any
>> kind of key would solve my problem.
>> My question is: Is this extension already discussed, or
>> is there an official extension request?
>
> If you want a map, use a map:-).

I don't want a map :) A map is intended to go from one thing to another
thing, not from one thing to that same thing. (At least, that's how I
see it)
I have a collection of one kind of items, there are no duplicates. It
just sounds very wrong to put it in a map, which is clearly intended for
two seperate things: a key and an associated value.

> Seriously, most of the time, there is absolutely nothing wrong with
> duplicating the key field.  You're copying the entire object anyway
> each time you insert ; you might as well copy the key field too.

I'm not too concerned with speed and memory consumption. It just doesn't
look pretty, and a templated find member would make it pretty, while it
doesn't violate the ideas behind a set being a collection of items
sorted in a specific way.

> If the objects involved are complex, to the point where the copying
> becomes a burden, I would use something along the lines of:
>
>     std::map< smart_ptr<T>, smart_ptr<T>, CompareKeys >

Then I still would have to construct a complete object in order to get a
smart_ptr<T> to pass to map::find.

> (If you want to use boost::shared_ptr for this, be very careful.  The
> boost::shared_ptr only works if all your pointers to the object are of
> that type.  In this case, I would definitly prefer an invasive smart
> pointer.)

In which case you have to alter your class because of the design of the
associative containers... I really don't like it.
Anyway, if you can't convince me my idea is wrong, what are my options
to make an extension proposal?

Best regards,

Richard Peters


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

Hello,

I would like to see a libary extension to std::set (The same would apply to
hash_set). First I'll give an introduction to a problem I have.
I have a lot of objects, stored in a container. The objects contain a name,
address, and various other members. I want to retrieve the object by
searching for the name. Storing the objects in a std::map would duplicate
the name field, and is therefore a quite ugly sollution. I could store it in
a std::set, but then, when I want to search for a name, I have to construct
a whole object. Making the std::set::find templated, so that it can search
for any kind of key would solve my problem. STLport already provides this
extension. My question is: Is this extension already discussed, or is there
an official extension request?

Best regards,

Richard Peters


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