前言:list是带头双向循环链表,物理空间不连续,导致对于迭代器的操作需要进行运算符重载,难点也在于对迭代器的使用与实现
//底层代码 #pragma once #include #includeusing namespace std; namespace bit { template struct ListNode { ListNode * next; ListNode * prev; T data; ListNode(T x = 0)//在这里进行数据的深拷贝 : next(nullptr), prev(nullptr), data(x)//初始化列表 {} }; template struct NodeIterator { typedef ListNode Node; typedef NodeIterator iterator; NodeIterator(Node* tmp) : _node( tmp) {} ref operator*() const { return _node->data; } //++it iterator operator++() { _node = _node->next; return *this; } // it++ iterator operator++(int) { iterator tmp(*this); _node = _node->next; return tmp; } //it-- iterator operator--(int) { iterator tmp(*this); _node = _node->prev; return tmp; } iterator operator--() { _node = _node->prev; return *this; } bool operator!=(const iterator& n) const { return _node != n._node; } ptr operator->() { return &(_node->data); } Node* _node; }; template class list { public: typedef NodeIterator iterator; typedef NodeIterator const_iterator; typedef ListNode Node; list(const list& s) { size = 0; phead = new Node(0); phead->prev = phead->next = phead; for (auto& e : s) push_back(e); } void clear() { auto it = begin(); while (it != end()) it = erase(it); } ~list() { clear(); delete phead; size = 0; phead = nullptr; } list() { size = 0; phead = new Node(0); phead->prev = phead->next = phead; } void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(end()._node->prev); } void pop_front() { erase(begin()); } iterator begin() { return phead->next; } iterator end() { return phead; } const_iterator begin()const { return phead->next; } const_iterator end()const { return phead; } void insert(iterator position, const T& val) { Node* _position = position._node; Node* tmp = new Node(val); tmp->next = _position; tmp->prev = _position->prev; _position->prev->next = tmp; _position->prev = tmp; size++; } iterator erase(iterator position) { Node* _position = position._node; Node* tt = _position->next; Node* tmp = _position->prev; tmp->next = _position->next; _position->next->prev = tmp; delete _position; size--; _position = nullptr; return tt; } list& operator= ( list x ) { swap(x); return *this; } bool empty() { return size == 0; } void swap(list s) { std::swap(size, s.size); std::swap(phead, s.phead); } list& operator= (list x) { swap(x); return *this; } private: Node* phead;//头结点 int size; }; }
迭代器
迭代器一般需要进行如下操作
std::list
while( it != s.end())
{
cout << *it << " ";
it++;
}
也就是需要对运算符 * != ++ 对操作符重载
明确一点:链表中的迭代器是节点的指针 , 指针是内置类型 ,但需要对内置类型的行为重新定义,则可以把内置类型转换成自定义类型(单独为迭代器写一个类)
首先 * 一般是取链表中的元素(节点中的data) ,在迭代器中需要取data,只需要将节点的指针作为迭代器类的成员变量
第二点 迭代器可以分为const 或者是 非const ,则可以将迭代器写成一个类模版
// 首先在begin函数中 分为 iterator begin() const_iterator begin() const // typedef NodeIterator< T , T& , typename T*> iterator; // typedef NodeIterator< T , const T& , T* > const_iterator; // 就导致NodeIterator只生成两个类 // iterator begin 放回的是iterator(他就只会调用第一个类) // const_iterator begin返回的是const_iterator(只会调用第二个类) templatestruct NodeIterator { typedef ListNode Node; typedef NodeIterator iterator; NodeIterator(Node* tmp) : _node( tmp) {} ref operator*() const { return _node->data; } //++it iterator operator++() { _node = _node->next; return *this; } // it++ iterator operator++(int) { iterator tmp(*this); _node = _node->next; return tmp; } //it-- iterator operator--(int) { iterator tmp(*this); _node = _node->prev; return tmp; } iterator operator--() { _node = _node->prev; return *this; } bool operator!=(const iterator& n) const { return _node != n._node; } ptr operator->() { return &(_node->data); } Node* _node; };
构造函数
方法1:初始化链表初始化
#include#include #include #include
using namespace std; int main() { list s = { 1 , 2 , 3 , 4 , 5 }; for (auto& e : s)cout << e << " "; cout << endl; }
方法2:迭代器区间初始化
#include#include #include #include
using namespace std; int main() { vector dp = { 1 , 2 , 3 ,4 , 6 }; auto it = dp.begin(); list s(it + 2, dp.end() - 1); for (auto& e : s)cout << e << " "; cout << endl; }
方法3:不加任何条件
#include#include #include #include
using namespace std; int main() { list s; return 0; }
拷贝构造与赋值重载
均为深拷贝
front与back函数
返回头和尾元素
#include#include #include #include
using namespace std; int main() { vector dp = { 1 , 2 , 3 ,4 , 6 }; int f = dp.front(); int t = dp.back(); cout << f << " " << t << endl; }
insert函数
在某一个位置之前插入一个值或一段区间
#include#include #include #include
using namespace std; int main() { list s = { 1 , 2 , 4 , 5 , 6 }; auto it = s.begin(); vector dp = { 1 , 0 , 9 }; s.insert(it, dp.begin(), dp.end()); for (auto& e : s)cout << e << " "; cout << endl; s.insert(s.end(), 10); for (auto& e : s)cout << e << " "; cout << endl; }
erase函数
去除某一个位置的值,或某一段区间的值
#include#include #include #include
using namespace std; int main() { list s = { 1 , 2 , 3 , 5 , 3 }; s.erase(s.begin()); list p = { 4 , 5 , 12 , 3 , 4 }; s.erase(++p.begin(), --p.end()); for (auto& e : p)cout << e << " "; cout << endl; }
push_back 与push_front函数
本质复用insert函数 尾插 头插
pop_back与pop_front函数
本质复用erase函数
assign函数
将链表中的内容重新分配
#include#include #include #include
using namespace std; int main() { list s = { 1, 2, 3, 4, 6 }; list k = { 9 , 1 , 0 }; s.assign({ 2,3,45 }); for (auto& e : s)cout << e << " "; cout << endl; s.assign(k.begin(),k.end()); for (auto& e : s)cout << e << " "; cout << endl; }