Creating a Node for a Linked List where the Data Lacks a Default Constructor

Question

I am trying to implement a class that represents a doubly-linked list, and I have a function createNode() which returns a new Node (A templated class) with all its members initialized. This function is going to be used to create linked lists where the size is known, but no data has been passed to it. For most data types, this works. However, this does not work for classes without default constructors, since they cannot be initialized without parameters. Here is the minimal code that exhibits this:

class Test // A class without a default constructor
{
public:
    Test(int value) : value_{ value } { };
private:
    int value_;
};

template<typename T>
struct Node
{
    Node* prev;
    Node* next;
    T value;
};

template<typename T>
Node<T>* createNode()
{
    return new Node<T>{ nullptr, nullptr, T() }; // How do I change T() so
                                                 // that I can use classes
                                                 // without default constructors?
}

int main()
{
    Node<Test>* testNode = createNode<Test>();
    delete testNode;
}

Basically, my final goal is to be able to create a linked list which can hold uninitialized nodes while keeping track of which nodes are initialized or not. I remember reading in an old textbook of mine about a method for solving this problem that involves using allocators (Which are used for handling construction/destruction of objects), but I don't remember the exact technique at all. So how should I go about this?

Answer 1

You can use placement new to place the object later in a pre-allocated memory.

It's just about splitting the memory allocation from the construction of the objects. So you can declare a member in your Node that takes memory but do not construct object because it needs parameter. Later you can construct the object with the needed parameters but not allocate memory with new but use placement new to just call the constructor with memory already allocated within the Node.

So following is an example of a self-made std::optional. In n3527 you can find more details about std::optional.

#include <vector>
#include <functional>
#include <iostream>
#include <algorithm>
#include <string>
#include <memory>

using namespace std;

class Test // A class without a default constructor
{
public:
    Test(int value) : value_{ value } { };
//private:
    int value_;
};

template<typename T>
struct Node
{
    Node* prev;
    Node* next;

    bool empty = true;
    union {
        T t;
    } value;    // Could be replaced with typename std::aligned_storage<sizeof(T), alignof(T)>::type value;

    // need a constructor that inits the value union and activate a field
    // Node()

    ~Node() {
        if (!empty) {
            value.t.~T();
        }
    }
    template<typename... Args>
    void setValue(Args... args) {
        if (!empty) {
            value.t.~T();
        }
        new (&value.t) T(std::forward<Args...>(args...));
        empty = false;
    }

    T& getValue() {
        // TODO:
        if (empty) {
            //throw
        }
        return value.t;
    }
};

template<typename T>
Node<T>* createNode()
{
    return new Node<T>{ nullptr, nullptr }; // How do I change T() so
                                                 // that I can use classes
                                                 // without default constructors?
}

int main()
{
    Node<Test>* testNode = createNode<Test>();
    testNode->setValue(42);
    if (!testNode->empty) {
        std::cout << testNode->getValue().value_;
    }
    delete testNode;
    return 0;
}

Live Demo

With few small changes and with reinterpret_cass you can also use typename std::aligned_storage<sizeof(T), alignof(T)>::type value; - Live Demo

Allocators manage the memory and you will not be able include (aggregate) the object in your class and have to use pointers and second allocation except you use allocator to place the entire Node.

There are interesting presentation form John Lakos about allocators on YouTube - CppCon 2017 Local 'Arena' Memory Allocators part 1 and 2.