 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Seungbeom Kim
Guest
|
 Posted: Tue Feb 22, 2005 6:56 pm Post subject: Why the 2-way comparison instead of the C-style 3-way compar |
 |
|
The comparison function used by bsearch and qsort from C is supposed to
return <0, =0, >0 when a<b, a=b, a>b respectively when called with (a,b).
On the other hand, the Compare object used by C++ standard library (25.3)
is supposed to return bool, indicating only whether a
worse than the old C way because we need two calls to the function to
test for equality: !comp(a, b) && !comp(b, a), which takes about twice
the time needed with the old 3-way comparison semantics.
The 2-way comparison also makes it difficult to combine multiple
comparisons into a single one; e.g.
struct A;
struct B;
struct C;
struct M { A a; B b; C c; };
// C way
int M_compare(const M& x, const M& y)
{
int c;
if ((c = A_compare(x.a, y.a)) != 0) return c;
if ((c = B_compare(x.b, y.b)) != 0) return c;
c = C_compare(x.c, y.c); return c;
}
// C++ way
bool M_compare(const M& x, const M& y)
{
if (A_compare(x.a, y.a)) return true;
if (A_compare(y.a, x.a)) return false;
if (B_compare(x.b, y.b)) return true;
if (B_compare(y.b, x.b)) return false;
return C_compare(x.a, y.a);
};
(And imagine what we would happen if we want to compare two M objects for
equality.. how many calls to A_compare?)
Why was this new-style 2-way comparison adopted instead of the good old
C-style 3-way comparison?
--
Seungbeom Kim
---
[ 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 ]
|
|
| Back to top |
|
 |
