Howard Hinnant <howard.hinnant_at_[hidden]> writes:

| On Oct 18, 2013, at 12:29 AM, Gabriel Dos Reis <gdr_at_[hidden]> wrote:
|
| > Nevin Liber <nevin_at_[hidden]> writes:
| >
| > | On 15 October 2013 17:39, Nevin Liber <nevin_at_[hidden]> wrote:
| > |
| > | Really? I've seen novices ask questions like "does pointer p point to an
| > | object inside array a?" A natural (but wrong) way to write it is:
| > |
| > | bool isInArray = std::begin(a) <= p && p < std::end(a);
| >
| > That is a wrong question to ask,
|
| Why?

See below.

| > and I am not too surprise that what you
| > think would be natural question would be wrong.
|
| On the surface this appears to be a rather demeaning comment.

no, it isn't.

| I'm sure you didn't mean it that way.
|
| > It is also not too
| > surprising for a novice to ask a wrong question -- not every question
| > that a novice ask makes sense.
|
| Agreed. Note also that not every question a novice asks is senseless.

Also agreed.

| In this case I am the novice to which Nevin refers. There are several
| places where I need to find out whether or not a range of memory is
| referenced by a pointer of unknown origin.
|
| One of them can be found in libc++'s vector::insert(iterator p, const T& x):

I am glad you bring this example; let's look at it, its context, and
alternatives.

| http://llvm.org/svn/llvm-project/libcxx/trunk/include/vector
|
| Search for "::insert".
|
| Here is a snippet of the code you will find there:
|
| __move_range(__p, this->__end_, __p + 1);
| const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
| if (__p <= __xr && __xr < this->__end_) // here
| ++__xr;
| *__p = *__xr;
|
| On the line I've commented "here" above, I am determining if the
| pointer xr is in the range [p, end).

Please note that your *implementation* is already implementing
std::less<T*> as operator<. As an implementer, you already know the
characteristic of your implementations and it is not at all surprising
that you are reusing that knowledge elsewhere in the library -- the
contrary would have been surprising. And in effect, because of that,
you are not the novice we are talking about.

| The reason I am doing this is because &x is allowed to reference
| *this vector. And if it does, and if size() < capacity(), and if the
| reference is in the range [p, end()), then the first line of this
| snippet of code will change the memory address of x, and result in
| inserting the wrong value into the vector.

Correct.

| There is another way to solve the self-referencing problem for this
| function. One can make a local copy of x, before doing any
| rearranging and then insert from the local copy.

Right! And this is done on popular implementations too.

| I chose not to do
| this for performance reasons. The copy construction of x is
| arbitrarily expensive. I do not want to make any more copies of x
| than I absolutely have to.

This assumes that copy-construction is always more expensive than assignment.

| Now implementing vector is not the most exotic of exercises known to
| computer science.

That is correct, again. There is nothing in that exercise that requires
this particular construct -- indeed, quality implementations have been
delivered without it.

| But even in this modest exercise, I found myself
| needing to know if a pointer referenced a range of memory. It does
| not seem like much of a stretch to me that other C++ programmers may
| find themselves facing the same question. So your statement:

Let's remember that as an implementer, you knew the characteristics of
your implementations -- and I assume your customers also hope you do.

| > That is a wrong question to ask,
|
| backed up by no rationale at all, seems incorrect to me. On what
| basis do you apply this statement to every single C++ programmer and
| C++ application that exists?

Let's not forget the context of the statement.
You've just described the experience of an implementer delivering his
implementation which is permitted to use every characteristic of its
implementation; that hardly counts the a novice exercise.

| > What you tell your novice if he asked you: "does this iterator p points
| > to an object in this container"?
|
| Personally I would look at the underlying data structure of the
| container and respond that it can be done very efficiently for some
| containers (e.g. vector and string), less efficiently on others
| (e.g. deque), and would be very expensive on several containers
| (e.g. list, set, etc.). Though the standard does not currently fully
| support asking this question. At the same time, I've seen
| well-motivated code in the wild that does ask this question.

Notice that I didn't deny the existence of such questions being asked.

| I do not know for sure, because I haven't examined the code, but I
| would not be surprised at all if the code to which this paper refers:
|
| http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2911.pdf
|
| compared iterators from different containers using == and !=. As I understand it, that code was also motivated by performance concerns.

Note that my statement do not preclude an implementer using known
characteristic of its implementations to achieve whatever it wants to achieve.

-- Gaby