Pointer to class member as template parameter (with type of the following class)

Question

I'm trying to define an internal list as template class that has a type safe container_of member function. For that the template must include the type of the container and the offset where in the container the list can be found (a member pointer). (See below for an example in C).

It should be something like this:

template <class T, List * T::*MEMBER> class List { ... }

But in the <> the type List is not yet defined so it can't be used. My next try was:

template <class T, class L, L * T::*MEMBER> class List { ... };

class Container {
    List<Container, List<???>, Container::list> list;
};

But what to put for the "???"? That would have to be the whole <>, including the ???. So you get an endless recursion.

Next I tried to cheat a bit on the type safety:

template <class T, void * T::*M>
class List {
public:
    T * container_of() {
        return (T *)(intptr_t(this) - intptr_t(&((T *)NULL)->M)); \
    }
};

class Container {
public:
    List<Container, Container::item1> item1;
};

But that gives me:

error: incomplete type 'Container' used in nested name specifier
       List<Container, Container::item1> item1;
                       ^

---

Using C preprocessor makros what I want looks like this:

#include <unistd.h> // for NULL
#include <stdint.h> // for intptr_t
#include <iostream>

#define LIST(TYPE, MEMBER) \
class List_ ## MEMBER ## _t { \
public: \
    TYPE * container_of() { \
    return (TYPE *)(intptr_t(this) - intptr_t(&((TYPE *)NULL)->MEMBER)); \
    } \
} MEMBER

class Container {
public:
    LIST(Container, item1);
    LIST(Container, item2);
};

int main() {
    Container c;
    std::cout << "Container at " << &c << std::endl;
    std::cout << "Container of item1 = " << c.item1.container_of() << std::endl;
    std::cout << "Container of item2 = " << c.item2.container_of() << std::endl;
}

So can this be expressed with templates at all?

Answer 1

I found a solution. It's not 100% perfect but close.

The idea is to have 3 classes:

class Item;
template <class T, Item T::*M> class Iterator;
template <class T, Item T::*M> class Head;

The Item class contains the next/prev links that form the actual list in memory. This doesn't include the container type and position of the list inside the container and (on its own) is unsafe. But an Item has no method to modify the list. All modifications are done through the Iterator. Even construction is done using a Head to get an Iterator and that to initialize the next/prev pointers.

The Iterator class can be constructed from a container T and has operator ++, --, == and !=, can insert a container into the current position or move the container behind another iterator to its own list. The Iterator also has operator * which returns the current container and operator bool to say if the end of the list has been reached.

The Head class contains a special head and tail Item with prev==NULL and next==NULL respectively. They are special since they aren't inside an instance of container T and mark the begining and end of the list. Other than holding the end markers the Head provides methods to create Iterators pointing at the head, tail, first and last element. This allows iterating the list or inserting at the start or end.

There is a 4th class ConstIterator that is like Iterator but for const access.

Note: This is only minimally tested. The remaining errors are left for the reader to fix.

---

class Item;
template <class T, Item T::*M> class Iterator;
template <class T, Item T::*M> class ConstIterator;
template <class T, Item T::*M> class Head;

template<class T, Item T::*M>
T * container_of(Item *item) {
    return (T *)(intptr_t(item) - intptr_t(&(((T *)NULL)->*M)));
}

template<class T, Item T::*M>
const T * container_of(const Item *item) {
    return (const T *)(intptr_t(item) - intptr_t(&(((const T *)NULL)->*M)));
}

class Item {
public:
    template <class T, Item T::*M> Item(Head<T, M> *head, T *container) {
        assert((container_of<T, M>(this)) == container);
        head->tail().insert_before(container);
    }
    ~Item() {
        if (next_) next_->prev_ = prev_;
        if (prev_) prev_->next_ = next_;
        next_ = NULL;
        prev_ = NULL;
    }
private:
    template <class T, Item T::*M> friend class Iterator;
    template <class T, Item T::*M> friend class ConstIterator;
    template <class T, Item T::*M> friend class Head;
    Item(Item *next__, Item *prev__) : next_(next__), prev_(prev__) { }
    Item(const Item &) = delete;
    Item & operator =(const Item &) = delete;
    Item *next_;
    Item *prev_;
};

