如何在没有动态内存分配的情况下创建链表作为 C++ 中的模板

Question

我开始阅读《C++ 系统编程实践》一书 我尝试使用没有动态内存分配的模板创建以下链表。但是每次我尝试构建链表时，除了必须使用 new 分配内存之外别无他法 - 我还能如何创建一个新节点？

据我了解，作者有一种方法可以通过使用 C++ 模板 代替创建新节点的需要，因为分配动态内存被认为很慢。 到目前为止，这并不意味着在编译时使用静态内存分配或数组或宏编程，而是在运行时使用相同的灵活性？还是误会？

我错过了什么？预先感谢您提供有关如何在不使用 C++ 模板进行动态内存分配的情况下动态创建链表的任何提示？

“这些类型的链表（和其他数据结构）在 Internet 上流传着多种实现，它们提供了链表的通用实现，无需动态分配数据。 “ 我没有在 C++ 中找到任何内容:(

和

“在前面的例子中，我们不仅可以创建一个没有宏或动态分配的链表（以及所有伴随而来的问题使用 void * 指针），但我们也能够封装功能，提供更清晰的实现和用户 API."

这就是我尝试做的，但我困惑的每一种方式我都必须动态分配内存：

template<typename T>
class MyLinkedList
{
    struct node
    {
        T data;
        node* next = nullptr;
    };

private:
    node m_head;

public:


    void setData(T value)
    {
        if(m_head.next == nullptr){
        m_head.data = value;
        }
    }

    T getData()
    {
        return m_head.data;
    }


};

int main()
{
    MyLinkedList<int> list;
    list.setData(4);
    std::cout << list.getData() << std::endl;



    return 0;
}

本书关于 C++ 模板的全文： Hands-On System Programming in C++

Templates used in C++

Template programming is often an undervalued, misunderstood addition to C++ that is not given enough credit. Most programmers need to look no further than attempting to create a generic linked list to understand why.

C++ templates provides you with the ability to define your code without having to define type information ahead of time.

One way to create a linked list in C is to use pointers and dynamic memory allocation, as seen in this simple example:

struct node  {
    void *data;
    node next; };

void add_data(node *n, void *val);

In the preceding example, we store data in the linked list using void *. An example of how to use this is as follows:

node head; add_data(&head, malloc(sizeof(int)));
*(int*)head.data = 42;

There are a few issues with this approach:

This type of linked list is clearly not type-safe. The use of the data and the data's allocation are completely unrelated, requiring the programmer using this linked list to manage all of this without error. A dynamic memory allocation is needed for both the nodes and the data. As was discussed earlier, memory allocations are slow as they require system calls. In general, this code is hard to read and clunky.

Another way to create a generic linked list is to use macros. There are several implementations of these types of linked lists (and other data structures) floating around on the internet, which provide a generic implementation of a linked list without the need for dynamically allocating data. These macros provide the user with a way to define the data type the linked list will manage at compile time.

The problem with these approaches, other than reliability, is these implementations use macros to implement template programming in a way that is far less elegant. In other words, the solution to adding generic data structures to C is to use C's macro language to manually implement template programming. The programmer would be better off just using C++ templates.

In C++, a data structure like a linked list can be created without having to declare the type the linked list is managing until it is declared, as follows:

template<typename T> class mylinked_list {
    struct node 
    {
        T data;
        node *next;
    };

public:

    ...

private:

    node m_head; };

In the preceding example, not only are we able to create a linked list without macros or dynamic allocations (and all the problems that come with the use of void * pointers), but we are also able to encapsulate the functionality, providing a cleaner implementation and user API.

One complaint that is often made about template programming is the amount of code it generates. Most code bloat from templates typically originates as a programming error. For example, a programmer might not realize that integers and unsigned integers are not the same types, resulting in code bloat when templates are used (as a definition for each type is created).

Even aside from that issue, the use of macros would produce the same code bloat. There is no free lunch. If you want to avoid the use of dynamic allocation and type casting while still providing generic algorithms, you have to create an instance of your algorithm for each type you plan to use. If reliability is your goal, allowing the compiler to generate the code needed to ensure your program executes properly outweighs the disadvantages.

我错过了什么？预先感谢您提供有关如何在不使用 C++ 模板进行动态内存分配的情况下动态创建链表的任何提示？

Answer 1

a find no other way than having to assign memory with new - how else would I create a new node?

您可以声明一个变量。或者，您可以使用 placement-new.

在 non-dynamic 内存中创建一个动态对象

这是使用节点变量的链表的最小示例：

template<class T>
struct node
{
    T data;
    node* next = nullptr;
};

// some function
node<int> n3{3, nullptr};
node<int> n2{2, &n3};
node<int> n1{1, &n2};

---

重用 non-dynamic 动态对象存储要复杂得多。我推荐使用 pre-existing 实现的结构化方法，例如 std::list 和自定义分配器。