Oleg Zabluda wrote:

> Matt Austern <austern@sgi.com> wrote:
> : Valentin Bonnard <bonnardv@pratique.fr> writes:
>
> : > Why is it less ill-defined than:
> : >   set<typeinfo>
> : > or
> : >   set<typeinfo, use_before>
> : >
> : > I repeat the question: how can you say that C++ types can
> : > be ordered but complex<> can't ?
>
> : Well, actually set<typeinfo> is ill-defined too.  It's ill-defined
> : for two reasons.
>
> : First, for the same reason as set<complex>: typeinfo has no
> operator<,
> : so less<typeinfo> doesn't make sense.
>
> I don't think you are right that less<typeinfo> doesn't make sense.
> In fact, I was under impression that the ability to implement
> less<typeinfo> was exactly the reason to introduce typeinfo::before().
>
> Which primary purpose, in turn, is to enable one to put
> typeinfo's into standard containers. Now that you've mentioned
> that you can't put typeinfo's into containers directly, I see
> that you can only put pointers to typeinfo's into a container,
> while having a meanigful specialization less<typeinfo*>.
>
> Either way, your argument is illogical. There are many classes with
> no standard operator<, but for which less<> makes a lot of sense.
> For example, if you want to make a set of sets, you will be forced
> to define some arbitrary less< set<> >. Say, lexicographical_compare
> or something. Calling it operator< would contradict the common
> practice,
> since it makes no mathemetical sense. The normal mathematical
> operator<
> on sets is "is contained in", which is unacceptable for the container
> 'set', because it's a partial order. While calling it less< set<> > is
>
> fine due to the commonly accepted practice of calling arbitrary,
> making-no-sense-mathematically ordering ``less<whatever>'', just to be
>
> able to put 'whatever' into a container, like set, or to able to apply
>
> some standard algorithms to a container of whatever's.
>

Yes! Be aware when dealing with mathematical entities. If a set in STLis
a mathematical "object", it is worthwhile to note that by defining
operator< to every possible (makes-no-sense) object, the mathematical
relation is inevitably broken.

Define less<> instead :)

FYI: a partial order is defined as follows:

A Relation "<=3D" ("less or equal to") is a partial order on a Set S if i=
t
has:

     1. Reflexivity:  a <=3D a for all a E S. (a is a member of, or
belongs to S)

     2. Antisymmetry:  a <=3D b and  b <=3D a implies a=3Db.

     3. Transitivity:  a <=3D b and  b <=3D c implies  a <=3D c.

For total order we would also need a comparability condition:

     4. Comparability: For any a, b E S, either a <=3D b or b <=3D a.

Jarkko
--
__________________________________________________________________
Jarkko K=F6ykk=E4
Nokia Mobile Phones          Tel. (gsm) +358-50-5816916
Wireless Data                Fax.  +358-10-5056733
P.O. Box 68 (Sinitaival 5)   Fax. (mobile) +358-50-8816916
FIN-33721 Tampere FINLAND    EMail: jarkko.koykka@nmp.nokia.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Valentin Bonnard wrote:
>
> Matt Austern <austern@sgi.com> writes:
>
> > Fergus Henderson <fjh@cs.mu.OZ.AU> writes:
> >
> > > But why should the user have to specify the ordering explicitly,
> > > when the particular ordering chosen is irrelevant?
> > > The fact that `set' uses an ordering at all is really an
> > > implementation detail of `set'.
> >
> > It's not an implementation detail at all.
>
> It's part of the public interface, but lots of people
> just want an _associative_ containner (for map) not an
> ordered containner. Were map an alias to hash_map they
> would be as happy. (I am not suggesting that map should be
> hash_map.)

