0

我需要一个侵入性的、排序的、双链表。我不想使用 boost::intrusive，所以我自己这样做并遇到问题

对于双向链表，有几个操作，这里只是其中一个有助于说明我的观点：

template<typename LIST, typename NODE>
void insertAfter(LIST *list, NODE *node, NODE *newNode)
{
    newNode->prev_ = node;
    newNode->next_ = node->next_;
    if(nullptr == node->next_)
        list->last_ = newNode;
    else
        node->next_->prev_ = newNode;
    node->next_ = newNode;
}

现在假设我有一组对象在一个这样的列表中，但我希望他们的胆量是私有的：

struct Object
{
private:
    Object *prev_, *next_;
};

现在我创建了我的列表（请忽略当列表为空时会出现 nullptr 异常的事实......）。

struct List
{
    Object *first_, *last_;

    void addObject(Object *o)
    {
        insertAfter(this, last_, o);  // not correct when list empty
    }
};

这不会编译，因为 prev_ 和 next_ 是私有的并且 insertAfter 没有访问权限。可以通过以下方式轻松解决：

// Fwd decl
struct List;

struct Object
{
    friend void insertAfter<List, Object>(List *, Object *, Object *);
private:
    Object *prev_, *next_;
};

struct List
{
    Object *first_, *last_;

    void addObject(Object *o)
    {
        insertAfter(this, last_, o);
    }
};

但这打开了一个访问漏洞，任何人都可以使用 insertAfter 来影响 Object 的私有成员。我真正想要的是让 List 成为 Object 的朋友。我可以通过不将模板用于我的链表操作（使用普通宏）来解决这个问题，但这显然有其缺点。去这里的正确方法是什么？

4

2 回答 2

1

这些方面的东西怎么样？

template<class ObjectType>
class List
{
    ObjectType *first_, *last_;

public:
    void addObject(ObjectType *o)
    {
        insertAfter(this, last_, o);
    }

    void insertAfter(ObjectType *node, ObjectType *newNode)
    {
        newNode->prev_ = node;
        newNode->next_ = node->next_;
        if(nullptr == node->next_)
            this->last_ = newNode;
        else
            node->next_->prev_ = newNode;
        node->next_ = newNode;
    }
};

class Object
{
private:
    Object *prev_, *next_;

    friend class List<Object>;
};

int main() {}

不过，我看不出它真的不像你已经做的那样令人反感：模板代码无论如何都是内联的，所以你不能阻止人们根据他们的喜好重写你的类。放松一下，对你的客户有合理的信任:)

于 2014-01-24T12:42:50.347 回答
0

您可以封装侵入性数据，例如：

template <typename Object>
class List
{
public:
    class PrivateData
    {
        friend class List;
    public: // minimal stuff which should be public go here
        PrivateData() : prev_(nullptr), next_(nullptr) {}
    private:
        // other stuff
        Object *prev_, *next_;
    };

    // Other stuff

};

然后在你的对象中：

class Object
{
public:
    List<Object>::privateData listData_;
private:
    // internal data.
};

由于里面的所有东西ListData都是私有的，用户不能做任何事情，listData_ 但可以被谁List是朋友访问。

于 2014-01-24T12:25:43.083 回答