How to implement an intrusive linked list that avoids undefined behavior?

The question remains: is it possible to make an intrusive member-based list with bidirectional iteration support, no undefined behavior, and no "unnecessary" memory overhead?

What you are trying to do is take a non-static data member of a C++ object, and convert it to a pointer to its containing class. In order to do that, you have to do some operation of the form:

node_ptr *ptr = ...;
auto p = reinterpret_cast<char*>(ptr) + offset;
T *t = reinterpret_cast<T*>(p);

To make this operation legal C++, you need all of the following to be well-defined:

1. Getting an byte offset from the particular NSDM for the node to the T that contains it.
2. Applying that offset to a pointer-to-a-member will result in a pointer value that is legal to cast to its owning type T.

Item 1 is only possible in well-defined C++ via offsetof; the standard provides no other way to compute that offset. And offsetof requires the type (in this case T) to be standard layout.

Of course, offsetof requires the name of the member as a parameter. And you can't pass parameter names through template arguments and the like; you have to do it through a macro. Unless you're willing to force the user to name the member in a specific way.

So there are your restrictions: T must be standard layout, and you have to either use a macro instead of a direct function call, or you must force the user to use a specific name for the member. If you do this, you should be safe, according to C++.

Here's what the code would look like:

struct intrusive_list_node
{
  intrusive_list_node *next;
  intrusive_list_node *prev;

  template<typename T, size_t offset> T *convert()
  {
    auto p = reinterpret_cast<char*>(this); //Legal conversion, preserves address.
    p -= offset; //Legal offset, so long as `offset` is correct
    return reinterpret_cast<T*>(p); //`p` has the same value representation as `T*` did originally, so should be legal.
  }
}

#define CONVERT_FROM_MEMBER(node, T, member_name) node->convert<T, offsetof(T, member_name)>()

If you don't mind changing the IntrusiveListNode type, you can have a node contain a handle pointing to the previous / next node - you'll only have to do the node -> handle lookup, not the reverse.

template<typename Node>
struct IntrusiveListHandle {
    Node *next = nullptr;
    // and Node* prev, etc ...
};

template<typename Node, IntrusiveListHandle<Node> Node::*handle>
struct IntrusiveList {
    Node *first;    

    static Node *next(Node *n) {
        auto h = (n->*handle).next;
    }
};

Usage example:

#include <iostream>

struct Test {
    IntrusiveListHandle<Test> handle;
    std::string value;

    Test(const std::string &v): value(v) {}
};

template<typename IntrusiveList>
void print(const IntrusiveList &list) {
    for (Test *n = list.first; n; n = list.next(n)) {
        std::cout << n->value << "\n";
    }
}

int main() {
    Test hello("hello");    
    Test world("world!");
    hello.handle.next = &world;
    IntrusiveList<Test, &Test::handle> list;
    list.first = &hello;
    print(list);
}

You should avoid undefined behaviour at all costs as compilers are getting smarter and smarter in exploiting UB for optimization - code that works fine now may suddenly break with the next compiler update.

I see that you mentioned reverse iteration. --end() would not work with this code, but the usual approach is to provide both a begin()/end() and an rbegin()/rend() pair to allow reverse iteration.

I think you can achieve the benefits using CRTP:

#include <iostream>
using namespace std;

template<typename T>
struct ListNode
{
    ListNode<T>* next;

    // this would be nodeToItem in the list class
    T* value()
    {
        return static_cast<T*>(this);
    }
};

// This would be your abstract base class
struct A: public ListNode<A>
{
    A(int i): x(i) {}
    virtual ~A() = 0;
    int x;
};

inline A::~A() {}

struct B: public A
{
    B(int i): A(i) {}
    virtual ~B() {}
};

template<typename T>
class IntrusiveList {
public:
IntrusiveList(ListNode<T>* ptr): root(ptr) 
{
    ptr->next = nullptr;
}

void append(ListNode<T>* ptr)
{
    ptr->next = root;
    root = ptr;
}

ListNode<T>* begin() {return root;}
private:
ListNode<T>* root;
};

int main() {
    B b(10);
    B b2(11);
    IntrusiveList<A> l(&b);
    l.append(&b2);

    for(ListNode<A>* n=l.begin(); n != nullptr; n = n->next)
    {
         std::cout << n->value()->x << std::endl;
    }
    return 0;
}

Having the elements in more than one list should be possible by using an array of ListNode pointers in the struct, and passing the index of the array to the list class as either a template parameter or constructor argument. Iterator would also need to store the index in the ListNode array.

You can Hardly get the original object with the pointer of one of it's member without invoking UB. Why you absolutely can't? Because a IntrusiveListNode can be hold anywhere. There is no clues that a specific IntrusiveListNode is held in a T and another proof you can't do that: The compiler can't know if the node sent to your function is really held in a T. What you are trying to do is undefined behaviour. The right way to do this would be to add a pointer to it's container in IntrusiveListNode.

template<typename T>
struct IntrusiveListNode {
    IntrusiveListNode * next_;
    IntrusiveListNode * prev_;
    T* item_;
};

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

    IntrusiveListNode<T> root_;
};

If you can't use template for IntrusiveListNode, you can use void* instead of T*

You can see an example of an implementation of an intrusive linked list here

With templates it is hard to do. It is possible with macro's, so the needed members _next, _prev etc are in the scope of the object itself, not inside a separate template object. Using the macro's it is possible to avoid typing in code that is very similar every time. In fact I created a Case tool "ClassBuilder" (http://sourceforge.net/projects/classbuilder/) years ago that writes code using macro's to create data structures that uses intrusive linked lists. In the area I work, the normal templated linked list stuff is just way to slow. In our business, it is normal to work with very large in core data structures which are also very dynamic. Thus lots of removals and additions and searches on the lists. With the tool you totally abstracts from the actual implementation, you just create class diagrams and generate the code from there. In a relative simple test case we did, the run time performance of the generated code was 40s and 400s for a C++ solution using the "normal" STL kind of implementation. A C# implementation of the same test case was aborted after a few hours of running. Its implementation was similar to teh STL one, but this one was hit very hard by the Garbage Collector. Due to the dynamic behavior of the test case all memory that could be reclaimed could only be reclaimed in a full scan.