如何实现一个避免未定义行为的侵入式链表？

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相同.具体来说,我想指定列表类型的类型IntrusiveList<Test, &Test::node_>而不是IntrusiveList<Test, offsetof(Test, node_)>.

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

---

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

1. 生活在未定义的行为中,因为该语言具有看似任意的限制,可以防止反向使用成员指针.

2. 在其中存储指向包含类的附加指针IntrusiveListNode.这当前可能是最干净的解决方案(不需要更改接口),但确实需要在每个列表节点中使用第三个指针(可能有小的优化).

3. 衍生IntrusiveListNode和使用static_cast.在boost中,这是base_hook一个侵入式链表的版本.我想坚持使用该member_hook版本以避免引入多重继承.

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

5. 提升侵入列表有一个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";
}