Указатель на член класса в качестве параметра шаблона (с типом следующего класса)
Я пытаюсь определить внутренний список как класс шаблона, который имеет функцию-тип 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;
^
С помощью препроцессора Макроса, что я хочу, выглядит так:
#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;
}
Так может ли это быть выражено с помощью шаблонов вообще?
Решение
Я нашел решение. Это не на 100% идеально, но близко.
Идея состоит в том, чтобы иметь 3 класса:
class Item;
template <class T, Item T::*M> class Iterator;
template <class T, Item T::*M> class Head;
Класс Item содержит ссылки next / prev, которые образуют фактический список в памяти. Это не включает тип контейнера и положение списка внутри контейнера и (само по себе) небезопасно. Но у предмета нет способа изменить список. Все изменения выполняются через итератор. Даже построение выполняется с использованием Head, чтобы получить Iterator и инициализировать следующие / prev указатели.
Класс Iterator может быть создан из контейнера T и имеет операторы ++, -, == и! =, Могут вставлять контейнер в текущую позицию или перемещать контейнер за другим итератором в свой собственный список. Итератор также имеет оператор *, который возвращает текущий контейнер и оператор bool, чтобы сказать, достигнут ли конец списка.
Класс Head содержит специальный элемент head и tail с prev == NULL и next == NULL соответственно. Они особенные, поскольку они не находятся внутри экземпляра контейнера T и отмечают начало и конец списка. Помимо удержания конечных маркеров, Head предоставляет методы для создания итераторов, указывающих на элементы head, tail, first и last. Это позволяет перебирать список или вставлять в начале или в конце.
Существует 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_;
};
Другие решения