template <class T, Item T::*M>
class Iterator {
public:
    Iterator() : item_(NULL) { }
    Iterator(T *container) : item_(&(container->*M)) { }
    ~Iterator() { }
    operator bool() const {
        assert(item_);
        // not head and not tail
        return ((item_->next_ != NULL) && (item_->prev_ != NULL));
    }
    T & operator *() {
        assert(item_);
        if ((item_->next_ == NULL) || (item_->prev_ == NULL)) {
            // head or tail has no container
            assert(false);
        }
        return *container_of<T, M>(item_);
    }
    T & operator ->() {
        assert(item_);
        if ((item_->next_ == NULL) || (item_->prev_ == NULL)) {
            // head or tail has no container
            assert(false);
        }
        return *container_of<T, M>(item_);
    }
    Iterator & operator ++() {
        assert(item_);
        assert(item_->next_);
        item_ = item_->next_;
        return *this;
    }
    Iterator & operator --() {
        assert(item_);
        assert(item_->prev_);
        item_ = item_->prev_;
        return *this;
    }
    bool operator ==(const Iterator &other) {
        assert(item_);
        return (item_ == other.item_);
    }
    bool operator !=(const Iterator &other) {
        assert(item_);
        return (item_ != other.item_);
    }
    void move_before(Iterator &from) {
        assert(item_);
        assert(from);
        assert(item_->prev_);

        Item *before = item_->prev_;
        Item *after = item_;
        Item *item = from.item_;

        // remove from old list
        item->next_->prev_ = item->prev_;
        item->prev_->next_ = item->next_;

        // insert into this list
        item->next_ = after;
        item->prev_ = before;
        before->next_ = item;
        after->prev_ = item;
    }
    void insert_before(T *container) {
        assert(item_);
        assert(item_->prev_);

        Item *before = item_->prev_;
        Item *after = item_;
        Item *item = &(container->*M);

        // insert into this list
        item->next_ = after;
        item->prev_ = before;
        before->next_ = item;
        after->prev_ = item;
    }
private:
    Item *item_;
};

template <class T, Item T::*M>
class ConstIterator {
public:
    ConstIterator() : item_(NULL) { }
    ConstIterator(const T *container) : item_(&(container->*M)) { }
    ~ConstIterator() { }
    operator bool() const {
        assert(item_);
        // not head and not tail
        return ((item_->next_ != NULL) && (item_->prev_ != NULL));
    }
    const T & operator *() const {
        assert(item_);
        if ((item_->next_ == NULL) || (item_->prev_ == NULL)) {
            // head or tail has no container
            assert(false);
        }
        return *container_of<T, M>(item_);
    }
    const T & operator ->() const {
        assert(item_);
        if ((item_->next_ == NULL) || (item_->prev_ == NULL)) {
            // head or tail has no container
            assert(false);
        }
        return *container_of<T, M>(item_);
    }
    ConstIterator & operator ++() {
        assert(item_);
        assert(item_->next_);
        item_ = item_->next_;
        return *this;
    }
    ConstIterator & operator --() {
        assert(item_);
        assert(item_->prev_);
        item_ = item_->prev_;
        return *this;
    }
    bool operator ==(const ConstIterator &other) const {
        assert(item_);
        return (item_ == other.item_);
    }
    bool operator !=(const ConstIterator &other) {
        assert(item_);
        return (item_ != other.item_);
    }
private:
    const Item *item_;
};

template <class T, Item T::*M>
class Head {
public:
    Head() : head_(&tail_, NULL), tail_(NULL, &head_) { }
    ~Head() { }
    Iterator<T, M> head() {
        return Iterator<T, M>(container_of<T, M>(&head_));
    }
    ConstIterator<T, M> head() const {
        return ConstIterator<T, M>(container_of<T, M>(&head_));
    }
    Iterator<T, M> tail() {
        return Iterator<T, M>(container_of<T, M>(&tail_));
    }
    ConstIterator<T, M> tail() const {
        return ConstIterator<T, M>(container_of<T, M>(&tail_));
    }
    Iterator<T, M> first() {
        return Iterator<T, M>(container_of<T, M>(head_.next_));
    }
    ConstIterator<T, M> first() const {
        return ConstIterator<T, M>(container_of<T, M>(head_.next_));
    }
    Iterator<T, M> last() {
        return Iterator<T, M>(container_of<T, M>(tail_.prev_));
    }
    ConstIterator<T, M> last() const {
        return ConstIterator<T, M>(container_of<T, M>(tail_.prev_));
    }
    bool is_empty() const {
        return (first() == tail());
    }
private:
    Head(const Head &) = delete;
    Head & operator =(const Head &) = delete;
    Item head_;
    Item tail_;
};