Как реализовать интрузивный связанный список, который позволяет избежать поведения undefined?

Ответ 1

Я бы поставил задачу и использовал node<T>, содержащий подходящие чтобы связать диапазон. Чтобы иметь дело с двунаправленным, навязчивым list Я использовал бы асимметричный node<T> следующим образом:

template <typename T>
class intrusive::node
{
    template <typename S, node<S> S::*> friend class intrusive::list;
    template <typename S, node<S> S::*> friend class intrusive::iterator;

    T*       next;
    node<T>* prev;
public:
    node(): next(), prev() {}
    node(node const&) {}
    void operator=(node const&) {}
};

Основная идея состоит в том, что list<T, L> содержит a node<T>, используя указатель next, чтобы указать на первый элемент. Это справедливо прямо: дано указатель p на T ссылку на следующую node можно пропустить с помощью (p->*L).next. Однако вместо непосредственно перемещая список с помощью T*, a iterator<T, L> на самом деле использует указатель на node<T>: в то время как это необязательно для прямой обход, он обеспечивает обратный обход и вставки в любом месте в списке без специальной обработки списка.

Конструктор копирования и назначение копии определены как ничего не сделанные для избежания полузагруженных узлов при копировании node. В зависимости от Потребности узлов могут быть более разумными, чем = delete эти операции. Однако это не связано с вопросом.

Итератор просто использует указатель на node<T>, чей next членов в текущем node. Для первого элемента в list это указатель на элемент list<T, L> node<T>. Предполагая, что у вас есть указатель на подходящий node<T>, из него можно создать iterator<T, L>:

template <typename T, intrusive::node<T> T::*Link>
class intrusive::iterator
{
    template <typename S, node<S> S::*> friend class intrusive::list;
    node<T>* current;

public:
    explicit iterator(node<T>* current): current(current) {}
    T& operator*() { return *this->operator->(); }
    T* operator->() { return this->current->next; }
    bool operator== (iterator const& other) const {
        return this->current == other.current;
    }
    bool operator!= (iterator const& other) const {
        return !(*this == other);
    }
    iterator& operator++() {
        this->current = &(this->current->next->*Link);
        return *this;
    }
    iterator operator++(int) {
        iterator rc(*this);
        this->operator++();
        return rc;
    }
    iterator& operator--() {
        this->current = this->current->prev;
        return *this;
    }
    iterator operator--(int) {
        iterator rc(*this);
        this->operator--();
        return rc;
    }
};

Выделение только использует указатель next. То же самое верно для вперед, которая использует указатель next вместе с указатель участника, чтобы получить адрес следующего node<T>. Поскольку итератор prev уже указывает на a node<T> назад итерации просто нужно заменить текущий node<T> на prev.

Наконец, это оставляет список, поддерживающий начало и конец списка. Работа с двунаправленным доступом и соответствующий доступ к последнему node добавляет некоторую сложность и необходимость на самом деле имеют выделенный node. Вот реализация (которая не проверено полностью: возможно, я испортил некоторые ссылки):

template <typename T, intrusive::node<T> T::*Link>
class intrusive::list
{
    node<T> content;

public:
    list() { this->content.prev = &this->content; }
    iterator<T, Link> begin() { return iterator<T, Link>(&this->content); }
    iterator<T, Link> end() { return iterator<T, Link>(this->content.prev); }

    T& front() { return *this->content.next; }
    T& back() { return *(this->content.prev->prev->next); }
    bool empty() const { return &this->content == this->content.prev; }
    void push_back(T& node) { this->insert(this->end(), node); }
    void push_front(T& node) { this->insert(this->begin(), node); }
    void insert(iterator<T, Link> pos, T& node) {
        (node.*Link).next = pos.current->next;
        ((node.*Link).next
         ? (pos.current->next->*Link).prev 
         : this->content.prev) = &(node.*Link);
        (node.*Link).prev = pos.current;
        pos.current->next = &node;
    }
    iterator<T, Link> erase(iterator<T, Link> it) {
        it.current->next = (it.current->next->*Link).next;
        (it.current->next
         ? (it.current->next->*Link).prev
         : this->content.prev) = it.current;
        return iterator<T, Link>(&(it.current->next->*Link));
    }
};

Просто для немного здравомыслия: вот функция, чтобы просто распечатать список:

template <typename T, intrusive::node<T> T::*Link>
std::ostream& intrusive::operator<< (std::ostream& out, intrusive::list<T, Link>& list)
{
    out << "[";
    if (!list.empty()) {
        std::copy(list.begin(), --list.end(), std::ostream_iterator<T>(out, ", "));
        out << list.back();
    }
    return out << "]";
}

Существует несколько других подходов, позволяющих избежать каких-либо фанки доступ к закрывающему классу. Вышесказанное позволяет избежать нескольких условий. Предполагая, что мне удалось установить соответствующие ссылки, исправьте код не будет полагаться на какую-либо определенную реализацию или поведение undefined.

Вы бы использовали следующий список:

class Node {
public:
    intrusive::node<Node> link0;
    intrusive::node<Node> link1;
    int                   n;
    Node(int n): n(n) {}
};
std::ostream& operator<< (std::ostream& out, Node const& n) {
    return out << n.n;
}

int main()
{
    intrusive::list<Node, &Node::link0> l0;
    intrusive::list<Node, &Node::link1> l1;

    Node n[] = { 10, 11, 12, 13, 14, 15 };

    l0.push_front(n[0]);
    l0.push_front(n[1]);
    l0.push_front(n[2]);

    l1.push_back(n[0]);
    l1.push_back(n[1]);
    l1.push_back(n[2]);

    std::cout << "l0=" << l0 << " l1=" << l1 << "\n";
}

Ответ 2

Остается вопрос: возможно ли создать интрузивный список на основе членов с поддержкой двунаправленной итерации, поведение undefined и отсутствие "лишних" накладных расходов памяти?

То, что вы пытаетесь сделать, это взять нестатический член данных объекта С++ и преобразовать его в указатель на его содержащий класс. Для этого вам нужно выполнить некоторую операцию формы:

node_ptr *ptr = ...;
auto p = reinterpret_cast<char*>(ptr) + offset;
T *t = reinterpret_cast<T*>(p);

Чтобы сделать эту операцию законной С++, вам необходимо четко определить следующее:

• Получение смещения байта от конкретного NSDM для node к T, который содержит его.
• Применение этого смещения к указателю-к-члену приведет к значению указателя, которое является законным для его собственного типа T.

Пункт 1 возможен только в хорошо определенном С++ через offsetof; стандарт не дает другого способа вычислить это смещение. И offsetof требует, чтобы тип (в данном случае T) был стандартным расположением.

Конечно, offsetof требует имя члена в качестве параметра. И вы не можете передавать имена параметров через шаблонные аргументы и т.п.; вам нужно сделать это через макрос. Если вы не хотите заставить пользователя называть его определенным образом.

Итак, существуют ваши ограничения: T должен быть стандартным макетом, и вам нужно либо использовать макрос вместо прямого вызова функции, либо вы должны заставить пользователя использовать определенное имя для этого элемента. Если вы это сделаете, вы должны быть в безопасности, согласно С++.

Вот как выглядит код:

struct intrusive_list_node
{
  intrusive_list_node *next;
  intrusive_list_node *prev;

  template<typename T, size_t offset> T *convert()
  {
    auto p = reinterpret_cast<char*>(this); //Legal conversion, preserves address.
    p -= offset; //Legal offset, so long as `offset` is correct
    return reinterpret_cast<T*>(p); //`p` has the same value representation as `T*` did originally, so should be legal.
  }
}

#define CONVERT_FROM_MEMBER(node, T, member_name) node->convert<T, offsetof(T, member_name)>()

Ответ 3

Если вы не возражаете изменить тип IntrusiveListNode, вы можете иметь node содержащий дескриптор, указывающий на предыдущий/следующий node - вам нужно будет только искать node -> handle, а не наоборот.

template<typename Node>
struct IntrusiveListHandle {
    Node *next = nullptr;
    // and Node* prev, etc ...
};

template<typename Node, IntrusiveListHandle<Node> Node::*handle>
struct IntrusiveList {
    Node *first;    

    static Node *next(Node *n) {
        auto h = (n->*handle).next;
    }
};

Пример использования:

#include <iostream>

struct Test {
    IntrusiveListHandle<Test> handle;
    std::string value;

    Test(const std::string &v): value(v) {}
};

template<typename IntrusiveList>
void print(const IntrusiveList &list) {
    for (Test *n = list.first; n; n = list.next(n)) {
        std::cout << n->value << "\n";
    }
}

int main() {
    Test hello("hello");    
    Test world("world!");
    hello.handle.next = &world;
    IntrusiveList<Test, &Test::handle> list;
    list.first = &hello;
    print(list);
}

