Discussion:
is `vector<T*> v = ~~~; std::sort(v.begin(), v.end();` UB?
(too old to reply)
Marc Mutz
2017-12-26 22:05:55 UTC
Permalink
Hi,

Absent an explicit `Compare` argument, `std::sort` is specified in
http://eel.is/c++draft/alg.sorting#1 as using `operator<`. For a
container of pointers, this would apply `operator<` to pointers that,
quite possibly, do not come from the same array. This is undefined
behaviour.

Do we need clarification in the standard that, for pointer
`value_type`s, `std::less` is used in lieu of `operator<`? Or do we
expect every user of `std::sort` & co to explicitly pass `std::less<T*>`
as the `Compare` predicate?

Thanks,
Marc
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Johnathon C
2017-12-27 17:21:39 UTC
Permalink
Passing any unrelated pointers to any range based function can potentially lead to undefined behavior.

The C++ standard explicitly uses the convention of inclusive, exclusive ranges with the exclusion being explicitly the element after the last in the range as the end. This is often noted as (] ranges.

The function overload that takes void* pointers follows the same convention as any other range based function, the beginning and end must be related in some way, and in this case must be from the same allocated block of memory (be it stack or free store).

The overloads that take iterators from the callee's perspective behave the same. They are just capable of iterating over elements of complex containers like lists that potentially have individually allocated elements. And this is why the iterator requirements are so important, as the same outcome can not be achieved with the exact same algorithim if the iterators are anything less than random access such as with a list.

It is the responsibility of the callee to understand these concepts. The standards intended auidence is compiler and standard library vendors, but is written so that any of us can consume it. It is, however, not the best tool by any means to learn the language.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Thiago Macieira
2017-12-27 20:03:08 UTC
Permalink
Post by Johnathon C
Passing any unrelated pointers to any range based function can potentially
lead to undefined behavior.
That's not what he's doing.

The range function in question (sort) is receiving two iterators pointing to
the same vector. So that's completely legal.

The issue is that the elements of that vector are not necessarily comparable
using the built-in operator<, but are if you use std::less.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
KD
2017-12-27 20:39:03 UTC
Permalink
How can a vector<T*> be comparable safely and correctly?

We have no idea what each T* was allocated from. It could be malloc, new,
placement new, or any system specific allocation function, or even be
pointing to the stack. We cant garentee that each T* is comparable by a <
b. There is no garentee, from the language its self, that the pointers are
related in any way other than the fact that they are presented to sort as a
std::vector<T*>::iterator which is, undeniably, an inplimentation specific
instanciated type.

I have a rather strong suspiscion what the gentleman needs is a
vector<vector<T>> because it appears he's trying to create a jagged array.
Any decent book on using the language and standard library addresses this
concept. In the case that is inaccurate then his vectors type needs to be
safe pointers if he specifically needs a pointer to his type, but vector
storage is allocated on the free store in the first place, and the
iterators are alreay designed to behave as pointers, in the case of vector
exactly so (random access), so why T* in the first place?

This is why I pointed out that the standard isnt the best place to learn
the language. The problem is not the standard.
Post by Johnathon C
Post by Johnathon C
Passing any unrelated pointers to any range based function can
potentially
Post by Johnathon C
lead to undefined behavior.
That's not what he's doing.
The range function in question (sort) is receiving two iterators pointing to
the same vector. So that's completely legal.
The issue is that the elements of that vector are not necessarily comparable
using the built-in operator<, but are if you use std::less.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to a topic in the
Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/
isocpp.org/d/topic/std-discussion/HPj2y9RLVG8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to
Visit this group at https://groups.google.com/a/isocpp.org/group/std-
discussion/.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Thiago Macieira
2017-12-27 21:06:08 UTC
Permalink
Post by KD
How can a vector<T*> be comparable safely and correctly?
Using std::less.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
KD
2017-12-27 21:53:26 UTC
Permalink
no.

There is no gurantee that his T* will correctly compare with std::less.

There is a gurantee that if an exception does not occur std::less will
return a comparable value, true or false.

The 1st T* could have a memory address of say 0xFFAA, the 2nd T* could have
a memory address of 0xAAAA but the OP could be wanting to compare the value
the T* points to, not the address of the value, and element 2 could have a
value greater than the 1st elememt but what is std::less going to say is
less? the 2nd because hes comparing pointers.

Each sequential call to an allocation function has no gurantee that it
will allocate from the same memory page, something thats system specific.

There certianly is no gurantee that each time the code is ran that it
will produce perdictable and consistant reaults. Remember his vector
elements are T* and the value it points to isnt allocated by the vector, as
it will only allocate T pointer storage not T storage so he's hopefully
doing that himself....or he's comparing garbage to begin with, which
certianly IS UB.

std::less will result in the comparison of a < b, and in the case of
pointers the value of the addresses, not the value of what they point to.

Uness all of his T*'s are allocated in 1 call to his allocation function
theres no gurantee that the addresses will even be sequential.

But really there is no way to know where his T* comes from and how to
handle it properly, hence, iterator requirements, again something thats
better to learn outside of the standard.

This is his whole problem. Results are not what he expects explicitly
because he doesn't understand how to use the language and the library. The
standard is not a good document to learn the language and library from
because its for experts and isnt designed to be consumed linerally. He's
not an expert or he'd already know to provide sort with a user defined
comparison function to handle his specific T* type and not thinking that
the *standard* needs to be updated to state that when using pointer types
to explicitly use std::less.
Post by Thiago Macieira
Post by KD
How can a vector<T*> be comparable safely and correctly?
Using std::less.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to a topic in the
Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/
isocpp.org/d/topic/std-discussion/HPj2y9RLVG8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to
Visit this group at https://groups.google.com/a/isocpp.org/group/std-
discussion/.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Brittany Friedman
2017-12-27 22:20:15 UTC
Permalink
KD, the original question being asked is in fact a valid question. Claiming
that someone doesn't know how to use the language and library based on this
question is unfair.