What would you recommend as the (purely internal) ordering function to
be used for set<T> when T is not LessThanComparable? memcmp(,,sizeof(T))
won't necessarily work right, due to to padding bits.
---
[ 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://reality.sgi.com/austern/std-c++/faq.html                  ]

STL is confused.  It doesn't have hash containers.

There are two kinds of comparison that often come up:

Some types have some sort of semantic comparison.  This should implement
some intuitive behavior of whether one object is `less than' another.
Each type may have a somewhat different idea about what this means.
This comparison may not be so useful in containers.  For one thing, it's
fairly common that such a comparison does not create a total order.
Floating-point numbers give a common example.

To use a type in a comparison-based collection, we want some sort of
arbitrary ordering on the type.  This often has little to do with the
previous semantic comparison.  The requirements are different and what
works well for one purpose may not work at all for the other.

I argue that these concepts should be kept separate, and it's mainly a
lucky accident when you can use the same comparison for both.  In fact,
i think it's a mistake for STL to have a default that confuses them.

Let's look at hash containers.  Keeping in mind a more general idea of
containers, it's easier to see where STL is messed up.

To use any sort of hash container on a type, you must provide a hash
function for the type.  But we know that a hash function is arbitrary;
its purpose is to make the hash tables work and that's it.  Whatever
makes the hash table work well is the function we want.

If someone says to you, `the complex number hash function is broken
because multiplying complex numbers doesn't multiply the hash values',
you just look at them like they're a moron, because everyone knows that
the hash function has nothing to do with the semantic operations.

Now suppose some collection uses both hashing and comparison functions.
We know that the two functions go together; they have the same purpose
and they should have similar properties.  Then the comparison function
can be just as arbitrary as the hash function.

If a collection uses just a comparison function, it's still the same.
The comparison is just some arbitrary ordering to make the data
structure work.  Whatever makes it work well is what we want.

--
Joe Keane, amateur mathematician
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

[my apologies if anyone sees this twice]

Matt Austern <austern@sgi.com> writes:

> Fergus Henderson <fjh@cs.mu.OZ.AU> writes:
>
> > But why should the user have to specify the ordering explicitly,
> > when the particular ordering chosen is irrelevant?
> > The fact that `set' uses an ordering at all is really an
> > implementation detail of `set'.
>
> It's not an implementation detail at all.

Sorry, I should have said "can be considered an implementation detail"
instead of "is really an implementation detail".

> One of the most important
> invariants of set (and of map, multiset, and multimap) is that the
> elements are guaranteed always to be sorted in ascending order by key.
> This is very much a part of set's public interface.

Yes, it is.   However, for types for which `less<T>' is defined, this is
an invariant that users can safely ignore.  If the user doesn't care about
the ordering --- as is often the case when using `set', particularly when
using `set' on types for which there is no natural ordering ---
then it is an invariant that the users *should* ignore.

> By default set
> orders its elements according to operator<;

Not quite.  By default set orders its elements according to `less<T>'.
`less<T>' in turn defaults to `operator <', except for pointer types.
But for pointer types or other types for which `less<T>' is specialized,
the default is not the same as `operator <'.

> If you don't care about the ordering within the container, then it's
> likely that set is the wrong choice for your application

I strongly disagree.

> and that something like hash_set would be better.

In such cases, something like `hash_set' may often be more efficient.
But alas, `hash_set' is not part of the standard, so using `hash_set'
may require much more programmer effort than using `set'.  If `set'
gives adequate performance, and the application doesn't otherwise
require `hash_set', then `set' may well be a better choice.

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Valentin Bonnard <bonnardv@pratique.fr> writes:

> Nathan Myers wrote:
>
> > Arguably one shouldn't put complex<float> values in a set because
> > it implicitly involves comparing them for equality, and float is
> > an imprecise representation: equality of floating-point values is
> > often illusory.  (E.g. assert(2.0 == sqrt(2.0)*sqrt(2.0)).)
>
> What about complex<int> ? Granted that isn't std, but it's a
> simple, meaningfull, common extension and it makes sens to
> put them in sets with the syntax: set<complex<int> >.
>
> But perhaps an implementor would be able to add
> less<complex<int> > without being non-conforming.

Actually, an implementor can do anything whatsoever with
complex<int> without being non-conforming.

The standard only specifies complex<float>, complex<double>, and
complex<long double>.  If you instantiate complex<> with any other
type, the behavior is undefined.  (Section 26.2, paragraph 2.)
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

--------------7742979E6EF6DF554D9FD3B8
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

> > Nathan Myers wrote:
> >
> > > Arguably one shouldn't put complex<float> values in a set because
> > > it implicitly involves comparing them for equality, and float is
> > > an imprecise representation: equality of floating-point values is
> > > often illusory.  (E.g. assert(2.0 == sqrt(2.0)*sqrt(2.0)).) ]

