时间戳

首页 > 解决方案 > 如何在C++中创建一个没有动态内存分配的链表作为模板

c++ - 如何在C++中创建一个没有动态内存分配的链表作为模板

问题描述

我开始阅读《Hands-On System Programming in C++》一书，并尝试使用没有动态内存分配的模板创建以下链表。但是每次我尝试构建链表时，除了必须用 new 分配内存之外别无他法 - 我将如何创建一个新节点？

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

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

“这些类型的链表（和其他数据结构）在互联网上有几种实现，它们提供了链表的通用实现，而不需要动态分配数据。” 我在 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++ 模板的全文：C++ 中的动手系统编程

C++ 中使用的模板

模板编程通常是 C++ 的一个被低估的、被误解的补充，没有得到足够的信任。大多数程序员只需尝试创建一个通用链表即可了解原因。

C++ 模板使您能够定义代码，而无需提前定义类型信息。

在 C 中创建链表的一种方法是使用指针和动态内存分配，如以下简单示例所示：

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

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

在前面的示例中，我们使用 void * 将数据存储在链表中。如何使用它的示例如下：

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

这种方法有几个问题：

这种类型的链表显然不是类型安全的。数据的使用和数据的分配是完全不相关的，需要程序员使用这个链表来无误地管理这一切。节点和数据都需要动态内存分配。如前所述，内存分配很慢，因为它们需要系统调用。通常，此代码难以阅读且笨拙。

创建通用链表的另一种方法是使用宏。这些类型的链表（和其他数据结构）在互联网上流传着多种实现，它们提供了链表的通用实现，而无需动态分配数据。这些宏为用户提供了一种方法来定义链表将在编译时管理的数据类型。

除了可靠性之外，这些方法的问题在于这些实现使用宏以一种不太优雅的方式来实现模板编程。也就是说，在C语言中加入泛型数据结构的解决方案是使用C语言的宏语言手动实现模板编程。程序员最好只使用 C++ 模板。

在 C++ 中，可以创建像链表这样的数据结构，而无需在声明链表之前声明它所管理的类型，如下所示：

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

public:

    ...

private:

    node m_head; };

在前面的示例中，我们不仅能够创建一个没有宏或动态分配的链表（以及使用 void * 指针带来的所有问题），而且我们还能够封装功能，提供更简洁的实现和用户 API。

经常对模板编程提出的一个抱怨是它生成的代码量。大多数来自模板的代码膨胀通常源于编程错误。例如，程序员可能没有意识到整数和无符号整数不是同一种类型，从而在使用模板时导致代码膨胀（因为创建了每种类型的定义）。

即使不考虑这个问题，使用宏也会产生同样的代码膨胀。天下没有免费的午餐。如果您想避免使用动态分配和类型转换，同时仍然提供通用算法，您必须为您计划使用的每种类型创建一个算法实例。如果可靠性是您的目标，那么允许编译器生成确保您的程序正确执行所需的代码比缺点更重要。

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

标签： c++templateslinked-listsystems-programmingstatic-memory-allocation

解决方案

除了必须用 new 分配内存之外别无他法 - 我还要如何创建一个新节点？

您可以声明一个变量。或者，您可以使用placement-new 在非动态内存中创建一个动态对象。

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

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

为动态对象重用非动态存储要复杂得多。我推荐一种使用预先存在的实现的结构化方法，例如std::list使用自定义分配器。

推荐阅读