用 C++ 创建单向链表 forward list

前言

用 C++ 创建了一个单向链表，用于练习使用现代 C++ 的特性，包括 3 点：

1. 对于容器，使用 std::initializer_list 作为参数创建构造函数。
   C++ Core Guidelines 中，推荐使用花括号 {} 初始化对象，并且对容器推荐使用 std::initializer_list 创建构造函数。
2. 使用智能指针 unique_ptr 。
3. 使用了 copy and move （即 copy and swap 惯用法的改进版）。
   关于 copy and move ，可参见我的另一篇文章
   《C++ 的 copy and swap 惯用法》https://blog.csdn.net/drin201312/article/details/149204977

1. 源码 forward_list.hpp

/*
自定义单向链表。包含功能：
1. 创建链表。
2. 头部插入元素，任意位置的前向插入。
3. 除最后一个元素之外，任意位置的后向插入。
4. 遍历链表并显示。
5. 根据输入位置，删除元素。
6. 根据输入的数值，删除链表中所有相同的元素。
7. 复制链表。
8. 清空链表。
*/

#ifndef FORWARD_LIST_H_
#define FORWARD_LIST_H_
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <memory>
#include <stdexcept>
#include <string>
#include <stack>
#include <utility>

// 链表的节点。
template<typename T>
class Node {
  public:
    Node() = default;
    // 常函数如果返回引用，则必须返回 const 引用。
    const T& get_data() const {  // 返回节点内的数据。
      return data_;  
    }
    // 给节点输入数据。
    void set_data(const T& data) {
      data_ = data;
    }
    // 返回下一个节点地址的 reference。
    std::unique_ptr<Node<T>>& get_next_ptr() {
      return ptr_next_;
    }
    // 夺取下一个节点的 unique_ptr
    void set_next_ptr(std::unique_ptr<Node<T>>&& next_node_ptr) { 
      ptr_next_ = std::move(next_node_ptr);  
    }
  private:
    T data_{};  // 节点内的数据。整数会默认初始化为 0 。
    std::unique_ptr<Node<T>> ptr_next_;  // 下一个节点的地址。
};


template<typename T>  // 必须设置 T，用作 Node 的类型。
class ForwardList {
  public:  // 该部分必须考虑如何处理 7 个函数：4 个构造函数，2 个赋值操作符，1 个析构函数。
    ForwardList() = default;  // 允许使用无括号 ForwardList foo 的形式创建对象。
    // 用 initializer_list 接收任意数量的参数。
    ForwardList(std::initializer_list<T> args) {
      std::cout << "Default initializer_list called.\n";
      // for (auto each : args | std::views::reverse) {  // C++ 20 使用此方式逆序。
      //   std::cout << "each= " << each << "\n";
      //   push_front(each);
      // }
      //  C++ 14 使用下面 std::rbegin 的方式逆序。
      for (auto it = std::rbegin(args); it != std::rend(args); ++it) {
        push_front(*it);
      }
    }
    // 拷贝构造函数，必须手动把链表复制过来。
    ForwardList(const ForwardList& other) {   
      std::cout << "Copy constructor called.\n";
      if (other.nodes_quantity_ != 0) {
        std::stack<T> data_record;  // 记录 other 中的所有 data
        Node<T>* running_node_ptr{other.front_node_ptr_.get()};
        for (size_t index = 0; index < other.nodes_quantity_; ++index) {
          data_record.emplace(running_node_ptr->get_data());
          running_node_ptr = running_node_ptr->get_next_ptr().get();
        }
        while (!data_record.empty()) {  // 根据记录的 data 新建整个链表。
          push_front(data_record.top());
          data_record.pop();
        }
      }
    }
    // 下面使用 copy and move 方法，把两个赋值运算符函数合二为一。
    // 转移 other 的资源，并且 other 应该是用 copy 或 move 新建的一个对象。
    void move_resource(ForwardList&& other) noexcept {
      std::cout << "move_resource called.\n";
      front_node_ptr_ = std::move(other.front_node_ptr_);
      nodes_quantity_ = other.nodes_quantity_;
      // 清理 other 中的资源。对于内置的数值类型， std::move 并不会将其归零，必须手动修改。
      other.nodes_quantity_ = 0;
    }
    // 移动构造函数，把链表资源转移到当前对象。
    ForwardList(ForwardList&& other) noexcept {
      std::cout << "Move constructor called.\n";
      // 初始化列表不能完成所有的转移工作，所以直接调用函数，不使用初始化列表。
      move_resource(std::move(other));  
    };
    // 赋值运算符，把拷贝赋值运算符和移动赋值运算符进行二合一，并且能避免自赋值问题。
    ForwardList& operator=(ForwardList other) {  // other 必须用值传递。
      std::cout << "operator= called.\n";
      move_resource(std::move(other));  
      return *this;
    }
    ~ForwardList() {
      clear();  
    }
    