Then arguably also one shouldn't put float values in a set with the same
argument....
And operator== shouldn't be defined for float (and doubles) which is definetely
not reasonnable.
Still, I believe that some people would like to use such containers on
floating-point based objects.
May be one more template argument should be added in the far future (C++0x) that
would default to equal_to<Key> ?

template <class Key, class Compare = less<Key>,class Alloc=alloc,class
Equal=equal_to<Key>>

        Theo.

--
--------------------------------------------------------------------------------
        Theodore Papadopoulo (papadop@sophia.inria.fr)

   Projet Robotvis, INRIA - Sophia Antipolis,
   2004, route des Lucioles, BP 93, 06902 Sophia Antipolis Cedex -- FRANCE
   Phone: (33) 04 92 38 76 01, Fax: (33) 04 92 38 78 45
--------------------------------------------------------------------------------



--------------7742979E6EF6DF554D9FD3B8
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit

<HTML>

<BLOCKQUOTE TYPE=CITE>> Nathan Myers wrote:
<BR>>
<BR>> > Arguably one shouldn't put complex&lt;float> values in a set because
<BR>> > it implicitly involves comparing them for equality, and float is
<BR>> > an imprecise representation: equality of floating-point values
is
<BR>> > often illusory.&nbsp; (E.g. assert(2.0 == sqrt(2.0)*sqrt(2.0)).)
]</BLOCKQUOTE>
Then arguably also one shouldn't put float values in a set with the same
argument....
<BR>And operator== shouldn't be defined for float (and doubles) which is
definetely not reasonnable.
<BR>Still, I believe that some people would like to use such containers
on floating-point based objects.
<BR>May be one more template argument should be added in the far future
(C++0x) that would default to equal_to&lt;Key> ?

<P>template &lt;class Key, class Compare = less&lt;Key>,class Alloc=alloc,class
Equal=equal_to&lt;Key>>

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Theo.
<PRE>--&nbsp;
--------------------------------------------------------------------------------
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Theodore Papadopoulo (papadop@sophia.inria.fr)

&nbsp;&nbsp; Projet Robotvis, INRIA - Sophia Antipolis,
&nbsp;&nbsp; 2004, route des Lucioles, BP 93, 06902 Sophia Antipolis Cedex -- FRANCE
&nbsp;&nbsp; Phone: (33) 04 92 38 76 01, Fax: (33) 04 92 38 78 45
--------------------------------------------------------------------------------</PRE>
&nbsp;</HTML>

--------------7742979E6EF6DF554D9FD3B8--
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Matt Austern <austern@sgi.com> writes:

> Fergus Henderson <fjh@cs.mu.OZ.AU> writes:
>
> > But why should the user have to specify the ordering explicitly,
> > when the particular ordering chosen is irrelevant?
> > The fact that `set' uses an ordering at all is really an
> > implementation detail of `set'.
>
> It's not an implementation detail at all.

It's part of the public interface, but lots of people
just want an _associative_ containner (for map) not an
ordered containner. Were map an alias to hash_map they
would be as happy. (I am not suggesting that map should be
hash_map.)

The same way, if we (when we'll) add hash associative
containners in the std, I hope that complex<>, and all
EqualtyComparable types will get a hash function.

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://www.pratique.fr/~bonnardv/
---
[ 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://reality.sgi.com/austern/std-c++/faq.html                  ]

J. Kanze <kanze@gabi-soft.fr> wrote:
: Matt Austern <austern@sgi.com> writes:

: |>  Fergus Henderson <fjh@cs.mu.OZ.AU> writes:
: |>
: |>  > But why should the user have to specify the ordering explicitly,
: |>  > when the particular ordering chosen is irrelevant?
: |>  > The fact that `set' uses an ordering at all is really an
: |>  > implementation detail of `set'.
: |>
: |>  It's not an implementation detail at all.  One of the most important
: |>  invariants of set (and of map, multiset, and multimap) is that the
: |>  elements are guaranteed always to be sorted in ascending order by key.
: |>  This is very much a part of set's public interface.

: So why is it called set, then.  This is NOT a characteristic of sets as
: I know them.

It's just an unfortunate choice of the name. The set should have been
called linearly_ordered_set. There is a need for just set
(no order whatsoever), partially_ordered_set (set of sets is an example,
where 'less' means 'is a subset of'), linearly_ordered_set (that's what
our standard set is), and about 20 other types of ordered sets, I don't
even want to mention. What a nice way to introduce OO into STL :-).
That would also introduce the opportunity to turn the notion of
'map' back into what god intended it to be, not what the programmers
turned it into :-).

