总述
list模拟实现主要包括四个类：节点类、迭代器类、反向迭代器类、list类。
list底层结构：
因为list的底层空间不连续，所以迭代器不能使用原生态的指针，将节点类型的指针封装成类，重载解引用及自增等常用操作。list可以保存多种数据类型，所以这些类都写成类模板
一、节点类
list底层是带头结点的双向循环链表，先实现节点类，给成类模板的形式，便于插入不同类型的数据。
template<class T>
struct ListNode
{
ListNode<T>* prev;
ListNode<T>* next;
T data;//要在链表中保存的数据类型
ListNode(const T& value = T())
:prev(nullptr)
, next(nullptr)
, data(value)
{ }
};
定义新节点的方法：
ListNode<变量类型>*变量名=new ListNode(value)；
二、迭代器类
迭代器类模板有三个参数
- T：迭代器指向的元素类型
- Ref：返回的引用类型
- Ptr：返回的指针类型
Ref和Ptr一般不写成T&和T*。
成员变量
迭代器类的成员变量就是节点类型的指针
Node* _pNode;//成员变量，节点类型指针构造函数
编译器默认的构造函数是无参的，构造函数需要给出
ListIterator(Node* pNode = nullptr)
:_pNode(pNode)
{}
*重载
返回节点中保存的数据
Ref operator*()
{
return _pNode->data;
}
->重载
返回节点中保存的数据的地址
Ptr operator->()
{
return &_pNode->data;
}
->的重载只对内置类型有意义：
“++”
前置++
返回值是迭代器自身类型的引用，前面已经将ListIterator<T, Ref, Ptr>重命名位Self，表示迭代器自身的类型。
Self& operator++()
{
_pNode = _pNode->next;
return *this;
}
后置++
定义临时变量，返回自增前的值
Self operator++(int)
{
Self temp(*this);
_pNode = _pNode->next;
return temp;
}
“–”
与++原理相同
Self& operator--()
{
_pNode = _pNode->prev;
return (*this);
}
Self operator--(int)
{
Self temp(*this);
_pNode = _pNode->prev;
return temp;
}
“==“和”!=”
比较两个迭代器中封装的指针
bool operator!=(const Self& it)
{
return _pNode != it._pNode;
}
bool operator==(const Self& it)
{
return _pNode == it._pNode;
}
三、反向迭代器类
反向迭代器可以对迭代器类进行复用
因为类外访问静态成员变量时也会使用类名::变量名的方式，所以对迭代器类中的Reference和Pointer进行重命名时要加上typename,明确告诉编译器要重命名的是一个数据类型。否则编译器会报错：
成员变量
反向迭代器对迭代器类进行复用
private:
Iterator _it;//正向迭代器
*重载
反向迭代器的解引用要做特殊处理，返回的是对迭代器–的值
Reference operator*()
{
/
//复用insert
insert(begin(), value);
}
void pop_front()
{
erase(begin());
}
//⭐insert
// iterator是ListIterator<T, T&, T*>
iterator insert(iterator Insertpos, const T& value)
{
Node* newnode = new Node(value);
Node* pos = Insertpos._pNode;//_pNode是节点类型的指针
newnode->next = pos;
newnode->prev = pos->prev;
newnode->prev->next = newnode;
pos->prev = newnode;
//return newnode;
//⭐迭代器是封装的Node*指针，此时不能再返回newnode
return iterator(newnode);//构造匿名对象返回
}
//⭐erase
iterator erase(iterator Erasepos)
{
Node* pos = Erasepos._pNode;
Node* ret = pos->next;
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
delete pos;
return iterator(ret);
}
iterator erase(iterator first, iterator last)
{
auto it = first;
while (it != last)
{
//it=erase(it);
erase(it++);
}
return it;
}
void clear()
{
erase(begin(), end());
}
void swap(list<T>& l)
{
std::swap(head, l.head);
}
private:
//提供一个创造头结点的方法
void CreatHead()
{
//调用节点类的构造方法
head = new Node();
head->next = head;
head->prev = head;
}
private:
Node* head;
};
template<class T>
void PrintList(const list<T>& l)
{
auto it = l.cbegin();
while (it != l.cend())
{
cout << *it << " ";
++it;
}
cout << endl;
}
}
void Test1()
{
ZH::list<int> l1;
ZH::list<int> l2(3, 1);
PrintList(l2);
ZH::list<int> l3(l2.begin(), l2.end());
PrintList(l3);
vector<int> v{ 0,1,2,3,4 };
ZH::list<int> l4(v.begin(), v.end());
PrintList(l4);
}
void Test2()
{
vector<int> v{ 1,2,3,4 };
ZH::list<int> L1(v.begin(), v.end());
L1.push_back(5);
L1.push_back(6);
L1.push_front(0);
PrintList(L1);
L1.pop_back();
L1.pop_front();
PrintList(L1);
L1.erase(--L1.end());
PrintList(L1);
}
void Test3()
{
ZH::list<int> L1;
L1.push_back(1);
L1.push_back(2);
L1.push_back(3);
L1.push_front(0);
PrintList(L1);
L1.resize(6, 5);
PrintList(L1);
}
struct A
{
int a;
int b;
int c;
};
void Test4()
{
A aa{ 1,2,3 };
A bb{ 4,5,6 };
A cc{ 7,8,9 };
ZH::list<A> L;
L.push_back(aa);
L.push_back(bb);
L.push_back(cc);
auto it = L.begin();
while (it != L.end())
{
//⭐it->得到的是节点的地址
//本应是it->->a，编译器做了特殊处理
cout << it->a << " ";
it++;
}
cout << endl;
}
void Test5()
{
ZH::list<int> L1;
L1.push_back(0);
L1.push_back(1);
L1.push_back(2);
L1.push_back(3);
PrintList(L1);
cout << L1.back() << endl;
cout << L1.front() << endl;
cout << L1.size() << endl;
L1.clear();
cout << L1.size() << endl;
}
void Test6()
{
ZH::list<int> L1;
L1.push_back(0);
L1.push_back(1);
L1.push_back(2);
L1.push_back(3);
PrintList(L1);
//区间删除
ZH::list<int> L2;
L2.push_back(1);
L2.push_back(2);
L2.push_back(3);
L2.push_back(4);
L2.push_back(5);
PrintList(L2);
L1.swap(L2);
PrintList(L1);
PrintList(L2);
}
int main()
{
Test6();
system("pause");
return 0;
}
总结
以上为个人经验，希望能给大家一个参考，也希望大家多多支持编程网。
