Topic: STL containers with non-ordered elements?


Author: James Kuyper <kuyper@wizard.net>
Date: 1998/02/06
Raw View
Tom McKearney wrote:
>
> thinker wrote in message <34d736d5.382690@news.infomall.co.il>...
> >the "problem" is STL. By STL definition any class using container must
> >have at least (sometimes more) default ctor, operator< and operator==
>
> Is this really true?  No offense, but I don't believe that it is.
> It is my understanding that the operator< and operator== are only used in
> those
> containers that are sorted (i.e. map<>).
>
> Can anyone verify this?
>
> Tom McKearney

Looking in CD2, I couldn't find operator<() or operator==() in any of
the container requirements on the stored objects, except as a
pre-condition on the ability to apply comparison and equality operators
to containers as a whole, which makes sense.
However, the associative containers do have a template parameter
'Compare', which defaults to less<Key>. If you use the default, then Key
must be a type convertible to bool (why "convertible to bool" rather
than LessThanComparable?) unless you've defined a specialization of
less<Key>.
Note: the priority_queue class also requires a Compare parameter.

I noticed that the lower_bound, upper_bound, equal_range, binary_search,
max, and min algorithms all have LessThanComparable requirements, which
apparantly even apply to the versions with explicit Compare parameters.
Why? I don't think those versions need that requirement.
The descriptions of the first four of these algorithms are confusing, in
that they say things like "if *j<value or comp(*j,value)", where the
first half of the 'or' apparantly applies to the first version, and the
second half to the second version. I suspect that the LessThanComparable
requirements were only meant to apply to the first version, but that is
not clear from the wording.

On the flip side, many other algorithms have versions with and without
an explicit Compare template parameter, yet the versions without that
parameter are not marked as requiring that T be LessThanComparable. Why?
These algorithms also have similarly unclear paired descriptions.

There is a similar issue for the algorithms with and without an explicit
Predicate parameter, that don't have matching distinctions with regard
to EqualityComparable requirements, and unclearly paired up
descriptions.
---
[ 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                  ]





Author: miker3@ix.netcom.com (Michael Rubenstein)
Date: 1998/02/05
Raw View
On 4 Feb 1998 06:49:24 GMT, "Tom McKearney" <no@spam.com> wrote:

>thinker wrote in message <34d736d5.382690@news.infomall.co.il>...
>>the "problem" is STL. By STL definition any class using container must
>>have at least (sometimes more) default ctor, operator< and operator==
>
>Is this really true?  No offense, but I don't believe that it is.
>It is my understanding that the operator< and operator== are only used in
>those
>containers that are sorted (i.e. map<>).
>
>Can anyone verify this?

Actually, they are not even needed for those if you specify a
comparison function.  They are needed if you use operator==,
operator<, ... on container objects.
--
Michael M Rubenstein
---
[ 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                             ]





Author: Oleg Zabluda <zabluda@math.psu.edu>
Date: 1998/02/04
Raw View
thinker <thinker@infomall.co.il> wrote:
: On 20 Jan 98 13:20:44 GMT, "Mark Sebern" <msebern@nospam.sebern.com>
: wrote:

: >> However, nothing in the
: >> standard requires that T have a default constructor, an assignment
: >> operator, or an operator<.
: >If you are correct, and I have no reason to doubt it,

: doubt it. He is wrong.
: >the problem is the STL or the template handling in the compiler.

: the "problem" is STL. By STL definition any class using container must
: have at least (sometimes more) default ctor, operator< and operator==

That's incorrect. None of the functions above are absolutely
needed to store an object in a container.

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                             ]





Author: "Tom McKearney" <no@spam.com>
Date: 1998/02/04
Raw View
thinker wrote in message <34d736d5.382690@news.infomall.co.il>...
>the "problem" is STL. By STL definition any class using container must
>have at least (sometimes more) default ctor, operator< and operator==

Is this really true?  No offense, but I don't believe that it is.
It is my understanding that the operator< and operator== are only used in
those
containers that are sorted (i.e. map<>).

Can anyone verify this?

Tom McKearney




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