Anyway, I think it was too much to ask from the committee to figure out
all that, and choose the names appropriately. However, I do think
that one should be able to put complex<whatever> into a set, without
even the need to know about the dreaded second templete parameter,
just like one is not required to know about the dreaded third, which
has about as much to do with mathematical notion of the complex numbers
as the second.

For now, just implement and use your own unordered_set.

P.S. It would be nice to have set of sets, etc. too.

Oleg.
--
Life is a sexually transmitted, 100% lethal disease.


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

kanze@gabi-soft.fr (J. Kanze) writes:

> |>  It's not an implementation detail at all.  One of the most important
> |>  invariants of set (and of map, multiset, and multimap) is that the
> |>  elements are guaranteed always to be sorted in ascending order by key.
> |>  This is very much a part of set's public interface.
>
> So why is it called set, then.  This is NOT a characteristic of sets as
> I know them.

You're certainly right that the class set<>, a sorted associative
container, has many features and invariants that you won't find in a
book of mathematical set theory.  (I'm not sure that ordinary set
theory even covers operations like insertion and erasure, actually.)

Whether it's close enough to the set-theoretical definition to deserve
the name---well, I don't know.  I didn't invent the name of that
container, but I also don't think it's a particularly outrageous name.
But maybe that's just because I've gotten used to it.

Names aside, part of the user-visible interface of sorted associative
containers is that they are always sorted in ascending order by key.



[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Nathan Myers wrote:

> Arguably one shouldn't put complex<float> values in a set because
> it implicitly involves comparing them for equality, and float is
> an imprecise representation: equality of floating-point values is
> often illusory.  (E.g. assert(2.0 == sqrt(2.0)*sqrt(2.0)).)

What about complex<int> ? Granted that isn't std, but it's a
simple, meaningfull, common extension and it makes sens to
put them in sets with the syntax: set<complex<int> >.

But perhaps an implementor would be able to add
less<complex<int> > without being non-conforming.

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://www.pratique.fr/~bonnardv/
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

J. Kanze wrote in message ...
> [Elements of std::set must support less()]
>So why is it called set, then.  This is NOT a characteristic of sets as
>I know them.


I guess elements of a mathematical set must support an equality test (either
value or identity).

However a common set operation is searching (is-a-member()).  Set
implementations that don't perform searching efficiently won't be used.
Conventional searching algorithms provide efficient searching only for
members which are either comparable (in a relational sense) or hashable.

In programs we also want to modify sets (insert new members).  The issue
arises of how that will be implemented.  Possibilities seem to be limited to
  1) By value.  Something like copy-construction must be available.
  2) By pointer.  Something like address-of must be available.
  3) By reference.
If either (2) or (3) is used ownership issues become considerable more
complex.

Finally, C++ is a strongly typed language, so it makes sense to make
containers homogeneous.  In mathematics it makes sense to talk about the set
  { President Lincoln, pink, All irrational numbers between 0 and 1 }
but it would be difficult to fit that set into a C++ framework.  It is
certainly difficult to enumerate the members ;-)

So the correct name for std::set should really be:

std::finite_homogenous_relational_value_set

If we decide that infinite or heterogeneous sets don't really fit C++ we can
still characterize sets by
  1) How is equality determined (value or identity)?
  2) How is lookup made efficient (relational or hash or inefficient)?
  3) How is membership maintained (value, address, reference)?  For address
and
      reference, who owns members?
