Указатель на член класса в качестве параметра шаблона (с типом следующего класса)

Question

Я пытаюсь определить внутренний список как класс шаблона, который имеет тип safe container_of функции-члена. Для этого шаблон должен включать тип контейнера и смещение, где в контейнере список может быть найден (указатель-член). (См. Ниже пример на C).

Это должно быть что-то вроде этого:

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

Но в <> Перечень тип не определен, поэтому он не может быть использован. Моя следующая попытка:

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

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

Но что поставить для «???»? Это должно быть целое <>, включая ???. Таким образом, вы получаете бесконечную рекурсию.

Далее я попытался обмануть немного о безопасности типа:

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; 
}; 

Но это дает мне:

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

---

Использование C препроцессор Makros что я хочу выглядеть следующим образом:

#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; 
} 

Так может ли это быть выражены с помощью шаблонов?

Answer 1

Я нашел решение. Это не на 100% отлично, но близко.

Идея состоит в том, чтобы иметь 3-х классов:

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

Класс Item содержит следующие/Prev ссылки, которые образуют фактический список в памяти. Это не включает тип контейнера и положение списка внутри контейнера и (само по себе) является небезопасным. Но у элемента нет способа изменить список. Все изменения выполняются через Iterator. Даже конструкция выполняется с помощью Head для получения Iterator и для инициализации указателей next/prev.

Класс Iterator может быть построен из контейнера T и имеет оператор ++, -, == и! =, Может вставить контейнер в текущую позицию или переместить контейнер за другим итератором в собственный список. Итератор также имеет оператор *, который возвращает текущий контейнер и оператор bool, чтобы сказать, достигнут ли конец списка.

Класс Head содержит специальную голову и хвост. Item with prev == NULL и next == NULL соответственно. Они являются особенными, поскольку они не находятся внутри экземпляра контейнера T и отмечают начало и конец списка. Помимо удерживания концевых маркеров, Head предоставляет методы для создания итераторов, указывающих на голову, хвост, первый и последний элемент. Это позволяет итерировать список или вставить в начале или в конце.

Существует 4-й класс ConstIterator, который похож на Iterator, но для доступа const.

Примечание: Это минимально проверено. Остальные ошибки оставляются читателю для исправления.

---

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_; 
};