There are perfectly valid reasons for sorting a vector<T*> according to the
memory addresses of those pointers. One reason why someone might want to do
so is to create more coherent memory access patterns when iterating that
vector. I can think of many other reasons.
Post by KD
no.
There is no gurantee that his T* will correctly compare with std::less.
There is a gurantee that if an exception does not occur std::less will
return a comparable value, true or false.
The 1st T* could have a memory address of say 0xFFAA, the 2nd T* could
have a memory address of 0xAAAA but the OP could be wanting to compare the
value the T* points to, not the address of the value, and element 2 could
have a value greater than the 1st elememt but what is std::less going to
say is less? the 2nd because hes comparing pointers.
Each sequential call to an allocation function has no gurantee that
it will allocate from the same memory page, something thats system
specific.
There certianly is no gurantee that each time the code is ran that it
will produce perdictable and consistant reaults. Remember his vector
elements are T* and the value it points to isnt allocated by the vector, as
it will only allocate T pointer storage not T storage so he's hopefully
doing that himself....or he's comparing garbage to begin with, which
certianly IS UB.
std::less will result in the comparison of a < b, and in the case of
pointers the value of the addresses, not the value of what they point to.
Uness all of his T*'s are allocated in 1 call to his allocation function
theres no gurantee that the addresses will even be sequential.
But really there is no way to know where his T* comes from and how to
handle it properly, hence, iterator requirements, again something thats
better to learn outside of the standard.
This is his whole problem. Results are not what he expects explicitly
because he doesn't understand how to use the language and the library. The
standard is not a good document to learn the language and library from
because its for experts and isnt designed to be consumed linerally. He's
not an expert or he'd already know to provide sort with a user defined
comparison function to handle his specific T* type and not thinking that
the *standard* needs to be updated to state that when using pointer types
to explicitly use std::less.
Post by Thiago Macieira
Post by KD
How can a vector<T*> be comparable safely and correctly?
Using std::less.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to a topic in the
Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/is
ocpp.org/d/topic/std-discussion/HPj2y9RLVG8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to
Visit this group at https://groups.google.com/a/is
ocpp.org/group/std-discussion/.
--
---
You received this message because you are subscribed to the Google Groups
"ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an
Visit this group at https://groups.google.com/a/isocpp.org/group/std-
discussion/.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
KD
2017-12-27 23:54:28 UTC
Permalink
Brittany,
Thats technically impossible for the standard to do.

Each operating system has its own underlying memory allocation sceme
that the standard has to abide by, see the definiton for the char type and
how its specifically worded to gurantee us a specific bit width of the
languages built in types and how the rest of the built in types are
defined. The operating systems are bound by the hardware they are running
on. Not all systems have CPU registers that are 4, 8, 16, 32, or 64 bits
wide. Some systems are 31 bits wide (IBM big iron).

Theres also the whole problem of virtual memory. On x86/x64 systems
that comes up at run level 2 ( on the cpu not the OS). Some systems that
C++ must run on do not employ virtual memory due to hardware constraints
(embedded). Theres no way to gurantee memory addresses we are given by
allocation functions are physically coherent based on address alone. We
dont control how the underlying system allocates memory.




On Dec 27, 2017 4:20 PM, "Brittany Friedman" <***@gmail.com> wrote:

KD, the original question being asked is in fact a valid question. Claiming
that someone doesn't know how to use the language and library based on this
question is unfair.

There are perfectly valid reasons for sorting a vector<T*> according to the
memory addresses of those pointers. One reason why someone might want to do
so is to create more coherent memory access patterns when iterating that
vector. I can think of many other reasons.
Post by KD
no.
There is no gurantee that his T* will correctly compare with std::less.
There is a gurantee that if an exception does not occur std::less will
return a comparable value, true or false.
The 1st T* could have a memory address of say 0xFFAA, the 2nd T* could
have a memory address of 0xAAAA but the OP could be wanting to compare the
value the T* points to, not the address of the value, and element 2 could
have a value greater than the 1st elememt but what is std::less going to
say is less? the 2nd because hes comparing pointers.
Each sequential call to an allocation function has no gurantee that
it will allocate from the same memory page, something thats system
specific.
There certianly is no gurantee that each time the code is ran that it
will produce perdictable and consistant reaults. Remember his vector
elements are T* and the value it points to isnt allocated by the vector, as
it will only allocate T pointer storage not T storage so he's hopefully
doing that himself....or he's comparing garbage to begin with, which
certianly IS UB.
std::less will result in the comparison of a < b, and in the case of
pointers the value of the addresses, not the value of what they point to.
Uness all of his T*'s are allocated in 1 call to his allocation function
theres no gurantee that the addresses will even be sequential.
But really there is no way to know where his T* comes from and how to
handle it properly, hence, iterator requirements, again something thats
better to learn outside of the standard.
This is his whole problem. Results are not what he expects explicitly
because he doesn't understand how to use the language and the library. The
standard is not a good document to learn the language and library from
because its for experts and isnt designed to be consumed linerally. He's
not an expert or he'd already know to provide sort with a user defined
comparison function to handle his specific T* type and not thinking that
the *standard* needs to be updated to state that when using pointer types
to explicitly use std::less.
Post by Thiago Macieira
Post by KD
How can a vector<T*> be comparable safely and correctly?
Using std::less.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to a topic in the
Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/is
ocpp.org/d/topic/std-discussion/HPj2y9RLVG8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to
Visit this group at https://groups.google.com/a/is
ocpp.org/group/std-discussion/.
--
---
You received this message because you are subscribed to the Google Groups
"ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an
Visit this group at https://groups.google.com/a/is
ocpp.org/group/std-discussion/.
--
---
You received this message because you are subscribed to a topic in the
Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/
isocpp.org/d/topic/std-discussion/HPj2y9RLVG8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to
std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-
discussion/.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Marc Mutz
2017-12-27 22:17:56 UTC
Permalink
Hi,

When the gentleman is done misunderstanding the OP and going off on
tangents, we may come back to the topic at hand, which is: is it ok that
the default comparator of std::sort invokes UB when sorting a range of
pointers? To compare, std::set _does_ use std::less to compare the keys.
Thus,

std::set<Object*> set(r.begin(), r.end());

works while the often preferable

std::vector<Object*> vec(r.begin(), r.end());
std::sort(vec.begin(), vec.end()); // UB here
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

does not.

I think this is a usability issue that should be fixed. The question,
imo, is only whether sort() can be re-formulated to call std::less for
all value-types or we need to restrict it to pointers.

Thanks,
Marc
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
KD
2017-12-27 22:53:25 UTC
Permalink
Mark,
1) set's keys are a value type, not a pointer.

2) a vector is an automatically
expandable array which his vector<T*> is conceivably a T**.

3) I never misunderstood the OP, but you seem to misunderstand
vectors, and perhaps pointers, and certianly me.

4) when you compare pointers your comparing memory addresses, that
is, unless you dereference the pointer. In the case of T** a single
dereference yeilds a T*.

5) A Set isnt a Vector, and a Set was recently added to the standard
to address the specific needs that pertain to the qualities of a set, which
is a mathematical concept. A vector is an expandable array, that expands on
push_ back, or emplace_back at an implimentation defined rate as to
amortize the cost of reallocation when its storage capasity is reached.
This isnt a usability issue its a lack of knowledge issue.
Post by Marc Mutz
Hi,
When the gentleman is done misunderstanding the OP and going off on
tangents, we may come back to the topic at hand, which is: is it ok that
the default comparator of std::sort invokes UB when sorting a range of
pointers? To compare, std::set _does_ use std::less to compare the keys.
Thus,
std::set<Object*> set(r.begin(), r.end());
works while the often preferable
std::vector<Object*> vec(r.begin(), r.end());
std::sort(vec.begin(), vec.end()); // UB here
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
does not.
I think this is a usability issue that should be fixed. The question, imo,
is only whether sort() can be re-formulated to call std::less for all
value-types or we need to restrict it to pointers.
Thanks,
Marc
--
--- You received this message because you are subscribed to a topic in the
Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/is
ocpp.org/d/topic/std-discussion/HPj2y9RLVG8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to
Visit this group at https://groups.google.com/a/is
ocpp.org/group/std-discussion/.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
T. C.
2017-12-28 03:34:12 UTC
Permalink
Ranges will fix this; ranges::sort always take a comparator, defaulted to
ranges::less<>{}, which has similar "magic" wording w/r/t pointer
comparisons.

