简易STL实现 | List的实现
基于双向链表的数据结构
1、list的特性
双向链表：允许在序列的两端和中间 执行高效的插入和删除操作
不支持随机访问：要访问list中的元素，必须通过迭代器进行
动态内存管理： list的内部实现使用节点，每个节点都包含一个元素和指向前后节点的指针。这种结构使得list在执行插入和删除操作时能够更好地管理内存
保持迭代器有效性： list在进行插入和删除操作时，能够更好地保持迭代器的有效性，不会导致所有迭代器失效
高效的插入和删除操作： 由于list是双向链表，插入和删除操作在两端和中间都是常量时间
2、list的性能考虑
插入和删除操作： 如果 主要进行频繁的插入和删除操作，并且不需要随机访问元素，list可能比vector和deque更为高效
随机访问： 如果需要 通过索引进行随机访问元素，使用vector可能更为合适，因为 提供了常量时间的随机访问
内存使用： 由于list使用了链表结构，可能引入一些额外的内存开销。在内存使用方面，vector和deque可能更为紧凑
3、list 工作原理
蓝色矩形框：堆内存
红色矩形块：栈内存
红色箭头：next指针
蓝色箭头：prev指针
List类也有一个控制结构, 包含 head, tail, size 三个成员, 分别控制 链表的头尾指针和大小
4、实现list
设计一个名为 List 的 List 类，该类具有以下功能和特性：
1、基础成员函数
构造函数：初始化 List 实例
析构函数：清理资源，确保无内存泄露
2、核心功能
在 List 末尾添加元素
在 List 开头添加元素
获取 List 中节点的数量
删除 List 末尾的元素
删除 List 开头的元素
删除 List 中指定值的节点
3、迭代与遍历
打印链表中的元素
4、辅助功能
重载[]运算符以对链表进行索引访问
重载<<运算符以打印链表
输入描述
题目的包含多行输入，第一行为正整数 N, 代表后续有 N 行命令序列，后面就是命令
17
push_back 10
push_back 20
push_front 30
push_front 40
size
print
get 1
pop_back
print
pop_front
print
remove 10
print
size
clear
print
size
输出描述
get 命令：输出一个整数，独占一行，代表 List 中索引为 index 的元素，如果索引无效，则输出 -1
print 命令：按照顺序打印当前 List 包含的所有元素，每个元素后都跟一个空格，打印结果独占一行；如果当前的 vector 为空，则打印 empty
4
40 30 10 20
30
40 30 10
30 10
30
1
empty
0
#include <iostream>
#include <string>
#include <sstream>
#include <stdexcept>template<typename T>
class List {template <typename L>friend std::ostream& operator<<(std::ostream& os, List<L>& l); // 注意T在参数的应用,typename不能和外层T重复:在定义友元函数时，模板参数需要独立于类模板的参数，这样可以避免与类模板的模板参数产生冲突// 避免歧义：在友元声明中，List<L>中使用的L必须是一个新的独立模板参数。虽然它可能与外层模板参数T类型相同，但它在语义上是独立的。这种做法避免了可能的歧义或冲突，尤其是在涉及多个模板参数的复杂情况下// 独立作用域：友元函数模板声明的模板参数L有自己的作用域，与类模板的模板参数T没有直接的联系或依赖关系。这种方式使得友元函数可以更加通用，适用于不同类型的List实例，而不受限于外层模板参数// 更好的可读性和维护性：通过引入新的模板参数L，可以更清楚地表达友元函数的独立性和泛型特性。即使在友元函数的实现中，L和T最终是同一种类型，使用不同的名称也有助于提高代码的可读性和维护性// 如果 不希望友元函数是模板函数，而是直接使用类模板参数 T，但定义必须在类的内部（在这种情况下，友元函数被限制为只能用于与 List<T> 匹配的类型，而不能用于其他类型的 List<U>）//template<typename T>//class List {// friend std::ostream& operator<<(std::ostream& os, const List<T>& l) {// for (auto* cur = l.head; cur; cur = cur->next) {// os << cur->data << " ";// }// return os;// }// // 其他成员...//};// 如果在类外面定义友元函数，并且希望使用类模板的模板参数 T，那么 必须在函数定义中重新声明模板参数 T// 就像代码实现的那样// 为什么<<运算符友元，[]运算符为成员函数// // << 运算符为什么是友元函数// 左操作数的类型： << 是一个二元运算符，通常用于输出流操作，其左操作数是一个 std::ostream 类型，而右操作数是用户自定义的类对象。如果 << 运算符被实现为成员函数，那么 std::ostream 必须是类的成员，这在实际中是不可能的，因为 std::ostream 是标准库中的类。为了允许 std::ostream 作为左操作数，因此通常将 << 运算符重载为友元函数// 对私有数据的访问：为了便于直接访问类的私有成员， << 运算符通常被定义为友元函数。友元函数虽然不属于类的成员，但它可以访问类的私有成员，这样可以方便地实现打印或输出类的内部状态// 操作符的对称性： << 运算符通常用于与 std::ostream 结合进行链式调用，如 std::cout << obj1 << obj2; 。通过友元函数，可以保证操作符的对称性和流操作的自然性//// [] 运算符为什么是成员函数// 对象的直接访问：[] 运算符通常用于通过索引访问类的内部数据。这个操作对类内部的数据结构有直接的操作需求，因此最好作为类的成员函数实现。这样可以直接访问类的私有或受保护成员，并根据索引返回对应的元素// 依赖对象的状态：[] 运算符的语义通常与对象的内部状态强相关。因为[] 操作是对当前对象（即 this 指针）的操作，通常需要知道该对象内部如何存储数据，并根据索引返回或修改数据。作为成员函数，[] 可以很自然地操作和返回对象内部的数据// 左值和右值支持：将[] 运算符作为成员函数，可以很容易地支持左值和右值访问。例如，可以分别重载 const 版本和非 const 版本的[] 运算符，以支持不同上下文中的使用需求// // 类的成员函数的左操作数必须是类的对象（即该类的实例），而右操作数则可以是任何类型。这是因为成员函数的第一个（隐式）参数是指向调用对象的 this 指针，因此左操作数就是调用该成员函数的对象// 成员函数是在类的对象上调用的，调用时隐式地传递了 this 指针作为左操作数。因此，左操作数必须是类的实例。例如，对于 obj.method()，obj 是左操作数，而 method 是成员函数。this 指针指向 obj，所以 obj 必须是类的对象// 对于运算符重载，如果运算符是成员函数，那么它的左操作数必须是类的实例。例如，对于重载的 operator[]，在表达式 obj[index] 中，obj 是类的对象，index 是右操作数
private:struct Node {T data;Node* next;Node* pre;Node(const T& d, Node* n = nullptr, Node* p = nullptr) : // 参数中的const一定要与后面初始化中的匹配data(d), next(n), pre(p) {}};// Node* data; 不用指向数据Node* head;Node* tail;size_t size;
public:List() : head(nullptr), tail(nullptr), size(0) {}List(Node* h, Node* t, size_t s) : head(h), tail(t), size(s) {}~List() {clear();}void push_back(const T& ele) { // 成员函数的参数都为T，不可能是NodeNode* n = new Node(ele, nullptr, tail);size++;if (head == nullptr) {head = n;tail = n;}else {tail->next = n;tail = n;}}void push_front(const T& ele) {Node* newFront = new Node(ele, head, nullptr); // 注意ele是const，定义的构造函数参数也要是 constsize++;if (head == nullptr) {head = newFront;tail = newFront;}else {head->pre = newFront;head = newFront;}}size_t getSize() {return size;}void pop_back() {if (head != nullptr) {size--;if (size == 0) {delete head;head = nullptr;tail = nullptr;return;}tail->pre->next = nullptr;Node* deleteNode = tail;tail = tail->pre;delete deleteNode;}}// void pop_back()//{// if (size > 0)// {// // 获取尾节点的前一个节点// Node* newTail = tail->prev;// // 删除尾节点// delete tail;// // 更新尾节点指针和链表大小// tail = newTail;// if (tail)// {// tail->next = nullptr;// }// else// {// head = nullptr; // 如果链表为空，头节点也置为空// }// --size;// }//}void pop_front() {if (head != nullptr) {Node* newHead = head->next;delete head;head = newHead;size--;if (newHead == nullptr) {tail = nullptr;}else {newHead->pre = nullptr;}}}T& get(size_t pos) {Node* cur = head;while (pos--) {if (cur == nullptr) {throw std::out_of_range("Index out of range");}cur = cur->next;}return cur->data;}void remove(const T& ele) {Node* cur = head;while (cur != nullptr) {if (cur->data == ele) {if (cur == head) {pop_front();}else if (cur == tail) {pop_back();}else {cur->pre->next = cur->next;cur->next->pre = cur->pre;delete cur; // 调用的析构函数是 Node 结构体的析构函数(析构函数负责清理对象内部的资源，但不会释放对象本身的内存),之后，delete 操作符会释放 cur 指向的内存(delete:析构函数+释放内存)// 如果没有显式定义析构函数，编译器会为 Node 生成一个默认的析构函数。这个默认的析构函数会调用成员变量的析构函数，依次销毁 data、next 和 pre 成员// 对于 next 和 pre 这两个指针成员，它们是普通指针，不涉及动态分配的内存管理，因此默认析构函数不会对它们进行任何特殊处理//struct Node {// int* data;// Node* next;// Node* pre;// Node(int value) : data(new int(value)), next(nullptr), pre(nullptr) {}// ~Node() {// delete data; // 释放动态分配的内存// }//};size--; // 别忘了减size}return;}cur = cur->next;}}Node* begin() {return head;}Node* end() {return nullptr; // 不是end}const Node* begin() const {return head;}const Node* end() const {return nullptr; // 不是end}void print() {Node* cur = head;if (head == nullptr)std::cout << "empty";while (cur) {std::cout << cur->data << " ";cur = cur->next;}std::cout << std::endl;}T& operator[](size_t pos) {return get(pos);}const T& operator[](size_t pos) const {return get(pos);}void clear() {size = 0;Node* cur = head;while (cur != nullptr) {Node* tmp = cur;cur = cur->next;delete tmp;}tail = nullptr; // 头，尾巴别忘了设nullptrhead = nullptr;}
};template <typename T>
std::ostream& operator<<(std::ostream& os, List<T>& l) {for (typename List<T>::Node* cur = l.head; cur; cur = cur->next) { // 注意调用List<T>的方式// 为什么要加 typename// 在模板代码中，编译器在解析模板时并不知道 List<T>::Node 是一个类型还是一个静态成员变量，除非你明确告诉它这是因为在模板实例化之前，编译器无法确定 T 是什么类型，因此无法确定 List<T>::Node 是什么os << cur->data << " ";}os << std::endl;
}int main() {int N;std::cin >> N;getchar(); // 读走回车List<int> myList; // 调用默认构造函数std::string line;while (N--) {getline(std::cin, line);std::istringstream iss(line);std::string command;iss >> command;if (command == "push_back") {int i;iss >> i;myList.push_back(i);}else if (command == "push_front") {int i;iss >> i;myList.push_front(i);}else if (command == "pop_back") {myList.pop_back();}else if (command == "pop_front") {myList.pop_front();}else if (command == "remove") {int i;iss >> i;myList.remove(i);}else if (command == "clear") {myList.clear();}else if (command == "size") {std::cout << myList.getSize() << std::endl;}else if (command == "get") {size_t pos;iss >> pos;std::cout << myList[pos] << std::endl;}else if (command == "print") {//for (auto& curNode : myList) {// // :前面 会去掉begin / end的指针// std::cout << curNode.data << " ";//} // 为什么没办法遍历所有元素 // C++ 的范围循环依赖于容器提供的 begin() 和 end() 成员函数，这些函数必须返回符合标准的迭代器对象。标准迭代器通常定义了以下运算符：// *：解引用运算符，用于访问当前元素// ++：前置或后置递增运算符，用于移动到下一个元素。// != ：用于判断两个迭代器是否不相等（通常在循环中作为终止条件）// List 类中，begin() 和 end() 返回的是指向 Node 的原始指针，而不是标准迭代器。因此，标准的 range-based for 循环无法直接使用这些原始指针进行遍历// 需要为 List 类提供自定义的迭代器//template<typename T>//class List {//public:// // 自定义迭代器类// class Iterator {// private:// Node* current;// public:// Iterator(Node* node) : current(node) {}// T& operator*() {// return current->data;// }// Iterator& operator++() {// current = current->next;// return *this;// }// bool operator!=(const Iterator& other) const {// return current != other.current;// }// };// // 提供 begin 和 end 函数，返回迭代器// Iterator begin() {// return Iterator(head);// }// Iterator end() {// return Iterator(nullptr);// }// // 其他成员函数和成员变量...//};//// begin() 函数：返回一个指向元素范围起始位置的指针或迭代器// end() 函数：返回一个指向元素范围结束位置的指针或迭代器。// 在 Vector 类中，begin() 和 end() 函数返回的是指向 elements 数组的指针。C++ 标准库规定，指针本身就是合法的迭代器// 在 C++ 中，指针实际上是最简单的迭代器类型，支持解引用 (*) 和递增 (++) 操作(而本例中的Node*显然都不支持，Vector类是int*)。因此，当 range-based for 使用 begin() 和 end() 返回的指针时，它能够正确地遍历数组中的每个元素myList.print();}}return 0;
}
1、注意 T 在参数的应用, typename 不能和外层T重复: 在定义友元函数时，模板参数需要独立于类模板的参数，这样可以避免与类模板的模板参数产生冲突
1）避免歧义：在友元声明中，List<L>中使用的 L 必须是一个新的独立模板参数。虽然它可能与外层模板参数 T 类型相同，但它在语义上是独立的。这种做法避免了 可能的歧义或冲突，尤其是在涉及多个模板参数的复杂情况下
2）独立作用域：友元函数模板声明的模板参数L有自己的作用域，与类模板的模板参数 T 没有直接的联系或依赖关系。这种方式使得友元函数可以更加通用，适用于不同类型的List实例，而不受限于外层模板参数
3）更好的可读性和维护性：通过引入新的模板参数 L，可以更清楚地表达友元函数的独立性 和 泛型特性。即使在友元函数的实现中，L 和 T 最终是同一种类型，使用不同的名称也有助于提高代码的可读性和维护性
如果 不希望友元函数是模板函数，而是直接使用类模板参数 T，但定义必须在类的内部（在这种情况下，友元函数被限制为只能用于与 List<T> 匹配的类型，而不能用于其他类型的 List<U>）
template<typename T>
class List {friend std::ostream& operator<<(std::ostream& os, const List<T>& l) {for (auto* cur = l.head; cur; cur = cur->next) {os << cur->data << " ";}return os;}// 其他成员...
};
如果在类外面定义友元函数，并且希望使用类模板的模板参数 T，那么 必须在函数定义中重新声明模板参数 T
就像代码实现的那样
2、为什么<<运算符友元，[]运算符为成员函数
<< 运算符为什么是友元函数
左操作数的类型： << 是一个二元运算符，通常用于输出流操作，其左操作数是一个 std::ostream 类型，而右操作数是用户自定义的类对象。如果 << 运算符被实现为成员函数，那么 std::ostream 必须是类的成员，这在实际中是不可能的，因为 std::ostream 是标准库中的类。为了允许 std::ostream 作为左操作数，因此通常将 << 运算符重载为友元函数
对私有数据的访问：为了便于直接访问类的私有成员， << 运算符通常被定义为友元函数。友元函数虽然不属于类的成员，但它可以访问类的私有成员，这样可以方便地实现打印或输出类的内部状态
操作符的对称性： << 运算符通常用于与 std::ostream 结合进行链式调用，如 std::cout << obj1 << obj2; 。通过友元函数，可以保证操作符的对称性和流操作的自然性
[] 运算符为什么是成员函数
对象的直接访问：[] 运算符通常用于通过索引访问类的内部数据。这个操作对类内部的数据结构有直接的操作需求，因此最好作为类的成员函数实现。这样可以直接访问类的私有或受保护成员，并根据索引返回对应的元素
依赖对象的状态：[] 运算符的语义通常与对象的内部状态强相关。因为[] 操作是对当前对象（即 this 指针）的操作，通常需要知道该对象内部如何存储数据，并根据索引返回或修改数据。作为成员函数，[] 可以很自然地操作和返回对象内部的数据
左值和右值支持：将[] 运算符作为成员函数，可以很容易地支持左值和右值访问。例如，可以分别重载 const 版本和非 const 版本的[] 运算符，以支持不同上下文中的使用需求
类的成员函数的左操作数必须是类的对象（即该类的实例），而右操作数则可以是任何类型。这是因为成员函数的第一个（隐式）参数是指向调用对象的 this 指针，因此左操作数就是调用该成员函数的对象
成员函数是在类的对象上调用的，调用时隐式地传递了 this 指针作为左操作数。因此，左操作数必须是类的实例。例如，对于 obj.method()，obj 是左操作数，而 method 是成员函数。this 指针指向 obj，所以 obj 必须是类的对象
对于运算符重载，如果运算符是成员函数，那么它的左操作数必须是类的实例。例如，对于重载的 operator[]，在表达式 obj[index] 中，obj 是类的对象，index 是右操作数
3、调用的析构函数是 Node 结构体的析构函数 (析构函数负责清理对象内部的资源，但不会释放对象本身的内存),之后，delete 操作符会释放 cur 指向的内存 (delete:析构函数+释放内存)
如果没有显式定义析构函数，编译器会为 Node 生成一个默认的析构函数。这个默认的析构函数会调用成员变量的析构函数，依次销毁 data、next 和 pre 成员
对于 next 和 pre 这两个指针成员，它们是普通指针，不涉及动态分配的内存管理，因此默认析构函数不会对它们进行任何特殊处理
struct Node {int* data;Node* next;Node* pre;Node(int value) : data(new int(value)), next(nullptr), pre(nullptr) {}~Node() {delete data; // 释放动态分配的内存}
};
4、为什么要加 typename
在模板代码中，编译器在解析模板时并不知道 List<T>::Node 是一个类型还是一个静态成员变量，除非你明确告诉它这是因为在模板实例化之前，编译器无法确定 T 是什么类型，因此无法确定 List<T>::Node 是什么
5、为什么没办法遍历所有元素
for (auto& curNode : myList) {// :前面 会去掉begin / end的指针std::cout << curNode.data << " ";
}
C++ 的范围循环依赖于容器提供的 begin() 和 end() 成员函数，这些函数必须返回符合标准的迭代器对象。标准迭代器通常定义了以下运算符：
*：解引用运算符，用于访问当前元素
++：前置或后置递增运算符，用于移动到下一个元素。
!= ：用于判断两个迭代器是否不相等（通常在循环中作为终止条件）
List 类中，begin() 和 end() 返回的是指向 Node 的原始指针，而不是标准迭代器。因此，标准的 range-based for 循环无法直接使用这些原始指针进行遍历
需要为 List 类提供自定义的迭代器
template<typename T>
class List {
public:// 自定义迭代器类class Iterator {private:Node* current;public:Iterator(Node* node) : current(node) {}T& operator*() {return current->data;}Iterator& operator++() {current = current->next;return *this;}bool operator!=(const Iterator& other) const {return current != other.current;}};// 提供 begin 和 end 函数，返回迭代器Iterator begin() {return Iterator(head);}Iterator end() {return Iterator(nullptr);}// 其他成员函数和成员变量...
};
begin() 函数：返回一个指向元素范围起始位置的指针或迭代器
end() 函数：返回一个指向元素范围结束位置的指针或迭代器
在 Vector 类中，begin() 和 end() 函数返回的是指向 elements 数组的指针。C++ 标准库规定，指针本身就是合法的迭代器
在 C++ 中，指针实际上是最简单的迭代器类型，支持解引用 (*) 和递增 (++) 操作(而本例中的 Node* 显然都不支持，Vector类是 int*)。因此，当 range-based for 使用 begin() 和 end() 返回的指针时，它能够正确地遍历数组中的每个元素
6、对照卡玛网，更好的写法
void pop_back(){if (size > 0){// 获取尾节点的前一个节点Node *newTail = tail->prev;// 删除尾节点delete tail;// 更新尾节点指针和链表大小tail = newTail;if (tail){tail->next = nullptr;}else{head = nullptr; // 如果链表为空，头节点也置为空}--size;}}
卡玛网多实现的函数
T *find(const T &val){Node *node = getNode(val);if (node == nullptr){return nullptr;}return &node->val;}https://kamacoder.com/ 手写简单版本STL，内容在此基础上整理补充