1 C++使用模板和智能指针构建一个双向链表工具类

本文使用模板和智能指针构建一个双向链表工具模板类DoubleLinkedList<T>，在链表的节点Node内部使用T用于接受模板参数，当前节点的上一个节点使用std::shared_ptr，为防止节点与节点之间的std::shared_ptr循环引用问题，避免造成内存泄漏，当前节点的下一个节点使用std::weak_ptr，具体的代码如下文所示。

1.1 双向链表工具类

DoubleLinkedList.h

#ifndef DOUBLE_LINKED_LIST_H_
#define DOUBLE_LINKED_LIST_H_

#include <vector>
#include <memory>
#include <iostream>

template<typename T>
struct Node {
    explicit Node(T val)
        : value{ val }
    {}
    ~Node() {
        std::cout << "Node " << value << " destroyed\n";
    }

    Node(const Node&) = default;
    Node(Node&&) = default;
    Node& operator=(const Node&) = default;
    Node& operator=(Node&&) = default;

    T value;
    std::shared_ptr<Node> next = nullptr;
    std::weak_ptr<Node> previous; // 使用std::weak_ptr防止std::shared_ptr循环引用，避免内存泄漏
};

template<typename T>
class DoubleLinkedList {
public:
    void PushFront(T x);
    void PushBack(T x);
    std::vector<T> GetNodesForward();
    std::vector<T> GetNodesReverse();
private:
    std::shared_ptr<Node<T>> front = nullptr;
    std::shared_ptr<Node<T>> back = nullptr;
};

template<typename T>
void DoubleLinkedList<T>::PushFront(T x)
{
    const auto n = std::make_shared<Node<T>>(x);
    if (not front) {
        front = n;
        back = n;
    }
    else {
        front->previous = n;
        n->next = front;
        front = n;
    }
}

template<typename T>
void DoubleLinkedList<T>::PushBack(T x)
{
    const auto n = std::make_shared<Node<T>>(x);
    if (not back) {
        front = n;
        back = n;
    }
    else {
        back->next = n;
        n->previous = back;
        back = n;
    }
}

template<typename T>
std::vector<T> DoubleLinkedList<T>::GetNodesForward()
{
    auto temp = front;
    std::vector<T> out;
    while (temp) {
        out.push_back(temp->value);
        temp = temp->next;
    }
    return out;
}

template<typename T>
std::vector<T> DoubleLinkedList<T>::GetNodesReverse()
{
    auto temp = back;
    std::vector<T> out;
    while (temp) {
        out.push_back(temp->value);
        temp = temp->previous.lock();
    }
    return out;
}

#endif // !DOUBLE_LINKED_LIST_H_

1.2 双向链表工具类使用示例

#include <iostream>
#include "DoubleLinkedList.h"

class Animal
{
public:
    Animal()
        :m_Age(0)
    {

    }
    Animal(int age)
        :m_Age(age)
    {

    }
    virtual~Animal()
    {

    }

    void SetAge(int age)
    {
        m_Age = age;
    }

    int GetAge()
    {
        return m_Age;
    }
private:
    int m_Age;

};

template<typename T>
void PrintVectorDouble(const std::vector<T>& vec)
{
    for (int i = 0; i < vec.size(); ++i)
    {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;
}

template<typename T>
void PrintVectorClass(const std::vector<T>& vec)
{
    for (int i = 0; i < vec.size(); ++i)
    {
        std::cout << vec[i]->GetAge() << " ";
    }
    std::cout << std::endl;
}

int main()
{
    // double
    DoubleLinkedList<double> double_linked_list;
    for (int i = 0; i < 4; ++i)
    {
        double_linked_list.PushFront(1.1 * i);
    }

    PrintVectorDouble(double_linked_list.GetNodesForward());

    PrintVectorDouble(double_linked_list.GetNodesReverse());

    for (int i = 0; i < 4; ++i)
    {
        double_linked_list.PushBack(1.1 * i);
    }

    PrintVectorDouble(double_linked_list.GetNodesForward());

    PrintVectorDouble(double_linked_list.GetNodesReverse());

    // Animal
    DoubleLinkedList<std::shared_ptr<Animal>> animal_linked_list;
    for (int i = 0; i < 4; ++i)
    {
        animal_linked_list.PushFront(std::make_shared<Animal>(i));
    }

    PrintVectorClass(animal_linked_list.GetNodesForward());

    PrintVectorClass(animal_linked_list.GetNodesReverse());

    for (int i = 0; i < 4; ++i)
    {
        animal_linked_list.PushBack(std::make_shared<Animal>(i));
    }

    PrintVectorClass(animal_linked_list.GetNodesForward());

    PrintVectorClass(animal_linked_list.GetNodesReverse());

    return 0;
}

结果输出

3.3 2.2 1.1 0
0 1.1 2.2 3.3
3.3 2.2 1.1 0 0 1.1 2.2 3.3
3.3 2.2 1.1 0 0 1.1 2.2 3.3
3 2 1 0
0 1 2 3
3 2 1 0 0 1 2 3
3 2 1 0 0 1 2 3
Node 00000000004F9060 destroyed
Node 00000000004F9000 destroyed
Node 00000000004F8FA0 destroyed
Node 00000000004F8F40 destroyed
Node 00000000004F90C0 destroyed
Node 00000000004F9120 destroyed
Node 00000000004F9180 destroyed
Node 00000000004F91E0 destroyed
Node 3.3 destroyed
Node 2.2 destroyed
Node 1.1 destroyed
Node 0 destroyed
Node 0 destroyed
Node 1.1 destroyed
Node 2.2 destroyed
Node 3.3 destroyed

参考链接