为数据缺少默认构造函数的链表创建节点

Question

我正在尝试实现一个表示双向链表的 class，并且我有一个函数 createNode()，其中 returns 一个新的 Node（模板化class) 及其所有成员都已初始化。此函数将用于创建已知大小但未向其传递数据的链表。对于大多数数据类型，这都有效。但是，这 不适用于 没有默认构造函数的 class es，因为它们不能在没有参数的情况下进行初始化。这是展示此内容的最小代码：

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;
}

基本上，我的最终目标是能够创建一个链表，该链表可以保存未初始化的节点，同时跟踪哪些节点已初始化或未初始化。我记得在我的一本旧教科书中读过有关解决此问题的方法，该方法涉及使用分配器（用于处理 construction/destruction 个对象），但我完全不记得确切的技术。那我该怎么办呢？

Answer 1

您所问的实际上是不可能的——默认构造一个没有默认构造函数的对象。也许考虑在 createNode() 中添加一个 T nodeValue 参数？或者更改 Node 本身，这样它就不再保存一个对象，而是保存一个指向该对象的指针。这看起来像是内存管理的噩梦，但它可以工作。

Answer 2

如果您可以访问 C++17，请使用 std::optional<T>，否则请使用 boost::optional<T>。

template<typename T>
struct Node
{
    Node* prev;
    Node* next;
    std::optional<T> value;  // or boost::optional<T> value;
};

template<typename T>
Node<T>* createNode()
{
    return new Node<T>{ nullptr, nullptr, std::nullopt /* or boost::none */ };
}

如果您无法访问 C++17 并且不想包含 boost，您可以使用类似这样的东西来构建自己的 optional 模板：

struct nullopt_t {};
nullopt_t nullopt;

template <typename T>
class optional
{
public:
    template <typename... Args>
    optional(Args&&... args)
        : ptr{new ((void*)&storage) T(std::forward<Args>(args)...)}
    {}

    optional(nullopt_t)
        : ptr{nullptr}
    {}

    ~optional()
    {
        if (ptr) {
            ptr->~T();
        }
    }

    optional& operator=(T obj)
    {
        if (ptr) {
            *ptr = std::move(obj);
        } else {
            ptr = new ((void*)&storage) T(std::move(obj));
        }
        return *this;
    }

    explicit operator bool()
    {
        return ptr != nullptr;
    }

    T& value()
    {
        if (!ptr) {
            throw std::exception();
        }
        return *ptr;
    }

    // Other const-correct and rvalue-correct accessors left
    // as an exercise to the reader
private:
    std::aligned_storage_t<sizeof(T), alignof(T)> storage;
    T* ptr;
};

Live Demo

Answer 3

您可以使用 placement new 稍后将对象放置在预分配的内存中。

它只是将内存分配与对象的构造分开。因此，您可以在 Node 中声明一个占用内存但不构造对象的成员，因为它需要参数。稍后您可以使用所需的参数构造对象，但不使用 new 分配内存，而是使用 placement new 仅使用已在 Node.

中分配的内存调用构造函数

所以下面是一个自制的例子std::optional. In n3527你可以找到更多关于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

稍作改动，使用 reinterpret_cass，您还可以使用 typename std::aligned_storage<sizeof(T), alignof(T)>::type value; - Live Demo

Allocators 管理内存，您将无法在 class 中包含（聚合）对象并且必须使用指针和第二次分配，除非您使用分配器放置整个 Node.

John Lakos 在 YouTube 上有关于分配器的有趣演示 - CppCon 2017 Local 'Arena' Memory Allocators part 1 and 2。

为数据缺少默认构造函数的链表创建节点

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

c++

initialization

linked-list

default-constructor

c++14