Author: "X. Liu" <liu@erdw.ethz.ch>
Date: 1998/02/04
Raw View
Matt Austern wrote in message ...
>There's nothing in the standard that says that.  The standard says
>that a copy constructor and an assignment operator are required; it
>does not say that a default constructor, operator<, or operator== are
>required, unless you actually use certain specific operations.
>
>The intention has always been that default constructors are not
>required unless you explicitly use them.  In fact, the standardization
>committee has spent a fair amount of time making sure of that.

I use VC++ 5.0 STL which requires == and < definition. Could you tell me
which STL does not need it? Maybe I need change a new STL.

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





Author: "Brock" <peabody@npcinternational.com>
Date: 1998/02/04
Raw View
Tom McKearney wrote in message <6b8ga8$jgh$1@ha2.rdc1.md.home.com>...
>thinker wrote in message <34d736d5.382690@news.infomall.co.il>...
>>the "problem" is STL. By STL definition any class using container must
>>have at least (sometimes more) default ctor, operator< and operator==
>
>Is this really true?  No offense, but I don't believe that it is.
>It is my understanding that the operator< and operator== are only used in
>those
>containers that are sorted (i.e. map<>).
<<snipp

You don't have to have operator< even for sorted containers as long as you
provide your own comparison functor.




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






Author: "Brock" <peabody@npcinternational.com>
Date: 1998/02/04
Raw View
X. Liu wrote in message <6b9hva$bqv$1@elna.ethz.ch>...
<<
>I use VC++ 5.0 STL which requires == and < definition. Could you tell me
>which STL does not need it? Maybe I need change a new STL.


I too use VC++ 5.0, the problem was with the compiler, which caused all
members of template classes to be instantiated whether used or not, not STL,
and I believe it was fixed with SP1 or SP2.



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






Author: miker3@ix.netcom.com (Michael Rubenstein)
Date: 1998/02/04
Raw View
On 04 Feb 98 15:08:54 GMT, "X. Liu" <liu@erdw.ethz.ch> wrote:

>Matt Austern wrote in message ...
>>There's nothing in the standard that says that.  The standard says
>>that a copy constructor and an assignment operator are required; it
>>does not say that a default constructor, operator<, or operator== are
>>required, unless you actually use certain specific operations.
>>
>>The intention has always been that default constructors are not
>>required unless you explicitly use them.  In fact, the standardization
>>committee has spent a fair amount of time making sure of that.
>
>I use VC++ 5.0 STL which requires == and < definition. Could you tell me
>which STL does not need it? Maybe I need change a new STL.

This was a bug that has been fixed in the service packs.  I'm not sure
which service pack first fixed it.

Actually, the bug was not in the STL implementation itself, but in the
compiler; it was instantiating member functions that it should not.
--
Michael M Rubenstein


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






Author: thinker@infomall.co.il (thinker)
Date: 1998/02/03
Raw View
On 20 Jan 98 13:20:44 GMT, "Mark Sebern" <msebern@nospam.sebern.com>
wrote:

>> However, nothing in the
>> standard requires that T have a default constructor, an assignment
>> operator, or an operator<.
>If you are correct, and I have no reason to doubt it,

doubt it. He is wrong.
>the problem is the STL or the template handling in the compiler.

the "problem" is STL. By STL definition any class using container must
have at least (sometimes more) default ctor, operator< and operator==
---
[ 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
]





Author: Matt Austern <austern@isolde.mti.sgi.com>
Date: 1998/02/04
Raw View
thinker@infomall.co.il (thinker) writes:

> doubt it. He is wrong.
> >the problem is the STL or the template handling in the compiler.
>
> the "problem" is STL. By STL definition any class using container must
> have at least (sometimes more) default ctor, operator< and operator==

There's nothing in the standard that says that.  The standard says
that a copy constructor and an assignment operator are required; it
does not say that a default constructor, operator<, or operator== are
required, unless you actually use certain specific operations.

The intention has always been that default constructors are not
required unless you explicitly use them.  In fact, the standardization
committee has spent a fair amount of time making sure of that.
---
[ 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                             ]





Author: "Mark Sebern" <msebern@nospam.sebern.com>
Date: 1998/01/19
Raw View
A colleague has been trying to combine the <complex> and <vector> libraries
to define a vector of complex values:

vector <complex<double> > vec_complex;

He's run into an apparent MSVC 5.0 library and/or compiler error, but
that's a separate issue.

