C++ size_t and ptrdiff_t for negative array indexing

Question

I'm having difficulty choosing between size_t and ptrdiff_t for the type of an index, which should need to be able to store a negative value.

To be precise, in my code I need to implement an array. I receive it's length (in the constructor) as a type of size_t, and when I overloaded the [] operator I need that the index would be of type ptrdiff_t (and not size_t), since I want to allow negative indexes, as this example shows:

std::size_t length = 50;
MyVector<int> vec(length);
vec[0] = 10;

MyVector<int> vec2 = vec+1;
std::cout << vec2[-1] << std::endl; //should print 10

The issue that arises from said design is that the range of avaiable indexes is limited by the maximum value of ptrdiff_t, and in some machines, this upper limit is less than the maximum value of size_t.

i.e. std::numeric_limits<std::ptrdiff_t>::max() < std::numeric_limits<std::size_t>::max()

Thus, the problem is that the user might create an array with a size which is larger than the maximum value of ptrdiff_t (but still in range of size_t, of course), but he wouldn't be able to access the array's elements which succeed over the maximum value of ptrdiff_t, because their indexes would overflow to a negative number. On my machine, this cuts the avaiable indexes in half! (since both size_t and ptrdiff_t are 64 bits, but one is unsigned and the other is signed)

Here are the solutions that I came up with, but sadly none of them are perfect:

1. In the constructor, accept a length of type ptrdiff_t instead of size_t, and add a check that verifies that the given length is not negative.

   Pros: It solves the issue, since now I would be able ot access all the elements in the array, and still allow for negative indexes.

   Cons: It limits the maximum possible length of the array. (e.g. like I said earlier, in my machine it cuts by half)

2. Leave things as they are, but in the [] operator, cast the index to type size_t, and make use of the fact that negative value would overflow.

   i.e. to the given index, add the difference between the element we're currently pointing to, and the

   for example, in my example before, since vec2 points to the second element in the arary, the [] operator would look something like

   template<class T>
   T& MyVector<T>::operator[] (std::ptrdiff_t index) {
       //Since vec2 points to the second element, we add 1.
       //For vec, we would add 0 since it points at the 
       //first element in the array.
       std::size_t actual_index = static_cast<std::size_t>(index + 1);
   
       //Do boundary checking
   
       return this->ptr[actual_index];
   }
   

   Pros: We're now able to access all the elements in the array.

   Cons: The usage becomes clumsy and ugly. For example, if we create a vector of size std::numeric_limits<std::size_t>::max(), then in order to access the last element, we need to access the '-1' element:

   MyVector<int> big_vector(std::numeric_limits<std::size_t>::max());
   big_vector[-1] = 5; // big_vector[-1] is the last element in the array.
   
   MyVector<int> big_vector2 = big_vector + 1;
   std::cout << big_vector2[-2] << std::endl; // would print 5, since big_vector2 points at the second element in the array
   

Answer 1

I'm having difficulty choosing between size_t and ptrdiff_t for the type of an index, which should need to be able to store a negative value.

Why have you limited yourself to size_t and ptrdiff_t? What about other integer types?

Do you have an actual plan to implement a container with 4.294.967.296 elements? (that is 2 ^ 32).

I don't think there is a platform today that will assign that much memory - at least, not in consumer-level computers. Are you working on specialized hardware?

For generic-purpose C++, you can safely write a std::size_t - accepting constructor to a std::ptrdiff_t indexed class.

You will probably have to configure the accepted range of indexes, so that if you accept negative indexes, effective index range should be (-max32bit, max32bit).

This means, if you attempt to use the class with an index in the range (max32bit, max64bit), your class should throw an exception.

My solution would accept a std::size_t in the constructor (with clear documentation stating that the index ranges from -max(ptrdiff_t) to max(ptrdiff_t), and not from 0 to max(std::size_t). The class would then be indexed using a std::ptrdiff_t.