Boost::documentation == false
-
If it was just you, I would. But it's @Yamikuronue asking. I like her.
NO LONGER WELCOME HERE
-
-
No, the WTF is that what they say your predicate should look like is ALL LIES!!!
It's boost, therefore the documentation was an afterthought and the code is probably terrifying once you expand out all the templates.
-
"for each adjacent elements [x,y] the expression pred(x,y) is true"
Isn't that equally true for a strict ordering?
For a strict ordering, we have three principles it must satisfy:
The first is transitivity:
if x < y and y < z then x < z
, which means you can go ahead and only check x < y and y < z, which is what their algorithm does to simplify checking.Secondly, we have asymmetry:
if x < y then not y < x
, which makes their choice of which to test irrelevant.Finally, we have irreflexibility:
not x < x
, which your predicate of "less than or equal to" does not satisfy, breaking down the whole system.
-
Fuck you. When I post a WTF, I make sure I explain it.
-
If you look at documentation, you're right. If you look at the code, you've got it backwards. I don't blame you - documentation should be the place to check how the code works. If it doesn't match the behavior of code, why bother having documentation at all? Especially if it's Open Sores. That's the problem I was talking about.
The documentation was gibberish anyway. It wasn't even English. You seem to be ignoring that little fact. "is and only if" is not a valid construct.
-
Fuck you. When I post a WTF, I make sure I explain it.
True to form, you misread a post!
We were all effectively complaining that we didn't have telepathy and he should just explain hisself already.
-
Pfft. Reading's for nerds.
-
Isn't that equally true for a strict ordering?
Only if you have unique elements. Unless you assume that a sequence with duplicate elements can never be sorted.The documentation was gibberish anyway. It wasn't even English. You seem to be ignoring that little fact. "is and only if" is not a valid construct.
This is the least important thing in the whole topic. Probably whole Side Bar WTF section. Typos happen. They should've corrected it ages ago, but still. Documentation written by someone who can't write in English can still be usable. Documentation written by a liar cannot.
-
...says the guy complaining about typos.
-
The point is, if the dickhole who wrote that documentation can't be bothered to run it by another person to see if there's grammar errors, why would you assume he'd check the code to see whether it's actually accurate?
He might as well have a huge sign over his head reading, "I don't give a shit about the sloppy work I do!!!"
-
Only if you have unique elements
If
x < x
for an ordering operation<
, it's not a strict ordering. That's one of the requirements.Let's say you're ordering
twosome items: Apples (cost: 10) ,Oranges (cost 10), and Bananas (cost 11). The predicatex <y if x's cost is less than or equal to y's cost
is not a strict order, because it can be satisfied two ways:Apples, Oranges, Bananas
orOranges, Apples, Bananas
. This happens because the predicate does not satisfy the axiom of irreflexibility. Now, the predicatex < y if x's cost is less than y's cost, or x's cost is less than y's cost and x's unique ID is less than y's unique ID
is a strict ordering, because the fallback condition ensures there's only one way to order any given list.
-
Let's say you're ordering two items: Apples (cost: 10) ,Oranges (cost 10), and Bananas (cost 11).
@OffByOnethe fallback condition ensures there's only one way to order any given list
It also ensures there are no duplicate elements.Using your example: I want to order an apple, an apple, and a banana. What strict order predicate can I apply that would satisfy the condition of "for each adjacent elements [x,y] the expression pred(x,y) is true"? It's impossible, because - as you said, twice - strict ordering by definition requires the predicate to return false for equal elements.
-
@Yamikuronue said:
Let's say you're ordering two items: Apples (cost: 10) ,Oranges (cost 10), and Bananas (cost 11).
@OffByOneDoesn't the predicate apply to only two items? The fact that there are three means a couple of pairwise comparisons.
-
Doesn't the predicate apply to only two items?
I must say the grammar there is pretty ambiguous. Is it "ordering two items, each being either an apple, an orange, or a banana", or is it "ordering two items, one being all the apples, another being all the oranges, and the last being all the bananas"?
-
Mea culpa: I added a third item halfway through typing the example. It should read "ordering three items"
It also ensures there are no duplicate elements.
Yes, exactly. You can't order a set of items strictly if there are exact duplicates. You have to use a partial order in that case. In fact, in mathematical terms, you don't have a set at all: a set contains distinct items.
-
Is it "ordering two items, each being either an apple, an orange, or a banana", or is it "ordering two items, one being all the apples, another being all the oranges, and the last being all the bananas"?
I took it to be "ordering 3 items using the requisite number of pairwise orderings"
Let's say you're ordering two items:
I took that to mean the second instance of the word order in my rephrasing, with the first being implicit. You're taking it to mean the first.
-
The documentation explicitly states that weak ordering should be used.
And you gave it a strict ordering. Gee, I wonder why you got bad results...
-
I took it to be "ordering 3 items using the requisite number of pairwise orderings"
In the example, there are three items. An ordering is defined, with a predicate that compares two items to determine which is the "lesser" and which is the "greater" so that an ordering can be derived.
(This is why computer science degrees require math.)
-
It's been reported a while ago, by the way. Just didn't get much attention: https://svn.boost.org/trac/boost/ticket/10483
C++11's
is_sorted
is documented better, and it's pretty much the same implementation (also probably why Boost's is neglected), so you can use this as a reference: http://en.cppreference.com/w/cpp/algorithm/is_sorted / http://en.cppreference.com/w/cpp/concept/Compare
-
If we assume they were meant to be doing the same thing, then yes, they screwed up the implementation: they implemented a check for strict ordering, while
is_sorted
allows weak ordering.
-
C++ standard things all require strict weak ordering specifically. The implementation is correct (if
p(*next, *first)
will be true iff next element is less-than current element, i.e. when the ordering is broken).
-
-
It is a thing Basically the only predicates that will work are < and >.
-
Pfft. Reading's for nerds.
Hmm, I think I'll bookmark this post for use the next time you accuse me of not reading something.
-
I like how the onebox picture is of a special snowflake.
-
You can't order a set of items strictly if there are exact duplicates.
You can if you don't differentiate between duplicates. Otherwise, it wouldn't be possible to sort non-unique sequences, and I assure you it's being done.And you gave it a strict ordering. Gee, I wonder why you got bad results...
No, I gave it weak ordering. And the function didn't work!
-
Otherwise, it wouldn't be possible to sort non-unique sequences, and I assure you it's being done.
I'm not saying it's not possible to sort, I'm saying it's not possible to define a strict ordering according to the three principles I laid out.
-
No, I gave it weak ordering. And the function didn't work!
<
defines a strict order, as any mathematician will tell you
-
I'm not saying it's not possible to sort, I'm saying it's not possible to define a strict ordering according to the three principles I laid out.
You can define a total weak ordering using either the strict operator,
<
, or the non-strict operator,<=
, using the identities that:(a <= b) == !(b < a) (a < b) == !(b <= a)
Which you choose is a matter of convention. And the C++ convention is to use the strict one, that is
<
.The code is written for use with strict operator,
<
, as is the C++ convention and can be therefore considered correct.The documentation, however, is written as if a non-strict (
<=
) operator was expected. That is a bug. Nobody ever notices it, because everybody just assumes the standard definition of being sorted under the standard convention for defining orderings and that is what the code does.On a side note, while a total ordering can be defined using either strict or non-strict operator, a partial ordering can only be defined using non-strict operator, because you need both a ≤ b ∧
b ≤ a for equivalent and ¬(a ≤ b) ∧ ¬(b ≤ a) for incomparable.
-
I'm not saying it's not possible to sort, I'm saying it's not possible to define a strict ordering according to the three principles I laid out.
Oh? Let's see.Transitivity:
x < y ∧ y < z ⇒ x < z
Since for anyx, y
it's true thatx = y ⇒ ¬(x < y ∨ y < x)
, then in the equation above, none ofx, y, z
can be equal to any other - in other words, if we insist thatx = y ∨ y = z ∨ x = z
, thenx < y ∧ y < z
is false, so the whole implication is true.Asymmetry:
x < y ⇒ ¬(y < x)
Again, sincex = y ⇒ ¬(x < y)
, the left side is false, so the whole implication is true.Irreflexibility:
¬(x < x)
Well, sincex = x
...As you see, none of your three principles are broken if we have duplicate elements in our sequence.
< defines a strict order, as any mathematician will tell you
OK, you got me. But before, I had <= there, and it didn't work, even though the docs said it should.
-
// Less reports whether the element with // index i should sort before the element with index j.
-
OK, you got me. But before, I had <= there, and it didn't work, even though the docs said it should.
Really? You never thought to mention this in eighty posts?
-
As I said over and over again (which you seem to not bother reading in any of my posts),
#IT DOESN'T MATTER WHAT PREDICATE I USE, BECAUSE THE DOCUMENTATION AND IMPLEMENTATION DON'T MATCH EACH OTHER ANYWAY!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
-
Yeah, and it took you, what, 60 posts to explain that?
-
Yes, because you are an idiot who cannot read and cannot think.
-
I do admit I find it difficult to read text that doesn't exist
-
Also, the WTF stays the same regardless of predicate.
Whether I pulled it out of my arse or not doesn't matter, because WTF IS THERE FOR ANY PREDICATE. Literally any.
Yep, totally doesn't exist.
-
Ah yes, about 20 posts before you actually deigned to explain the
-
Actually, 20 posts after. But who cares about facts? It's all about ranting at the other person.
-
-
Sure, I totally made up those quotes where it says what you claim I didn't ever say.
-
It's all about ranting at the other person.
Duh. Why did you think we came here to read and think?
-
Sure, I totally made up those quotes where it says what you claim I didn't ever say.
I'm glad you agree
-
The bickering explodes across the screen!
-
Fuck, forgot about Poe's law.
-
Mug? Trophy?
CLOSED - DUPLICATE
in 3 more posts?
-
-
This post is deleted!
-
Also, the WTF stays the same regardless of predicate.
This tells us what the WTF is not, not what it is.Whether I pulled it out of my arse or not doesn't matter, because WTF IS THERE FOR ANY PREDICATE. Literally any.
This tells us what the WTF is not, not what it is.
THE DOCUMENTATION AND IMPLEMENTATION DON'T MATCH EACH OTHER
This tells us what the WTF is, not what it is not.