Re: [boost] Please don't define a fake "operator<"justfor orderedcontainers
----Original Message---- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Peter Dimov Sent: 11 July 2006 12:21 To: boost@lists.boost.org Subject: Re: [boost] Please don't define a fake "operator<"justfor orderedcontainers
Martin Bonner wrote:
----Original Message---- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Peter Dimov
Daryle Walker wrote:
[1] If you make a fake order for "std::complex<>", would you compare real components then imaginary components, or would you use magnitude then angle?
Real, then imaginary. Compare with:
Interesting. I would have chosen magnitude and then angle. Why components.
There are two reasons for that. First, composite types use lexicographical ordering by default, and std::complex is (de facto) a (real, imag) pair. Second, the magnitude/angle ordering has the property that if you have three numbers a, b, c, where a and b are very close to one another but not to c, it is possible to have a < c and c < b.
That is true for your comparison too. Consider a=-1, b=+1, c=10000i.
"If you make a FAKE order for std::string, would you compare left to right or right to left?"
I don't think that is a legitimate comparison. In my world view, strings have a natural order but complex numbers don't.
Possibly. So you define "fake" as "unnatural", and define "natural" as "feels natural to me". This approach can work but it's a bit subjective, isn't it? Yes.
Consider the progression:
complex<double> struct { double x, double y; } pair<double, double> tuple<double, double> vector<double> vector<char> string
If we take the "feel" of operator< out of the equation, where should we draw the line, and based on what?
complex<double> should not have an operator <() because it models a mathematical concept (complex number) for which "less than" does not make sense. struct, pair, and tuple should not have an operator < because they are essentially unordered collections of data (I know that the elements of pair are called first and second, but it seems to me that they are essentially arbitrary labels). vector is an interesting case. Some vectors are used to store lists of things (in which case ordering makes sense), but others are used to model things like mathematical vectors (in which case we are back to the complex case, and < does not make sense). string definitely should have operator <() because it models the real world concept (string of letters and other characters) for which "less than" definitely makes sense. -- Martin Bonner Martin.Bonner@Pitechnology.com Pi Technology, Milton Hall, Ely Road, Milton, Cambridge, CB4 6WZ, ENGLAND Tel: +44 (0)1223 203894
Martin Bonner wrote:
Consider the progression:
complex<double> struct { double x, double y; } pair<double, double> tuple<double, double> vector<double> vector<char> string
If we take the "feel" of operator< out of the equation, where should we draw the line, and based on what?
complex<double> should not have an operator <() because it models a mathematical concept (complex number) for which "less than" does not make sense.
How would you make a std::set of complex<>?
struct, pair, and tuple should not have an operator < because they are essentially unordered collections of data (I know that the elements of pair are called first and second, but it seems to me that they are essentially arbitrary labels).
How do you make a std::set of structs, pairs, or tuples?
vector is an interesting case. Some vectors are used to store lists of things (in which case ordering makes sense), but others are used to model things like mathematical vectors (in which case we are back to the complex case, and < does not make sense).
OK, do you define an operator< for vector or not? You don't know a priori what it will be used to hold.
string definitely should have operator <() because it models the real world concept (string of letters and other characters) for which "less than" definitely makes sense.
Still, there are several different "less than"s, all of which make sense. Based on the principle that operator< should be defined only if it's unique, string should not have operator<.
How do you make a std::set of structs, pairs, or tuples?
Maybe it was already said (didn't read the whole thread), but I thought I'd add my 0.02$. I think we should not define meaningless operator< for the structs/whatever, and let the user define one if he wants to use those structs in a set. We could maybe also do some template / macro fun to help them to define those ? Something like : #define DEF_OP_MIN(cont) bool cont::operator<(const cont& a, const cont&b) { return &a < &b; } Philippe
Philippe Vaucher wrote:
How do you make a std::set of structs, pairs, or tuples?
Maybe it was already said (didn't read the whole thread), but I thought I'd add my 0.02$.
I think we should not define meaningless operator< for the structs/whatever, and let the user define one if he wants to use those structs in a set.
That's the claim being made in this thread, true. The user can't necessarily define operator< for a foreign class because different users may have different ideas about what operator< should do, so their translation units won't be able to coexist. It is the responsibility of the author of the class to define its operator< (if there is one.) This leaves us with the option of defining and using custom comparators. So, if the author of pair<> does nothing, every time you need to make a set out of pair<X, Y>, you'll need to define a separate function object for it. This isn't very convenient; most of these function objects would end up being exact copies. So maybe the author of pair<> needs to provide a comparator. template<class P> struct pair_compare { bool operator()( P const & p ) const { // ??? } }; What would you put in the ??? portion? (Warning, this is a trap.)
On 7/11/06 8:50 AM, "Peter Dimov" <pdimov@mmltd.net> wrote:
Philippe Vaucher wrote:
How do you make a std::set of structs, pairs, or tuples?
Maybe it was already said (didn't read the whole thread), but I thought I'd add my 0.02$.
I think we should not define meaningless operator< for the structs/whatever, and let the user define one if he wants to use those structs in a set.
That's the claim being made in this thread, true.
The user can't necessarily define operator< for a foreign class because different users may have different ideas about what operator< should do, so their translation units won't be able to coexist. It is the responsibility of the author of the class to define its operator< (if there is one.)
This leaves us with the option of defining and using custom comparators. So, if the author of pair<> does nothing, every time you need to make a set out of pair<X, Y>, you'll need to define a separate function object for it. This isn't very convenient; most of these function objects would end up being exact copies.
When you mention "separate" function objects that will mostly be "exact copies," do you really mean objects, which are at the run-time level, or do you actually mean class (templates) at the compile-time level? You wrote the former, but I think you meant the latter. If you really did mean the former, then you're too late. It already happens. Each associative container object keeps a separate copy of its comparison function object, even if all those comparison objects are equivalent. Having separate comparison objects for each container object allows comparison classes with state that gives different comparison objects slightly different criteria (so two containers of the same type could sort differently). If you meant the latter, then if you like someone else's comparison object, then use his/her class instead of making a copy of it!
So maybe the author of pair<> needs to provide a comparator.
template<class P> struct pair_compare { bool operator()( P const & p ) const { // ??? } };
What would you put in the ??? portion? (Warning, this is a trap.)
Why is this a trap? Anyway, why should the author provide a comparator class after not providing an operator "<"? If the author couldn't decide on a standardized order, then any provided comparator class would use a criteria determined by fiat. You're back to providing your own class if you disagree with the author. I know it's inconvenient after using sets/maps with types that let you skip specifying the comparison parameter, but maybe there was a reason the author didn't provide a standardized order. -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
"Philippe Vaucher" <philippe.vaucher@gmail.com> writes:
How do you make a std::set of structs, pairs, or tuples?
Maybe it was already said (didn't read the whole thread), but I thought I'd add my 0.02$.
I think we should not define meaningless operator< for the structs/whatever, and let the user define one if he wants to use those structs in a set.
That would be exceedingly inconvenient. Having a builtin operator< for tuples is a huge win for users. -- Dave Abrahams Boost Consulting www.boost-consulting.com
On 7/11/06 11:51 AM, "David Abrahams" <dave@boost-consulting.com> wrote:
"Philippe Vaucher" <philippe.vaucher@gmail.com> writes:
How do you make a std::set of structs, pairs, or tuples?
Maybe it was already said (didn't read the whole thread), but I thought I'd add my 0.02$.
I think we should not define meaningless operator< for the structs/whatever, and let the user define one if he wants to use those structs in a set.
That would be exceedingly inconvenient. Having a builtin operator< for tuples is a huge win for users.
But should a convenient lie (providing fake operators "<" to use in sets & maps) trump an inconvenient truth (not providing such operators for types that model an unordered concept)? Convenient lies can suddenly turn inconvenient at the worst times.... -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
Daryle Walker <darylew@hotmail.com> writes:
On 7/11/06 11:51 AM, "David Abrahams" <dave@boost-consulting.com> wrote:
"Philippe Vaucher" <philippe.vaucher@gmail.com> writes:
How do you make a std::set of structs, pairs, or tuples?
Maybe it was already said (didn't read the whole thread), but I thought I'd add my 0.02$.
I think we should not define meaningless operator< for the structs/whatever, and let the user define one if he wants to use those structs in a set.
That would be exceedingly inconvenient. Having a builtin operator< for tuples is a huge win for users.
But should a convenient lie (providing fake operators "<" to use in sets & maps) trump an inconvenient truth (not providing such operators for types that model an unordered concept)? Convenient lies can suddenly turn inconvenient at the worst times....
shared_ptr's operator< is neither fake nor is it a lie. The same applies to operator< for tuples. They are both well-specified and consistent with the standard's expected requirements for operator<. Certainly tuple, a heterogeneous container, has an operator< that's consistent with the ones for std::vector and std::string. I request that you objectively justify your use of "fake" and "lie" here, or that you set aside the hyperbolic language and start dealing with facts. As far as I can tell these operators have _never_ been shown to cause any problems other than violating some peoples' sense of purity. -- Dave Abrahams Boost Consulting www.boost-consulting.com
On 7/19/06 8:02 AM, "David Abrahams" <dave@boost-consulting.com> wrote:
Daryle Walker <darylew@hotmail.com> writes:
On 7/11/06 11:51 AM, "David Abrahams" <dave@boost-consulting.com> wrote:
"Philippe Vaucher" <philippe.vaucher@gmail.com> writes: [SNIP]
I think we should not define meaningless operator< for the structs/whatever, and let the user define one if he wants to use those structs in a set.
That would be exceedingly inconvenient. Having a builtin operator< for tuples is a huge win for users.
But should a convenient lie (providing fake operators "<" to use in sets & maps) trump an inconvenient truth (not providing such operators for types that model an unordered concept)? Convenient lies can suddenly turn inconvenient at the worst times....
shared_ptr's operator< is neither fake nor is it a lie. The same applies to operator< for tuples. They are both well-specified and consistent with the standard's expected requirements for operator<. Certainly tuple, a heterogeneous container, has an operator< that's consistent with the ones for std::vector and std::string.
I request that you objectively justify your use of "fake" and "lie" here, or that you set aside the hyperbolic language and start dealing with facts.
The argument I'm making is between shortcuts versus modeling. Obviously the shared_ptr's operator "<" is consistent and provides (at least) a strict weak ordering, otherwise it wouldn't be useful at all. The question is if that operator is provided _solely_ for making a shortcut for programmers that don't want to bother explicitly specify a comparison function object for their sets and maps. Does the operator serve any use for the class outside of the shortcut? If there are other uses, then shared_ptr should have all the ordering operators defined, and not just "<". (Otherwise, users would have to contort their expressions to avoid ">", "<=", and ">=".) If there are no uses beside this shortcut, then the ordering operator should be removed since the class's model doesn't need it. (This is why std::complex<> doesn't have ordering operators.) We minimize confusion by not loading types with extra operations that the user doesn't need just so the programmer can have a shortcut. That's why I called these controversial operators "fake." Almost any type in C++ can have some default lexicographic order defined for it. (A major exception is types that are or contain unions.) That doesn't mean that said ordering has any significance for the type's abstract model. Ordering works mainly for models with a linear orientation. Should non-linear models (e.g. complex numbers) have ordering operators thrust upon them? For types like tuple, helpers for implementing other types, it's arguable whether or not it should have ordering operators. (If a tuple does have such operators, then a type that contains a tuple doesn't have to peek into the tuple's implementation if it wants to use tuple's piecewise lexicographic comparison for itself.) The standard templates give us the ability to override the default comparison routine. This arrangement allows comparisons of the same type with different criteria, and gives the user a way to enable comparison with unordered types. Said user could make a comparison function object use a lexicographic order of the main type's sub-objects, or s/he could use different priorities. If arbitrary ordering operators are added to a type with an unordered model, the user still has to check how said operators work to confirm if sorting will be made to need, and still has to define a new comparison function object class if the user disagrees with the ordering decisions. This makes no difference in computation (for user-defined types), only in the amount of typing.
As far as I can tell these operators have _never_ been shown to cause any problems other than violating some peoples' sense of purity.
The history of C++ has had "cute" ideas added, potentially popular, only to discover said ideas can backfire (e.g. std::vector<bool>). I want to keep us from adding similar mistakes; maintaining model consistency can help. -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
Daryle Walker <darylew@hotmail.com> writes:
would have to contort their expressions to avoid ">", "<=", and ">=".) If there are no uses beside this shortcut, then the ordering operator should be removed since the class's model doesn't need it.
An ordering property is extremely useful outside of set/map, and it becomes part of the class' model. If you remove ordering, you change the model. -- Dave Abrahams Boost Consulting www.boost-consulting.com
On 7/22/06 8:28 AM, "David Abrahams" <dave@boost-consulting.com> wrote:
Daryle Walker <darylew@hotmail.com> writes:
would have to contort their expressions to avoid ">", "<=", and ">=".) If there are no uses beside this shortcut, then the ordering operator should be removed since the class's model doesn't need it.
An ordering property is extremely useful outside of set/map, and it becomes part of the class' model. If you remove ordering, you change the model.
The "becomes part" sounds like the existence of an ordering property justifies its own existence. We need to take a step back and look at this type and what it's modeling from a higher perspective to avoid the circular argument. What uses besides set/map do you envision for ordering operators? And shouldn't _all_ the operators be defined then, not just "<"? (The docs at <http://www.boost.org/libs/smart_ptr/shared_ptr.htm> state that the full set of ordering operators is deliberately omitted.) -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
Daryle Walker <darylew@hotmail.com> writes:
On 7/22/06 8:28 AM, "David Abrahams" <dave@boost-consulting.com> wrote:
Daryle Walker <darylew@hotmail.com> writes:
would have to contort their expressions to avoid ">", "<=", and ">=".) If there are no uses beside this shortcut, then the ordering operator should be removed since the class's model doesn't need it.
An ordering property is extremely useful outside of set/map, and it becomes part of the class' model. If you remove ordering, you change the model.
The "becomes part" sounds like the existence of an ordering property justifies its own existence.
Usefulness justifies its existence.
We need to take a step back and look at this type and what it's modeling from a higher perspective to avoid the circular argument. What uses besides set/map do you envision for ordering operators?
Sort... Heapify... I'm sure I could think of others.
And shouldn't _all_ the operators be defined then, not just "<"? (The docs at <http://www.boost.org/libs/smart_ptr/shared_ptr.htm> state that the full set of ordering operators is deliberately omitted.)
I don't have an opinion about that. -- Dave Abrahams Boost Consulting www.boost-consulting.com
On 7/11/06, Philippe Vaucher <philippe.vaucher@gmail.com> wrote:
We could maybe also do some template / macro fun to help them to define those ? Something like :
#define DEF_OP_MIN(cont) bool cont::operator<(const cont& a, const cont&b) { return &a < &b; }
That's not a valid way to define a operator< that can be used to store objects in an associative container. It is (implicitly?) expected that if an object is copied constructed from another object, the original object and the copied object will have the same total ordering. I justify this statement by the fact that containers are required to have linear complexity for copy construction, which implies the elements have to be copy constructed and maintain the same order as the original elements. Kevin Spinar
On 7/11/06 8:37 AM, "Philippe Vaucher" <philippe.vaucher@gmail.com> wrote:
How do you make a std::set of structs, pairs, or tuples?
Maybe it was already said (didn't read the whole thread), but I thought I'd add my 0.02$.
I think we should not define meaningless operator< for the structs/whatever, and let the user define one if he wants to use those structs in a set.
We could maybe also do some template / macro fun to help them to define those ? Something like : [TRUNCATE the problematic example macro/function]
If the user has to define his/her own criteria, why can't they just encapsulate it in a custom class they use with a set? They don't have to define it as operator "<", which could have longer-reaching consequences. You do waste keystrokes, but there's no difference computationally (besides avoiding the ADL issues that operator "<" could bring). -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
participants (6)
-
Daryle Walker -
David Abrahams -
Kevin Spinar -
Martin Bonner -
Peter Dimov -
Philippe Vaucher