C++ synthesize linked list in constexpr

Question

I have the following problem, consider a linked list like this:

struct Element {
 struct Element* const next; // the const is required here

 constexpr Element(struct Element* _nxt)
 : next(_nxt)
 { }
};

struct Element* const nil = NULL;

// there are a lot of subclasses for Element, like this
struct Car: public Element {
 int speed;
 
 constexpr Car(int _speed, Element* nxt = nil)
 : Element(nxt)
 , speed(_speed)
 { }
};

This linked list has to be "synthesized" in a constexpr container like this. Note that all the different subclasses can be saved in this container.

template <typename... Args>
struct ElementContainer: public tuple<Args...> {´
 struct Element fst;

 constexpr /* important! */ ElementContainer(Args&&... args)
 : tuple<Args...>(forward(Args)(args)... /* I need to provide the correct address of the next element here */ )
 , fst(/* how do I assign this ? */ nil)
 { }
};

The usage of this function should be like this:

constexpr ElementContainer cont {
 Car(10)
 , OtherSubclass(20, 30, "")
};

The Container should then synthesize the list together, so that the whole construct looks like this in memory:

Container:
 fst -> &Car1
 tuple<Car, OtherSubclass>
  Car:
   nxt -> &OtherSubclass
   speed: 10
  OtherSubclass:
   next -> nil
   /* other data */

Note that both the constness of struct Element and constexpr is required. Why? I use the same struct all over the place and some of them are stored in a read-only-memory, which would result in problems if it were not const.

Answer 1

With addition to a "copy" constructor with additional next element, and use of delegate constructor, you might do

struct Car : public Element
{
    int speed;

    constexpr Car(int _speed, Element* nxt = nullptr)
        : Element(nxt)
        , speed(_speed)
    {
    }

    constexpr Car(const Car& rhs, Element* nxt = nullptr)
        : Element(nxt)
        , speed(rhs.speed)
    {
    }
};

// ...

template<typename... Args>
struct ElementContainer : public std::tuple<Args...>
{
    template<std::size_t... Is, typename Tuple>
    constexpr ElementContainer(std::index_sequence<Is...>, const Tuple& tup)
        : std::tuple<Args...>{Args{std::get<Is>(tup), [this]() {
                                       if constexpr(Is + 1 < sizeof...(Is))
                                       {
                                           return &std::get<Is + 1>(*this);
                                       }
                                       else
                                       {
                                           static_cast<void>(this); // Avoid warning for unused capture
                                           return nullptr;
                                       }
                                   }()}...}
    {
    }

    constexpr ElementContainer(const Args&... args)
        : ElementContainer(std::index_sequence_for<Args...>(), std::tuple{args...})
    {
    }
};

// ...

constexpr ElementContainer cont{Car(10), OtherSubclass(20, 30, "")};

Demo

Clang dislikes to have its own address though as pointer constant...

Answer 2

As @HolyBlackCat suggested in the comments, I would loose the const specifier of the next pointer in element. But since you insist on it, here is an option, it is not pretty, though.

• Instead of deriving ElementContainer from std::tuple, you could have ElementContainer<E, Es...> inherit ElemenContainer<Es...> and have it store an E instance.
• Instead of passing instances of the subclasses to the ElementContainer constructor, all already having an immutable next pointer, you would pass in a tuple containing the constructor arguments, excluding the optional nxt pointer.
• In the constructor of ElementContainer<E, Es...>, you can static_cast this to the base class, get the pointer of its held element and pass it as additional argument to the constructor of the held E attribute.

// construct a new Element from a tuple of constructor arguments and a pointer to next

template <typename T, typename Tup, size_t... I>
constexpr T new_element_impl(Tup const& tup, Element* nxt, std::index_sequence<I...>)
{
    return T(std::get<I>(tup)..., nxt);
}

template <typename T, typename... Args>
constexpr T new_element(std::tuple<Args...> const& args, Element* nxt) 
{
    return new_element_impl<T>(args, nxt, std::make_index_sequence<sizeof...(Args)>{});
}

// define ElementContainer via "linked inheritence"

template <typename E, typename... Es>
struct ElementContainer : ElementContainer<Es...>
{
    template <typename Tuple, typename... Tuples>
    constexpr ElementContainer(Tuple const& tup, Tuples const&... tups)
     : ElementContainer<Es...>(tups...)
     , node(new_element<E>(tup, &static_cast<ElementContainer<Es...>&>(*this).node))
    {}

    E node;
};

template <typename E>
struct ElementContainer<E> {

    template <typename... Args>
    constexpr ElementContainer(std::tuple<Args...> const& tup) 
     : node(new_element<E>(tup, nil))
    {}

    E node;
};

You can instantiate via

constexpr ElementContainer<Car, OtherSubclass> cont {
  std::forward_as_tuple(10),
  std::forward_as_tuple(20, 30, "")
};

Now there might be able to tune this answer with some dark magic for automatic template argument deduction, but I will leave that as an exercise.

Godbolt link

Addendum

I couldn't resist, here is a solution with argument deduction: Godbold link

Creating the container would look like this:

constexpr ElementContainer cont {
  insert<Car>(10),
  insert<OtherSubclass>(20, 30, "")
};