I'm not sure it's worth proposing separately.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Marc Mutz
2017-12-28 10:42:38 UTC
Permalink
Post by T. C.
Ranges will fix this; ranges::sort always take a comparator, defaulted
to ranges::less<>{}, which has similar "magic" wording w/r/t pointer
comparisons.
I'm not sure it's worth proposing separately.
There will be another decade until people move to Ranges TS wholesale.
If submitted as a DR, we might change existing standards retroactively,
thus help a whole lot of people who don't even know they have a problem.

Thanks,
Marc
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Nicol Bolas
2017-12-27 22:44:45 UTC
Permalink
Post by KD
no.
There is no gurantee that his T* will correctly compare with std::less.
There is a gurantee that if an exception does not occur std::less will
return a comparable value, true or false.
For templates less, greater, less_equal, and greater_equal, the
specializations for any pointer type yield a *strict total order* that is
consistent among those specializations and is also consistent with the
partial order imposed by the built-in operators < , > , <= , >= .

Emphasis added. So it does not merely return a comparable value; it
specifies that there will be a strict order of all pointer values, one that
is consistent with the built-in operators but also creates a total order.

The 1st T* could have a memory address of say 0xFFAA, the 2nd T* could have
Post by KD
a memory address of 0xAAAA but the OP could be wanting to compare the value
the T* points to, not the address of the value, and element 2 could have a
value greater than the 1st elememt but what is std::less going to say is
less? the 2nd because hes comparing pointers.
If the OP wanted to do that, then they would have passed a comparison
functor that would actually dereference the pointers and compare them. The
OP clearly wants to compare the pointer values, not what they point to.

Each sequential call to an allocation function has no gurantee that it
Post by KD
will allocate from the same memory page, something thats system specific.
There certianly is no gurantee that each time the code is ran that it
will produce perdictable and consistant reaults.
Certainly. But this is also irrelevant. What matters is that there is* an
order*; it doesn't necessarily need to be a consistent one. If you're
sorting a vector so that you can later search for a particular pointer
value in log(n) time, you* don't care* what the order is, so long as it is
a strict, weak ordering.

std::less gives you that.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
KD
2017-12-28 00:11:47 UTC
Permalink
bool std::less.

BOOL

strict weak ordering yes! The same as <.

theres no gurantee that multiple calls to an allocation function will
result in sequential addresses such as in the case of a *jagged array*
which a vactor<T*> is.

std::less will yeild an ordering of which pointer has a lower numerical
value. that may or may not be the first or second allocation, or even the
third. Theres no way to gurentee any specific behavior other than pointer
ordering. Because of things like virtual memory theres not even a gurantee
that a pointer ordering would reduce cache hits.

If thats what the OP wanted he wouldent have posted anything as std::less
isnt needed to accomplish that. sort will do that on its own with a jagged
array. he posted because his results arent what he expects and thats why he
thinks hes experiencing UB when he's not.

Again. The problem isnt the standard.
Post by Nicol Bolas
Post by KD
no.
There is no gurantee that his T* will correctly compare with std::less.
There is a gurantee that if an exception does not occur std::less will
return a comparable value, true or false.
For templates less, greater, less_equal, and greater_equal, the
specializations for any pointer type yield a *strict total order* that is
consistent among those specializations and is also consistent with the
partial order imposed by the built-in operators < , > , <= , >= .
Emphasis added. So it does not merely return a comparable value; it
specifies that there will be a strict order of all pointer values, one that
is consistent with the built-in operators but also creates a total order.
The 1st T* could have a memory address of say 0xFFAA, the 2nd T* could
Post by KD
have a memory address of 0xAAAA but the OP could be wanting to compare the
value the T* points to, not the address of the value, and element 2 could
have a value greater than the 1st elememt but what is std::less going to
say is less? the 2nd because hes comparing pointers.
If the OP wanted to do that, then they would have passed a comparison
functor that would actually dereference the pointers and compare them. The
OP clearly wants to compare the pointer values, not what they point to.
Each sequential call to an allocation function has no gurantee that
Post by KD
it will allocate from the same memory page, something thats system
specific.
There certianly is no gurantee that each time the code is ran that
it will produce perdictable and consistant reaults.
Certainly. But this is also irrelevant. What matters is that there is* an
order*; it doesn't necessarily need to be a consistent one. If you're
sorting a vector so that you can later search for a particular pointer
value in log(n) time, you* don't care* what the order is, so long as it
is a strict, weak ordering.
std::less gives you that.
Post by KD
--
---
You received this message because you are subscribed to a topic in the
Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/
isocpp.org/d/topic/std-discussion/HPj2y9RLVG8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to
Visit this group at https://groups.google.com/a/isocpp.org/group/std-
discussion/.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Nicol Bolas
2017-12-28 01:09:21 UTC
Permalink
Post by KD
bool std::less.
BOOL
strict weak ordering yes! The same as <.
No, strict* TOTAL* ordering. And therefore* not* the same thing as <. The
standard very clearly says that `std::less<T*>` imposes a strict total
ordering on *all* `T*` values, not just ones in the same array.
Post by KD
theres no gurantee that multiple calls to an allocation function will
result in sequential addresses such as in the case of a *jagged array*
which a vactor<T*> is.
Nobody suggested that it will, and `std::less` does not require that it
does.
Post by KD
std::less will yeild an ordering of which pointer has a lower numerical
value. that may or may not be the first or second allocation, or even the
third. Theres no way to gurentee any specific behavior other than pointer
ordering. Because of things like virtual memory theres not even a gurantee
that a pointer ordering would reduce cache hits.
... what does cache hits have to do with anything?

The only guarantee of `std::less<T*>` is that, for any two unequal `T*`s,
one is strictly less than the other. That's it, and that's all that's being
asked of it. It doesn't matter if the first allocation is lower than the
second. The specification does not define what the order is, but the
specification does require that there* be an ordering*. That ordering does
not have to be consistent from execution to execution, but it must
certainly exist.

If thats what the OP wanted he wouldent have posted anything as std::less
Post by KD
isnt needed to accomplish that. sort will do that on its own with a jagged
array. he posted because his results arent what he expects and thats why he
thinks hes experiencing UB when he's not.
Again. The problem isnt the standard.
The standard does exactly what we've said. What the OP wants is for
`std::sort(T*, T*)` to be equivalent to `std::sort(T*, T*, std::less<T*>)`.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
KD
2017-12-28 02:13:06 UTC
Permalink
What does std::less. have anything to do with the ordering of a
vector<T*> passed to a functuon that defaults to < comparison of T*? The
resulting order will be the same regardless if the op uses std::less or not.

