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 ?

does this code compiles? in `push_back` function there is no `begin` and `end` until and unless you made them global. — Ankur, Jan 03 '15 at 19:09
There is no guarantee about the placement of the separate nodes in a list; the first node might be located before the second and after the third. The `ptrdiff_t` type is for taking the difference between two pointers into guaranteed contiguous memory, which means two pointers pointing at locations in a single array (or one element beyond the end of the array). Anything else leads to undefined behaviour; any result is possible and all of them are correct. — Jonathan Leffler, Jan 03 '15 at 19:13
@Shan: the posted code won't compile but the source does, I hacked out the pertinent parts to make it easier on the eyes. — tuk, Jan 03 '15 at 19:35

Benjamin Lindley · Answer 1 · 2015-01-03T19:18:57.260

4

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.

edited Jan 03 '15 at 19:18

answered Jan 03 '15 at 19:13

Benjamin Lindley

101,917
9
204
274

score 3 · Accepted Answer · answered Jan 03 '15 at 19:13

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.

Using std::ptrdiff_t on user defined types

2 Answers2