C++ How to avoid friend template functions with home-made intrusive lists

Question

I need an intrusive, sorted, double-linked list. I do not want to use boost::intrusive, so I'm doing this myself and running into an issue

For a doubly-linked list there are several operations, here is just one of them which will help to illustrate my point:

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

Now suppose I have a set of objects that are in one such list BUT I want their guts private:

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

Now I create my List (please ignore the fact that when the list is empty there will be a nullptr exception...).

struct List
{
    Object *first_, *last_;

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

This will not compile because prev_ and next_ are private and insertAfter does not have access. It can be solved easily with this:

// 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);
    }
};

But this opens an access hole such that anyone can use insertAfter to affect Object's private members. What I really want is for List to be a friend of Object. I could solve this by not using templates for my linked list operation (use plain macros instead) but this obviously has its downside. What's the right way to go here?

Answer 1

How about something along these lines?

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() {}

I can't see how it's really less offensive than what you've been doing already, though: template code is inline anyway, so you can't stop people from rewriting your class to their liking. Just relax and have reasonable degree of trust in your clients :)

Answer 2

You may do encapsulate the intrusive data, something like:

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

};

And then in your Object:

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

As all things in ListData are private, user can't do anything with listData_ but can be accessed by List which is friend.