The OPs results were not what he expected. None of you have suggested
what he needs to do to remidy his problem and I at least guided him on the
right path.

When you can specifically tell me anything that points to an issue
with how std::vector is defined, std::less is defined, and srd::sort is
defined that do not work as they should then we all should be speaking up.
But this isnt a problem with the standard at all.

std::less possible implementation:

namespace std {
template <typename T>
bool less(T a, T b) {
return a < b;
}
}
Sure looks identical in behavior to < to me.

Bark all you want to about it. The standard is not the issue with the
OP's problem and its obvious every person that's replied knows it.

Your attemts to pick apart anything Ive stated is hilarious. And sir,
if you have to ask me what cache hits have to do with anything you are not
following along, you might have missed something else to bark about.

So anyone care to take a deep breath, calm down, and explain to the OP
how jagged arrays work?

Theres books, online forums (not unlike this one ), and tutorials
that can help the OP out and all you all have done is bicker with me.

Nicol Bolas, I'm going to pretend you understand english better than you do
and you can be assured that I've a better understanding of how pointers,
allocations, systems, and C++ works than what you've presumed that I
possess.

std::sort<T*>(T*, T*) results in the pointers ordered by <.

std::sort<T*>(T*,T*,std::less<T*>) results in the pointers ourdered by,
drum roll, <.

I really dont think its necessairy to get the point across that if your
comparing memory addresses it dosent matter if they are sequential or not
and ive stated that how many times? What matters is what the OP expected
and ordered pointers did not give him the result he expected.

Really, you think that the language's less than comparison is somehow less
capable than a function written in the language? Brilliantly moronic
argument. Im now worried about more than just your grasp of my language.

std::less will only order two elements thats passed to it.

It returns a bool that indicates if the first paremeter is less than the
second.

std::sort calls its comparison on all the elements passed to it.

std::sort provides the total ordering of all the elements passed to it, not
std::less.

The standard is not the problem, My posts arent the problem, and the
standard does exactly what we all have said.

So how does jmkesson translate to Nicol Bolas anyway, a pseudo name?
Post by KD
bool std::less.
BOOL
strict weak ordering yes! The same as <.
No, strict* TOTAL* ordering. And therefore* not* the same thing as <. The
standard very clearly says that `std::less<T*>` imposes a strict total
ordering on *all* `T*` values, not just ones in the same array.
Post by KD
theres no gurantee that multiple calls to an allocation function will
result in sequential addresses such as in the case of a *jagged array*
which a vactor<T*> is.
Nobody suggested that it will, and `std::less` does not require that it
does.
Post by KD
std::less will yeild an ordering of which pointer has a lower numerical
value. that may or may not be the first or second allocation, or even the
third. Theres no way to gurentee any specific behavior other than pointer
ordering. Because of things like virtual memory theres not even a gurantee
that a pointer ordering would reduce cache hits.
... what does cache hits have to do with anything?

The only guarantee of `std::less<T*>` is that, for any two unequal `T*`s,
one is strictly less than the other. That's it, and that's all that's being
asked of it. It doesn't matter if the first allocation is lower than the
second. The specification does not define what the order is, but the
specification does require that there* be an ordering*. That ordering does
not have to be consistent from execution to execution, but it must
certainly exist.

If thats what the OP wanted he wouldent have posted anything as std::less
Post by KD
isnt needed to accomplish that. sort will do that on its own with a jagged
array. he posted because his results arent what he expects and thats why he
thinks hes experiencing UB when he's not.
Again. The problem isnt the standard.
The standard does exactly what we've said. What the OP wants is for
`std::sort(T*, T*)` to be equivalent to `std::sort(T*, T*, std::less<T*>)`.
Post by KD
--
---
You received this message because you are subscribed to a topic in the
Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/
isocpp.org/d/topic/std-discussion/HPj2y9RLVG8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to
std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-
discussion/.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Thiago Macieira
2017-12-28 02:34:07 UTC
Permalink
Post by KD
What does std::less. have anything to do with the ordering of a
vector<T*> passed to a functuon that defaults to < comparison of T*? The
resulting order will be the same regardless if the op uses std::less or not.
That's where you're wrong.

op< is only defined for pointers of the same array. You cannot compare two
pointers if they come from different objects, that's UB.

