那些做面点的网站好,广州地区网站建设,wordpress 搬家500错误,做网站和app需要多久1. list的介绍及使用
1.1 list的介绍
list的文档介绍 list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代。 list的底层是双向链表结构#xff0c;双向链表中每个元素存储在互不相关的独立节点中#xff0c;在节点中通过…1. list的介绍及使用
1.1 list的介绍
list的文档介绍 list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。 list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。 list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。 与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。 与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素
1.2 list的使用
头插、尾插、尾删、头删
#include vector
#include algorithm
#include time.h
#include set
using namespace std;#include List.hvoid test_list1()
{// 尾插listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;// 头插lt.push_front(10);lt.push_front(20);lt.push_front(30);lt.push_front(40);for (auto e : lt){cout e ;}cout endl;// 尾删lt.pop_back();lt.pop_back();// 头删lt.pop_front();lt.pop_front();for (auto e : lt){cout e ;}cout endl;lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();//lt.pop_back();for (auto e : lt){cout e ;}cout endl;
}insert的用法
void test_list2()
{listint lt;// 尾插lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);auto pos find(lt.begin(), lt.end(), 3);if (pos ! lt.end()){// insert就是在pos位置前插入一个节点// insert以后pos是否失效呢此处不存在失效// 在vector中扩容后pos的形参发生改变但是实参不会发生改变// 但是list是用链表结构就算扩容也不会使pos的形参发生变化lt.insert(pos, 30);}// 下面两个代码的测试可以发现pos并不会失效cout *pos endl;(*pos);for (auto e : lt){cout e ;}cout endl;// 此处pos失效因为pos指向的节点都被释放了那么再访问pos指向的空间就会造成野指针lt.erase(pos);//cout *pos endl;for (auto e : lt){cout e ;}cout endl;
}remove的用法
void test_list3()
{listint lt;lt.push_back(10);lt.push_back(2);lt.push_back(5);lt.push_back(3);lt.push_back(4);lt.push_back(4);lt.push_back(6);lt.push_back(4);lt.push_back(3);for (auto e : lt){cout e ;}cout endl;// 打印结果为10 2 5 3 4 4 6 4 3// void remove (const value_type val);// 从容器中删除所有与 val 相等的元素。这将调用这些对象的析构函数并按删除的元素数减小容器大小。// 因此会将链表中val值为3的节点全部删除并缩小容器的大小lt.remove(3);for (auto e : lt){cout e ;}cout endl;// 打印结果为10 2 5 4 4 6 4lt.remove(30);for (auto e : lt){cout e ;}cout endl;// 打印结果为10 2 5 4 4 6 4lt.sort(); // 链表自带的排序功能/*sort(lt.begin(), lt.end()); // 库里面自带的排序功能参数为迭代器的起始和结束位置*/for (auto e : lt){cout e ;}cout endl;// 先排序才能实现去重/*void unique();没有参数的版本从容器中每个连续的相等元素组中删除除第一个元素之外的所有元素。请注意只有当元素与紧接其前面的元素相等时才会从列表容器中删除该元素。因此此函数对于排序列表特别有用。*/lt.unique();for (auto e : lt){cout e ;}cout endl;
}vector和list排序速度的比较
void test_op()
{srand(time(0));const int N 100000;// 创建一个vector对象并提前预留足够大的空间vectorint v;v.reserve(N);// 创建两个list对象listint lt1;listint lt2;for (int i 0; i N; i){// 将生成的随机数尾插到两个链表中auto e rand();//v.push_back(e);lt1.push_back(e);lt2.push_back(e);}// 将链表lt1中的数据拷贝到vector对象v中int begin1 clock();for (auto e : lt1){v.push_back(e);}// 使用std::sort对vector对象v中的数据进行排序sort(v.begin(), v.end());size_t i 0;for (auto e : lt1){// e是lt1数据的引用// 所以对e进行赋值就是拷贝v中的数据到lt1中e v[i];}int end1 clock();// 直接使用链表中自带的排序函数对链表2中的数据进行排序int begin2 clock();// sort(lt.begin(), lt.end());lt2.sort();int end2 clock();printf(vector sort:%d\n, end1 - begin1);printf(list sort:%d\n, end2 - begin2);/*// 打印结果为vector sort : 246list sort : 118*/// 综上可知vector的排序速度是远大于list的排序速度的
}2. list的模拟实现
list的私有成员变量
private:node* _head; // 链表的头节点size_t _size; // 链表的大小list_node(节点的类)
// 此处的T和listT是同一个模板参数
templateclass T
struct list_node
{// _next指向下一个节点list_nodeT* _next;// _prev指向前一个节点list_nodeT* _prev;// 该节点存放的数据T _data;// 节点的构造函数list_node(const T x) :_next(nullptr) , _prev(nullptr), _data(x){}
};__list_iterator(迭代器的类)
迭代器的价值
1.封装底层实现不暴露底层实现的细节。
2.提供统一的访问方式降低使用成本。// 迭代器的类类型就是__list_iteratorT
// 类名就是__list_iterator
templateclass T
struct __list_iterator
{// list_nodeT 就是节点的类类型将节点的类类型定义为nodetypedef list_nodeT node;// 定义了一个节点指针但是并没有进行初始化node* _pnode; // 迭代器的构造函数__list_iterator(node* p) :_pnode(p) // 使用传递的节点p来初始化_pnode{}// 迭代器的解引用// it为迭代器(*it) 其实就是对_pnode-_data进行, 因为是传引用返回// T会根据_pnode-_data的类型实例化对应的类型T operator*() // 解引用就是返回 _pnode-data{return _pnode-_data;}// 迭代器// 也就是返回_pnode-next指向节点的地址// 此处是传引用返回因为_pnode-_next指向的节点存在于主函数中// 所以传引用返回后依旧可以进行读写操作// __list_iteratorT 就是对迭代器对象的引用// __list_iteratorT是迭代器的类型__list_iteratorT operator() {// 修改迭代器成员变量_pnode指向的节点_pnode _pnode-_next;// this就是迭代器对象的指针// 返回*this就是返回迭代器对象return *this; }bool operator!(const __list_iteratorT it){// 判断是否相等也就是判断两个迭代器的_pnode是否相等比较地址是否相等return _pnode ! it._pnode; }
};__list_const_iterator(const迭代器的类)
// 跟普通迭代器的区别遍历不能用*it修改数据
// it就是迭代器对象*it就是迭代器指向的节点的数据
// 对于const迭代器const修饰的是*it因此对于*it只能读不能够进行修改/*
1.const T* p1; // const在*左侧修饰的是*p1
2.T* const p2; // const在*右侧修饰的是p2
// const迭代器类似于第一种情况保护指向的对象不被修改但是迭代器本身是可以修改的注普通迭代器前加const可不是const迭代器如下
const listint::iterator cit lt.begin();
// 这里的const修饰的是cit也就是保护迭代器本身不可以进行修改那么就不可以对cit进行或者--的操作这不符合迭代器的行为
*/templateclass T
struct __list_const_iterator
{// list_nodeT 就是节点的类类型将节点的类类型定义为nodetypedef list_nodeT node;// 定义了一个节点指针但是并没有进行初始化node* _pnode;// const迭代器的构造函数__list_const_iterator( node* p):_pnode(p){}// const迭代器的解引用const T operator*() {// 会根据_pnode-_data类型来实例化const T 的类型// const修饰的是返回值因此返回值无法进行修改// 之所以可以进行引用返回是因为_pnode-_data不会随着函数而结束自身的生命周期return _pnode-_data;}// const迭代器// __list_const_iteratorT是const迭代器的类型// __list_const_iteratorT 是对const迭代器对象的引用// 此处的返回值可以被传引用返回__list_const_iteratorT operator(){// 更新const迭代器对象的成员变量_pnode指向的节点_pnode _pnode-_next;// 返回迭代器对象return *this;}// const迭代器--__list_const_iteratorT operator--(){_pnode _pnode-_prev;return *this;}// const迭代器判断是否相等bool operator!(const __list_const_iteratorT it){return _pnode ! it._pnode;}
};对普通迭代器和const迭代器的合并
// 我们发现迭代器和const迭代器有大量的冗余代码因此做出合并
/*
Ref 是reference的缩写
ref就是引用ptr就是指针
templateclass T, class Ref, class Ptr同一个类模板实例化出的两个类型
Ref可以被实例化为T也可以被实例化为const T
Ptr可以被实例化为T*也可以被实例化为const T*
typedef __list_iteratorT, T, T* iterator;
typedef __list_iteratorT, const T, const T* const_iterator;如果是节点类型为 listint
则templateclass T, class Ref, class Ptr将被实例化为下面两种类类型
也就是将一个迭代器类模板实例化为了两个类一个普通迭代器的类一个const迭代器的类
typedef __list_iteratorint, int, int* iterator;
typedef __list_iteratorint, const int, const int* const_iterator;
*/templateclass T, class Ref, class Ptr
struct __list_iterator
{// 将节点的类类型定义为nodetypedef list_nodeT node;// 将迭代器的类类型定义为Selftypedef __list_iteratorT, Ref, Ptr Self;// 定义了一个节点指针但是并没有进行初始化node* _pnode;// 迭代器的构造函数__list_iterator(node* p):_pnode(p){}// 迭代器的-操作// 通过指针访问节点对象的成员变量data// 在主函数中如果创建const迭代器也就是 const_iterator cit(head-next)// 因为typedef __list_iteratorT, const T, const T* const_iterator;// templateclass T, class Ref, class Ptr// 所以Ptr对应的类型是const int*// 如果链表的类类型是listint// 那么Ptr的类型是const int*Ptr operator-(){ // _pnode是链表节点的指针// _pnode-_data可以拿到链表节点存放的数据// _pnode-_data也就是取链表节点存放的数据的地址return _pnode-_data;}/*// (详细看test_list5)下面这两种方法是等价的cout it-_row : it-_col endl;cout it.operator-()-_row : it.operator-()-_col endl;// it- 是一个函数调用即it.operator-()// it.operator-() 的返回对象类类型是pos*所以再次使用- 返回pos类型的成员变量row的值// 本来面貌it--_row编译器为了可读性做了特殊处理省略了一个-*/// 同上Ref的类型应该是const intRef operator*(){return _pnode-_data;}// it 前置// 因为typedef __list_iteratorT, Ref, Ptr Self;所以Self就是一个迭代器的类类型Self operator(){_pnode _pnode-_next;// 返回一个迭代器对象之后的迭代器对象return *this;}// it 后置:括号中的int为占位符Self operator(int){// 使用this指针指向的迭代器对象构造一个临时的迭代器对象Self tmp(*this);_pnode _pnode-_next; // 返回之前的迭代器对象这个对象是一个临时对象因此不可以进行传引用返回return tmp;}// 前置Self operator--(){_pnode _pnode-_prev;return *this;}// 后置括号中的int为占位符Self operator--(int){Self tmp(*this);_pnode _pnode-_prev;return tmp;}bool operator!(const Self it) const{return _pnode ! it._pnode;}bool operator(const Self it) const{return _pnode it._pnode;}
};反向迭代器的类模板
// reverse_iterator.h
// 如果要使用反向迭代器必须要使用反向迭代器的头文件
// 给我不同容器的正向迭代器适配出对应的这个容器需要的反向迭代器
templateclass Iterator, class Ref, class Ptr
class ReverseIterator
{typedef ReverseIteratorIterator, Ref, Ptr Self;public:// 构造函数ReverseIterator(Iterator it):_it(it){}// 以list为例// begin() 对应的是 rend() ; begin() 指向首个元素 -- rend() 指向首个元素// end() 对应的是 rbegin() ; end() 指向的是哨兵位 -- rbegin() 指向的是哨兵位/*end() begin()哨兵位 1 2 3 4rbegin() rend()rend() rbegin() 进行--操作之后的位置*/// 因此 解引用指向的元素时必须 --tmp// 因为begin() 进行--操作之后与rbegin()对应的节点是一致的// 如 return reverse_iterator(begin()); 使用正向迭代器的开始迭代器 构造 反向迭代器的结束迭代器// 如果要进行解引用--正向迭代器之后才是其正确的位置Ref operator*(){Iterator tmp _it;return *(--tmp);}Ptr operator-(){return (operator*());}Self operator(){// 反向迭代器的对应正常迭代器的----_it;return *this;}Self operator--(){_it;return *this;}bool operator! (const Self s) const{return _it ! s._it;}private:Iterator _it;
};list双向链表的构造函数
/*
// 节点的构造函数
list_node(const T x)
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
*//*
list()
{// T()就是构造节点所需要的参数const T x// T()也就是调用x的默认构造函数去初始化这个参数x // T()类型为x的一个匿名对象_head new node(T()); _head-_next _head;_head-_prev _head;
}
*/void empty_initialize()
{_head new node(T());_head-_next _head;_head-_prev _head;
}// 双向链表的无参构造函数
list()
{empty_initialize();
}list::push_back, push_front, pop_front, pop_back
//尾插
void push_back(const T x)
{// 方法一/*// 先创建一个新节点node* newnode new node(x); // _head-prev中存放的是tail节点的地址node* tail _head-_prev; // _head newnode tail// 将上面三个节点按顺序双向链接起来tail-_next newnode; newnode-_prev tail;newnode-_next _head;_head-_prev newnode;*/// 方法二// 当我们实现insert()之后我们就可以通过insert()来实现 push_back// 也就是在end()位置前插入insert(end(), x);
}// 头插
void push_front(const T x)
{// 头插就是在begin()位置前插入insert(begin(), x);
}// 头删
void pop_front()
{// 头删就是删除begin()位置的节点erase(begin());
}// 尾删
void pop_back()
{// 尾删就是删除end()位置前的节点// --end() 会调用operator--erase(--end());
} list的拷贝构造函数的传统写法
void empty_initialize()
{_head new node(T());_head-_next _head;_head-_prev _head;
}// lt3(lt1)
list(const listT lt)
{// 初始化这个对象,也就是初始化lt3empty_initialize();// 将迭代器节点指向数据尾插到新对象中// lt是lt1的引用也就是将lt1的数据尾插到lt3// 这样就实现了lt1到lt3的拷贝for (const auto e : lt){push_back(e);}
}list拷贝函数的现代写法
// 类名 类型
// 普通类 类名 等价于 类型
// 类模板 类名 不等价于 类型
// 如list模板 类名是list 类型是listT
// 类模板里面可以用类名代表类型但是建议不要那么用// 构造函数使用迭代器来构造对象
// tmp(lt)
template class InputIterator
list(InputIterator first, InputIterator last)
{// 初始化这个对象,也就是初始化tmpempty_initialize();// first就是链表lt起始位置的迭代器对象// last就是链表lt结束位置的迭代器对象while (first ! last){// 将迭代器的数据尾插到新的链表tmp中push_back(*first);first;}
}void swap(listT lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}// 现代写法
// lt3(lt1)
list(const listT lt)
{// 初始化这个对象,也就是初始化lt3empty_initialize();// 用it的迭代区间数据创建一个list的临时对象listT tmp(lt.begin(), lt.end()); // 再将临时对象与目标对象的_head_size进行交换// 出了当前函数的作用域之后tmp就会被销毁// 但是构造给tmp的资源都已经交给了lt3swap(tmp);
}list对象的赋值重载
void clear()
{iterator it begin();while (it ! end()){// erase()会返回被删除节点的下一个节点的迭代器// 最后it就是end()位置的迭代器那么就会跳出循环// end()位置的迭代器也就是_head哨兵位节点的迭代器it erase(it); }
}// 传统写法
// lt2 lt1
listT operator(const listT lt)
{// lt就是lt1的传引用// this就是lt2的地址// this ! lt 就是判断lt2的地址是否与lt1的地址相等if (this ! lt) {// 使用clear()清空双向循环链表中除哨兵位的所有节点clear();for (const auto e : lt) // 此处使用传引用就可以减少拷贝{// 将lt的数据全部插入到lt2中push_back(e);}}// 返回lt2的迭代器对象return *this;
}// 现代写法
// lt3 lt1
listT operator(listT lt)
//list operator(list lt) // 不建议
{swap(lt);return *this;
}list::insert
// 在pos迭代器的节点位置前插入新节点
iterator insert(iterator pos, const T x)
{node* newnode new node(x);node* cur pos._pnode; // pos迭代器位置处的节点为 pos._pnodenode* prev cur-_prev; // 再找到cur的前一个节点// prev newnode cur 将这三个节点双向链接起来prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;// 使用newnode构建一个迭代器,并返回这个迭代器对象return iterator(newnode);
}list::erase
iterator erase(iterator pos)
{assert(pos ! end()); // 保证链表不为空node* prev pos._pnode-_prev; // prev 为pos._pnode前一个节点的地址node* next pos._pnode-_next; // next 为pos._pnode后一个节点的地址// 将prev next双向链接起来prev-_next next;next-_prev prev;delete pos._pnode; // 释放 pos._pnode节点// 返回 pos._pnode节点下一个节点的迭代器// 也就是返回next节点构建的迭代器return iterator(next);
}list的析构函数
void clear()
{iterator it begin();while (it ! end()){// erase()会返回被删除节点的下一个节点的迭代器// 最后it就是end()位置的迭代器那么就会跳出循环// end()位置的迭代器也就是_head哨兵位节点的迭代器it erase(it); }
}~list()
{clear();delete _head;_head nullptr;
}list类的完整实现
templateclass T
class list
{typedef list_nodeT node;
public:// 迭代器的老版本// typedef __list_iteratorT iterator;// typedef __list_const_iteratorT const_iterator;// 迭代器的改良版本// typedef __list_iteratorT, T iterator;// typedef __list_iteratorT, const T const_iterator;// 再次改良迭代器// 此处的T和listT是同一个模板参数typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;// 反向迭代器typedef ReverseIteratoriterator, T, T* reverse_iterator;typedef ReverseIteratorconst_iterator, const T, const T* const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}// 右侧的const修饰的是this指针const_iterator begin() const{// head是带头双向循环链表的哨兵位// _head-_next是双向链表的头节点// 使用头节点的指针构造一个迭代器的对象return const_iterator(_head-_next);}const_iterator end() const{// _head-next 是带头双向循环链表头节点// _head-prev 是带头双向循环链表的尾节点// end()是只迭代器的末尾位置end是尾节点的下一个位置也就是tail-next// tail-next就是哨兵位也就是_headreturn const_iterator(_head);}iterator begin(){return iterator(_head-_next);}iterator end(){// iterator it(_head);// return it;return iterator(_head); // 返回迭代器的匿名对象}void empty_initialize(){// 这里只能使用T的默认构造来对node进行构造// 因为此时并不能确定T是什么类型// 如果T是int类型那么T的默认构造T()就是0_head new node(T());_head-_next _head;_head-_prev _head;_size 0;}// 链表的构造函数list(){empty_initialize();}// 传统的拷贝函数// lt2(lt1) /*list(const listT lt){empty_initialize();for (const auto e : lt){push_back(e);}}*/// 传统的赋值重载函数// lt1 lt3//listT operator(const listT lt)//{// if (this ! lt)// {// clear();// for (const auto e : lt)// {// push_back(e);// }// }// return *this;//}// 构造函数通过迭代器来构造template class InputIterator list(InputIterator first, InputIterator last){empty_initialize();while (first ! last){push_back(*first);first;}}// 自己写的交换函数void swap(listT lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}// 拷贝函数的现代写法// 普通类 类名 等价于 类型// 类模板 类名 不等价于 类型// 如list模板 类名list 类型listT // 类模板里面也就是类模板内部可以用类名代表类型但是建议不要那么用// 拷贝函数// lt2(lt1)list(const listT lt)//list(const list lt) // 不建议这么写最好将类型写为listT {empty_initialize();listT tmp(lt.begin(), lt.end());swap(tmp);}// 赋值重载的现代写法// lt3 lt1listT operator(listT lt)//list operator(list lt) // 不建议这么写最好将类型写为listT {swap(lt);return *this;}size_t size() const{return _size;}bool empty() const{return _size 0;}~list(){clear();delete _head;_head nullptr;}void clear(){iterator it begin();while (it ! end()){it erase(it);}}void push_back(const T x){//node* newnode new node(x);//node* tail _head-_prev; _head tail newnode//tail-_next newnode;//newnode-_prev tail;//newnode-_next _head;//_head-_prev newnode;insert(end(), x);}void push_front(const T x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}iterator insert(iterator pos, const T x){node* newnode new node(x);node* cur pos._pnode;node* prev cur-_prev;// prev newnode curprev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;return iterator(newnode);}iterator erase(iterator pos){assert(pos ! end());node* prev pos._pnode-_prev;node* next pos._pnode-_next;prev-_next next;next-_prev prev;delete pos._pnode;--_size;return iterator(next);}private:node* _head;size_t _size;
};3.测试
测试迭代器test1
void test_list1()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);// iterator是类里面的类型那么有如下两种情况// 1、内嵌类型 // 2、迭代器的行为是像指针一样// 对于vector的迭代器类型typedef int* iterator; // 迭代器跳过4个字节// 对于string的迭代器类型typedef char* iterator; // 迭代器跳过1个字节// vector和string的迭代器或者--之后都可以找到对应的数据因为其存储空间是连续的// 但是对于list却不能够像vector和list一样因为每个节点的空间都是独立的因此对于list的迭代器// 需要专门实现一个迭代器的类listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;for (auto e : lt){cout e ;}cout endl;
}test_list5
struct Pos
{int _row;int _col;Pos(int row 0, int col 0):_row(row),_col(col){}
};void print_list(const listPos lt)
{// it就是链表的初始位置的迭代器// 在list类里面的定义typedef __list_iteratorT, const T, const T* const_iterator;listPos::const_iterator it lt.begin();while (it ! lt.end()){/*it- 是一个函数调用即it.operator-()it.operator-() 的返回对象类类型是const pos*所以拿到的类型为pos的对象的值是不可以被修改的因此const在*左侧这个对象被const修饰再次使用- 返回pos类型的成员变量row的值本来面貌it--_row编译器为了可读性做了特殊处理省略了一个-*/// 那么下面这行代码的使用就是错误的// it-_row;cout it-_row : it-_col endl;it;}cout endl;
}void test_list5()
{// 创建一个链表对象模版类型被实例化为pos类型listPos lt;// 创建一个pos对象Pos p1(1, 1);// 将pos对象p1尾插到链表中lt.push_back(p1);lt.push_back(p1);lt.push_back(p1);// 构建一个匿名的pos对象并将其尾插到链表中// 这个匿名的pos的生命周期只在当前这一行除了这一行这个匿名对象就会被销毁lt.push_back(Pos(2,2));lt.push_back(Pos(3,3));// int* p *p 可以通过解引用找到p指针所指向的数据// Pos* p p- 可以通过- 找到pos指针所指向的数据listPos::iterator it lt.begin();while (it ! lt.end()){// pos为一个类_row,_col为pos类的成员变量// 因为pos对象存放在链表中所以*it 解引用就可以拿到类类型为pos的对象// 在通过这个对象来访问其成员变量cout (*it)._row : (*it)._col endl;// 当我们写了 -的重载函数后// 使用- 打印pos类中数据的三种方法/*cout ((*it))-_row : (*it)._col endl;// *it 是pos (*it) 也就是pos*, 在通过pos*进行-操作找到_row的数据*//*// 下面这两种方法是等价的cout it-_row : it-_col endl;cout it.operator-()-_row : it.operator-()-_col endl;// it- 是一个函数调用即it.operator-()// it.operator-() 的返回对象类类型是pos*所以再次使用- 返回pos类型的成员变量row的值// 本来面貌it--_row编译器为了可读性做了特殊处理省略了一个-*/it;}cout endl;print_list(lt);
}4.完整的模拟实现并测试
namespace qwy
{// 链表的节点的类模板templateclass Tstruct list_node{list_nodeT* _next;list_nodeT* _prev;T _data;list_node(const T x):_next(nullptr), _prev(nullptr), _data(x){}};// 迭代器的类模板// 同一个类模板实例化出的两个类分别是普通迭代器的类和const迭代器的类// typedef __list_iteratorT, T, T* iterator;// typedef __list_iteratorT, const T, const T* const_iterator;templateclass T, class Ref, class Ptrstruct __list_iterator{typedef list_nodeT node;typedef __list_iteratorT, Ref, Ptr Self;node* _pnode;__list_iterator(node* p):_pnode(p){}Ptr operator-(){return _pnode-_data;}Ref operator*(){return _pnode-_data;}Self operator(){_pnode _pnode-_next;return *this;}Self operator(int){Self tmp(*this);_pnode _pnode-_next; return tmp;}Self operator--(){_pnode _pnode-_prev;return *this;}Self operator--(int){Self tmp(*this);_pnode _pnode-_prev;return tmp;}bool operator!(const Self it) const{return _pnode ! it._pnode;}bool operator(const Self it) const{return _pnode it._pnode;}};// 带头双向循环链表的类模板templateclass Tclass list{typedef list_nodeT node;public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);}iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}void empty_initialize(){_head new node(T());_head-_next _head;_head-_prev _head;_size 0;}list(){empty_initialize();}template class InputIterator list(InputIterator first, InputIterator last){empty_initialize();while (first ! last){push_back(*first);first;}}void swap(listT lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}// 拷贝构造的现代写法// lt2(lt1)list(const listT lt){empty_initialize();listT tmp(lt.begin(), lt.end());swap(tmp);}// 负值重载的现代写法// lt3 lt1listT operator(listT lt){swap(lt);return *this;}size_t size() const{return _size;}bool empty() const{return _size 0;}~list(){clear();delete _head;_head nullptr;}void clear(){iterator it begin();while (it ! end()){it erase(it);}}void push_back(const T x){//node* newnode new node(x);//node* tail _head-_prev; _head tail newnode//tail-_next newnode;//newnode-_prev tail;//newnode-_next _head;//_head-_prev newnode;insert(end(), x);}void push_front(const T x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}iterator insert(iterator pos, const T x){node* newnode new node(x);node* cur pos._pnode;node* prev cur-_prev;// prev newnode curprev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;return iterator(newnode);}iterator erase(iterator pos){assert(pos ! end());node* prev pos._pnode-_prev;node* next pos._pnode-_next;prev-_next next;next-_prev prev;delete pos._pnode;--_size;return iterator(next);}private:node* _head;size_t _size;};void test_list1(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);// iterator 1、内嵌类型 2、行为像指针一样 listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;for (auto e : lt){cout e ;}cout endl;}void test_list2(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);lt.push_front(6);for (auto e : lt){cout e ;}cout endl;lt.pop_back();lt.pop_back();lt.pop_front();lt.pop_front();for (auto e : lt){cout e ;}cout endl;}void test_list3(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);lt.push_front(6);for (auto e : lt){cout e ;}cout endl;cout lt.size() endl;listint lt1(lt);for (auto e : lt1){cout e ;}cout endl;listint lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);cout lt2.size() endl;lt lt2;for (auto e : lt){cout e ;}cout endl;}void print_list(const listint lt){listint::const_iterator it lt.begin();while (it ! lt.end()){// (*it) 2; // 不能写cout *it ;it;}cout endl;}void test_list4(){listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);listint::iterator it lt1.begin();while (it ! lt1.end()){(*it) 2; // 可以写cout *it ;it;}cout endl;print_list(lt1);}struct Pos{int _row;int _col;Pos(int row 0, int col 0):_row(row),_col(col){}};void print_list(const listPos lt){listPos::const_iterator it lt.begin();while (it ! lt.end()){//it-_row;cout it-_row : it-_col endl;it;}cout endl;}void test_list5(){listPos lt;Pos p1(1, 1);lt.push_back(p1);lt.push_back(p1);lt.push_back(p1);lt.push_back(Pos(2,2));lt.push_back(Pos(3,3));// int* p - *p// Pos* p - p-listPos::iterator it lt.begin();//listPos::iterator it2 it;while (it ! lt.end()){it-_row;//cout ((*it))-_row : (*it)._col endl;cout it-_row : it-_col endl;//cout it.operator-()-_row : it-_col endl;it;}cout endl;print_list(lt);}
}5.vector和list的对比
vector优点1.下标随机访问2.尾插尾删效率高3.CPU高速缓存命中高缺点1.前面部分插入删除数据低2.扩容有消耗还存在一定空间浪费list优点1.按需申请释放无需扩容2.任意位置插入删除时间复杂度为O(1)缺点1.不支持随机访问2.CPU高速缓存命中低迭代器失效vector: insert/eraselist: earsestring: insert/erase和vector类似但是string一般不关注失效因为string的insert/erase 重用接口函数都是下标支持的迭代器支持用得很少
