c++ - 如何实现避免未定义行为的侵入式链表？

Question

几年来我第三次发现自己需要一个侵入式链表来处理一个不允许提升的项目(询问管理层...)。

第三次我发现我拥有的侵入式链表实现完美运行，但我真的不喜欢它使用未定义的行为 - 即将指向列表节点的指针转换为指向包含该列表节点的对象。

那个糟糕的代码目前看起来像这样:

struct IntrusiveListNode {
    IntrusiveListNode * next_;
    IntrusiveListNode * prev_;
};

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

    IntrusiveListNode root_;
};

我不在乎有多丑 nodeToItem_得到，但我想保留 IntrusiveList 的公共(public)接口(interface)和语法相同。具体来说，我想使用 IntrusiveList<Test, &Test::node_> 指定列表类型的类型。而不是 IntrusiveList<Test, offsetof(Test, node_)> .

快到 2016 年了 - 有没有办法在不调用未定义行为的情况下做到这一点？

---

编辑:我想在这里总结的评论中有一些建议的解决方案(涉及列表的不同结构):

1. 存在未定义的行为，因为该语言似乎具有任意限制，阻止反向使用成员指针。

2. 在 IntrusiveListNode 中存储一个指向包含类的附加指针.这可能是目前最干净的解决方案(无需更改接口(interface))，但确实需要在每个列表节点中添加第三个指针(可能进行小的优化)。

3. 源自 IntrusiveListNode并使用 static_cast .在提升中，这是 base_hook侵入式链表的版本。我想坚持 member_hook版本以避免引入多重继承。

4. 存储指向下一个和上一个包含类的指针，而不是指向 IntrusiveListNode 内的下一个和上一个列表节点的指针.这使得在侵入列表中创建根节点变得困难。列表必须包含 T 的完整实例化。 (这是不可能的，例如如果 T 是抽象的)，或者列表的末尾需要是一个空指针(这会破坏 --list.end() ，只允许向前迭代)。

5. Boost 侵入式列表有 member_hook以某种方式工作的版本，但尚未理解实现(并且它可能还依赖于未定义的行为)。

问题仍然存在:是否可以创建一个具有双向迭代支持、没有未定义行为和“不必要”内存开销的侵入式基于成员的列表？

Answer 1

我会回避这个问题并使用 node<T>含有合适的成员链接范围。应对双向、侵入性列表我会使用不对称的 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>包含 node<T>使用next指向第一个元素的指针。这是相当的直截了当:给定一个指针 p到 T下一个链接可以使用 (p->*L).next 遍历节点.然而，而不是使用 T* 直接导航列表, 一个 iterator<T, L>实际上使用指向 node<T> 的指针:虽然这不是必需的前向遍历，它支持后向遍历和插入列表中的任何位置，无需对列表头进行特殊处理。

复制构造函数和复制赋值被定义为什么都不做在复制节点时避免半插入节点。取决于节点的需求可能更合理= delete这些操作。但是，这与手头的问题无关。

迭代器只使用指向 node<T> 的指针。谁的next当前节点的成员点。对于第一个元素列出这是指向 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已经指向 node<T>落后迭代只需要替换当前的node<T>与 prev元素。

最后，这留下了一个维护开头和结尾的列表的名单。处理双向访问和相应的访问最后一个节点会增加一些复杂性，并且需要实际上有一个专用节点。这是一个实现(其中没有经过彻底测试:我可能弄乱了一些链接):

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

几乎没有其他方法可以避免做任何时髦的事情访问封闭类。以上避免了几个条件。假设我设法设置适当的链接更正代码不会依赖任何实现定义或未定义的行为。

你会像这样使用列表:

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