汕头企业网站模板建站,创建站点的方法,外贸网站优化排名,平面设计软件免费目录 1. list的介绍及使用
1.1 list的介绍
1.2 list的使用
1.2.1 list的构造 1.2.2 list iterator的使用 1.2.3 list capacity
1.2.4 list element access 1.2.5 list modififiers
1.2.6 list的迭代器失效
2. list的模拟实现
2.1 模拟实现list
2.2 list的反向迭代器 1.…目录 1. list的介绍及使用
1.1 list的介绍
1.2 list的使用
1.2.1 list的构造 1.2.2 list iterator的使用 1.2.3 list capacity
1.2.4 list element access 1.2.5 list modififiers
1.2.6 list的迭代器失效
2. list的模拟实现
2.1 模拟实现list
2.2 list的反向迭代器 1. list的介绍及使用 1.1 list的介绍 1. list 是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。 2. list 的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。 3. list 与 forward_list 非常相似最主要的不同在于 forward_list 是单链表只能朝前迭代已让其更简单高效。 4. 与其他的序列式容器相比 (array vector deque) list 通常在任意位置进行插入、移除元素的执行效率更好。 5. 与其他序列式容器相比 list 和 forward_list 最大的缺陷是不支持任意位置的随机访问比如要访问 list的第6 个元素必须从已知的位置 ( 比如头部或者尾部 ) 迭代到该位置在这段位置上迭代需要线性的时间开销list 还需要一些额外的空间以保存每个节点的相关联信息 ( 对于存储类型较小元素的大 list 来说这可能是一个重要的因素) 1.2 list的使用 list 中的接口比较多此处类似只需要掌握如何正确的使用然后再去深入研究背后的原理已达到可扩展的能力。以下为list 中一些 常见的重要接口 1.2.1 list的构造 构造函数 (constructor) 接口说明 list (size_type n, const value_type val value_type()) 构造的 list 中包含 n 个值为 val 的元素 list() 构造空的 list list (const list x) 拷贝构造函数 list (InputIterator fifirst, InputIterator last) 用 [fifirst, last) 区间中的元素构造 list 1.2.2 list iterator的使用 此处大家可暂时 将迭代器理解成一个指针该指针指向 list 中的某个节点 。 【注意】 1. begin 与 end 为正向迭代器对迭代器执行 操作迭代器向后移动 2. rbegin(end) 与 rend(begin) 为反向迭代器对迭代器执行 操作迭代器向前移动 1.2.3 list capacity 1.2.4 list element access 1.2.5 list modififiers 函数声明 接口说明 push_front 在 list 首元素前插入值为 val 的元素 pop_front 删除 list 中第一个元素 push_back 在 list 尾部插入值为 val 的元素 pop_back 删除 list 中最后一个元素 insert 在 list position 位置中插入值为 val 的元素 erase 删除 list position 位置的元素 swap 交换两个 list 中的元素 clear 清空 list 中的有效元素 1.2.6 list的迭代器失效 前面说过此处大家可将迭代器暂时理解成类似于指针 迭代器失效即迭代器所指向的节点的无效即该节 点被删除了 。因为 list 的底层结构为带头结点的双向循环链表 因此 在 list 中进行插入时是不会导致 list 的迭代 器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响 。 2. list的模拟实现 2.1 模拟实现list 要模拟实现 list 必须要熟悉 list 的底层结构以及其接口的含义通过上面的学习这些内容已基本掌握现在我们来模拟实现list 。 #pragma once#include iostream
using namespace std;
#include assert.hnamespace bite
{// List的节点类templateclass Tstruct ListNode{ListNode(const T val T()): _prev(nullptr), _next(nullptr), _val(val){}ListNodeT* _prev;ListNodeT* _next;T _val;};/*List 的迭代器迭代器有两种实现方式具体应根据容器底层数据结构实现1. 原生态指针比如vector2. 将原生态指针进行封装因迭代器使用形式与指针完全相同因此在自定义的类中必须实现以下方法1. 指针可以解引用迭代器的类中必须重载operator*()2. 指针可以通过-访问其所指空间成员迭代器类中必须重载oprator-()3. 指针可以向后移动迭代器类中必须重载operator()与operator(int)至于operator--()/operator--(int)释放需要重载根据具体的结构来抉择双向链表可以向前 移动所以需要重载如果是forward_list就不需要重载--4. 迭代器需要进行是否相等的比较因此还需要重载operator()与operator!()*/templateclass T, class Ref, class Ptrclass ListIterator{typedef ListNodeT Node;typedef ListIteratorT, Ref, Ptr Self;// Ref 和 Ptr 类型需要重定义下实现反向迭代器时需要用到public:typedef Ref Ref;typedef Ptr Ptr;public://// 构造ListIterator(Node* node nullptr): _node(node){}//// 具有指针类似行为Ref operator*() { return _node-_val;}Ptr operator-() { return (operator*()); }//// 迭代器支持移动Self operator(){_node _node-_next;return *this;}Self operator(int){Self temp(*this);_node _node-_next;return temp;}Self operator--(){_node _node-_prev;return *this;}Self operator--(int){Self temp(*this);_node _node-_prev;return temp;}//// 迭代器支持比较bool operator!(const Self l)const{ return _node ! l._node;}bool operator(const Self l)const{ return _node ! l._node;}Node* _node;};templateclass Iteratorclass ReverseListIterator{// 注意此处typename的作用是明确告诉编译器Ref是Iterator类中的一个类型而不是静态成员变量// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的public:typedef typename Iterator::Ref Ref;typedef typename Iterator::Ptr Ptr;typedef ReverseListIteratorIterator Self;public://// 构造ReverseListIterator(Iterator it): _it(it){}//// 具有指针类似行为Ref operator*(){Iterator temp(_it);--temp;return *temp;}Ptr operator-(){return (operator*());}//// 迭代器支持移动Self operator(){--_it;return *this;}Self operator(int){Self temp(*this);--_it;return temp;}Self operator--(){_it;return *this;}Self operator--(int){Self temp(*this);_it;return temp;}//// 迭代器支持比较bool operator!(const Self l)const{return _it ! l._it;}bool operator(const Self l)const{return _it ! l._it;}Iterator _it;};templateclass Tclass list{typedef ListNodeT Node;public:// 正向迭代器typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T const_iterator;// 反向迭代器typedef ReverseListIteratoriterator reverse_iterator;typedef ReverseListIteratorconst_iterator const_reverse_iterator;public:///// List的构造list(){CreateHead();}list(int n, const T value T()){CreateHead();for (int i 0; i n; i)push_back(value);}template class Iteratorlist(Iterator first, Iterator last){CreateHead();while (first ! last){push_back(*first);first;}}list(const listT l){CreateHead();// 用l中的元素构造临时的temp,然后与当前对象交换listT temp(l.begin(), l.end());this-swap(temp);}listT operator(listT l){this-swap(l);return *this;}~list(){clear();delete _head;_head nullptr;}///// List的迭代器iterator begin() { return iterator(_head-_next); }iterator end() { return iterator(_head); }const_iterator begin()const { return const_iterator(_head-_next); }const_iterator end()const{ return const_iterator(_head); }reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin()const{return const_reverse_iterator(end());}const_reverse_iterator rend()const{return const_reverse_iterator(begin());}///// List的容量相关size_t size()const{Node* cur _head-_next;size_t count 0;while (cur ! _head){count;cur cur-_next;}return count;}bool empty()const{return _head-_next _head;}void resize(size_t newsize, const T data T()){size_t oldsize size();if (newsize oldsize){// 有效元素个数减少到newsizewhile (newsize oldsize){pop_back();oldsize--;}}else{while (oldsize newsize){push_back(data);oldsize;}}}// List的元素访问操作// 注意List不支持operator[]T front(){return _head-_next-_val;}const T front()const{return _head-_next-_val;}T back(){return _head-_prev-_val;}const T back()const{return _head-_prev-_val;}// List的插入和删除void push_back(const T val) { insert(end(), val); }void pop_back() { erase(--end()); }void push_front(const T val) { insert(begin(), val); }void pop_front() { erase(begin()); }// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T val){Node* pNewNode new Node(val);Node* pCur pos._node;// 先将新节点插入pNewNode-_prev pCur-_prev;pNewNode-_next pCur;pNewNode-_prev-_next pNewNode;pCur-_prev pNewNode;return iterator(pNewNode);}// 删除pos位置的节点返回该节点的下一个位置iterator erase(iterator pos){// 找到待删除的节点Node* pDel pos._node;Node* pRet pDel-_next;// 将该节点从链表中拆下来并删除pDel-_prev-_next pDel-_next;pDel-_next-_prev pDel-_prev;delete pDel;return iterator(pRet);}void clear(){Node* cur _head-_next;// 采用头删除删除while (cur ! _head){_head-_next cur-_next;delete cur;cur _head-_next;}_head-_next _head-_prev _head;}void swap(bite::listT l){std::swap(_head, l._head);}private:void CreateHead(){_head new Node;_head-_prev _head;_head-_next _head;}private:Node* _head;};
}///
// 对模拟实现的list进行测试
// 正向打印链表
templateclass T
void PrintList(const bite::listT l)
{auto it l.begin();while (it ! l.end()){cout *it ;it;}cout endl;
}// 测试List的构造
void TestBiteList1()
{bite::listint l1;bite::listint l2(10, 5);PrintList(l2);int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };bite::listint l3(array, array sizeof(array) / sizeof(array[0]));PrintList(l3);bite::listint l4(l3);PrintList(l4);l1 l4;PrintList(l1);
}// PushBack()/PopBack()/PushFront()/PopFront()
void TestBiteList2()
{// 测试PushBack与PopBackbite::listint l;l.push_back(1);l.push_back(2);l.push_back(3);PrintList(l);l.pop_back();l.pop_back();PrintList(l);l.pop_back();cout l.size() endl;// 测试PushFront与PopFrontl.push_front(1);l.push_front(2);l.push_front(3);PrintList(l);l.pop_front();l.pop_front();PrintList(l);l.pop_front();cout l.size() endl;
}// 测试insert和erase
void TestBiteList3()
{int array[] { 1, 2, 3, 4, 5 };bite::listint l(array, array sizeof(array) / sizeof(array[0]));auto pos l.begin();l.insert(l.begin(), 0);PrintList(l);pos;l.insert(pos, 2);PrintList(l);l.erase(l.begin());l.erase(pos);PrintList(l);// pos指向的节点已经被删除pos迭代器失效cout *pos endl;auto it l.begin();while (it ! l.end()){it l.erase(it);}cout l.size() endl;
}// 测试反向迭代器
void TestBiteList4()
{int array[] { 1, 2, 3, 4, 5 };bite::listint l(array, array sizeof(array) / sizeof(array[0]));auto rit l.rbegin();while (rit ! l.rend()){cout *rit ;rit;}cout endl;const bite::listint cl(l);auto crit l.rbegin();while (crit ! l.rend()){cout *crit ;crit;}cout endl;
} 2.2 list的反向迭代器 通过前面例子知道反向迭代器的 就是正向迭代器的 -- 反向迭代器的 -- 就是正向迭代器的 因此反向迭代器的实现可以借助正向迭代器即反向迭代器内部可以包含一个正向迭代器对正向迭代器的接口进行包装即可。 templateclass Iterator
class ReverseListIterator
{// 注意此处typename的作用是明确告诉编译器Ref是Iterator类中的类型而不是静态成员变量// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:typedef typename Iterator::Ref Ref;typedef typename Iterator::Ptr Ptr;typedef ReverseListIteratorIterator Self;
public://// 构造ReverseListIterator(Iterator it): _it(it){}//// 具有指针类似行为Ref operator*(){Iterator temp(_it);--temp;return *temp;}Ptr operator-(){ return (operator*());}//// 迭代器支持移动Self operator(){
--_it;return *this;}Self operator(int){Self temp(*this);--_it;return temp;}Self operator--(){_it;return *this;}Self operator--(int){Self temp(*this);_it;return temp;}//// 迭代器支持比较bool operator!(const Self l)const{ return _it ! l._it;}bool operator(const Self l)const{ return _it ! l._it;}Iterator _it;
};