std::set makes it reasonably easy to implement any meaningful combination of
the above (I'm not sure about membership by reference) using relational
lookup.  Vector can easily be used if inefficient lookup is preferable to
sophisticated element operations.  The lack of hash_set is an obvious hole
in the standard, but it is becoming widely available from other sources.

Maybe a better method for coming up with a name would be to follow the
precedence used for integers.  C++ has a concept which represents a subset
of the set of integers, and named it int, using a subset of the word
integer.  So since the thing in STL is a subset (restricted) concept of set,
lets just call it an 's' or an 'se'.

On a more serious note, less_set would be a more accurate name and matches
well with hash_set.  However the amount of confusion caused by the name is
IMO negligible.  It ain't perfect, but its pretty darn good.




[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

kanze@gabi-soft.fr (J. Kanze) wrote:

: Matt Austern <austern@sgi.com> writes:

: |>  It's not an implementation detail at all.  One of the most important
: |>  invariants of set (and of map, multiset, and multimap) is that the
: |>  elements are guaranteed always to be sorted in ascending order by key.
: |>  This is very much a part of set's public interface.

: So why is it called set, then.  This is NOT a characteristic of sets as
: I know them.

While {123} == {132} == {213} == {231} == {312} == {321} as sets, the
cannonical representation is ordered (regardless of sensibility) and
is {123}.  Set also serves as an ordered list (using list in the
general form, not linked).  Set does all of the things that a set
should do and also provides cannonical order traversal as do most
other representations of set (less hashing which may be a fault for
it).

John
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Matt Austern <austern@sgi.com> wrote:
: Valentin Bonnard <bonnardv@pratique.fr> writes:

: > Why is it less ill-defined than:
: >   set<typeinfo>
: > or
: >   set<typeinfo, use_before>
: >
: > I repeat the question: how can you say that C++ types can
: > be ordered but complex<> can't ?

: Well, actually set<typeinfo> is ill-defined too.  It's ill-defined
: for two reasons.

: First, for the same reason as set<complex>: typeinfo has no operator<,
: so less<typeinfo> doesn't make sense.

I don't think you are right that less<typeinfo> doesn't make sense.
In fact, I was under impression that the ability to implement
less<typeinfo> was exactly the reason to introduce typeinfo::before().
Which primary purpose, in turn, is to enable one to put
typeinfo's into standard containers. Now that you've mentioned
that you can't put typeinfo's into containers directly, I see
that you can only put pointers to typeinfo's into a container,
while having a meanigful specialization less<typeinfo*>.

Either way, your argument is illogical. There are many classes with
no standard operator<, but for which less<> makes a lot of sense.
For example, if you want to make a set of sets, you will be forced
to define some arbitrary less< set<> >. Say, lexicographical_compare
or something. Calling it operator< would contradict the common practice,
since it makes no mathemetical sense. The normal mathematical operator<
on sets is "is contained in", which is unacceptable for the container
'set', because it's a partial order. While calling it less< set<> > is
fine due to the commonly accepted practice of calling arbitrary,
making-no-sense-mathematically ordering ``less<whatever>'', just to be
able to put 'whatever' into a container, like set, or to able to apply
some standard algorithms to a container of whatever's.

: Second, typeinfo doesn't meet the basic requirements for a type that's
: stored in any of the standard containers: it doesn't have a publicly
: accessible copy constructor or assignment operator.  (In fact, it
: doesn't have any public constructors at all)

Hmm... My copy (CD2) says that it has the public default constructor.
This doesn't seem to be a typo, because it also has a public
virtual destructor (and no friend classes or functions), which whould
not have made sense otherwize. Which brings up the question. What
the virtual destructor is for?

Oleg.
--
Life is a sexually transmitted, 100% lethal disease.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

J. Kanze wrote:
>
> Matt Austern <austern@sgi.com> writes:
>
> |>  Fergus Henderson <fjh@cs.mu.OZ.AU> writes:
> |>
> |>  > But why should the user have to specify the ordering explicitly,
> |>  > when the particular ordering chosen is irrelevant?
> |>  > The fact that `set' uses an ordering at all is really an
> |>  > implementation detail of `set'.
> |>
> |>  It's not an implementation detail at all.  One of the most important
> |>  invariants of set (and of map, multiset, and multimap) is that the
> |>  elements are guaranteed always to be sorted in ascending order by key.
> |>  This is very much a part of set's public interface.
>
> So why is it called set, then.  This is NOT a characteristic of sets as
> I know them.

It is not a characteristic of mathematical sets, but it is a practical
necessity for reasonably fast access to a set represented inside a
computer. The relative access speed of various 'set' members is part of
the specification of 'set', and I don't believe it's achievable without
being able to order the elements, thereby allowing the use of btrees or
something comparable. As long as the elements must be ordered, it's a
cheap additional requirement that the iterators access them in that
order.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Valentin Bonnard  <bonnardv@pratique.fr> wrote:
>Nathan Myers wrote:
>> Arguably one shouldn't put complex<float> values in a set because
>> it implicitly involves comparing them for equality, and float is
>> an imprecise representation: equality of floating-point values is
>> often illusory.  (E.g. assert(2.0 == sqrt(2.0)*sqrt(2.0)).)
>
>What about complex<int> ? Granted that isn't std, but it's a
>simple, meaningful, common extension and it makes sense to
>put them in sets with the syntax: set<complex<int> >.
>
>But perhaps an implementor would be able to add
>less<complex<int> > without being non-conforming.

Both complex<int> and less< complex<int> > would be
conforming extensions.  Of course no two implementations
might agree on how the latter is defined, but so what?

Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/



[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Matt Austern wrote:
>
> kanze@gabi-soft.fr (J. Kanze) writes:
>
> > |>  No.  Defining less<typeinfo> might be reasonable, but defining
> > |>  less<complex<T> > would be a terrible mistake.  Complex numbers are
> > |>  not ordered.
> >
> > So.  By not defining less< complex< T > >, you are not saying the
> > complex numbers are not ordered, you are saying that complex numbers
> > cannot be members of a set.
>
> No, all I'm saying is that the type
>     set<complex<double> >
> is ill-defined.  There's nothing that prohibits the type
>     set<complex<double>, MyArbitraryOrdering>
> if it happens to be appropriate.

Why is it less ill-defined than:
  set<typeinfo>
or
  set<typeinfo, use_before>

I repeat the question: how can you say that C++ types can
be ordered but complex<> can't ?

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://www.pratique.fr/~bonnardv/
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Fergus Henderson <fjh@cs.mu.OZ.AU> writes:

> But why should the user have to specify the ordering explicitly,
> when the particular ordering chosen is irrelevant?
> The fact that `set' uses an ordering at all is really an
> implementation detail of `set'.

It's not an implementation detail at all.  One of the most important
invariants of set (and of map, multiset, and multimap) is that the
elements are guaranteed always to be sorted in ascending order by key.
This is very much a part of set's public interface.  By default set
orders its elements according to operator<; you specify the ordering
if you want the elements to be ordered differently, or if the elements
you're using have no operator< at all.

If you don't care about the ordering within the container, then it's
likely that set is the wrong choice for your application and that
something like hash_set would be better.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Valentin Bonnard <bonnardv@pratique.fr> writes:

> Why is it less ill-defined than:
>   set<typeinfo>
> or
>   set<typeinfo, use_before>
>
> I repeat the question: how can you say that C++ types can
> be ordered but complex<> can't ?

Well, actually set<typeinfo> is ill-defined too.  It's ill-defined
for two reasons.

First, for the same reason as set<complex>: typeinfo has no operator<,
so less<typeinfo> doesn't make sense.

Second, typeinfo doesn't meet the basic requirements for a type that's
stored in any of the standard containers: it doesn't have a publicly
accessible copy constructor or assignment operator.  (In fact, it
doesn't have any public constructors at all)
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

In article <34D165EB.41C6@cs.mu.oz.au>, Fergus Henderson <fjh@cs.mu.OZ.AU> wrote:
>Matt Austern wrote:
>> No, all I'm saying is that the type
>>     set<complex<double> >
>> is ill-defined.  There's nothing that prohibits the type
>>     set<complex<double>, MyArbitraryOrdering>
>> if it happens to be appropriate.
>
>But why should the user have to specify the ordering explicitly,
>when the particular ordering chosen is irrelevant?
>The fact that `set' uses an ordering at all is really an
>implementation detail of `set'.  Why should the user have
>to specify MyArbitraryOrdering for `complex', but not for
>`int *' or `type_info'?

At what point is the ordering a detail?  It seems to me that
part of the specification of set<> is test for inclusion
time on the order O(log(N)).  This seems (without some magic
that I am not aware of) to require an (partial) ordering.
I suppose the set could be hashed instead, but that would
require a hashing function and leave us worse off (since
there is no default hashing function for int).

One of the many interesting bits of the STL is the specification
of costs.

marco
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Matt Austern <austern@sgi.com> writes:

|>  Fergus Henderson <fjh@cs.mu.OZ.AU> writes:
|>
|>  > But why should the user have to specify the ordering explicitly,
|>  > when the particular ordering chosen is irrelevant?
|>  > The fact that `set' uses an ordering at all is really an
|>  > implementation detail of `set'.
|>
|>  It's not an implementation detail at all.  One of the most important
|>  invariants of set (and of map, multiset, and multimap) is that the
|>  elements are guaranteed always to be sorted in ascending order by key.
|>  This is very much a part of set's public interface.

So why is it called set, then.  This is NOT a characteristic of sets as
I know them.

--
James Kanze    +33 (0)1 39 23 84 71    mailto: kanze@gabi-soft.fr
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
Conseils en informatique orient   e objet --
              -- Beratung in objektorientierter Datenverarbeitung
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

In article <34D1C28D.5EDB@pratique.fr>,
Valentin Bonnard  <bonnardv@pratique.fr> wrote:
>Matt Austern wrote:
>> ... all I'm saying is that the type
>>     set<complex<double> >
>> is ill-defined.  There's nothing that prohibits the type
>>     set<complex<double>, MyArbitraryOrdering>
>> if it happens to be appropriate.
>
>Why is it less ill-defined than:
>  set<typeinfo>
>or
>  set<typeinfo, use_before>
>
>I repeat the question: how can you say that C++ types can
>be ordered but complex<> can't ?

You can say it because if you try it out, set<char*> works,
but set< complex<float> > doesn't.  Anything else is just
hand-waving.

It was pointed out, and the committee agreed, that pointers would
be put in sets often enough to be worth special dispensation.

Arguably one shouldn't put complex<float> values in a set because
it implicitly involves comparing them for equality, and float is
an imprecise representation: equality of floating-point values is
often illusory.  (E.g. assert(2.0 == sqrt(2.0)*sqrt(2.0)).)

Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

kanze@gabi-soft.fr (J. Kanze) writes:

> |>  No.  Defining less<typeinfo> might be reasonable, but defining
> |>  less<complex<T> > would be a terrible mistake.  Complex numbers are
> |>  not ordered.
>
> So.  By not defining less< complex< T > >, you are not saying the
> complex numbers are not ordered, you are saying that complex numbers
> cannot be members of a set.

No, all I'm saying is that the type
    set<complex<double> >
is ill-defined.  There's nothing that prohibits the type
    set<complex<double>, MyArbitraryOrdering>
if it happens to be appropriate.
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Matt Austern wrote:
>
> kanze@gabi-soft.fr (J. Kanze) writes:
>
> > By not defining less< complex< T > >, you are not saying the
> > complex numbers are not ordered, you are saying that complex numbers
> > cannot be members of a set.
>
> No, all I'm saying is that the type
>     set<complex<double> >
> is ill-defined.  There's nothing that prohibits the type
>     set<complex<double>, MyArbitraryOrdering>
> if it happens to be appropriate.

But why should the user have to specify the ordering explicitly,
when the particular ordering chosen is irrelevant?
The fact that `set' uses an ordering at all is really an
implementation detail of `set'.  Why should the user have
to specify MyArbitraryOrdering for `complex', but not for
`int *' or `type_info'?
--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the
pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S.
Garp.


[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Matt Austern <austern@isolde.mti.sgi.com> writes:

|>  Valentin Bonnard <bonnardv@pratique.fr> writes:
|>
|>  > Mark Sebern <msebern@nospam.sebern.com> writes:
|>  >
|>  > > A colleague has been trying to combine the <complex> and <vector>
|>  > > libraries to define a vector of complex values:
|>  > >
|>  > > vector <complex<double> > vec_complex;
|>  >
|>  > On a related topic, I can't find a definition of:
|>  > - less<complex>
|>  > - less<typeinfo>
|>  > in CD2. Is it an intentionnal ommision ? Shouldn't less<> be
|>  > defined for every type with op== ?
|>
|>  No.  Defining less<typeinfo> might be reasonable, but defining
|>  less<complex<T> > would be a terrible mistake.  Complex numbers are
|>  not ordered.

So.  By not defining less< complex< T > >, you are not saying the
complex numbers are not ordered, you are saying that complex numbers
cannot be members of a set.

The specification of "order", in the traditional sense, is given by
operator<.  Any attempt to define this for complex would be, IMHO, a
disasterous error.  The function less, however, generally defines a
relationship that is more general (over incomparible pointers, for
example, or even pair), and more precise (the ordering must be total).
People don't write "if ( less< complex< double > >( z1 , z2 ) )", they
write "if ( z1 < z2 )".  On the other hand, they do want to be able to
write: "set< complex< double > >", which requires the total (but
probably arbitrary) ordering of less.

--
James Kanze    +33 (0)1 39 23 84 71    mailto: kanze@gabi-soft.fr
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Mark Sebern <msebern@nospam.sebern.com> writes:

> A colleague has been trying to combine the <complex> and <vector>
> libraries to define a vector of complex values:
>
> vector <complex<double> > vec_complex;

On a related topic, I can't find a definition of:
- less<complex>
- less<typeinfo>
in CD2. Is it an intentionnal ommision ? Shouldn't less<> be
defined for every type with op== ?

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://www.pratique.fr/~bonnardv/
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Valentin Bonnard writes:

> Shouldn't less<> be defined for every type with op== ?

Certainly not.  For some types, equality makes sense while an ordering
relation cannot be established.  Some operations require types to be
EqualityComparable only; while others need types to be
LessThanComparable, which are completely disjoint requirements.

--
Alexandre Oliva
mailto:oliva@dcc.unicamp.br mailto:aoliva@acm.org
http://www.dcc.unicamp.br/~oliva
Universidade Estadual de Campinas, SP, Brasil
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Valentin Bonnard <bonnardv@pratique.fr> writes:

> Mark Sebern <msebern@nospam.sebern.com> writes:
>
> > A colleague has been trying to combine the <complex> and <vector>
> > libraries to define a vector of complex values:
> >
> > vector <complex<double> > vec_complex;
>
> On a related topic, I can't find a definition of:
> - less<complex>
> - less<typeinfo>
> in CD2. Is it an intentionnal ommision ? Shouldn't less<> be
> defined for every type with op== ?

No.  Defining less<typeinfo> might be reasonable, but defining
less<complex<T> > would be a terrible mistake.  Complex numbers are
not ordered.
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Matt Austern <austern@isolde.mti.sgi.com> writes:

> Valentin Bonnard <bonnardv@pratique.fr> writes:
>
> > On a related topic, I can't find a definition of:
> > - less<complex>
> > - less<typeinfo>
> > in CD2. Is it an intentionnal ommission ? Shouldn't less<> be
> > defined for every type with op== ?
>
> No.  Defining less<typeinfo> might be reasonable, but defining
> less<complex<T> > would be a terrible mistake.  Complex numbers are
> not ordered.

I don't see how the notion of _type_ can be more or less
ordered than the notion of complex number. How can you say
that a type is greater than another one ? Or do you have
a complete ordering over the possibillity to order
notions ?  ;-)

Seriously, if you admit less<typeinfo>, then you can
tolerate less<> for any EqualtyComparable types (and
also hash<>).

Note: I have the requirement that op== exist because
I only want less<> for objects which have a value, but
not for objects which have a state but no value like
istream.

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://www.pratique.fr/~bonnardv/
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Valentin Bonnard <bonnardv@pratique.fr> writes:

> Matt Austern <austern@isolde.mti.sgi.com> writes:
>
> > Valentin Bonnard <bonnardv@pratique.fr> writes:
> >
> > > On a related topic, I can't find a definition of:
> > > - less<complex>
> > > - less<typeinfo>
> > > in CD2. Is it an intentionnal ommission ? Shouldn't less<> be
> > > defined for every type with op== ?
> >
> > No.  Defining less<typeinfo> might be reasonable, but defining
> > less<complex<T> > would be a terrible mistake.  Complex numbers are
> > not ordered.
>
> I don't see how the notion of _type_ can be more or less
> ordered than the notion of complex number. How can you say
> that a type is greater than another one ? Or do you have
> a complete ordering over the possibillity to order
> notions ?  ;-)

I agree that the notion of ordering types is problematic.  The only
reason I could possibly tolerate less<typeinfo> at all is that the
standard already demands that types have some (possibly arbitrary)
ordering.  Given that that ordering must exist, it would be acceptable
(not required, merely acceptable) to define less<typeinfo> in terms of
that ordering.

In mathematics, however, there is no standard ordering of complex
numbers; that's one of the more important differences between real and
complex numbers.  Defining less<> or operator< for complex<> would be
a major difference between the C++ class and the underlying
abstraction that it represents.
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]