c++linked-listconstexprstdtuple

C++ synthesize linked list in constexpr


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.


Solution

  • 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...