Using std::ptrdiff_t on user defined types

Question

I have a simple struct called node which holds a value + 2 pointers to next/previous nodes.

template <class T>
struct node {

     node<T> *prev = NULL;
     node<T> *next = NULL;
     T data;        
};

Here we have the function which adds a new node to the end.

void push_back( T val ) {           

    node<T> *n = new node<T>;   // create node to hold val
    n->data = val;              // set node data with val

    if ( node_count == 0 ) {     

        begins = n;             // begins points to first node          
    }
    else{

        ends->next = n;         // set next in ends
        n->prev = ends;         // set previous             
    }

    ends = n;                   // update ends
    node_count++;               // update list size
}                                       

In main we create 100 linked nodes, each holding a unique int value.

for (int i = 0; i != 100; i++){  push_back(i); }

Here are the pointers to the first/last node:

node<T> *begins; 
node<T> *ends; 

The trouble starts when attempting to apply pointer arithmetic:

std::ptrdiff_t node_sum = ends - begins;

Somehow node_sum == 528, if I do a x32 compile then node_sum == 781.

Why is node_sum not 100 ?

Answer 1

Remember that allocations doesn't have to be consecutive, even if you do the allocations right next to each other.

That means that if you have e.g.

begin = new node<T>;
end = new node<T>;

it's not guaranteed that begin and end will be next to each other.

You can only use pointer arithmetic on pointers that point to the same memory area, like an array, otherwise you have undefined behavior.

Answer 2

Your nodes are not part of an array. They are each allocated separately, in whatever location the memory allocator could find for them. You cannot subtract them and expect any particular value. In fact, doing so is undefined behavior. In order to count the distance between the nodes in your linked list, you need to iterate through it by following the next or prev pointers.