C++奇迹之旅:深度解析list的模拟实现
文章目录
- 📝前言
- 🌠list节点
- 🌉list
- 🌠迭代器的创建
- 🌉const迭代器
- 🌠代码
- 🚩总结
📝前言
🌠list节点
我们先建立一个列表里的节点类listnode
,用来构造list的节点使用:
// 这个宏定义用于禁用编译器的安全警告。
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <assert.h>
using namespace std;
namespace own
{
// 定义一个模板结构 listnode,代表链表中的节点
template<typename T>
struct listnode
{
// 指向前一个节点的指针
listnode<T>* _prev;
// 指向下一个节点的指针
listnode<T>* _next;
// 节点中存储的数据
T _data;
// 构造函数,初始化链表节点
listnode(const T& data = T())
: _prev(nullptr) // 前一个节点指针初始化为 nullptr
, _next(nullptr) // 下一个节点指针初始化为 nullptr
, _data(data) // 节点中存储的数据初始化为传入的值(或默认值)
{}
};
}
🌉list
list主要框架:
template<typename T>
class list
{
typedef listnode<T> Node;
public:
typedef ListIterator<T> iterator;
typedef Listconst_Iterator<T> const_Iterator;
list()
{
_head = new Node();
_head->_prev = _head;
_head->_next = _head;
}
iterator begin()
{
//iterator it(head->next);
//return it
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_Iterator begin() const
{
//iterator it(head->next);
//return it
return const_Iterator(_head->_next);
}
const_Iterator end() const
{
return const_Iterator(_head);
}
private:
Node* _head;
};
begin
使用迭代器iterator返回第一个数据,end
返回最后一个数据的下一个位置,也就是头结点。
void test_list01()
{
list<int> first;
for (int i = 0; i < 4; i++)
{
first.push_back(i);
}
//ListIterator<int> it = first.begin();
list<int>::iterator it = first.begin();
while (it != first.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : first)
{
cout << e << " ";
}
cout << endl;
}
为了方便使用iterator,需要重新typedef命名:
typedef ListIterator<T> iterator;
typedef Listconst_Iterator<T> const_Iterator;
🌠迭代器的创建
我们使用模拟实现vector时,迭代器类型使用的是T*,因为vector底层是数组,地址连续,但是list不能使用T*,因为指针不能直接++,或–;也不能直接使用Node进行++或–,因此Node不符合遍历的行为,需要Listlterator类封装Node*,再通过重载运算符控制他的行为,具体原因也有以下:
-
内存布局:
- 在
vector
中,元素是连续存储在内存中的,因此可以使用指针(如T*
)进行简单的算术运算(如++
和--
)来访问相邻元素。 - 在
list
中,元素是分散存储的,每个节点通过指针连接到前一个和下一个节点。节点之间的内存地址不连续,因此不能简单地通过指针算术来访问相邻节点。
- 在
-
迭代器的设计:
- 对于
vector
,迭代器通常是一个指向数组元素的指针(如T*
),可以直接进行指针运算。 - 对于
list
,迭代器需要封装一个指向节点的指针(如Node*
),并提供自定义的++
和--
操作符来遍历链表。这是因为在链表中,节点之间的关系是通过指针而不是通过内存地址的连续性来维护的。
- 对于
-
迭代器的有效性:
- 在链表中,插入和删除操作可能会导致迭代器失效。使用
Node*
作为迭代器类型时,删除节点后,指向该节点的迭代器将变得无效。因此,链表的迭代器需要在操作后返回一个新的有效迭代器(如在erase
方法中返回下一个节点的迭代器)。
- 在链表中,插入和删除操作可能会导致迭代器失效。使用
template<typename T>
struct ListIterator
{
typedef listnode<T> Node;
typedef ListIterator<T> self;
Node* _node;
ListIterator(Node* node)
:_node(node)
{}
bool operator!=(const self& it)
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node = it._node;
}
};
我们先实现list
的简单构造函数,接下来是迭代器++和–
//++it
self& operator++()
{
_node = _node->_next;
return *this;
}
//it++
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
那么迭代器怎么访问数据的两种方法:
对于pos
类:
struct Pos
{
int _row;
int _col;
Pos(int row = 0, int col = 0)
:_row(row)
,_col(col)
{}
};
先把数据插入的多种方法:
void test_list2()
{
list<Pos> lt1;
A aa1(100,100);
A aa2 = {100,100};
lt1.push_back(aa1);
lt1.push_back(aa2);
lt1.push_back({100,100})
lt1.push_back(Pos(100, 100));
}
我们使用其中一种方法插入数据就行:
void test_list2()
{
list<Pos> lt1;
lt1.push_back(Pos(100, 100));
lt1.push_back(Pos(200, 200));
lt1.push_back(Pos(300, 300));
list<Pos>::iterator it = lt1.begin();
while (it != lt1.end())
{
cout << (*it)._row << ":" << (*it)._col << endl;
++it;
}
cout << endl;
}
这里数据是struct
公有的,解引用得到的可以通过.
访问符进行访问
cout << (*it)._row << ":" << (*it)._col << endl;
这里访问方式就是指针解引用用.
访问符进行取数据:
A* ptr = &aa1;
(*ptr)._a1;
第二种:
还有使用->访问:
cout << it->_row << ":" << it->_col << endl;
但是这样需要重载operator->
运算符
T* operator->()
{
return &_node->_data;
}
返回的是_data
的地址
实际上它是有两个->的,第一个是oeprator()->
,第二个是->
cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;
这里隐藏了一个箭头,一个是重载,一个是原生指针的访问操作
在你提供的test_list02
函数中,确实存在一个关于箭头操作符(->
)的重载和原生指针访问的混合使用。让我们详细分析一下这个情况。
🌉const迭代器
typedef Listconst_Iterator<const T> const_Iterator;
对于这个cons_itertator
直接这样加是不行的,无法编译成功,const
不能调用非const
成员函数
我们增加const版本的迭代器
typedef Listconst_Iterator<T> const_Iterator;
const_Iterator begin() const
{
//iterator it(head->next);
//return it
return const_Iterator(_head->_next);
}
const_Iterator end() const
{
return const_Iterator(_head);
}
这里实现const迭代器呢?
第一种:单独实现一个类,修改正常版本的迭代器:
template<typename T>
class Listconst_Iterator
{
typedef listnode<T> Node;
typedef Listconst_Iterator<T> self;
public:
Node* _node;
Listconst_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;
}
self& operator--()
{
_node = _node->_prev;
return _node;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
const T* operator->()
{
return &_node->_data;
}
const T& operator*()
{
return _node->_data;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node = it._node;
}
};
我们目的是不修改指向的值,只需要在这两个函数前面加上const即可:
const T* operator->()
{
return &_node->_data;
}
const T& operator*()
{
return _node->_data;
}
第二种:合并两个迭代器
template<typename T,class ptr,class ref>
struct ListIterator
{
typedef listnode<T> Node;
typedef ListIterator<T, ptr, ref> self;
Node* _node;
ListIterator(Node* node)
:_node(node)
{}
ptr operator->()
{
return &_node->_data;
}
ref operator*()
{
return _node->_data;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node = it._node;
}
};
- 模板定义
template<typename T, class ptr, class ref>
struct ListIterator
ListIterator
是一个模板结构体,接受三个模板参数:T
:表示链表中存储的数据类型。ptr
:表示指向T
类型的指针类型(通常是T*
)。ref
:表示对T
类型的引用类型(通常是T&
)。
- 类型别名
typedef listnode<T> Node;
typedef ListIterator<T, ptr, ref> self;
Node
是一个类型别名,表示链表节点的类型,即listnode<T>
。self
是一个类型别名,表示当前迭代器类型ListIterator<T, ptr, ref>
,用于在成员函数中引用自身类型。
ptr operator->()
{
return &_node->_data;
}
- 重载了箭头操作符
operator->()
,使得可以通过迭代器访问节点中的数据。 - 返回
_node
指向的节点的_data
成员的地址,允许使用it->
语法来访问数据。
ref operator*()
{
return _node->_data;
}
- 重载了解引用操作符
operator*()
,使得可以通过迭代器直接访问节点中的数据。 - 返回
_node
指向的节点的_data
成员,允许使用*it
语法来访问数据。
最后我们需要在使用list里重新定义:
template<typename T>
class list
{
typedef listnode<T> Node;
public:
//typedef ListIterator<T> iterator;
//typedef Listconst_Iterator<T> const_Iterator;
typedef ListIterator<T, T*, T&> iterator;
typedef ListIterator<T, const T*, const T&> const_Iterator;
list()
{
_head = new Node();
_head->_prev = _head;
_head->_next = _head;
}
......
}
搞定了这些就是插入的删除的一些操作了
push_back
void push_back(const T& val = T())
{
Node* newnode = new Node(val);
Node* tail = _head->_prev;
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
//insert(end(), val);
}
insert()
insert
在这里不会出现迭代器失效,我们可以按照库里的写法进行模仿:
//没有iterator失效
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* newnode = new Node(x);
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return iterator(newnode);
}
erase
//erase 后pos失效了,pos指向的节点就被释放了
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
erase()
函数完成后,it所指向的节点已被删除,所以it
无效,在下一次使用it时,必须先给其赋值erase
删除返回的是下一个位置的迭代器
🌠代码
list.h
# define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <assert.h>
using namespace std;
namespace own
{
template<typename T>
struct listnode
{
listnode<T>* _prev;
listnode<T>* _next;
T _data;
listnode(const T& data = T())
:_prev(nullptr)
, _next(nullptr)
, _data(data)
{}
};
template<typename T,class ptr,class ref>
struct ListIterator
{
typedef listnode<T> Node;
typedef ListIterator<T, ptr, ref> self;
Node* _node;
ListIterator(Node* node)
:_node(node)
{}
//++it
self& operator++()
{
_node = _node->_next;
return *this;
}
//it++
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
ptr operator->()
{
return &_node->_data;
}
ref operator*()
{
return _node->_data;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node = it._node;
}
};
//template<typename T>
//class Listconst_Iterator
//{
// typedef listnode<T> Node;
// typedef Listconst_Iterator<T> self;
//public:
// Node* _node;
// Listconst_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;
// }
// self& operator--()
// {
// _node = _node->_prev;
// return _node;
// }
// self operator--(int)
// {
// self tmp(*this);
// _node = _node->_prev;
// return tmp;
// }
// const T* operator->()
// {
// return &_node->_data;
// }
// const T& operator*()
// {
// return _node->_data;
// }
// bool operator!=(const self& it)
// {
// return _node != it._node;
// }
// bool operator==(const self& it)
// {
// return _node = it._node;
// }
//};
template<typename T>
class list
{
typedef listnode<T> Node;
public:
//typedef ListIterator<T> iterator;
//typedef Listconst_Iterator<T> const_Iterator;
typedef ListIterator<T, T*, T&> iterator;
typedef ListIterator<T, const T*, const T&> const_Iterator;
list()
{
_head = new Node();
_head->_prev = _head;
_head->_next = _head;
}
iterator begin()
{
//iterator it(head->next);
//return it
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_Iterator begin() const
{
//iterator it(head->next);
//return it
return const_Iterator(_head->_next);
}
const_Iterator end() const
{
return const_Iterator(_head);
}
void push_back(const T& val = T())
{
/*Node* newnode = new Node(val);
Node* tail = _head->_prev;
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;*/
insert(end(), val);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& val = T())
{
insert(begin(), val);
}
void pop_front()
{
erase(begin());
}
//没有iterator失效
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* newnode = new Node(x);
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return iterator(newnode);
}
//erase 后pos失效了,pos指向的节点就被释放了
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
private:
Node* _head;
};
void test_list01()
{
list<int> first;
for (int i = 0; i < 4; i++)
{
first.push_back(i);
}
//ListIterator<int> it = first.begin();
list<int>::iterator it = first.begin();
while (it != first.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : first)
{
cout << e << " ";
}
cout << endl;
}
struct pos
{
int _row;
int _col;
pos(int row = 0, int col = 0)
:_row(row)
, _col(col)
{}
};
void test_list02()
{
list<pos> It1;
It1.push_back(pos(100, 200));
It1.push_back(pos(300, 400));
It1.push_back(pos(500, 600));
list<pos>::iterator it = It1.begin();
while (it != It1.end())
{
//cout << (*it)._row << ":" << (*it)._col << endl;
// 为了可读性,省略了一个->
//cout << it->_row << ":" << it->_col << endl;
//cout << it->->_row << ":" << it->->_col << endl;
cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;
++it;
}
cout << endl;
}
void Fun(const list<int>& lt)
{
list<int>::const_Iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void test_list03()
{
list<int> It2;
It2.push_back(1);
It2.push_back(2);
It2.push_back(3);
Fun(It2);
}
void test_list04()
{
list<int> It3;
It3.push_back(1);
It3.push_back(2);
It3.push_back(3);
It3.insert(It3.begin(), 100);
It3.push_back(1);
It3.push_back(2);
It3.push_back(3);
It3.erase(++It3.begin());
list<int>::iterator it = It3.begin();
while (it != It3.end())
{
cout << *it << " ";
++it;
}
cout << endl;
It3.pop_back();
list<int>::iterator it2 = It3.begin();
while (it2 != It3.end())
{
cout << *it2 << " ";
++it2;
}
cout << endl;
It3.push_front(200);
list<int>::iterator it3 = It3.begin();
while (it3 != It3.end())
{
cout << *it3 << " ";
++it3;
}
cout << endl;
It3.pop_front();
list<int>::iterator it4 = It3.begin();
while (it4 != It3.end())
{
cout << *it4 << " ";
++it4;
}
}
}