    // 头部插入一个 node。
    void push_front(const T& data) {  
      std::cout << "@push_front" << "\tdata= " << data << "\n";
      auto new_node_ptr = create_node(data);  // 这里会进行 NRVO 。
      new_node_ptr->set_next_ptr(std::move(front_node_ptr_));
      // 每个新节点，都会成为首节点。
      front_node_ptr_ = std::move(new_node_ptr);
    }
    // 在指定 node 位置的后面再插入一个 node 。
    void insert_after(const size_t node_index, const T& data) { 
      std::cout << "@insert_after, node_index= " << node_index << "\n";
      check_index(node_index); 
      if (nodes_quantity_ == 0) {
        push_front(data);
      } else {
        auto new_node_ptr = create_node(data);  // 这里会进行 NRVO 。
        Node<T>& current_node = goto_node(node_index);
        // 如果返回值是一个 reference，则该函数返回结果属于左值。
        // 下面两个输入参数都是左值，需用 std::move 转换为右值引用。
        new_node_ptr->set_next_ptr(std::move(current_node.get_next_ptr())); 
        current_node.set_next_ptr(std::move(new_node_ptr));
        std::cout << "current_node.get_data()= " << current_node.get_data() << "\n";
      }
    }
    // 在指定 node 的位置，前面再插入一个 node 。
    void insert_before(size_t node_index, const T& data) { 
      std::cout << "@insert_before, node_index= " << node_index << "\n";
      if (node_index == 0) {
        push_front(data);
      } else {  // 第 n 个位置向前插入一个节点，等于第 n-1 位置向后插入一个节点。
        insert_after(node_index - 1, data);
      }
    }
    
    void show_list() const {  // 显示整个链表。
      std::cout << "\nshowing the whole forward list: \n";
      if (nodes_quantity_ == 0) {
        std::cout << "Empty forward list.\n";
      } else {
        // 用到原始指针时，尽量缩小范围。因为只限于这个函数内部，生命周期极短，不会发生内存泄漏。
        Node<T>* running_node_ptr = front_node_ptr_.get();
        for (size_t i = 0; i < nodes_quantity_; ++i) {
          std::cout << "node[" << i << "].data= " << running_node_ptr->get_data() << "\n";
          running_node_ptr = running_node_ptr->get_next_ptr().get();
          }
      }
    }
    // 根据输入的位置 index ，删除元素。
    void delete_by_index(size_t node_index) {
      std::cout << "@delete_by_index, node_index= " << node_index << "\n";
      check_index(node_index); 
      if (nodes_quantity_ != 0) {  // 避开空链表。
        if (node_index == 0) {
          front_node_ptr_ = std::move(front_node_ptr_->get_next_ptr());
        } else {  // 把前一个节点链接到后一个节点即可。
          Node<T>& previous_node = goto_node(node_index - 1);
          previous_node.set_next_ptr(std::move(
            previous_node.get_next_ptr()->get_next_ptr()));
        }
        --nodes_quantity_;
      }
    }
    // 根据输入的值，删除链表中所有具有相同值的 node 。
    void delete_by_value(const T& value) {
      std::cout << "@delete_by_value, value= " << value << "\n";
      std::stack<size_t> index_record;  // 使用一个后进先出的容器来记录 index 。
      Node<T>* running_node_ptr = front_node_ptr_.get();
      for (size_t index = 0; index < nodes_quantity_; ++index) {
        if (running_node_ptr->get_data() == value) {
          index_record.emplace(index);  // 记录当前 index。
        }
        running_node_ptr = running_node_ptr->get_next_ptr().get();
      }
      std::cout << "Found " << index_record.size() << " of " << value << "\n";
      while (!index_record.empty()) {
        size_t index = index_record.top();  // 先删除大的索引，再删除小的索引。
        index_record.pop();  // 必须同时删除对应的 index 。
        delete_by_index(index);
      }
    }
    // 返回链表的大小。
    size_t size() const {
      return nodes_quantity_;
    }
    // 清除链表数据。
    void clear() {
      std::cout << "@clear, clearing the whole forward list.\n";
      while (front_node_ptr_) {  // unique_ptr 只要指向新的资源，原有资源就被释放。
        front_node_ptr_ = std::move(front_node_ptr_->get_next_ptr());
      }
      nodes_quantity_ = 0;
    }

