In article <KANZE.95May2180931@slsvhdt.lts.sel.alcatel.de>,
   kanze@lts.sel.alcatel.de (James Kanze US/ESC 60/3/141 #40763) wrote:
>On the other hand, since the STL containers are instantiated over
>class Compare, which is in fact used to do the comparison (and not
>operator<, like the poster seems to believe), this is not a problem.

Mea culpa.  Let me correct:

According to the STL doc dated Feb. 7 1995, at the top of page 20, it talks
about the expression "a < b" (where a and b are values of a container class
X containing objects of type T) and says in part:

 "pre[condition]: < is defined for values of T.
 < is a total ordering relation."

This is a common requirement of all container classes.  However, it appears
to me that this requirement is only needed if a comparison between two
containers is attempted (which is not what I first said).

>(Operator< *is* the default, if the user does not specify another
>comparison operator.)

(Nitpick/Quibble:  That's as close as makes no difference, but it's not
actually a default; there are two versions of such an operation.)

As James pointed out, STL does allow you to use a Compare function object
instead of supplying operator< (see page 47, at the top).  This is for
sorting and related operations (sort, stable_sort, nth_element,
inplace_merge, etc.).  However, whether you end up using operator< or a
Compare, a total ordering is still required.

If any of this is different in the draft standard (I haven't looked), please
enlighten me.  I've got Modena's STL++ on order and it should arrive early
next week, so I'll verify this against their docs too.


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Herb Sutter                 2228 Urwin, Ste 102         voice (416) 618-0184
Connected Object Solutions  Oakville ON Canada L6L 2T2    fax (905) 847-6019

In article <3o03lk$7q0@steel.interlog.com> herbs@interlog.com (Herb
Sutter) writes:

|> In article <3nluih$cs3@eurybia.rz.uni-konstanz.de>,
|>    weihe@hornmatups.fr (Karsten Weihe) wrote:
|> >
|> >  2. Imagine you have a type for which no ``natural''
|> >     total ordering exists.  Defining operator < for such
|> >     a type may introduce a bias in the type definition,
|> >     which may be misleading, unless accompanied by a comment
|> >     like, ``just to satisfy STL requirements.''  Is this
|> >     problem regarded negligible?

|> STL favours ordered containers.  If you always provide operator<, you can
|> use the type in any container, ordered or unordered.  If you don't provide
|> operator<, it restricts your choice of containers.

|> I understand what you're saying, but: a) most types do have a natural
|> ordering;

Really.  Almost none of the types I deal with have a natural ordering.

|> b) if they don't, it's simple to make an arbitrary one;

The problem occurs if there is a natural *incomplete* ordering.  For
example, I have generally overloaded < to mean "is a subset of" for
sets.  This is an incomplete ordering, and this operator cannot be
used by the STL containers.

On the other hand, since the STL containers are instantiated over
class Compare, which is in fact used to do the comparison (and not
operator<, like the poster seems to believe), this is not a problem.
(Operator< *is* the default, if the user does not specify another
comparison operator.)

|> and c)
|> doing so relieves you of the impact of extraneous code changes if you do
|> decide to use an ordered container for that type later on.

Just defined a (functor) class which can be used for comparison, and
you can use an ordered container, regardless of whether operator< is
defined.

|> Special case: If you are writing a library, all classes the client can see
|> should definitely define operator< simply because you can never know whether
|> the client will use an ordered container.  The alternative is to explicitly
|> tell the client he can't use an ordered container, which seems unnecessarily
|> restrictive to me.

The alternative is to provide a comparison class, and tell the client
that ordered container classes must be instantiated from it.

|> >  3. How likely is it that this requirement will be part of
|> >     the ANSI standard?

