CODEWITHSUNDEEP
c++c++17stdlist
conditionalMethod
conditionalMethod

Reputation: 167

How to use std::list as the implementation of an interface for a list that exposes the nodes?

I have the interface of a doubly-linked list that exposes its edges. For example:

template <typename T>
class Listnode
{
public:
    Listnode *prev;
    Listnode *next;
    T val;
};

template <typename T>
class List
{
public:
    Listnode *head;
    Listnode *tail;
    // insert, remove, etc.
};

Assume that external old code uses this interface.

I took the implementation of std::list::sort and imitated it in List. However, it would be nicer to use it, if possible, instead of copying.

Question: Is it possible to use std::list somehow to get the implementation of List::sort? In particular, use std::list::sort to modify the prev-next pointers of the ListNode's of the List such that the List ends up sorted. Well, without essentially duplicating the list inside an std::list.

My answer: It seems to me that it won't be possible since std::list, as far as I can see in the documentation, doesn't expose (see also this other question) the edges between nodes, except traversing them through its iterator, while its implementation of std::list::sort seems to modify directly the edges, or at least it works with the iterators until a call to a method (_M_transfer), like in the GNU implementation.

But I am a beginner. I could be easily be missing something.

Upvotes: 0

Views: 202

Answers (1)

Nicol Bolas
Nicol Bolas

Reputation: 474236

You cannot make std::list conform to what you're trying to do. The closest you could do is have the T in your Listnode type be a std::list<ActualT>::iterator to the element in the std::list. But if this interface is being used by existing code that has its own expectations for what T is, that's not really an option.

Upvotes: 0

Related Questions