前言
在 C++ STL(标准模板库)中,List
是一个带头双向链表,可以存储多个元素并且支持动态调整大小,适合频繁插入和删除操作;而 Vector
是一个动态数组,元素在内存中是连续存储的,适合需要快速随机访问的场景。List
提供了添加、删除、查找等操作,而 Vector
除了这些基本操作外,还提供了按索引访问元素、在指定位置插入元素等功能,进而就可以很好的支持排序算法,二分查找,堆算法等,它的缺点是扩容要付出一定的代价,而且除了尾上的插入和删除外其他位置的插入和删除都不快(因为要挪动数据)。
list 代码实现
#include <iostream>
#include <assert.h>
using namespace std;
namespace hd
{
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
ListNode(const T& x = T()) // ListNode的构造函数
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
};
template<class T, class Ref, class Ptr>
struct _list_iterator // 链表迭代器
{
typedef ListNode<T> Node;
typedef _list_iterator<T, Ref, Ptr> self;
Node* _node; //存放一个节点的指针变量
_list_iterator(Node* node)
:_node(node)
{}
//++it
self& operator++() {
_node = _node->_next;
return *this;
}
//it++
self operator++(int) {
self tmp(*this);
_node = _node->_next;
return tmp;
}
//--it
self& operator--() {
_node = _node->_prev;
return *this;
}
//it--
self operator--(int) {
self tmp(*this);
_node = _node->_prev;
return tmp;
}
// 模仿指针的 *
Ref operator*() {
return _node->_data;
}
// 模仿指针的 ->
Ptr operator->() {
return &_node->_data;
}
bool operator != (const self& s) {
return _node != s._node;
}
bool operator == (const self& s) {
return _node == s._node;
}
};
template<class T>
class list // 带头双向循环链表
{
typedef ListNode<T> Node; // 节点的重定义
public:
typedef _list_iterator<T, T&, T*> iterator; // 迭代器的重定义
typedef _list_iterator<T, const T&, const T*> const_iterator; // const迭代器的重定义
//迭代器相关
iterator begin() {
return _head->_next;
}
iterator end() {
return _head;
}
const_iterator begin() const {
return _head->_next;
}
const_iterator end() const {
return _head;
}
void empty_init() { // 初始化链表
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
list() { //构造函数
empty_init();
}
void clear() { //清除链表元素
iterator it = begin();
while (it != end()) {
it = erase(it);
}
}
~list() { //析构函数
clear();
delete _head;
_head = nullptr;
}
list(const list<T>& It) { // 拷贝构造
empty_init();
for (const auto& e : It) {
push_back(e);
}
}
void swap(list<T> tmp) {
std::swap(_head, tmp._head);
}
//It1 = It2;
list<T> operator=(const list<T> It) const {
clear();
for (const auto& e : It) {
push_back(e);
}
return *this;
}
list<T>& operator=(list<T>/*&*/ It) {
//if (this != &It) {
// clear();
// for (const auto& e : It) {
// push_back(e);
// }
//}
// 现代写法
swap(It);
return *this;
}
void push_back(const T& x) {
//Node* newnode = new Node(x);
//Node* tail = _head->_prev;
//tail->_next = newnode;
//newnode->_prev = tail;
//_head->_prev = newnode;
//newnode->_next = _head;
insert(end(), x); // 复用insert
}
void push_front(const T& x) {
insert(begin(), x);
}
void pop_back() {
erase(--end());
}
void pop_front() {
erase(begin());
}
// vector insert会导致迭代器失效
// list intert 不会导致迭代器失效
iterator insert(iterator pos, const T& x)
{
Node* newnode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
newnode->_prev = prev;
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
//return iterator(newnode); //单参数的构造函数可以隐式类型转换
return newnode; // 返回插入节点迭代器
}
// 节点被delete掉了,存在迭代器失效
iterator erase(iterator pos) {
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return next; //返回被删除元素元素的下一个元素的迭代器
}
private:
Node* _head; //头节点
};
}
1. 构造函数和析构函数
1.1 构造函数
目的是对链表以及节点进行初始化
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
ListNode(const T& x = T()) // ListNode的构造函数
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};
template<class T>
class list // 带头双向循环链表
{
typedef ListNode<T> Node; // 节点的重定义
void empty_init() { // 初始化链表
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
list() { // list的构造函数
empty_init();
}
}
1.2析构函数
析构函数主要完成对资源的清理,这里通过调用clear
对链表的节点进行删除。最后在将头结点空间进行释放,然后置空。
void clear() { //清除链表元素
iterator it = begin();
while (it != end()) {
it = erase(it);
}
}
~list() { //析构函数
clear();
delete _head;
_head = nullptr;
}
2.operator=的重载 和 拷贝构造函数
2.1 拷贝构造
对链表进行初始化,之后调用push_back
函数尾插数据,完成拷贝构造。
void empty_init() { // 初始化链表
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
list(const list<T>& It) { // 拷贝构造
empty_init();
for (const auto& e : It) {
push_back(e);
}
}
2.2 operator=的重载
下面分别是对const
对象和非const
对象的operator=
的重载 /
void swap(list<T> tmp) {
std::swap(_head, tmp._head);
}
//It1 = It2;
list<T> operator=(const list<T> It) const {
clear();
for (const auto& e : It) {
push_back(e);
}
return *this;
}
list<T>& operator=(list<T>/*&*/ It) {
//if (this != &It) {
// clear();
// for (const auto& e : It) {
// push_back(e);
// }
//}
// 现代写法
swap(It);
return *this;
}
3. 迭代器的实现
list
的迭代器与 vector
不同,它不是原生指针,而是将节点的指针进行封装,然后重载operator*,operator++,operator--
等与指针相关的操作符来模拟指针的行为。
3.1 普通迭代器
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
ListNode(const T& x = T()) // ListNode的构造函数
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};
template<class T>
struct _list_iterator // 链表迭代器
{
typedef ListNode<T> Node;
typedef _list_iterator<T> self;
Node* _node; //存放一个节点的指针变量
_list_iterator(Node* node)
:_node(node)
{}
//++it
self& operator++() {
_node = _node->_next;
return *this;
}
//it++
self operator++(int) {
self tmp(*this);
_node = _node->_next;
return tmp;
}
//--it
self& operator--() {
_node = _node->_prev;
return *this;
}
//it--
self operator--(int) {
self tmp(*this);
_node = _node->_prev;
return tmp;
}
// 模仿指针的 *
T& operator*() {
return _node->_data;
}
// 模仿指针的 ->
T* operator->() {
return &_node->_data;
}
bool operator != (const self& s) {
return _node != s._node;
}
bool operator == (const self& s) {
return _node == s._node;
}
};
注意:operator->
在调用时,后面还会有一个->
,相当于 it.operator->()->_a1
,只不过特殊处理被省略掉了
struct AA
{
int _a1;
int _a2;
AA(int a1 = 1, int a2 = 1)
:_a1(a1)
, _a2(a2)
{}
};
void test_list3() {
list<AA> It;
AA aa1;
It.push_back(aa1);
It.push_back(AA());
AA aa2(2, 2);
It.push_back(aa2);
It.push_back(AA(2, 2));
list<AA>::iterator it = It.begin();
while (it != It.end()) {
cout << (*it)._a1 << ":" << (*it)._a2 << endl;
cout << it.operator*()._a1 << ":" << it.operator*()._a2 << endl;
cout << it->_a1 << ":" << it->_a2 << endl; //为了可读性,简化了一个->,特殊处理
cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl; //相当于上面一行的
++it;
}
cout << endl;
}
其实 it->_a1
是it->_node->_a1
,只是编译器对其进行了简化。
3.2 const迭代器
const
类型的对象只能使用const
类型的迭代器,那么const
类型的迭代器如何实现呢、需要再重新封装吗,像上面那样?为了减少代码量,我们只需要给模板增加两个参数就可以了。template<class T, class Ref, class Ptr>
。实现如下:
template<class T, class Ref, class Ptr>
struct _list_iterator // 链表迭代器
{
typedef ListNode<T> Node;
typedef _list_iterator<T, Ref, Ptr> self;
Node* _node; //存放一个节点的指针变量
_list_iterator(Node* node)
:_node(node)
{}
//++it
self& operator++() {
_node = _node->_next;
return *this;
}
//it++
self operator++(int) {
self tmp(*this);
_node = _node->_next;
return tmp;
}
//--it
self& operator--() {
_node = _node->_prev;
return *this;
}
//it--
self operator--(int) {
self tmp(*this);
_node = _node->_prev;
return tmp;
}
// 模仿指针的 *
Ref operator*() {
return _node->_data;
}
// 模仿指针的 ->
Ptr operator->() {
return &_node->_data;
}
bool operator != (const self& s) {
return _node != s._node;
}
bool operator == (const self& s) {
return _node == s._node;
}
};
const
迭代器与普通迭代器只是在operator*()
和 operator->()
的返回值上有所不同所以,只需要在实例化模板的时候给不同的参数就可以实例化不同的内容。文章来源:https://www.toymoban.com/news/detail-831628.html
typedef _list_iterator<T, T&, T*> iterator; // 迭代器的重定义
typedef _list_iterator<T, const T&, const T*> const_iterator; // const迭代器的重定义
4. 插入和删除
// vector insert会导致迭代器失效
// list intert 不会导致迭代器失效
iterator insert(iterator pos, const T& x)
{
Node* newnode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
newnode->_prev = prev;
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
//return iterator(newnode); //单参数的构造函数可以隐式类型转换
return newnode; // 返回插入节点迭代器
}
// 节点被delete掉了,存在迭代器失效
iterator erase(iterator pos) {
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return next; //返回被删除元素元素的下一个元素的迭代器
}
void push_back(const T& x) {
//Node* newnode = new Node(x);
//Node* tail = _head->_prev;
//tail->_next = newnode;
//newnode->_prev = tail;
//_head->_prev = newnode;
//newnode->_next = _head;
insert(end(), x); // 复用insert
}
void push_front(const T& x) {
insert(begin(), x);
}
void pop_back() {
erase(--end());
}
void pop_front() {
erase(begin());
}
5. 测试代码
namespace hd
{
void test_list()
{
list<int> It;
It.push_back(1);
It.push_back(2);
It.push_back(3);
It.push_back(4);
It.push_back(5);
It.push_back(6);
list<int>::iterator it = It.begin();
while (it != It.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : It) {
cout << e << " ";
}
cout << endl;
list<int> It1 = It;
list<int>::iterator it1 = It1.begin();
while (it1 != It1.end())
{
cout << *it1 << " ";
++it1;
}
cout << endl;
for (auto e : It1) {
cout << e << " ";
}
cout << endl;
}
void print_list(const list<int>& It) {
list<int>::const_iterator it = It.begin();
while (it != It.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : It) {
cout << e << " ";
}
cout << endl;
}
void test_list2() {
list<int> It;
It.push_back(1);
It.push_back(2);
It.push_back(3);
It.push_back(4);
It.push_back(5);
It.push_back(6);
print_list(It);
}
struct AA
{
int _a1;
int _a2;
AA(int a1 = 1, int a2 = 1)
:_a1(a1)
, _a2(a2)
{}
};
void test_list3() {
list<AA> It;
AA aa1;
It.push_back(aa1);
It.push_back(AA());
AA aa2(2, 2);
It.push_back(aa2);
It.push_back(AA(2, 2));
list<AA>::iterator it = It.begin();
while (it != It.end()) {
cout << (*it)._a1 << ":" << (*it)._a2 << endl;
cout << it.operator*()._a1 << ":" << it.operator*()._a2 << endl;
cout << it->_a1 << ":" << it->_a2 << endl; //为了可读性,简化了一个->,特殊处理
cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl; //相当于上面一行的
++it;
}
cout << endl;
}
}
总结
文章详细介绍了 C++ STL 中 List
的实现。List
是一个带头双向链表,适用于频繁插入和删除操作。构造函数、析构函数、拷贝构造函数、operator=
的重载、迭代器的实现以及插入和删除操作的具体实现方式。通过这些内容,可以深入了解 List
的内部工作原理,并学习如何使用和优化 List
数据结构。文章来源地址https://www.toymoban.com/news/detail-831628.html
到了这里,关于【C++】STL中List的详细实现解析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!