CPP|简单实现List容器
引言
书接上回,对list的简单容器实现.继续灌水
List特性
- 双向链表： list是一个双向链表，允许在序列的两端和中间执行高效的插入和删除操作。
- 不支持随机访问： 与vector和deque不同，list不支持通过索引进行常量时间内的随机访问。要访问list中的元素，必须通过迭代器进行。
- 动态内存管理： list的内部实现使用节点，每个节点都包含一个元素和指向前后节点的指针。这种结构使得list在执行插入和删除操作时能够更好地管理内存。
- 保持迭代器有效性： list在进行插入和删除操作时，能够更好地保持迭代器的有效性。这意味着在进行这些操作后，不会导致所有迭代器失效。
- 高效的插入和删除操作： 由于list是双向链表，插入和删除操作在两端和中间都是常量时间的，使其成为处理这类操作的理想容器。
当然了,还是先从简单的入手构造析构函数入手
首先,设定好存储结构
template<typename T>
struct ListNode {
T value;
std::shared_ptr<ListNode> next;
std::weak_ptr<ListNode> prev;
ListNode(const T& val) : value(val), next(nullptr), prev() {}
};有人可能不熟悉,不常用weak_ptr 为什么要指上一个节点.是的没错,这个就是很经典的循环引用问题了:
list的特性是双向的,假设有节点 A 和节点 B：
- 节点 A 的
next指向节点 B - 节点 B 的
prev指向节点 A
如果都使用了std::shared_ptr 两者之间就形成了一个循环引用，使得引用计数永远不会归零，导致内存永远不会被释放.
而std::weak_ptr 是一种不拥有对象所有权的智能指针,总是搭配shared来用.它不会增加引用计数.我们就可以将上一个节点交给shared的指针管理
后续管理这些节点的数据结构,就是链表的实现
template <typename T>
class List
{
public:
template <typename L>
friend std::ostream &operator<<(std::ostream &os, const List<L> &pt);
private:
std::shared_ptr<Node<T>> head;
std::shared_ptr<Node<T>> tail;
size_t size; // 链表中节点的数量
public:
// 构造函数
List() : head(nullptr), tail(nullptr), size(0) {}
// 析构函数
~List()
{
while (head) {
head = head->next;
}
tail = nullptr;
size = 0;
}
void push_back(const T& value) {
auto newNode = std::make_shared<ListNode<T>>(value);
if (!head) {
head = tail = newNode;
} else {
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
++size;
}
void push_front(const T& value) {
auto newNode = std::make_shared<ListNode<T>>(value);
if (!head) {
head = tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
++size;
}
void pop_back() {
if (!tail) return;
if (head == tail) {
head = tail = nullptr;
} else {
tail = tail->prev.lock();
tail->next = nullptr;
}
--size;
}
void pop_front() {
if (!head) return;
if (head == tail) {
head = tail = nullptr;
} else {
head = head->next;
head->prev.reset();
}
--size;
}
bool remove(const T& value) {
bool found = false;
auto current = head;
while (current) {
if (current->value == value) {
found = true;
if (current == head && current == tail) {
head = tail = nullptr;
--size;
} else if (current == head) {
pop_front();
} else if (current == tail) {
pop_back();
} else {
auto prev = current->prev.lock();
auto next = current->next;
prev->next = next;
next->prev = prev;
--size;
}
current = current->next;
} else {
current = current->next;
}
}
return found;
}
}在pop_back中,需要注意的就是使用 std::weak_ptr::lock,获取前一个节点的 std::shared_ptr，如果前一个节点已经析构（即 weak_ptr 已经过期）,则返回一个空的 std::shared_ptr。
在这个list类中,我们模仿个迭代器的实现,在list 类中嵌入一个Iterator
class Iterator {
public:
using iterator_category = std::bidirectional_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
Iterator(std::shared_ptr<ListNode<T>> node) : node_ptr(node) {}
reference operator*() const { return node_ptr->value; }
pointer operator->() { return &(node_ptr->value); }
Iterator& operator++() {
node_ptr = node_ptr->next;
return *this;
}
Iterator operator++(int) {
Iterator tmp = *this;
node_ptr = node_ptr->next;
return tmp;
}
Iterator& operator--() {
node_ptr = node_ptr->prev.lock();
return *this;
}
Iterator operator--(int) {
Iterator tmp = *this;
node_ptr = node_ptr->prev.lock();
return tmp;
}
friend bool operator==(const Iterator& a, const Iterator& b) { return a.node_ptr == b.node_ptr; }
friend bool operator!=(const Iterator& a, const Iterator& b) { return a.node_ptr != b.node_ptr; }
private:
std::shared_ptr<ListNode<T>> node_ptr;
};
Iterator begin() const { return Iterator(head); }
Iterator end() const { return Iterator(nullptr); }当然,基本迭代器的功能到此我们就已经仿出来了
那么在给他添加一个初始化列表把,不想一个一个push,于是可以给这个类添加一个初始化列表的构造.
List(std::initializer_list<T> init_list) : head(nullptr), tail(nullptr), size(0) {
for (const T& value : init_list) {
push_back(value);
}
}这下简单例子基本与标准库无二
List<int> myList = {1,2,3,4,5};
for (const auto& val : myList) {
std::cout << val << " ";
}std::list 的实现往往比这复杂的多,比如说范围检查,异常处理等.搞不好我这个实现可能还有循环引用的问题.
Q&A
1. list 的迭代器失效情况
题目：在对 STL list 进行插入和删除操作时，哪些情况下迭代器会失效？
参考答案：
对于 STL list 来说，迭代器失效的情况相对较少。由于 list 是一个双向链表，迭代器在插入和删除操作之后通常仍然有效。具体来说：
- 插入操作：在
list中插入操作不会导致任何现有迭代器失效，包括指向插入位置的迭代器。插入操作后，原来的迭代器仍然指向它们原来指向的元素。 - 删除操作：删除操作会导致指向被删除元素的迭代器失效。然而，其他迭代器，包括指向前一个和后一个元素的迭代器，仍然有效。
2. list 与 vector 的比较
题目：比较 C++ STL list 和 vector，它们的优势、劣势和适用场景是什么？
参考答案：
list 和 vector 是 C++ STL 中的两种常用序列容器，它们各有优缺点。
- 内部实现：
list是一个双向链表，不支持随机访问。vector是一个动态数组，支持快速随机访问。
- 性能特点：
- list
- 插入和删除操作快（O(1)），不论在容器中的哪个位置。
- 遍历操作慢（O(n)），因为它不支持随机访问。
- vector
- 插入和删除操作在尾部快（O(1)），但在中间或开头慢（O(n)），因为可能需要移动元素。
- 遍历- 内部实现：
vector是基于连续内存空间的动态数组实现，这意味着它的元素存储在一个连续的内存块中。list是基于双向链表实现的，它的每个元素都是单独的内存块，通过指针连接。
- 性能特点：
- vector
- 支持随机访问，可以通过索引以 O(1) 时间复杂度访问任意元素。
- 尾部插入和删除操作快（通常是 O(1)），但在中间或开头插入或删除元素需要移动后续元素，可能导致 O(n) 时间复杂度。
- 当超出当前容量时，需要重新分配内存并复制所有元素到新空间，这是一个相对昂贵的操作。
- list
- 不支持随机访问，访问特定元素需要 O(n) 时间复杂度。
- 在任意位置插入和删除操作都很快（O(1)），因为只需要改变指针。
- 不需要重新分配整个容器的内存空间，因为它不是连续存储的。
- 内存使用：
vector通常有较小的内存开销，因为它不需要为每个元素存储额外的指针。list对于每个元素都需要存储两个额外的指针（前驱和后继），这意味着更高的内存开销。
- 迭代器失效：
vector的迭代器在重新分配内存后可能会失效，或者在除了尾部之外的任何位置进行插入或删除操作时会失效。list的迭代器在插入和删除操作后依然有效，除了被删除元素的迭代器外。
- 适用场景：
vector适合用于元素数量固定或仅在尾部进行添加和删除操作的场景，以及需要频繁随机访问元素的场景。list适合用于元素数量经常变动，特别是需要在列表中间频繁进行插入和删除操作的场景。
Comments NOTHING