Dietmar Kuehl
Guest
|
| Posted: Wed Feb 23, 2005 2:58 am Post subject: Re: Why the 2-way comparison instead of the C-style 3-way co |
|
|
Seungbeom Kim wrote:
| Quote: | On the other hand, the Compare object used by C++ standard library (25.3)
is supposed to return bool, indicating only whether a<b. This seems to be
worse than the old C way because we need two calls to the function to
test for equality: !comp(a, b) && !comp(b, a), which takes about twice
the time needed with the old 3-way comparison semantics.
|
Have you measured the effect? I can imagine that there are types which are
faster with 2-way comparison and ones which are faster with 3-way
comparison. That is, I doubt that it is a universal trait that 3-way
comparison is always faster.
| Quote: | The 2-way comparison also makes it difficult to combine multiple
comparisons into a single one;
|
On the other hand, it is more difficult to take advantage of the 3-way
result (unless you call the comparison function twice). I don't buy
any argument in this direction either.
| Quote: | (And imagine what we would happen if we want to compare two M objects for
equality.. how many calls to A_compare?)
|
Two. How many would you imagine?
| Quote: | Why was this new-style 2-way comparison adopted instead of the good old
C-style 3-way comparison?
|
Personally, I think the 2-way comparison is much clearer: I always need
to look up what 1 and -1 mean if I call comp(a, b): is a smaller or b
if the result is 1? (I think b because you might implement the comparator
to return "a - b" but this actually shows that you need to compare the
result against something anyway).
--
<http://www.contendix.com> - Software Development & Consulting
---
[ 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 ]
|
|
| Back to top |
|
|
Ben Hutchings
Guest
|
| Posted: Wed Feb 23, 2005 2:58 am Post subject: Re: Why the 2-way comparison instead of the C-style 3-way co |
|
|
Seungbeom Kim wrote:
| Quote: | The comparison function used by bsearch and qsort from C is supposed to
return <0, =0, >0 when a<b, a=b, a>b respectively when called with (a,b).
On the other hand, the Compare object used by C++ standard library (25.3)
is supposed to return bool, indicating only whether a<b. This seems to be
worse than the old C way because we need two calls to the function to
test for equality: !comp(a, b) && !comp(b, a), which takes about twice
the time needed with the old 3-way comparison semantics.
|
I *think* (but am not sure) that binary searching with an order
predicate only requires 1 more comparison than binary searching with a
3-way comparator, on average. Since 3-way comparisons tend to take
marginally longer, order predicates may actually result in faster
searching. But do try comparing actual speeds, if you're concerned
about this.
As evidence, see the implementations of lower_bound, upper_bound and
binary_search for random-access iterators in
(or <http://tinyurl.com/6gxve>). (These are not quite correct; read
the follow-up too.)
| Quote: | The 2-way comparison also makes it difficult to combine multiple
comparisons into a single one; e.g.
struct A;
struct B;
struct C;
struct M { A a; B b; C c; };
// C way
int M_compare(const M& x, const M& y)
{
int c;
if ((c = A_compare(x.a, y.a)) != 0) return c;
if ((c = B_compare(x.b, y.b)) != 0) return c;
c = C_compare(x.c, y.c); return c;
}
// C++ way
bool M_compare(const M& x, const M& y)
{
if (A_compare(x.a, y.a)) return true;
if (A_compare(y.a, x.a)) return false;
if (B_compare(x.b, y.b)) return true;
if (B_compare(y.b, x.b)) return false;
return C_compare(x.a, y.a);
};
|
The C++ way is to overload equality and inequality operators, so you
can just write:
return x.a < y.a || (x.a == y.a
&& (x.b < y.b || (x.b == y.b
&& x.c < y.c)));
| Quote: | (And imagine what we would happen if we want to compare two M objects for
equality.. how many calls to A_compare?)
|
Yes, I can see how this could get inefficient for complex types
(though probably not for std::complex types!).
| Quote: | Why was this new-style 2-way comparison adopted instead of the good old
C-style 3-way comparison?
|
I couldn't say, but one point in their favour is that the mathematics
of ordering relations are better understood.
--
Ben Hutchings
It is easier to write an incorrect program than to understand a correct one.
---
[ 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 ]
|
|
| Back to top |
|
|
Thomas Mang
Guest
|
| Posted: Sat Feb 26, 2005 3:41 pm Post subject: Re: Why the 2-way comparison instead of the C-style 3-way co |
|
|
"Seungbeom Kim" <musiphil (AT) bawi (DOT) org> schrieb im Newsbeitrag
news:cvdf6s$och$1 (AT) news (DOT) Stanford.EDU...
| Quote: | The comparison function used by bsearch and qsort from C is supposed to
return <0, =0, >0 when a<b, a=b, a>b respectively when called with (a,b).
On the other hand, the Compare object used by C++ standard library (25.3)
is supposed to return bool, indicating only whether a
worse than the old C way because we need two calls to the function to
test for equality: !comp(a, b) && !comp(b, a), which takes about twice
the time needed with the old 3-way comparison semantics.
|
Maybe I am missing something, but the new way, you make - inside comp - only
one comparison.
E.g. for ints:
bool operator()(int a, int b)
{ return a < b;}
Whereas for the C-style - way, you'd need to make (potentially) a second
comparison. That's an additional cost!
But for ordererd containers, this second comparison is usually useless,
since operator<() == true already suffices to travel forward one node.
I can easily imagine the C-style way costing more than the C++-style under
certain - probably quite common - circumstances.
Thomas
---
[ 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 ]
|
|
| Back to top |
|
|
Niklas Matthies
Guest
|
| Posted: Sun Feb 27, 2005 9:58 pm Post subject: Re: Why the 2-way comparison instead of the C-style 3-way co |
|
|
On 2005-02-23 02:58, Dietmar Kuehl wrote:
:
| Quote: | Personally, I think the 2-way comparison is much clearer: I always need
to look up what 1 and -1 mean if I call comp(a, b): is a smaller or b
if the result is 1?
|
I find it quite intuitive: a is </=/> b iff comp(a, b) is </=/> zero,
respectively.
-- Niklas Matthies
---
[ 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 ]
|
|
| Back to top |
|
|
Max T. Woodbury
Guest
|
| Posted: Sun Feb 27, 2005 9:59 pm Post subject: Re: Why the 2-way comparison instead of the C-style 3-way co |
|
|
Thomas Mang wrote:
| Quote: | "Seungbeom Kim" <musiphil (AT) bawi (DOT) org> schrieb im Newsbeitrag
news:cvdf6s$och$1 (AT) news (DOT) Stanford.EDU...
The comparison function used by bsearch and qsort from C is supposed to
return <0, =0, >0 when a<b, a=b, a>b respectively when called with (a,b).
On the other hand, the Compare object used by C++ standard library (25.3)
is supposed to return bool, indicating only whether a<b. This seems to be
worse than the old C way because we need two calls to the function to
test for equality: !comp(a, b) && !comp(b, a), which takes about twice
the time needed with the old 3-way comparison semantics.
Maybe I am missing something, but the new way, you make - inside comp - only
one comparison.
E.g. for ints:
bool operator()(int a, int b)
{ return a < b;}
Whereas for the C-style - way, you'd need to make (potentially) a second
comparison. That's an additional cost!
|
a C style comparison is typically done with a subtraction:
int cmpbyte( char a, char b) { return (int)a - b; }
[or is it (int)b - a? Always build a unit tester to make sure you
meet your specification!]
| Quote: | But for ordererd containers, this second comparison is usually useless,
since operator<() == true already suffices to travel forward one node.
I can easily imagine the C-style way costing more than the C++-style under
certain - probably quite common - circumstances.
|
Your imagination has failed you...
On the hardware level most comparisons return a three, sometimes four
value result (<, ==, >, and not comparable). Those results are then
converted into binary actions; you either change the instruction pointer
value or let it continue to the next sequential instruction. Usually
the comparison instruction takes more resources than the action
instruction but the branch instruction may trash the contents of the
prefetch pipeline. However all this is minor compared to the cost of
a real subroutine call.
A well optimized C style comparison function would typically do one
comparison and then a sequence of two conditional branches to sort
out the three cases. In at least some cases no action is needed
because the result of a simple subtraction of two values has the
correct form.
The STL style comparisons have the advantage of being analytically
simpler and easier to document, but they are typically slower in
execution because they have to be called twice. That makes them
cheaper from the implementer's manager's point of view, but more
expensive from the user's point of view. The manager usually wins.
[email]max (AT) mtew (DOT) isa-geek.net[/email]
---
[ 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 ]
|
|
| Back to top |
|
|
Carl Barron
Guest
|
| Posted: Mon Feb 28, 2005 3:22 am Post subject: Re: Why the 2-way comparison instead of the C-style 3-way co |
|
|
"Max T. Woodbury" <max.teneyck.woodbury (AT) verizon (DOT) net> wrote:
| Quote: |
The STL style comparisons have the advantage of being analytically
simpler and easier to document, but they are typically slower in
execution because they have to be called twice. That makes them
cheaper from the implementer's manager's point of view, but more
expensive from the user's point of view. The manager usually wins.
Typically slower?? I don't think so, possibly slower yes, but then |
a fine tuned implimentation of a mathematical algorithm is often better
than a generic one, the question becomes is it SIGNIFIGANTLY better?
Now a threw compare requires a function/functor inlined or not to
create the three way result and a compare against zero. If you write
your three way compare and provide simple inline functions operator <(),
operator == () that do this compare to zero then what is the loss in the
algorithem assuming a complier will inline something as simple as a one
line compare to zero?
My route is if a three way is easy or more efficient than a direct
two way compare is to provide both and be done with the problem:)
---
[ 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 ]
|
|
| Back to top |
|
|
Ron House
Guest
|
| Posted: Mon Feb 28, 2005 5:10 am Post subject: Re: Why the 2-way comparison instead of the C-style 3-way co |
|
|
Max T. Woodbury wrote:
| Quote: | a C style comparison is typically done with a subtraction:
int cmpbyte( char a, char b) { return (int)a - b; }
|
Is it? Guess what this program prints:
#include <iostream>
#include <climits>
int main() {
int a=INT_MAX, b=-INT_MAX;
// if (a > b) ...
if (a-b > 0) {
std::cout << a << " > " << b << std::endl;
} else {
std::cout << a << " <= " << b << std::endl;
}
return 0;
}
Answer:
2147483647 <= -2147483647
Now what do you think would happen to code that relied on the sign of
that subtraction?
Hardware might indeed yield three-way flags, but most types are compound
objects, and the simpleminded tests don't work.
--
Ron House [email]house (AT) usq (DOT) edu.au[/email]
http://www.sci.usq.edu.au/staff/house
---
[ 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 ]
|
|
| Back to top |
|
|
Dave Harris
Guest
|
| Posted: Mon Feb 28, 2005 12:54 pm Post subject: Re: Why the 2-way comparison instead of the C-style 3-way co |
|
|
[email]max.teneyck.woodbury (AT) verizon (DOT) net[/email] ("Max T. Woodbury") wrote (abridged):
| Quote: | a C style comparison is typically done with a subtraction:
int cmpbyte( char a, char b) { return (int)a - b; }
|
That's how I think of it, but as an actual implementation it often doesn't
work because of overflow. If the arguments are ints or doubles, for
example, the difference between them may be too big to fit in an int.
| Quote: | The STL style comparisons have the advantage of being analytically
simpler and easier to document, but they are typically slower in
execution because they have to be called twice.
|
"Typically"? For at least some important algorithms, they only have to be
called once.
For example, you are apparently expecting lower_bound to be written like:
T *lower_bound( T *first, T *last, T target ) {
while (first < last) {
T *mid = first + (last - first) / 2;
if (*mid < target)
first = mid + 1;
else if (*mid == target)
return mid;
else
last = mid;
}
return last;
}
but it can also be written like:
T *lower_bound( T *first, T *last, T target ) {
while (first < last) {
T *mid = first + (last - first)/2;
if (*mid < target)
first = mid + 1;
else
last = mid;
}
return last;
}
The second version will make more iterations of the loop, but the work
done in each iteration is smaller. If you think about the shape of a
binary tree, half the items are leaf nodes so the equality test usually
fails and usually saves very little even when it succeeds. And if the
target is absent it will always fail. That equality test is a very dubious
attempt at optimisation.
-- Dave Harris, Nottingham, UK
---
[ 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 ]
|
|
| Back to top |
|
|
kuyper@wizard.net
Guest
|
| Posted: Mon Feb 28, 2005 5:08 pm Post subject: Re: Why the 2-way comparison instead of the C-style 3-way co |
|
|
Max T. Woodbury wrote:
| Quote: | Thomas Mang wrote:
...
Maybe I am missing something, but the new way, you make - inside
comp
- only
one comparison.
E.g. for ints:
bool operator()(int a, int b)
{ return a < b;}
Whereas for the C-style - way, you'd need to make (potentially) a
second
comparison. That's an additional cost!
a C style comparison is typically done with a subtraction:
int cmpbyte( char a, char b) { return (int)a - b; }
|
That works correctly for types where the maximum difference fits in an
'int'. For other types (in particular, for 'int' itself), it can
overflow.
...
| Quote: | On the hardware level most comparisons return a three, sometimes four
value result (<, ==, >, and not comparable). Those results are then
converted into binary actions; you either change the instruction
pointer
value or let it continue to the next sequential instruction. Usually
the comparison instruction takes more resources than the action
instruction but the branch instruction may trash the contents of the
prefetch pipeline. However all this is minor compared to the cost of
a real subroutine call.
|
Note that comparison functions are typically inline, except when
they're so somplex that the subroutine call overhead is minor.
| Quote: | The STL style comparisons have the advantage of being analytically
simpler and easier to document, but they are typically slower in
execution because they have to be called twice.
|
One of the points that was made earlier in this thread is that most of
the relevant algorithms don't require many equality comparisons;
inequality comparisons are all that's needed, and an algorith that uses
a C-style comparison function to perform those inequality comparisons
can easily be less efficient.
---
[ 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 ]
|
|
| Back to top |
|
|
Thomas Mang
Guest
|
| Posted: Mon Feb 28, 2005 5:09 pm Post subject: Re: Why the 2-way comparison instead of the C-style 3-way co |
|
|
""Max T. Woodbury"" <max.teneyck.woodbury (AT) verizon (DOT) net> schrieb im
Newsbeitrag news:_e3Ud.62381$wc.47045 (AT) trnddc07 (DOT) ..
| Quote: | Thomas Mang wrote:
"Seungbeom Kim" <musiphil (AT) bawi (DOT) org> schrieb im Newsbeitrag
news:cvdf6s$och$1 (AT) news (DOT) Stanford.EDU...
The comparison function used by bsearch and qsort from C is supposed to
return <0, =0, >0 when a<b, a=b, a>b respectively when called with
(a,b).
On the other hand, the Compare object used by C++ standard library
(25.3)
is supposed to return bool, indicating only whether a<b. This seems to
be
worse than the old C way because we need two calls to the function to
test for equality: !comp(a, b) && !comp(b, a), which takes about twice
the time needed with the old 3-way comparison semantics.
Maybe I am missing something, but the new way, you make - inside comp -
only
one comparison.
E.g. for ints:
bool operator()(int a, int b)
{ return a < b;}
Whereas for the C-style - way, you'd need to make (potentially) a second
comparison. That's an additional cost!
a C style comparison is typically done with a subtraction:
int cmpbyte( char a, char b) { return (int)a - b; }
[or is it (int)b - a? Always build a unit tester to make sure you
meet your specification!]
But for ordererd containers, this second comparison is usually useless,
since operator<() == true already suffices to travel forward one node.
I can easily imagine the C-style way costing more than the C++-style
under
certain - probably quite common - circumstances.
Your imagination has failed you...
On the hardware level most comparisons return a three, sometimes four
value result (<, ==, >, and not comparable). Those results are then
converted into binary actions; you either change the instruction pointer
value or let it continue to the next sequential instruction. Usually
the comparison instruction takes more resources than the action
instruction but the branch instruction may trash the contents of the
prefetch pipeline. However all this is minor compared to the cost of
a real subroutine call.
|
How do you want to access the hardware-level in portable C++?
The Standard Library could, of course, add new "predicates" that yield
either negative, zero, or positive values and specialize that for built-in
types that take advantage of the hardware level. For UDTs, once could then
call these specializations (if the subobjects are built-in). If not, one
needs to use plain ordinary < and ==. Looks expensive to me if the result of
operator< suffices to make a decision.
Thomas
---
[ 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 ]
|
|
| Back to top |
|
|
Max T. Woodbury
Guest
|
| Posted: Mon Feb 28, 2005 5:34 pm Post subject: Re: Why the 2-way comparison instead of the C-style 3-way co |
|
|
Dave Harris wrote:
| Quote: | max.teneyck.woodbury (AT) verizon (DOT) net ("Max T. Woodbury") wrote (abridged):
a C style comparison is typically done with a subtraction:
int cmpbyte( char a, char b) { return (int)a - b; }
That's how I think of it, but as an actual implementation it often doesn't
work because of overflow. If the arguments are ints or doubles, for
example, the difference between them may be too big to fit in an int.
|
Actually it should be (int)b - a. You should also notice the
cast to a wider type would avoid the overflow issue unless char
and int are the same size. For wider types you need to encode
the result to avoid overflow, but even that overhead is going to
be swamped by the cost of doing the function call. The fact that
the STL allows inlining of the comparison is in fact one of its
more important attributes.
However this does not answer the original question. The STL
comparison specification is based on extensibility and proof
of correctness criteria rather than on performance criteria.
The older C comparison specification put more emphasis on
performance. Which is 'better' depends on how you define
'better'.
| Quote: | The STL style comparisons have the advantage of being analytically
simpler and easier to document, but they are typically slower in
execution because they have to be called twice.
"Typically"? For at least some important algorithms, they only have to be
called once.
For example, you are apparently expecting lower_bound to be written like:
T *lower_bound( T *first, T *last, T target ) {
while (first < last) {
T *mid = first + (last - first) / 2;
if (*mid < target)
first = mid + 1;
else if (*mid == target)
return mid;
else
last = mid;
}
return last;
}
but it can also be written like:
T *lower_bound( T *first, T *last, T target ) {
while (first < last) {
T *mid = first + (last - first)/2;
if (*mid < target)
first = mid + 1;
else
last = mid;
}
return last;
}
The second version will make more iterations of the loop, but the work
done in each iteration is smaller. If you think about the shape of a
binary tree, half the items are leaf nodes so the equality test usually
fails and usually saves very little even when it succeeds. And if the
target is absent it will always fail. That equality test is a very dubious
attempt at optimisation.
|
OK. 'Typically' was not the best way to express what I meant.
You have chosen an example where an equality condition actually
complicates the algorithm. In other algorithms where equality is
a requirement, not a complication, the analysis would yield different
results.
As I said above, the criteria used to design comparisons in
the STL are different from those used in the original C library.
Your example illustrates that clearly. However it is only part
of the answer to the original question. A proper answer, if there
is ever a proper answer to any 'why' question, requires a larger
perspective and a different point of view.
[email]max (AT) mtew (DOT) isa-geek.net[/email]
---
[ 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 ]
|
|
| Back to top |
|
|
Chris Jefferson
Guest
|
| Posted: Tue Mar 01, 2005 2:16 am Post subject: Re: Why the 2-way comparison instead of the C-style 3-way co |
|
|
Max T. Woodbury wrote:
| Quote: |
A well optimized C style comparison function would typically do one
comparison and then a sequence of two conditional branches to sort
out the three cases. In at least some cases no action is needed
because the result of a simple subtraction of two values has the
correct form.
The STL style comparisons have the advantage of being analytically
simpler and easier to document, but they are typically slower in
execution because they have to be called twice. That makes them
cheaper from the implementer's manager's point of view, but more
expensive from the user's point of view. The manager usually wins.
|
Having spent a reasonable amount of time with the STL algorithms, I
would say that in most of the algorithms, having a 3-way comparison
function wouldn't help in most cases. Also you are assuming that the STL
algorithms are only used on built-in types, remember lots of people use
STL algorithms on vectors of vectors, and such structures.
It comes down to the question of could you implement a more efficent
sort / lexicographic compare / etc. if you had a 3-way comparison
function. I reckon it would actually be slower, although I'd be more
than happy to be proved wrong.
Chris
---
[ 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 ]
|
|
| Back to top |
|
|
kuyper@wizard.net
Guest
|
| Posted: Thu Mar 03, 2005 6:08 am Post subject: Re: Why the 2-way comparison instead of the C-style 3-way co |
|
|
Max T. Woodbury wrote:
..
| Quote: | OK. 'Typically' was not the best way to express what I meant.
You have chosen an example where an equality condition actually
complicates the algorithm. In other algorithms where equality is
a requirement, not a complication, the analysis would yield different
results.
|
Would you care to identify an algorithm where, when the size of the
ranges operated on is large, the implementation would be significantly
speeded up by use of three-way comparisons rather than two-way, even if
the three-way one is 50% more expensive.? Make sure that you're
comparing with an algorithm actually optimized for use of the two-way
comparison.
I'm not saying there aren't any; but I suspect there are fewer of them
than you think.
---
[ 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 ]
|
|
| Back to top |
|
|
Dave Harris
Guest
|
| Posted: Thu Mar 03, 2005 6:26 am Post subject: Re: Why the 2-way comparison instead of the C-style 3-way co |
|
|
[email]max.teneyck.woodbury (AT) verizon (DOT) net[/email] ("Max T. Woodbury") wrote (abridged):
| Quote: | a C style comparison is typically done with a subtraction:
int cmpbyte( char a, char b) { return (int)a - b; }
That's how I think of it, ...
Actually it should be (int)b - a.
|
Not if you want to sort in ascending order. strcmp( a, b ) returns < 0 if
a should come before b, and similarly for the other cmp() functions. These
expressions:
cmp( a, b ) < 0
a - b < 0
a < b
should all yield the same result, ignoring overflow. Notice that a and b
always appear in the same order, and the "<" always points the same way.
| Quote: | ... but as an actual implementation it often doesn't work because
of overflow. If the arguments are ints or doubles, for example,
the difference between them may be too big to fit in an int.
You should also notice the cast to a wider type would avoid the
overflow issue unless char and int are the same size.
|
I did notice that, but I also noticed you said "typically", so I thought
you were suggesting it worked more generally than that. We agree it
doesn't work for int, and to my mind that makes it rather a special case.
| Quote: | For wider types you need to encode the result to avoid overflow,
but even that overhead is going to be swamped by the cost of doing
the function call. The fact that the STL allows inlining of
the comparison is in fact one of its more important attributes.
|
Indeed. And it means that the most efficient design for C may not be most
efficient for C++.
| Quote: | The STL comparison specification is based on extensibility and proof
of correctness criteria rather than on performance criteria.
|
I'm not convinced. I don't see why using less() is more extensible than
using cmp(). Nor do I see much difference in the proof of correctness,
whether we write "less(a,b)" or "cmp(a,b)<0". My impression is that
Stepanov was driven by a desire for performance (albeit a fairly academic
notion of it). That's why there is so much emphasis on compile-time
dispatch. I believe less() was chosen because it is faster, because it
does the minimum work needed by the algorithm.
| Quote: | You have chosen an example where an equality condition actually
complicates the algorithm. In other algorithms where equality is
a requirement, not a complication, the analysis would yield
different results.
|
Which algorithms?
Generally std algorithms which need equality use equality - for example,
std::find. Can you give some examples of std algorithms which are
significantly slower because they synthesise equality from a 3-way cmp() ?
(By "significantly", I mean they do it in their inner loop.)
-- Dave Harris, Nottingham, UK
---
[ 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 ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
