Index from address in array of pointers?

Question

The code below a solution to the following requirement:

"Change the representation of Link and List from §27.9 without changing the user interface provided by the functions. Allocate Links in an array of Links and have the members: first, last, prev, and next be ints (indices into the array). "
- Exercise 6 Chapter 27 - Programming: Principles and Practice Using C++ B. Stroustrup

The interface is inherited from an ordinary implementation of an Intrusive doubly linked list. I've added the bool array (and the associated functions) to keep track of memory:

 #include <iostream>

struct Link
{
    int next;
    int prev;
};

//------------------------------------------------------------------------------------

struct List
{
    Link** head;
    int first;      // points to the current first node
    int last;

    bool* available;
    int list_size;

    int get_index()
    {
        for (int i = 0; i < list_size; ++i)
        {
            if (available[i] == true) 
            {
                available[i] = false;
                return i;
            }
        }
        throw std::bad_alloc("bla bla!\n");
    }

    List()
    {
        list_size = 30;

        head = new Link*[list_size];
        available = new bool[list_size];

        first = -1;
        last = -1;

        for (int i = 0; i < list_size; ++i)
        {
            available[i] = true;
        }
    }

    void List::push_back(Link* l)
    {
        if (l == nullptr)
        {
            throw std::invalid_argument("bla bla!\n");
        }

        int index = get_index();
        head[index] = l;

        if (last != -1)
        {
            head[last]->next = index;
            head[index]->prev = last;
        }
        else
        {
           first = index;
           head[index]->prev = -1;
        }

        last = index;
        head[index]->next = -1;
    }

    void push_front(Link* l)
    {
        if (l == nullptr)
        {
            throw std::invalid_argument("bla bla\n");
        }

        int index = get_index();
        head[index] = l;

        if (first != -1)
        {
            head[first]->prev = index;
            head[index]->next = first;
        }
        else
        {
            last = index;
            head[index]->next = -1;
        }

        first = index;
        head[index]->prev = -1;
    }

    // index = ptr - base
    std::ptrdiff_t index_from_address(Link* l) { return l - head[0]; }

    Link* front() const { return head[first]; }
};

//------------------------------------------------------------------------------------

int main()
{
    List l;

    for (int i = 0; i < 10; ++i)
    {
        l.push_back(new Link());
    }

    for (int i = 0; i < 10; ++i)
    {
        l.push_front(new Link());
    }

    std::cout <<"first = "<< l.first <<", index = " << l.index_from_address(l.front());
    getchar();
}

Expected result:

first = 19, index = 19

Actual result:

first = 19, index = 194

Why?

Answer 1

l - head[0]

Here you compare the values of the two pointers. You let all pointers in the array be default initialized, so their values are indeterminate, and therefore the behaviour of accessing the values is undefined.

You probably intended index_from_address to find the index where a particular pointer object is stored - rather than the object that is pointed to, since the pointed to object is not in the array pointed by head. To do that, you must add a whole bunch of &:

 Link*& front() const // return a reference to the pointer object, not a copy

 //  take a reference to the pointer as an argument, add const for good measure
 std::ptrdiff_t index_from_address(Link*& l) const
// compare the addresses of the pointers, rather than values
 { return &l - &head[0]; }