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?

> 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. 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.

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):

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). 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.

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. 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.

Now implementing vector is not the most exotic of exercises known to computer science. 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:

> 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?

> 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.

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.

Howard