|> Very.  (It's in the current draft, at any rate.)

Not in my copy.  At least not in the container classes.  E.g.:

 template< class Key ,
           class T ,
           class Compare = less< Key > ,
           class Allocator = allocator >
 class map ...

The template instantiation comparison type can even be overridden for
specific objects, since the constructor takes a parameter of this
type.

Thus, my SetOfChar class, which defines operator<, etc. as "is
strict subset of", etc., also contains a function `compare'.  This
function defines a complete ordering, returning a value <, == or > 0
according to whether the *this object comes before, is the same as, or
comes after the parameter object in this (arbitrary) complete
ordering.  (If my conventions are not those of STL, it is because my
SetOf template class was written before I knew of STL.)  To create a
set of SetOf's:

 struct CompareSetOfChars
 {
     bool                operator()( SetOfChars const& o1 ,
                                     SetOfChars const& o2 )
         {   return o1.compare( o2 ) < 0 ;   }
 } ;

(Naturally, I have since added this declaration to the header file of
SetOf.)

 typedef set< SetOfChars , NodeId , CompareSetOfsChars >
                     SetOfCharToNodeIdMap ;

then gives me the data type I need.

Note: the above is untested.  I have not yet had the time to generate
the STL for my compiler.  With any luck, Sun will beat me to it.
--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils en informatique industrielle --
                              -- Beratung in industrieller Datenverarbeitung

|> In article <DOUG.95Apr26134111@monet.ads.com>,
|> Doug Morgan <doug@monet.ads.com> wrote:
|> >
|> >>   2. Imagine you have a type for which no ``natural''
|> >>      total ordering exists.  Defining operator < for such
|> >>      a type may introduce a bias in the type definition,
|> >>      which may be misleading, unless accompanied by a comment
|> >>      like, ``just to satisfy STL requirements.''  Is this
|> >>      problem regarded negligible?
|> >
|> >Seems to be by those that matter.

I keep hearing of how STL `requires' an operator< to be defined for
the types on which it is instantiated.  I have been unable to find
this requirement in the specification (after an admittedly very quick
search in the most probably locations).  Could someone please point
out to me where this is the case.  (In all of the cases I spotted
off-hand, STL uses a Compare object to make the comparison.)
--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils en informatique industrielle --
                              -- Beratung in industrieller Datenverarbeitung

In article <3nluih$cs3@eurybia.rz.uni-konstanz.de>,
   weihe@hornmatups.fr (Karsten Weihe) wrote:
>
>  2. Imagine you have a type for which no ``natural''
>     total ordering exists.  Defining operator < for such
>     a type may introduce a bias in the type definition,
>     which may be misleading, unless accompanied by a comment
>     like, ``just to satisfy STL requirements.''  Is this
>     problem regarded negligible?

STL favours ordered containers.  If you always provide operator<, you can
use the type in any container, ordered or unordered.  If you don't provide
operator<, it restricts your choice of containers.

I understand what you're saying, but: a) most types do have a natural
ordering; b) if they don't, it's simple to make an arbitrary one; and c)
doing so relieves you of the impact of extraneous code changes if you do
decide to use an ordered container for that type later on.

Special case: If you are writing a library, all classes the client can see
should definitely define operator< simply because you can never know whether
the client will use an ordered container.  The alternative is to explicitly
tell the client he can't use an ordered container, which seems unnecessarily
restrictive to me.  (And what if the client derives from your class, and the
new type _does_ have a total ordering?  Sure, an operator< in the base
class isn't a necessity, but he might be in for a nasty surprise when he
first writes his own operator< to call the base operator< as part of its
processing.)

>  3. How likely is it that this requirement will be part of
>     the ANSI standard?

Very.  (It's in the current draft, at any rate.)


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Herb Sutter                 2228 Urwin, Ste 102         voice (416) 618-0184
Connected Object Solutions  Oakville ON Canada L6L 2T2    fax (905) 847-6019

Hi,

the paper of Alexander Stepanov and Meng Lee, ``The
Standard Template Library,'' version from 9/20/1994
(Copyright(c)1994 Hewlett-Packard Company), says on
p. 20 that, to be STL-Like, each container class must
provide an operator <, which compares two containers
lexicographically. This, in turn, requires operator <
for every type you want to store in a container.

Questions to the audience:

  1. Why is this particular feature regarded so important that
     this is part of the general requirements, although
     ``requirements should be as general as possible'' (p. 4)?

  2. Imagine you have a type for which no ``natural''
     total ordering exists.  Defining operator < for such
     a type may introduce a bias in the type definition,
     which may be misleading, unless accompanied by a comment
     like, ``just to satisfy STL requirements.''  Is this
     problem regarded negligible?

  3. How likely is it that this requirement will be part of
     the ANSI standard?

Thanks for any comments,

Karsten Weihe

--

   Uni Konstanz
   Informatik
   78434 Konstanz
   Germany

   Email: karsten.weihe@uni-konstanz.de

   Phone: ++49-7531-884375
   Fax:   ++49-7531-883577

   WWW:   ~weihe/me.html or ~weihe/ich.html (German)
          at  http://www.informatik.uni-konstanz.de/

In article <3nluih$cs3@eurybia.rz.uni-konstanz.de> weihe@hornmatups.fr (Karsten Weihe) writes:
> ...
> the paper of Alexander Stepanov and Meng Lee, ``The
> Standard Template Library,'' version from 9/20/1994
> (Copyright(c)1994 Hewlett-Packard Company), says on
> p. 20 that, to be STL-Like, each container class must
> provide an operator <, which compares two containers
> lexicographically. This, in turn, requires operator <
> for every type you want to store in a container.

Sometimes you might get (nonportably) lucky and not call any
comparison operators on the collections, use a compiler that only
instantiates member functions that are actually called, and not call
any function templates that use element comparisons.  Then, you might
"get away" with not defining an operator < on elements.

> Questions to the audience:
>
>   1. Why is this particular feature regarded so important that
>      this is part of the general requirements, although
>      ``requirements should be as general as possible'' (p. 4)?

STL as currently spec'ed has a strong bias toward *ordered*
containers.  This is due to a combination of reasons including
historical developments, personal preferences, and C++ standardization
deadline pressures.  Unfortunately, it's now pretty late for changes.

>   2. Imagine you have a type for which no ``natural''
>      total ordering exists.  Defining operator < for such
>      a type may introduce a bias in the type definition,
>      which may be misleading, unless accompanied by a comment
>      like, ``just to satisfy STL requirements.''  Is this
>      problem regarded negligible?

Seems to be by those that matter.

>   3. How likely is it that this requirement will be part of
>      the ANSI standard?

Very, I think.

Doug
----------
Doug Morgan, doug@ads.com
Booz-Allen & Hamilton
1500 Plymouth St.
Mountain View, CA 94043-1230
     (415) 960-7444
FAX: (415) 960-7500
----------