My current question is based on the observation that complex values (and
many other things you might want to put into an STL container) are not
ordered. In other words, it's not clear there is an entirely acceptable
value for the expression "(complex_value_1 < complex_value_2)". (Should you
compare "real" components, magnitudes, etc.?)

In the case of user-defined types, it has often been necessary to invent an
ordering ("<" and "==" operators) to satisfy the compile-time needs of the
"find" and "sort" operations (algorithms or member functions).

THE QUESTION: Is there any support in the C++ library standard for cleanly
using STL containers with non-ordered element types, assuming that you do
not intend to use operations like "sort"? (I know that on an ad-hoc basis
you should be able to declare, but perhaps not define, comparison
operations; this, however, seems unnecessarily messy.)

Thanks.

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





Author: Alexandre Oliva <oliva@dcc.unicamp.br>
Date: 1998/01/19
Raw View
Mark Sebern writes:

> vector <complex<double> > vec_complex;

> My current question is based on the observation that complex values (and
> many other things you might want to put into an STL container) are not
> ordered.

> In the case of user-defined types, it has often been necessary to invent an
> ordering ("<" and "==" operators) to satisfy the compile-time needs of the
> "find" and "sort" operations (algorithms or member functions).

These operations should only be instantiated if they're actually
used, which implies that some ordering must be defined.  If these
methods are never called, the C++ compiler must *not* instantiate
them, which means the ordering operators need not be defined at all.

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





Author: Matt Austern <austern@sgi.com>
Date: 1998/01/19
Raw View
"Mark Sebern" <msebern@nospam.sebern.com> writes:

> THE QUESTION: Is there any support in the C++ library standard for cleanly
> using STL containers with non-ordered element types, assuming that you do
> not intend to use operations like "sort"? (I know that on an ad-hoc basis
> you should be able to declare, but perhaps not define, comparison
> operations; this, however, seems unnecessarily messy.)

Yes.  If you construct a vector of type vector<T>, then T must have an
assignment operator and a copy constructor.  However, nothing in the
standard requires that T have a default constructor, an assignment
operator, or an operator<.  (Unless, as you say, you actually use
operations like equal() and sort().)

If your implementation says otherwise, then you are running into a
bug.
---
[ 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
]





Author: "Mark Sebern" <msebern@nospam.sebern.com>
Date: 1998/01/20
Raw View
Matt Austern <austern@sgi.com> wrote in article
<fxtoh18mjpf.fsf@isolde.mti.sgi.com>...
> "Mark Sebern" <msebern@nospam.sebern.com> writes:

> Yes.  If you construct a vector of type vector<T>, then T must have an
> assignment operator and a copy constructor.  However, nothing in the
> standard requires that T have a default constructor, an assignment
> operator, or an operator<.  (Unless, as you say, you actually use
> operations like equal() and sort().)
>
> If your implementation says otherwise, then you are running into a
> bug.

If you are correct, and I have no reason to doubt it, then the MSVC 5.0 STL
and/or compiler may well be noncompliant. It requires that operators ==,
!=, <, >, <=, and >= be declared (though not necessarily defined). Some of
these are needed because the relational operator templates (in namespace
std::rel_ops) are not accessible without additional effort. (In MSVC 4.2, I
believe, only == and < were required.)

I'll look around in MSVC to see if I can find any other way to avoid having
to define at least == and <. Without further investigation, I don't know if
the problem is the STL or the template handling in the compiler.

If anyone is aware of something I might be doing wrong, I'd like to hear
about it.

Thanks.

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





Author: "X. Liu" <liu@erdw.ethz.ch>
Date: 1998/01/20
Raw View
Mark Sebern wrote in message <6a1b1u$ljr@newsops.execpc.com>...
>Matt Austern <austern@sgi.com> wrote in article
><fxtoh18mjpf.fsf@isolde.mti.sgi.com>...
>> "Mark Sebern" <msebern@nospam.sebern.com> writes:

>I'll look around in MSVC to see if I can find any other way to avoid having
>to define at least == and <. Without further investigation, I don't know if
>the problem is the STL or the template handling in the compiler.


I think you can can not avoid declaring == and < for STL container elements
in MSVC 5.0. In their documentation, these two operation are clearly stated
as "must do". I also think this is a flaw in STL. In most of the case I find
I use non-order containers. Every time I need to define == and <, it is
really not elegent.

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