用 C++ 创建单向链表 forward list
文章目录
- 前言
- 1. 源码 forward_list.hpp
- 2. 使用示例
前言
用 C++ 创建了一个单向链表，用于练习使用现代 C++ 的特性，包括 3 点：
- 对于容器，使用 std::initializer_list 作为参数创建构造函数。
C++ Core Guidelines 中，推荐使用花括号 {} 初始化对象，并且对容器推荐使用 std::initializer_list 创建构造函数。 - 使用智能指针 unique_ptr 。
- 使用了 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 #include #include #include #include #include #include #include #include // 链表的节点。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 #include 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 的运行结果如下图：
—————————— 本文结束 ——————————