std::less is defined for any pointer of the same type.
Post by KD
The OPs results were not what he expected. None of you have suggested
what he needs to do to remidy his problem and I at least guided him on the
right path.
No, you've ventured down a completely irrelevant path by not addressing the
stated problem.
Post by KD
When you can specifically tell me anything that points to an issue
with how std::vector is defined, std::less is defined, and srd::sort is
defined that do not work as they should then we all should be speaking up.
But this isnt a problem with the standard at all.
The OP did. std::sort(RandomIterator, RandomIterator is defined to use
operator< to compare elements. See
http://en.cppreference.com/w/cpp/algorithm/sort

That means if the range contains pointers from different objects, the sort
function with two arguments is UB, while passing an extra argument with
std::less makes it completely defined.

The OP wants it to be defined to use std::less if RandomIterator is a
pointer. That's a completely reasonable request.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
KD
2017-12-28 02:42:44 UTC
Permalink
And you think C++'s a < b is less capable of comparing pointers than
std::less when std::less is implmented using C++'s <?

Im not wrong.

Sense when does two pointer memory addresses have to come from the same
allocation call for C++ to compare thier memory address values?

Theres no requirement that two pointers have to be in the same array for
the language to compare them at all. Where did you get this nonsense?

The problem is not the standard. The problem isnt my post.
Post by Thiago Macieira
Post by KD
What does std::less. have anything to do with the ordering of a
vector<T*> passed to a functuon that defaults to < comparison of T*? The
resulting order will be the same regardless if the op uses std::less or
not.
That's where you're wrong.
op< is only defined for pointers of the same array. You cannot compare two
pointers if they come from different objects, that's UB.
std::less is defined for any pointer of the same type.
Post by KD
The OPs results were not what he expected. None of you have
suggested
Post by KD
what he needs to do to remidy his problem and I at least guided him on
the
Post by KD
right path.
No, you've ventured down a completely irrelevant path by not addressing the
stated problem.
Post by KD
When you can specifically tell me anything that points to an issue
with how std::vector is defined, std::less is defined, and srd::sort is
defined that do not work as they should then we all should be speaking
up.
Post by KD
But this isnt a problem with the standard at all.
The OP did. std::sort(RandomIterator, RandomIterator is defined to use
operator< to compare elements. See
http://en.cppreference.com/w/cpp/algorithm/sort
That means if the range contains pointers from different objects, the sort
function with two arguments is UB, while passing an extra argument with
std::less makes it completely defined.
The OP wants it to be defined to use std::less if RandomIterator is a
pointer. That's a completely reasonable request.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to a topic in the
Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/
isocpp.org/d/topic/std-discussion/HPj2y9RLVG8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to
Visit this group at https://groups.google.com/a/isocpp.org/group/std-
discussion/.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Nicol Bolas
2017-12-28 02:52:31 UTC
Permalink
Post by KD
And you think C++'s a < b is less capable of comparing pointers than
std::less when std::less is implmented using C++'s <?
Im not wrong.
Then prove it. He quoted the specification; that's the only authority that
matters on this forum. If he's wrong, you should be able to go to the
specification and find the place that says that they're identical.

Until then, you are nothing but words.

Sense when does two pointer memory addresses have to come from the same
Post by KD
allocation call for C++ to compare thier memory address values?
Theres no requirement that two pointers have to be in the same array for
the language to compare them at all. Where did you get this nonsense?
We're getting it from the standard, right where we said.

In this forum, the only thing that matters is the standard. It backs up
what we have said, and it contradicts what you have said.

It doesn't matter how you *think* the language works; the standard defines
how it actually does work. C++ doesn't work the way you think it does. This
happens (a lot); best deal with it.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
KD
2017-12-28 03:09:47 UTC
Permalink
Your the one in need of the brown paper bag. Im quite cozy if I do say
so myself. Ive managed to enrage a community with nothing but two thumbs
and a cellphone all because every thing I've stated is fact. Twist it all
you want. Ive nothing new to add to this because frankly my teenage son can
present a better debate than you.

And now we all know why the standard didnt progress for so many years.
When a post better suited for another site causes this much floundering
debate over a well thought out and kind reaponse its a little beyond
comical that its garnered this vehemenant of a social response.

I think the most hilarious part was people implying that some
comparison function is more capable of comparing pointers than the
languages built in comparison.

Ive no doubt that was painful for some of you to type. If it wasn't it
should have been. That was just multiple levels of wrong.

So punch angrily away on the keyboard while copying and paisting my
text into your post. Angry little group members do you really think Im
going to budge? Im from the southern portion of the USA. 'Merica. We dont
budge.

The standard isnt the OP's problem.

You might want to see an anger management theripist though before you
die of a heart attack over a group discussion. See, I in no way dislike any
of you. I dont know any of you TO dislike you. But Im genuially concerned
that your hurting yourself over nothing. So take that bag and breathe..just
breathe. It'll be ok.

But the standard isnt the OP's problem.
Post by KD
And you think C++'s a < b is less capable of comparing pointers than
std::less when std::less is implmented using C++'s <?
Im not wrong.
Sense when does two pointer memory addresses have to come from the same
allocation call for C++ to compare thier memory address values?
Theres no requirement that two pointers have to be in the same array for
the language to compare them at all. Where did you get this nonsense?
The problem is not the standard. The problem isnt my post.
Post by Thiago Macieira
Post by KD
What does std::less. have anything to do with the ordering of a
vector<T*> passed to a functuon that defaults to < comparison of T*? The
resulting order will be the same regardless if the op uses std::less or
not.
That's where you're wrong.
op< is only defined for pointers of the same array. You cannot compare two
pointers if they come from different objects, that's UB.
std::less is defined for any pointer of the same type.
Post by KD
The OPs results were not what he expected. None of you have
suggested
Post by KD
what he needs to do to remidy his problem and I at least guided him on
the
Post by KD
right path.
No, you've ventured down a completely irrelevant path by not addressing the
stated problem.
Post by KD
When you can specifically tell me anything that points to an issue
with how std::vector is defined, std::less is defined, and srd::sort is
defined that do not work as they should then we all should be speaking
up.
Post by KD
But this isnt a problem with the standard at all.
The OP did. std::sort(RandomIterator, RandomIterator is defined to use
operator< to compare elements. See
http://en.cppreference.com/w/cpp/algorithm/sort
That means if the range contains pointers from different objects, the sort
function with two arguments is UB, while passing an extra argument with
std::less makes it completely defined.
The OP wants it to be defined to use std::less if RandomIterator is a
pointer. That's a completely reasonable request.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to a topic in the
Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/is
ocpp.org/d/topic/std-discussion/HPj2y9RLVG8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to
Visit this group at https://groups.google.com/a/is
ocpp.org/group/std-discussion/.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Michael Kilburn
2017-12-28 03:30:28 UTC
Permalink
I think KD is (quite brilliantly) trolling you :-)
Post by KD
Your the one in need of the brown paper bag. Im quite cozy if I do
say so myself. Ive managed to enrage a community with nothing but two
thumbs and a cellphone all because every thing I've stated is fact. Twist
it all you want. Ive nothing new to add to this because frankly my teenage
son can present a better debate than you.
And now we all know why the standard didnt progress for so many
years. When a post better suited for another site causes this much
floundering debate over a well thought out and kind reaponse its a little
beyond comical that its garnered this vehemenant of a social response.
I think the most hilarious part was people implying that some
comparison function is more capable of comparing pointers than the
languages built in comparison.
Ive no doubt that was painful for some of you to type. If it wasn't
it should have been. That was just multiple levels of wrong.
So punch angrily away on the keyboard while copying and paisting my
text into your post. Angry little group members do you really think Im
going to budge? Im from the southern portion of the USA. 'Merica. We dont
budge.
The standard isnt the OP's problem.
You might want to see an anger management theripist though before you
die of a heart attack over a group discussion. See, I in no way dislike any
of you. I dont know any of you TO dislike you. But Im genuially concerned
that your hurting yourself over nothing. So take that bag and breathe..just
breathe. It'll be ok.
But the standard isnt the OP's problem.
Post by KD
And you think C++'s a < b is less capable of comparing pointers than
std::less when std::less is implmented using C++'s <?
Im not wrong.
Sense when does two pointer memory addresses have to come from the same
allocation call for C++ to compare thier memory address values?
Theres no requirement that two pointers have to be in the same array for
the language to compare them at all. Where did you get this nonsense?
The problem is not the standard. The problem isnt my post.
Post by KD
Post by KD
What does std::less. have anything to do with the ordering of a
vector<T*> passed to a functuon that defaults to < comparison of T*?
The
Post by KD
resulting order will be the same regardless if the op uses std::less
or not.
That's where you're wrong.
op< is only defined for pointers of the same array. You cannot compare two
pointers if they come from different objects, that's UB.
std::less is defined for any pointer of the same type.
Post by KD
The OPs results were not what he expected. None of you have
suggested
Post by KD
what he needs to do to remidy his problem and I at least guided him on
the
Post by KD
right path.
No, you've ventured down a completely irrelevant path by not addressing the
stated problem.
Post by KD
When you can specifically tell me anything that points to an issue
with how std::vector is defined, std::less is defined, and srd::sort is
defined that do not work as they should then we all should be speaking
up.
Post by KD
But this isnt a problem with the standard at all.
The OP did. std::sort(RandomIterator, RandomIterator is defined to use
operator< to compare elements. See
http://en.cppreference.com/w/cpp/algorithm/sort
That means if the range contains pointers from different objects, the sort
function with two arguments is UB, while passing an extra argument with
std::less makes it completely defined.
The OP wants it to be defined to use std::less if RandomIterator is a
pointer. That's a completely reasonable request.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to a topic in the
Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/is
ocpp.org/d/topic/std-discussion/HPj2y9RLVG8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to
Visit this group at https://groups.google.com/a/is
ocpp.org/group/std-discussion/.
--
---
You received this message because you are subscribed to the Google Groups
"ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an
Visit this group at https://groups.google.com/a/isocpp.org/group/std-
discussion/.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Thiago Macieira
2017-12-28 10:40:15 UTC
Permalink
Post by Michael Kilburn
I think KD is (quite brilliantly) trolling you
I think so too. I'll just ignore his unwelcome and off-topic contributions to
the discussion.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Nathan Ernst
2017-12-28 02:49:17 UTC
Permalink
I'm sorry - I don't mean to be pedantic, but when you say:

op< is only defined for pointers of the same array. You cannot compare
two pointers
Post by Thiago Macieira
if they come from different objects, that's UB
I don't think this is entirely accurate. Say I have:

class Foo;

Foo f1[3];
Foo f2[3];

Unless I am sorely mistaken, comparing f1 < f2 is entirely well defined
(albeit, may not give the desired/intended outcome).

What I think you are intending to state is in the case we have:

class Foo;
class Bar;
Foo f1[3];
Bar b1[3];

f1 < b1 may be UB.

Am I misunderstanding a subtlety in the spec?

Regards,
Nate
Post by Thiago Macieira
Post by KD
What does std::less. have anything to do with the ordering of a
vector<T*> passed to a functuon that defaults to < comparison of T*? The
resulting order will be the same regardless if the op uses std::less or
not.
That's where you're wrong.
op< is only defined for pointers of the same array. You cannot compare two
pointers if they come from different objects, that's UB.
std::less is defined for any pointer of the same type.
Post by KD
The OPs results were not what he expected. None of you have
suggested
Post by KD
what he needs to do to remidy his problem and I at least guided him on
the
Post by KD
right path.
No, you've ventured down a completely irrelevant path by not addressing the
stated problem.
Post by KD
When you can specifically tell me anything that points to an issue
with how std::vector is defined, std::less is defined, and srd::sort is
defined that do not work as they should then we all should be speaking
up.
Post by KD
But this isnt a problem with the standard at all.
The OP did. std::sort(RandomIterator, RandomIterator is defined to use
operator< to compare elements. See
http://en.cppreference.com/w/cpp/algorithm/sort
That means if the range contains pointers from different objects, the sort
function with two arguments is UB, while passing an extra argument with
std::less makes it completely defined.
The OP wants it to be defined to use std::less if RandomIterator is a
pointer. That's a completely reasonable request.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to the Google Groups
"ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an
Visit this group at https://groups.google.com/a/isocpp.org/group/std-
discussion/.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Nicol Bolas
2017-12-28 02:58:53 UTC
Permalink
op< is only defined for pointers of the same array. You cannot compare two pointers
Post by Thiago Macieira
if they come from different objects, that's UB
class Foo;
Foo f1[3];
Foo f2[3];
Unless I am sorely mistaken, comparing f1 < f2 is entirely well defined
(albeit, may not give the desired/intended outcome).
class Foo;
class Bar;
Foo f1[3];
Bar b1[3];
f1 < b1 may be UB.
Am I misunderstanding a subtlety in the spec?
No, the spec means exactly what he said. Read what the specification says:
<http://www.google.com/url?q=http%3A%2F%2Feel.is%2Fc%2B%2Bdraft%2Fexpr.rel&sa=D&sntz=1&usg=AFQjCNEqmgVqSkUb8HQ31EdjeZMdB8CPwg>

Case 1: If two pointers point to different elements of the same array, or
to
subobjects thereof

`f1` does not point to an element in the `f2` array, and vice versa. Nor
are they subobjects of the same array.

Case 2: If two pointers point to different non-static data members of the
same
object, or to subobjects of such members, recursively,

Neither `f1` nor `f2` is a data member of the same object, or subobjects of
such members, recursively.

Since neither Case 1 nor Case 2 applies, Case 3 applies: neither pointer
compares greater than the other.

This isn't rocket science; it's simply C++ not working the way you thought
it does.

Now, implementations can, and often do, provide a total order to pointers
via `<`. But this is extra-standard behavior.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Nathan Ernst
2017-12-28 03:18:03 UTC
Permalink
Fair enough, as you said, a case of the standard working in a way I didn't
expect it to. Thanks for the clarification.

Regards,
Nate
Post by Nicol Bolas
Post by Thiago Macieira
op< is only defined for pointers of the same array. You cannot compare
two pointers if they come from different objects, that's UB
class Foo;
Foo f1[3];
Foo f2[3];
Unless I am sorely mistaken, comparing f1 < f2 is entirely well defined
(albeit, may not give the desired/intended outcome).
class Foo;
class Bar;
Foo f1[3];
Bar b1[3];
f1 < b1 may be UB.
Am I misunderstanding a subtlety in the spec?
<http://www.google.com/url?q=http%3A%2F%2Feel.is%2Fc%2B%2Bdraft%2Fexpr.rel&sa=D&sntz=1&usg=AFQjCNEqmgVqSkUb8HQ31EdjeZMdB8CPwg>
Case 1: If two pointers point to different elements of the same array, or
to
subobjects thereof
`f1` does not point to an element in the `f2` array, and vice versa. Nor
are they subobjects of the same array.
Case 2: If two pointers point to different non-static data members of the
same
object, or to subobjects of such members, recursively,
Neither `f1` nor `f2` is a data member of the same object, or subobjects
of such members, recursively.
Since neither Case 1 nor Case 2 applies, Case 3 applies: neither pointer
compares greater than the other.
This isn't rocket science; it's simply C++ not working the way you thought
it does.
Now, implementations can, and often do, provide a total order to pointers
via `<`. But this is extra-standard behavior.
Post by Thiago Macieira
--
---
You received this message because you are subscribed to the Google Groups
"ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an
Visit this group at https://groups.google.com/a/isocpp.org/group/std-
discussion/.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Thiago Macieira
2017-12-28 10:45:13 UTC
Permalink
Post by Nathan Ernst
Fair enough, as you said, a case of the standard working in a way I didn't
expect it to. Thanks for the clarification.
To make it more clear:

extern Foo f1;
extern Foo f2;

&f1 < &f2;

Is it true or not?

You clearly cannot answer this, since the order is not determined until link
time, while the standard talks about the compilation of one translation unit.
That's why the [expr.rel] passage Nicol and I quoted says that it doesn't
compare.

As a side-effect, it is UB to compare two pointers that come from neither the
same array nor the same object. That's despite pointers being represented by a
simple integer, which is quite comparable, in most current, modern memory
architectures (flat address space).

But you can easily think of esoteric architectures where that may not be the
case. Example: segmented, 16-bit x86 in large memory model.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Thiago Macieira
2017-12-28 02:35:38 UTC
Permalink
Post by KD
std::sort<T*>(T*, T*) results in the pointers ordered by <.
std::sort<T*>(T*,T*,std::less<T*>) results in the pointers ourdered by,
drum roll, <.
In the implementation you found. Can you be certain all implementations will
do that? That's entirely the point. You've found ONE implementation of
std::less and generalised to all implementations.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Nicol Bolas
2017-12-28 02:39:49 UTC
Permalink
Post by KD
What does std::less. have anything to do with the ordering of a
vector<T*> passed to a functuon that defaults to < comparison of T*? The
resulting order will be the same regardless if the op uses std::less or not.
No, it won't. That is literally the whole point of this thread.

[expr.rel]/8 governs the behavior of the comparison operators when applied
to pointers. It says that comparison is meaningful in the following cases:

1) "If two pointers point to different elements of the same array, or to
subobjects thereof"

2) "If two pointers point to different non-static data members of the same
object, or to subobjects of such
members, recursively,"

[comparisons] governs the behavior of the comparison function objects when
Post by KD
For templates less, greater, less_equal, and greater_equal, the
specializations for any pointer type yield a *strict total order* that is
consistent among those specializations and is also consistent with the
partial order imposed by the built-in operators < , > , <= , >= .

To put it in simpler language, the standard comparison operators give a
partial order to pointers: they only order some of the values. `std::less`
and the other comparison functors provide a *total order*; they order* all*
values of the pointer type.

A partial order is not the same thing as a total order. Their behaviors are
different, and therefore `sort(T*, T*, std::less())` can have different
results from `sort(T*, T*)`.

What the OP wants is to have `std::less`'s behavior be the* default* mode
of comparison for algorithms like `std::sort`.
Post by KD
The OPs results were not what he expected. None of you have suggested
what he needs to do to remidy his problem and I at least guided him on the
right path.
When you can specifically tell me anything that points to an issue
with how std::vector is defined, std::less is defined, and srd::sort is
defined that do not work as they should then we all should be speaking up.
But this isnt a problem with the standard at all.
namespace std {
template <typename T>
bool less(T a, T b) {
return a < b;
}
}
Sure looks identical in behavior to < to me.
First, `std::less` is a* functor*; so that's not a "possible
implementation" of any sort.

Second, that would only be a legal implementation if the compiler permits,
as implementation-defined behavior, < comparison between pointers outside
of the two cases above. Otherwise, the implementation would have to provide
a specialization for pointer types that cast them to `uintptr_t` and
perform comparisons that way.

Bark all you want to about it. The standard is not the issue with the
Post by KD
OP's problem and its obvious every person that's replied knows it.
Your attemts to pick apart anything Ive stated is hilarious. And sir,
if you have to ask me what cache hits have to do with anything you are not
following along, you might have missed something else to bark about.
So anyone care to take a deep breath, calm down, and explain to the
OP how jagged arrays work?
Theres books, online forums (not unlike this one ), and tutorials
that can help the OP out and all you all have done is bicker with me.
Nicol Bolas, I'm going to pretend you understand english better than you
do and you can be assured that I've a better understanding of how pointers,
allocations, systems, and C++ works than what you've presumed that I
possess.
... I'm not sure how to take a statement like that from a person who didn't
even know `std::less` was a functor rather than a template function.

I mean, I totally understand that you wouldn't know an esoteric point like
< not behaving the same as `std::less` for pointers. Most compilers provide
a total order for pointer comparison anyway, so most people don't realize
that it's not actually required behavior. But normally, when people are
told that the standard says something, and it doesn't agree with how they
think things work, they would generally go look at the standard for
confirmation or contradiction, not continue to argue from a position of
ignorance.

std::sort<T*>(T*, T*) results in the pointers ordered by <.
Post by KD
std::sort<T*>(T*,T*,std::less<T*>) results in the pointers ourdered by,
drum roll, <.
I really dont think its necessairy to get the point across that if your
comparing memory addresses it dosent matter if they are sequential or not
and ive stated that how many times?
Well, the C++ standard says that it is; that's all that matters.
Post by KD
What matters is what the OP expected and ordered pointers did not give him
the result he expected.
Really, you think that the language's less than comparison is somehow less
capable than a function written in the language? Brilliantly moronic
argument. Im now worried about more than just your grasp of my language.
std::less will only order two elements thats passed to it.
It returns a bool that indicates if the first paremeter is less than the
second.
std::sort calls its comparison on all the elements passed to it.
std::sort provides the total ordering of all the elements passed to it,
not std::less.
The standard is not the problem, My posts arent the problem, and the
standard does exactly what we all have said.
So how does jmkesson translate to Nicol Bolas anyway, a pseudo name?
Yes. People online often have pseudonyms or handles. Welcome to the
Internet circa 1980.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
KD
2017-12-28 03:21:40 UTC
Permalink
Walls of text dont bother me Nicol. See tiago's reaponse for how pointer
comparisons work. The only point I didnt touch on is Unions.

Function is Functor it dosent matter. For less theres no state to store so
its a bit overkill for it to be an actual object no matter how its defined.

None of you can explain how the OP is confused when using the same
comparison to sort pointers.

We've got 0 information on how he obtains his pointers.

I checked 0 implementations for any of my information. Its all from memory.

So, another brown paper bag for Nicol too?
Post by Nicol Bolas
Post by KD
What does std::less. have anything to do with the ordering of a
vector<T*> passed to a functuon that defaults to < comparison of T*? The
resulting order will be the same regardless if the op uses std::less or not.
No, it won't. That is literally the whole point of this thread.
[expr.rel]/8 governs the behavior of the comparison operators when applied
1) "If two pointers point to different elements of the same array, or to
subobjects thereof"
2) "If two pointers point to different non-static data members of the same
object, or to subobjects of such
members, recursively,"
[comparisons] governs the behavior of the comparison function objects when
Post by KD
For templates less, greater, less_equal, and greater_equal, the
specializations for any pointer type yield a *strict total order* that is
consistent among those specializations and is also consistent with the
partial order imposed by the built-in operators < , > , <= , >= .
To put it in simpler language, the standard comparison operators give a
partial order to pointers: they only order some of the values. `std::less`
and the other comparison functors provide a *total order*; they order*
all* values of the pointer type.
A partial order is not the same thing as a total order. Their behaviors
are different, and therefore `sort(T*, T*, std::less())` can have different
results from `sort(T*, T*)`.
What the OP wants is to have `std::less`'s behavior be the* default* mode
of comparison for algorithms like `std::sort`.
Post by KD
The OPs results were not what he expected. None of you have
suggested what he needs to do to remidy his problem and I at least guided
him on the right path.
When you can specifically tell me anything that points to an issue
with how std::vector is defined, std::less is defined, and srd::sort is
defined that do not work as they should then we all should be speaking up.
But this isnt a problem with the standard at all.
namespace std {
template <typename T>
bool less(T a, T b) {
return a < b;
}
}
Sure looks identical in behavior to < to me.
First, `std::less` is a* functor*; so that's not a "possible
implementation" of any sort.
Second, that would only be a legal implementation if the compiler permits,
as implementation-defined behavior, < comparison between pointers outside
of the two cases above. Otherwise, the implementation would have to provide
a specialization for pointer types that cast them to `uintptr_t` and
perform comparisons that way.
Bark all you want to about it. The standard is not the issue with the
Post by KD
OP's problem and its obvious every person that's replied knows it.
Your attemts to pick apart anything Ive stated is hilarious. And sir,
if you have to ask me what cache hits have to do with anything you are not
following along, you might have missed something else to bark about.
So anyone care to take a deep breath, calm down, and explain to the
OP how jagged arrays work?
Theres books, online forums (not unlike this one ), and tutorials
that can help the OP out and all you all have done is bicker with me.
Nicol Bolas, I'm going to pretend you understand english better than you
do and you can be assured that I've a better understanding of how pointers,
allocations, systems, and C++ works than what you've presumed that I
possess.
... I'm not sure how to take a statement like that from a person who
didn't even know `std::less` was a functor rather than a template function.
I mean, I totally understand that you wouldn't know an esoteric point like
< not behaving the same as `std::less` for pointers. Most compilers provide
a total order for pointer comparison anyway, so most people don't realize
that it's not actually required behavior. But normally, when people are
told that the standard says something, and it doesn't agree with how they
think things work, they would generally go look at the standard for
confirmation or contradiction, not continue to argue from a position of
ignorance.
std::sort<T*>(T*, T*) results in the pointers ordered by <.
Post by KD
std::sort<T*>(T*,T*,std::less<T*>) results in the pointers ourdered by,
drum roll, <.
I really dont think its necessairy to get the point across that if your
comparing memory addresses it dosent matter if they are sequential or not
and ive stated that how many times?
Well, the C++ standard says that it is; that's all that matters.
Post by KD
What matters is what the OP expected and ordered pointers did not give
him the result he expected.
Really, you think that the language's less than comparison is somehow
less capable than a function written in the language? Brilliantly moronic
argument. Im now worried about more than just your grasp of my language.
std::less will only order two elements thats passed to it.
It returns a bool that indicates if the first paremeter is less than the
second.
std::sort calls its comparison on all the elements passed to it.
std::sort provides the total ordering of all the elements passed to it,
not std::less.
The standard is not the problem, My posts arent the problem, and the
standard does exactly what we all have said.
So how does jmkesson translate to Nicol Bolas anyway, a pseudo name?
Yes. People online often have pseudonyms or handles. Welcome to the
Internet circa 1980.
Post by KD
--
---
You received this message because you are subscribed to a topic in the
Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/a/
isocpp.org/d/topic/std-discussion/HPj2y9RLVG8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to
Visit this group at https://groups.google.com/a/isocpp.org/group/std-
discussion/.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Marc Mutz
2017-12-28 10:37:44 UTC
Permalink
Post by KD
Walls of text dont bother me Nicol. See tiago's reaponse for how
pointer comparisons work. The only point I didnt touch on is Unions.
Function is Functor it dosent matter. For less theres no state to
store so its a bit overkill for it to be an actual object no matter
how its defined.
None of you can explain how the OP is confused when using the same
comparison to sort pointers.
We've got 0 information on how he obtains his pointers.
I checked 0 implementations for any of my information. Its all from memory.
So, another brown paper bag for Nicol too?
[I think we experience now first-hand how Trump's advisory panel feels
like very day :)]
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Michael Kilburn
2017-12-28 10:43:42 UTC
Permalink
Great idea! Let's politicize C++ too.
Post by Marc Mutz
Post by KD
Walls of text dont bother me Nicol. See tiago's reaponse for how
pointer comparisons work. The only point I didnt touch on is Unions.
Function is Functor it dosent matter. For less theres no state to
store so its a bit overkill for it to be an actual object no matter
how its defined.
None of you can explain how the OP is confused when using the same
comparison to sort pointers.
We've got 0 information on how he obtains his pointers.
I checked 0 implementations for any of my information. Its all from memory.
So, another brown paper bag for Nicol too?
[I think we experience now first-hand how Trump's advisory panel feels
like very day :)]
--
--- You received this message because you are subscribed to the Google
Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an
Visit this group at https://groups.google.com/a/is
ocpp.org/group/std-discussion/.
--
Sincerely yours,
Michael.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Matthew Woehlke
2017-12-28 18:12:19 UTC
Permalink
Post by KD
Walls of text dont bother me Nicol.
"Walls of text" is *the entire point of this forum*. This is a forum for
discussing *the standard*, not implementations (except w.r.t. how they
implement, or fail to implement, the standard).
Post by KD
None of you can explain how the OP is confused when using the same
comparison to sort pointers.
There is at most one "confused" person in this thread. Hint: his name
isn't Marc.
Post by KD
So, another brown paper bag for Nicol too?
I *sincerely* hope you are intentionally trolling, because if you
aren't, the level of ignorance (to put it politely) is simply unbelievable.

