ben@pcae.hep.phy.cam.ac.uk (Ben Bullock) writes:

> There is very poor efficiency in the STL container classes when the
> comparison operations are expensive.
>
> I am currently making a whole new container class of my own just to
> avoid the inefficient STL method based on operator overloading of <
> and ==.  I thought that the point of STL was to be general enough that
> I didn't have to do this.

This is a valid complaint.  There are cases where three-valued
comparison functions are better than two-valued comparison functions
like operator< and less<T>.  This is a problem for the sorted
associative containers (set, map, multiset, multimap), and also for
equal_range.  In addition to the efficiency issue, it's annoying that
strcmp() is not an acceptable comparison function for strings.

Very early versions of the STL did, in fact, use three-valued
comparisons instead of two-valued.  The reason this was changed was
largely one of convenience: operator< is already defined on the
built-in numeric types, and the C++ language does not provide a
three-valued comparison function for them.  Using three-valued
comparisons throughout the STL would have required either that
programers use a non-default version of algorithms and containers when
storing built-in types, or that the default version be less general
than it might otherwise be.

It's too late to put three-valued comparison versions of containers
and algorithms into the standard (at least into this round of the
standard), but there is nothing to stop vendors from providing them as
extensions.  We at SGI are aware of this problem, and we do plan to
address it.
---
[ 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 wrote:
> Very early versions of the STL did, in fact, use three-valued
> comparisons instead of two-valued.  The reason this was changed was
> largely one of convenience: operator< is already defined on the
> built-in numeric types, and the C++ language does not provide a
> three-valued comparison function for them.  Using three-valued
> comparisons throughout the STL would have required either that
> programers use a non-default version of algorithms and containers when
> storing built-in types, or that the default version be less general
> than it might otherwise be.

The default could have been to use two valued < and ==; the user could also
choose to use two value Less or three value; an adptator would be used to
convert from Less to Compare.

--

Valentin Bonnard
mailto:bonnardv@pratique.fr
http://www.pratique.fr/~bonnardv (Informations sur le C++ en Francais)
---
[ 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
]

There is very poor efficiency in the STL container classes when the
comparison operations are expensive.

I am currently making a whole new container class of my own just to
avoid the inefficient STL method based on operator overloading of <
and ==.  I thought that the point of STL was to be general enough that
I didn't have to do this.

If there is an easy way out of the problem that I have that I haven't
seen, please let me know.

Here is my original article:

Ben Bullock wrote:
> I would like to use the set class in STL for my program, but I am
> concerned about the comparison function used by it.  It seems that the
> `set' container uses < and == operators.  However, I would much prefer
> to have a set container which would use a "compare" function which
> could return for instance -1, 0 and +1 for <, ==, > or some such.

> The reason that this is necessary is the complicated nature of the
> things I am comparing.  Typically I would expect that the value of A <
> B and A > B would not require much time to work out, but that A == B
> would be expensive because of needing to compare every element of a
> complicated structure, and further that I would be repeating the same
> loop over all the elements with < and ==.  I expect that this
> comparing part of my application which will involve several thousands
> or even tens of thousands of A's and B's will be the most
> time-intensive part, which is why I am not really willing to use a
> container which will waste time repeating comparisons.

> This problem has occurred in two different applications that I am
> developing (one a Feynman graph drawing program where I need to
> compare topologies of graphs and another one a computer algebra system
> where I need to compare products of algebraic objects).  I would be
> surprised if no-one else had the same problem.  So, I wonder if anyone
> else has a solution to this problem.

> In fact I can't really see a good case for operator overloading `=='
> and `<' in this case since a `compare(A,B)' that can return three
> values -1,0,+1 should ALWAYS require less computation than using `<'
> and `==' separately.

--
Ben Bullock @ Cavendish Laboratory, University of Cambridge, Britain
email: bullock@hep.phy.cam.ac.uk
www:   http://www.hep.phy.cam.ac.uk/theory/ben/index.html
---
[ 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
]