Вы должны избегать поведения undefined любой ценой, поскольку компиляторы становятся более умными и умными в использовании UB для оптимизации - код, который отлично работает, теперь может внезапно разорваться со следующим обновлением компилятора.

Я вижу, что вы упомянули обратную итерацию. --end() не будет работать с этим кодом, но обычный подход заключается в предоставлении пары begin()/end() и rbegin()/rend(), чтобы разрешить обратную итерацию.

Ответ 4

Я думаю, вы можете достичь преимуществ с помощью CRTP:

#include <iostream>
using namespace std;

template<typename T>
struct ListNode
{
    ListNode<T>* next;

    // this would be nodeToItem in the list class
    T* value()
    {
        return static_cast<T*>(this);
    }
};

// This would be your abstract base class
struct A: public ListNode<A>
{
    A(int i): x(i) {}
    virtual ~A() = 0;
    int x;
};

inline A::~A() {}

struct B: public A
{
    B(int i): A(i) {}
    virtual ~B() {}
};

template<typename T>
class IntrusiveList {
public:
IntrusiveList(ListNode<T>* ptr): root(ptr) 
{
    ptr->next = nullptr;
}

void append(ListNode<T>* ptr)
{
    ptr->next = root;
    root = ptr;
}

ListNode<T>* begin() {return root;}
private:
ListNode<T>* root;
};

int main() {
    B b(10);
    B b2(11);
    IntrusiveList<A> l(&b);
    l.append(&b2);

    for(ListNode<A>* n=l.begin(); n != nullptr; n = n->next)
    {
         std::cout << n->value()->x << std::endl;
    }
    return 0;
}

Наличие элементов в более чем одном списке должно быть возможным с помощью массива указателей ListNode в структуре и передачи индекса массива в класс списка как аргумент шаблона или аргумент конструктора. Итератору также необходимо будет сохранить индекс в массиве ListNode.

Ответ 5

Вы можете легко получить исходный объект с указателем одного из его членов без вызова UB. Почему вы абсолютно не можете? Потому что IntrusiveListNode можно держать где угодно. Нет никаких указаний на то, что конкретный IntrusiveListNode хранится в T и еще одно доказательство, которое вы не можете сделать: компилятор не может знать, действительно ли node, отправленный вашей функции, в T, То, что вы пытаетесь сделать, - это поведение undefined. Правильный способ сделать это - добавить указатель на контейнер в IntrusiveListNode.

template<typename T>
struct IntrusiveListNode {
    IntrusiveListNode * next_;
    IntrusiveListNode * prev_;
    T* item_;
};

template <typename T, IntrusiveListNode<T> T::*member>
class IntrusiveList {
// snip ...
private:
    T & nodeToItem_(IntrusiveListNode<T> & node) {
        return *(node->item_);
    }

    IntrusiveListNode<T> root_;
};

Если вы не можете использовать шаблон для IntrusiveListNode, вы можете использовать void* вместо T*

Вы можете увидеть пример реализации навязчивого связанного списка здесь

Ответ 6

С шаблонами это сложно сделать. Это возможно с помощью макроса, поэтому необходимые члены _next, _prev и т.д. Находятся в области самого объекта, а не внутри отдельного объекта шаблона. Используя макрос, можно избежать ввода кода, который очень сходен каждый раз. На самом деле я создал инструмент Case "ClassBuilder" (http://sourceforge.net/projects/classbuilder/) лет назад, который пишет код с использованием макроса для создания структур данных, которые используют навязчивые связанные списки, В области, в которой я работаю, обычный шаблонный связанный список - это просто способ замедлить работу. В нашем бизнесе нормально работать с очень большими в основных структурах данных, которые также очень динамичны. Таким образом, много изъятий и дополнений и поисков в списках. С помощью инструмента, который вы полностью абстрагируетесь от реальной реализации, вы просто создаете диаграммы классов и генерируете код оттуда. В относительном простом тестовом примере мы выполнили время выполнения сгенерированного кода 40 и 400 для решения С++ с использованием "нормального" типа STL. Реализация С# того же тестового случая была прервана после нескольких часов работы. Его реализация была похожа на STL, но этот был очень сильно поражен сборщиком мусора. Из-за динамического поведения тестового случая вся память, которая могла быть восстановлена, могла быть восстановлена ​​только при полном сканировании.