Congratulations, BTW; I now have an "idiocy filter" on this group.
--
Matthew
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Thiago Macieira
2017-12-28 02:41:25 UTC
Permalink
Post by KD
Really, you think that the language's less than comparison is somehow less
capable than a function written in the language? Brilliantly moronic
argument. Im now worried about more than just your grasp of my language.
http://eel.is/c++draft/expr.rel

Comparing unequal pointers to objects is defined as follows:

(3.1)
If two pointers point to different elements of the same array, or to
subobjects thereof, the pointer to the element with the higher subscript
compares greater.
(3.2)
If two pointers point to different non-static data members of the same
object, or to subobjects of such members, recursively, the pointer to the
later declared member compares greater provided the two members have the same
access control and provided their class is not a union.
(3.3)
Otherwise, neither pointer compares greater than the other.

Do you need a brown paper bag?
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Thiago Macieira
2017-12-28 00:06:08 UTC
Permalink
Post by KD
There is no gurantee that his T* will correctly compare with std::less.
There is. It's right there in the standard. See
http://eel.is/c++draft/comparisons#2

For templates less, greater, less_­equal, and greater_­equal, the
specializations for any pointer type yield a strict total order that is
consistent among those specializations and is also consistent with the partial
order imposed by the built-in operators <, >, <=, >=.
Post by KD
The 1st T* could have a memory address of say 0xFFAA, the 2nd T* could have
a memory address of 0xAAAA but the OP could be wanting to compare the value
the T* points to, not the address of the value, and element 2 could have a
value greater than the 1st elememt but what is std::less going to say is
less? the 2nd because hes comparing pointers.
No, he does not. He quite clearly wants to compare pointer addresses, not
pointed objects.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Continue reading on narkive:
Loading...