  private:
    // 链表状态有变化时，下面两个成员变量，必须同步更新。
    size_t nodes_quantity_ = 0;
    // 链表为动态大小，因此要把数据放在堆区。
    std::unique_ptr<Node<T>> front_node_ptr_;
    
    // 移动到指定的节点位置，并且返回该节点。从 0 开始计算 node_index 。
    // node_index 可以是 0 ，也可以是最后一个 node 。
    Node<T>& goto_node(size_t node_index) {  
      if (size() == 0) {  // 处理空链表的情况。
        throw std::range_error("The forward list is empty!");
      }
      // 使用 get 返回的原始指针。因为原始指针只存活在这个函数内，生命周期极短，不会造成内存泄漏。
      check_index(node_index);
      Node<T>* running_node_ptr_ = front_node_ptr_.get();
      for (size_t i = 0; i < node_index; ++i) {
        // 获取下一个节点的原始指针。
        running_node_ptr_ = (running_node_ptr_->get_next_ptr()).get();
        }
      return *running_node_ptr_;  // 只能返回堆区对象，不可返回原始指针，避免对象的生命周期管理混乱。
    }
    // 使用输入的数据，创建一个新的 node 。
    std::unique_ptr<Node<T>> create_node(const T& data){
      auto new_node_ptr{std::make_unique<Node<T>>()};
      new_node_ptr->set_data(data);
      ++nodes_quantity_; 
      return new_node_ptr;  // 返回局部变量，编译器进行 NRVO 。
    }
    // 不允许索引大于节点数量。
    void check_index (const size_t node_index) const{  
      // 始终允许 node_index 为 0 ，无须判断节点数量。
      if ((node_index != 0) && (node_index >= nodes_quantity_)) {
        throw std::range_error("node_index + 1 > nodes_quantity_ \nnode_index= " + 
          std::to_string(node_index) + " , nodes_quantity_= " + 
          std::to_string(nodes_quantity_));
      }
    }
};
#endif  // FORWARD_LIST_H_

2. 使用示例

#include "forward_list.hpp"
#include <cctype>
#include <iostream>

void insert_and_show() {
  ForwardList<int> foo;
  foo.push_front(2025);

  ForwardList<int> list{2025, 888};
  list.insert_before(0, 200);
  list.insert_before(0, 200);
  list.insert_after(3, 300);  
  list.insert_after(3, 300);  
  list.show_list();
  list.show_list();
}

void delete_and_show() {
  ForwardList<int> list{100, 2025, 888, 2025};
  // list.delete_by_index(1);
  list.delete_by_index(0);
  list.show_list();

  list.delete_by_value(200);
  list.show_list();
  list.delete_by_value(2025);
  list.show_list();
}

void copy_and_move() {
  ForwardList<int> list{2025, 888};

  ForwardList<int> foo;
  std::cout << "\nfoo = list\n";
  foo = list;  // 调用拷贝赋值运算符。
  std::cout << "\nfoo.show_list()= ";
  foo.show_list();
  
  ForwardList<int> bar;
  std::cout << "\nbar = std::move(list)\n";
  bar = std::move(list);  // 调用移动赋值运算符。
  std::cout << "\nbar.show_list()= ";
  bar.show_list();

  // 再查看原有链表。
  std::cout << "\nlist.show_list()= ";
  list.show_list();
}
void clear_and_show() {
  ForwardList<int> foo{2025, 888};
  std::cout << "\nfoo.show_list()= ";
  foo.show_list();

  foo.clear();
  std::cout << "\nfoo.show_list()= ";
  foo.show_list();
}

int main() {
  insert_and_show();
  // delete_and_show();  
  // copy_and_move();  
  // clear_and_show();  
  return 0;
}

调用 insert_and_show 的运行结果如下图：

—————————— 本文结束 ——————————