Как создать связанный список без динамического выделения памяти в качестве шаблона в С++

Я начал работать с книгой Практическое системное программирование на C++ и попытался создать следующий связанный список с шаблоном без динамического выделения памяти. Но каждый раз, когда я пытаюсь создать связанный список, я не нахожу другого способа, кроме как назначить память с помощью new - как еще я мог бы создать новый узел?

Насколько я понимаю автора, существует способ заменить необходимость создания нового узла с помощью шаблонов 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.

Одной из жалоб, которые часто предъявляются к программированию шаблонов, является объем генерируемого кода. Большая часть раздувания кода из шаблонов обычно возникает из-за ошибки программирования. Например, программист может не понимать, что целые числа и целые числа без знака не являются одними и теми же типами, что приводит к раздуванию кода при использовании шаблонов (поскольку создается определение для каждого типа).

Даже помимо этой проблемы использование макросов приведет к такому же раздуванию кода. Бесплатных обедов не бывает. Если вы хотите избежать использования динамического размещения и приведения типов, но при этом предоставлять общие алгоритмы, вам необходимо создать экземпляр вашего алгоритма для каждого типа, который вы планируете использовать. Если надежность является вашей целью, предоставление компилятору возможности генерировать код, необходимый для обеспечения правильного выполнения вашей программы, перевешивает недостатки.

Что я упустил? Заранее спасибо за любую подсказку о том, как я могу динамически создать связанный список без динамического выделения памяти с помощью шаблонов С++?