做网站必须要有数据库,php网站开发简历,开发帮官方网站,html网页生成工具list(2) list的迭代器 const迭代器
根据我们之前学过的知识#xff1a;
const int*p1;//修饰的是指向的内容
int *const p2;//修饰的是迭代器本身我们写const迭代器#xff0c;期望的是指向的内容不能修改。 所以更期望写上面p1的形式
const迭代器与普通迭代器的不同点在于…list(2) list的迭代器 const迭代器
根据我们之前学过的知识
const int*p1;//修饰的是指向的内容
int *const p2;//修饰的是迭代器本身我们写const迭代器期望的是指向的内容不能修改。 所以更期望写上面p1的形式
const迭代器与普通迭代器的不同点在于普通迭代器既可以读也可以写但是const修饰的迭代器只可以读
它的实现基本和普通迭代器一致
templateclass Tstruct list_const_iterator{typedef list_nodeT Node;typedef list_const_iteratorT Self;Node* _node;list_const_iterator(Node* node):_node(node){}const T operator*(){return _node-_data;}const T* operator-(){return _node-_data;}Self operator(){_node _node-_next;return *this;}Self operator--(){_node _node-_prev;return *this;}Self operator(int){Self tmp(*this);_node _node-_next;return tmp;}Self operator--(int){Self tmp(*this);_node _node-_prev;return tmp;}bool operator!(const Self s){return _node ! s._node;}};不同点在于返回值的不同因为const不希望被修改所以要用const修饰 const T operator*(){return _node-_data;}const T* operator-(){return _node-_data;}这样子写的代码会显得有些冗余和重复我们看stl_list.h的源代码可以发现 从这里看出来const迭代器和普通迭代器在编译器中都是用一个模板写出来两个类模板的本质是复用
可以这样写代码
struct list_iterator
{typedef list_nodeT Node;typedef list_iteratorT, Ref, Ptr Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*()//引用{return _node-_data;}Ptr operator-()//指针{return _node-_data;}Self operator(){_node _node-_next;return *this;}Self operator--(){_node _node-_prev;return *this;}Self operator(int){Self tmp(*this);_node _node-_next;return tmp;}Self operator--(int){Self tmp(*this);_node _node-_prev;return tmp;}bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}
};typedef list_iteratorT, T, T* iterator;
typedef list_iteratorT, const T, const T* const_iterator;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);
}迭代器不需要析构拷贝和赋值只需要做到访问和拷贝即可也就是浅拷贝
list的增删查改
代码如下 list(size_t n, const T val T()){empty_init();for (size_t i 0; i n; i){push_back(val);}}void push_back(const T x){/*Node* new_node new Node(x);Node* tail _head-_prev;tail-_next new_node;new_node-_prev tail;new_node-_next _head;_head-_prev new_node;*/insert(end(), x);//尾插是对插入的复用//因为list底层是双向循环链表物理结构不连续所以是在哨兵位附近的位置}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 val){Node* cur pos._node;Node* newnode new Node(val);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* del pos._node;Node* prev del-_prev;Node* next del-_next;prev-_next next;next-_prev prev;delete del;--_size;return iterator(next);}private:Node* _head;size_t _size;string和vector可能会出现迭代器失效的问题但是string相比较失效的可能性更小一点因为string会通过下标访问
析构
~list(){clear();delete _head;_head nullptr;}//clear只清理数据不清理空间void clear(){auto it begin();while (it ! end()){//避免迭代器失效it erase(it);}}拷贝
list()
{empty_init();
}// lt2(lt1)
list(const listT lt)
{empty_init();
//这里是深拷贝引用不是引用的话又会形成拷贝for (auto e : lt){push_back(e);}
}赋值
// lt2 lt3
//list operator(list lt)
listT operator(listT lt)
{swap(lt);return *this;
}
void swap(listT tmp)
{std::swap(_head, tmp._head);std::swap(_size, tmp._size);
}交换
template class T//这个是调用库里面的
void swap(T a, T b)
{T c(a); a b; b c;
}
//这个是针对list提炼出的一个模板
template class T
void swap(listT a, listT b)
{a.swap(b);
}模板的话编译器会更加优先匹配适配程度更高的模板所以我们这里会调用下面的模板效率会更加高效
模拟实现list的代码如下
List.h
#pragma once
#includeassert.hnamespace soobin
{// 惯例// 全部都是公有一般用structtemplateclass Tstruct list_node{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T x T()):_data(x), _next(nullptr), _prev(nullptr){}};// 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* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){_node _node-_next;return *this;}Self operator--(){_node _node-_prev;return *this;}Self operator(int){Self tmp(*this);_node _node-_next;return tmp;}Self operator--(int){Self tmp(*this);_node _node-_prev;return tmp;}bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}};/*templateclass Tstruct list_const_iterator{typedef list_nodeT Node;typedef list_const_iteratorT Self;Node* _node;list_const_iterator(Node* node):_node(node){}const T operator*(){return _node-_data;}const T* operator-(){return _node-_data;}Self operator(){_node _node-_next;return *this;}Self operator--(){_node _node-_prev;return *this;}Self operator(int){Self tmp(*this);_node _node-_next;return tmp;}Self operator--(int){Self tmp(*this);_node _node-_prev;return tmp;}bool operator!(const Self s){return _node ! s._node;}};*/templateclass Tclass list{typedef list_nodeT Node;public:/*typedef list_iteratorT iterator;typedef list_const_iteratorT const_iterator;*/typedef list_iteratorT, T, T* iterator;typedef list_iteratorT, const T, const T* const_iterator;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);}void empty_init(){_head new Node();_head-_next _head;_head-_prev _head;_size 0;//有效个数大小增加这个成员变量使其更高效}list(){empty_init();}// lt2(lt1)list(const listT lt){empty_init();for (auto e : lt){push_back(e);}}// lt2 lt3//list operator(list lt)listT operator(listT lt){swap(lt);return *this;}~list(){clear();delete _head;_head nullptr;}void swap(listT tmp){std::swap(_head, tmp._head);std::swap(_size, tmp._size);}void clear(){auto it begin();while (it ! end()){it erase(it);}}list(size_t n, const T val T()){empty_init();for (size_t i 0; i n; i){push_back(val);}}void push_back(const T x){/*Node* new_node new Node(x);Node* tail _head-_prev;tail-_next new_node;new_node-_prev tail;new_node-_next _head;_head-_prev new_node;*/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 val){Node* cur pos._node;Node* newnode new Node(val);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* del pos._node;Node* prev del-_prev;Node* next del-_next;prev-_next next;next-_prev prev;delete del;--_size;//删除元素高效return iterator(next);}private:Node* _head;size_t _size;};template class Tvoid swap(T a, T b){T c(a); a b; b c;}template class Tvoid swap(listT a, listT b){a.swap(b);}
}Test.cpp
#includeiostream
#includealgorithm
#includelist
#includevector
using namespace std;//int main()
//{
// listint lt1;
// lt1.push_back(1);
// lt1.push_back(1);
// lt1.push_back(1);
// lt1.push_back(1);
// lt1.emplace_back(10);
//
// listint lt2 {1,2,3,4,5};
//
// listint::iterator it1 lt1.begin();
// while (it1 ! lt1.end())
// {
// cout *it1 ;
// it1;
// }
// cout endl;
//
// for (auto e : lt2)
// {
// cout e ;
// }
// cout endl;
//
// return 0;
//}class Pos
{
public:int _row;int _col;Pos(int row 0, int col 0):_row(row), _col(col){cout Pos(int row, int col) endl;}Pos(const Pos p):_row(p._row), _col(p._col){cout Pos(const Pos p) endl;}
};//int main()
//{
// listPos lt;
//
// // 构造拷贝构造
// Pos p1(1, 1);
// lt.push_back(p1);
// lt.push_back(Pos(2, 2));
// lt.push_back({3,3});
//
// lt.emplace_back(p1);
// lt.emplace_back(Pos(2, 2));
// //lt.emplace_back({ 3,3 });
//
// // 直接构造
// lt.emplace_back(3, 3);
//
// return 0;
//}//int main()
//{
// listint lt1 { 1,2,3,4,5 };
//
// for (auto e : lt1)
// {
// cout e ;
// }
// cout endl;
//
// int x;
// cin x;
// auto it find(lt1.begin(), lt1.end(), x);
// if (it ! lt1.end())
// {
// lt1.erase(it);
// }
//
// for (auto e : lt1)
// {
// cout e ;
// }
// cout endl;
//
// return 0;
//}//int main()
//{
// listint lt1 { 1,2,3,4,5 };
// // LRU
// int x;
//
// while (cin x)
// {
// auto pos find(lt1.begin(), lt1.end(), x);
// if (pos ! lt1.end())
// {
// lt1.splice(lt1.begin(), lt1, pos);
// }
//
// for (auto e : lt1)
// {
// cout e ;
// }
// cout endl;
// }
//
// cout xxxxxxxxxxxxxxxxxxxxxx endl;
//
// return 0;
//}//int main()
//{
// listint lt1 { 1,20,3,-4,5 };
// for (auto e : lt1)
// {
// cout e ;
// }
// cout endl;
//
// //
// //lt1.sort();
// //
// /*greaterint gt;
// lt1.sort(gt);*/
// lt1.sort(greaterint());
//
// // 不能用
// //sort(lt1.begin(), lt1.end(), greaterint());
// for (auto e : lt1)
// {
// cout e ;
// }
// cout endl;
//
// vectorint v1 { 1,20,3,-4,5 };
// for (auto e : v1)
// {
// cout e ;
// }
// cout endl;
//
// //sort(v1.begin(), v1.end());
// sort(v1.begin(), v1.end(), greaterint());
// for (auto e : v1)
// {
// cout e ;
// }
// cout endl;
//
//
// return 0;
//}void test_op1()
{srand(time(0));const int N 1000000;listint lt1;listint lt2;vectorint v;for (int i 0; i N; i){auto e rand() i;lt1.push_back(e);v.push_back(e);}int begin1 clock();// 排序sort(v.begin(), v.end());int end1 clock();int begin2 clock();lt1.sort();int end2 clock();printf(vector sort:%d\n, end1 - begin1);printf(list sort:%d\n, end2 - begin2);
}void test_op2()
{srand(time(0));const int N 1000000;listint lt1;listint lt2;for (int i 0; i N; i){auto e rand();lt1.push_back(e);lt2.push_back(e);}int begin1 clock();// 拷贝vectorvectorint v(lt2.begin(), lt2.end());// 排序sort(v.begin(), v.end());// 拷贝回lt2lt2.assign(v.begin(), v.end());int end1 clock();int begin2 clock();lt1.sort();int end2 clock();printf(list copy vector sort copy list sort:%d\n, end1 - begin1);printf(list sort:%d\n, end2 - begin2);
}
//
//int main()
//{
// test_op1();
// test_op2();
//
// return 0;
//}#includeList.h//int main()
//{
// bit::listint lt1;
// lt1.push_back(1);
// lt1.push_back(1);
// lt1.push_back(1);
// lt1.push_back(1);
//
// soobin::listint::iterator it1 lt1.begin();
// while (it1 ! lt1.end())
// {
// *it1 2;
//
// cout *it1 ;
// it1;
// }
// cout endl;
//
// for (auto e : lt1)
// {
// cout e ;
// }
// cout endl;
//
// soobin::listPos lt2;
// Pos p1(1, 1);
// lt2.push_back(p1);
// lt2.push_back(Pos(2, 2));
// lt2.push_back({3,3});
//
// soobin::listPos::iterator it2 lt2.begin();
// while (it2 ! lt2.end())
// {
// //cout (*it2)._row : (*it2)._col endl;
// // 为了可读性特殊处理省略了一个-
// cout it2-_row : it2-_col endl;
// cout it2.operator-()-_row : it2.operator-()-_col endl;
//
// it2;
// }
// cout endl;
//}//int main()
//{
// const soonbin::listint lt1(10, 1);
//
// // const int* p1
// // int* const p2
// soobin::listint::const_iterator it1 lt1.begin();
// while (it1 ! lt1.end())
// {
// //*it1 2;
// cout *it1 ;
// it1;
// }
// cout endl;
//
// for (auto e : lt1)
// {
// cout e ;
// }
// cout endl;
//
// return 0;
//}//int main()
//{
// soobin::listint lt1;
// lt1.push_back(1);
// lt1.push_back(2);
// lt1.push_back(3);
// lt1.push_back(4);
// lt1.push_front(0);
// lt1.push_front(-1);
//
// soobin::listint::iterator it1 lt1.begin();
// while (it1 ! lt1.end())
// {
// cout *it1 ;
// it1;
// }
// cout endl;
//
// lt1.pop_front();
// lt1.pop_back();
//
// for (auto e : lt1)
// {
// cout e ;
// }
// cout endl;
//
// soobin::listint lt2(lt1);
// for (auto e : lt2)
// {
// cout e ;
// }
// cout endl;
//
// soobin::listint lt3(10, 1);
// lt2 lt3;
// for (auto e : lt2)
// {
// cout e ;
// }
// cout endl;
//}int main()
{bit::listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_front(0);lt1.push_front(-1);soobin::listint lt2(10, 1);//lt1.swap(lt2);int i 1, j 2;soobin::swap(i, j);soobin::swap(lt1, lt2);for (auto e : lt1){cout e ;}cout endl;for (auto e : lt2){cout e ;}cout endl;return 0;
}
