CODEWITHSUNDEEP
c++cpointers
Joshua Green
Joshua Green

Reputation: 1575

Pointer Subtraction and an Alternative

When working with arrays, standard algorithms (in both C and C++) often return pointers to elements. It is sometimes convenient to have the index of the element, perhaps to index into another array, and I normally get that by subtracting the beginning of the array from the pointer:

int arr[100];
int *addressICareAbout = f(arr, 100);
size_t index = addressICareAbout - arr;

This always seemed simple and effective enough. However, it was recently pointed out to me that pointer subtraction actually returns a ptrdiff_t and that, in principle, there could be problems if the "index" doesn't fit in a ptrdiff_t. I didn't really believe that any implementation would be perverse enough to allow one to create such a large arr (and thereby cause such issues), but the accepted answer here admits that that's possible and I've found no evidence to suggest otherwise. I've therefore resigned myself to this being the case (unless someone can convince me otherwise) and will be careful going forward. That answer proposes a fairly convoluted method of "safely" getting the index; is there really nothing better?

That said, I'm confused about a possible workaround in C++. There we have std::distance, but is std::distance(arr, addressICareAbout) guaranteed to be well-defined? On the one hand, (the pointer to the first element of) arr can be incremented to reach addressICareAbout (right?), but on the other hand std::distance should return a ptrdiff_t. The iterators for the standard containers can (presumably) have the same issues.

Upvotes: 11

Views: 1833

Answers (3)

Ben Voigt
Ben Voigt

Reputation: 283624

Possible workaround:

Cast both pointers to uintptr_t, subtract, and divide by sizeof (T) yourself. This is not precisely portable, but it's guaranteed never to be undefined behavior, and most systems specify integer<->pointer conversion in a way that makes this work.

Really portable (but less efficient) workaround:

Use an alternative base pointer. If the array is more than 2<<30 elements, then you can legally compute step = p1 + (2<<30), use relational operators to see whether p2 > step, and if so, calculate the offset as (2u << 30) + uintptr_t(distance(step, p2)) Note that the recursive call may require taking another step.

Upvotes: 0

gnasher729
gnasher729

Reputation: 52530

It is extremely unlikely that you will ever have two pointers to the same array where the difference doesn't fit into ptrdiff_t.

On 64 bit implementations, ptrdiff_t is signed 64 bit, so you'd need an array of 8 billion gigabytes. On 32 bit implementations, usually your total address space is limited to 3 GB, 3 1/4 GB if you are lucky (it's address space, not RAM, that counts), so you'd need an array of more than 2 GB which doesn't leave much for anything else. And it is quite possible that malloc will refuse to allocate an array of that size in the first place. Your judgement of course.

While std::distance has advantages, I suspect it has the same theoretical problem as ptrdiff_t, since distances can be positive and negative, and it's probably not a 64 bit type on a 32 bit implementation.

Note that if you can allocate a 3 GB array on a 32 bit implementation, and you have two int* to the first and the last element of that array, I wouldn't be surprised if the pointer difference is calculated incorrectly even though the result fits into ptrdiff_t.

Upvotes: 6

Richard Hodges
Richard Hodges

Reputation: 69854

I've found no evidence to suggest otherwise.

Fortunately there is evidence here: http://en.cppreference.com/w/cpp/types/size_t

std::size_t can store the maximum size of a theoretically possible object of any type (including array). A type whose size cannot be represented by std::size_t is ill-formed (since C++14)

Upvotes: -2

Related Questions