哈尔滨地铁爱建站,游戏加速器,网页编程入门,构建网站需要会什么意思目录
list使用
reverse
sort
unique
splice
list模拟实现
类与成员函数声明
节点类型的定义
非const正向迭代器的实现
list成员函数
构造函数
尾插
头插
头删
尾删
任意位置插入
任意位置删除
清空数据
析构函数
拷贝构造函数
赋值重载函数
const迭代器的…目录
list使用
reverse
sort
unique
splice
list模拟实现
类与成员函数声明
节点类型的定义
非const正向迭代器的实现
list成员函数
构造函数
尾插
头插
头删
尾删
任意位置插入
任意位置删除
清空数据
析构函数
拷贝构造函数
赋值重载函数
const迭代器的设计
终极版正向迭代器的实现
终极版反向迭代器的实现
迭代器扩充小知识 list使用
list的诸多使用与前面博客讲解的string仍然类似我们此处只讲解比较特殊的接口函数
list的底层是带头双向循环链表在我的数据结构专栏博客 带头双向循环链表_CSDN博客 已经讲解过了重点是体会带头双向循环链表与顺序表的不同尤其是某个位置插入与删除数据的效率
reverse
void test_list1()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout e ; //1 2 3 4 }cout endl;lt.reverse(); //逆置链表for (auto e : lt){cout e ; //4 3 2 1 }cout endl;
}
sort
void test_list2()
{listint lt;lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(1);for (auto e : lt){cout e ; //2 3 4 1 }cout endl;//默认是升序 less//lt.sort(); //降序: greatergreaterint gt;lt.sort(gt);lt.sort(greaterint()); //匿名对象for (auto e : lt){cout e ; //4 3 2 1}cout endl;
}
注意: list的排序无法使用算法库中的sort主要原因是list不支持随机访问的迭代器 迭代器类型按性质或者底层实现分为三种: 1.单向:只支持, 单链表/哈希表 2.双向:与--都支持双向链表/红黑树(map和set) 3.随机:/--//- vector/string/deque 注意: 2是兼容1的3是兼容2的(本质是继承关系) unique
void test_list3()
{listint lt;lt.push_back(4);lt.push_back(1);lt.push_back(1);lt.push_back(2);lt.push_back(5);lt.push_back(5);lt.push_back(3);for (auto e : lt){cout e ; //4 1 1 2 5 5 3}cout endl;lt.sort();lt.unique(); //把相邻的重复去掉, 配合sort可以达到去重的功能for (auto e : lt){cout e ; //1 2 3 4 5}cout endl;
}
splice void test_list5()
{listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);listint lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);listint::iterator it lt1.begin();it;lt1.splice(it, lt2); //将lt2嫁接到lt1第2个位置之后, lt2就为空了!for (auto e : lt1){cout e ; //1 10 20 30 40 2 3 4}cout endl;for (auto e : lt2){cout e ; //空}cout endl;
}
void test_list5()
{listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);listint lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);lt1.splice(lt1.begin(), lt2, lt2.begin()); //将lt2的第一个节点接到lt1开始for (auto e : lt1){cout e ; //10 1 2 3 4 }cout endl;for (auto e : lt2){cout e ; //20 30 40}cout endl;
}void test_list5()
{listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);listint lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);lt1.splice(lt1.begin(), lt2, lt2.begin(), lt2.end()); //将lt2的全部接到lt1开始for (auto e : lt1){cout e ; //10 20 30 40 1 2 3 4}cout endl;for (auto e : lt2){cout e ; //空}cout endl;
}
list模拟实现
关于带头双向链表的结构与实现可以直接看我之前的博客: 带头双向循环链表-CSDN博客 类与成员函数声明
namespace dck
{//每个节点的类型template class Tstruct list_node{T _data; //数据域list_nodeT* _next; //前驱指针list_nodeT* _prev; //后继指针list_node(const T x T()); //构造函数};//非const迭代器template class Tstruct __list_iterator //前加_表示内部的实现{typedef list_nodeT Node;Node* _node;//构造函数__list_iterator(Node* node);//迭代器(前置)typedef __list_iteratorT self;self operator();//迭代器--(前置--)self operator--();//迭代器(后置)self operator(int);//迭代器--(后置--)self operator--(int);//迭代器解引用T operator*();T* operator-();//两个迭代器进行比较bool operator!(const self s);bool operator (const self s);};//list的类型template class Tclass list{typedef list_nodeT Node;public:void empty_init(); //空初始化list(); //构造函数void push_back(const T x); //尾插void push_front(const T x); //头插void pop_front(); //头删void pop_back(); //尾删iterator insert(iterator pos, const T x); //任意位置插入iterator erase(iterator pos); //任意位置删除iterator begin(); //起始位置迭代器iterator end(); //结束位置迭代器void clear(); //清空数据~list(); //析构函数list(const listT lt); //拷贝构造函数listT operator(const listT lt); //赋值重载函数传统写法void swap(listT lt); //交换两个list, 赋值重载函数现代写法要调用swap函数listT operator(listT lt); //赋值重载函数现代写法private:Node* _head;size_t size; //记录链表中节点的个数降低时间复杂度};
}节点类型的定义
//每个节点的类型
template class T
struct list_node
{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T x T()) :_data(x),_next(nullptr),_prev(nullptr){}
};
非const正向迭代器的实现 之前讲解的string与vector的迭代器都是原生指针而list的迭代器不是原生指针主要原因是因为list的底层是双向链表如果用原生指针是无法到下一个节点的直接解引用拿到的也不是具体的数据而是整个节点对象而迭代器的访问与遍历方式都是类似的都是 解引用判断, 所以我们只需要把list的迭代器设计成类在类中对原生指针做封装 //迭代器的实现 --- 封装屏蔽了底层差异和细节提供了统一的访问遍历修改方式!
template class T
struct __list_iterator //前加_表示内部的实现
{typedef list_nodeT Node;Node* _node;//构造函数__list_iterator(Node* node):_node(node){}//迭代器(前置)typedef __list_iteratorT self;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;}//迭代器解引用T operator*(){return _node-_data;}T* operator-(){return _node-_data;}//两个迭代器进行比较bool operator!(const self s){return _node ! s._node;}bool operator (const self s){return _node s._node;}
};
注意: 当list中存放的是自定义类型的对象时使用-解引用时写法如下:
class AA
{
public:AA(int aa1 1, int aa2 1):_a1(aa1),_a2(aa2){}int _a1;int _a2;
};void test_list()
{listAA lt1;lt1.push_back(AA(1, 2));lt1.push_back(AA(3, 4));lt1.push_back(AA(5, 6));listAA::iterator it lt1.begin();while (it ! lt1.end()){//显式应该这么写因为operator-()拿到的是原生指针还要再次-解引用拿到数据cout it.operator-()-_a1 it.operator-()-_a2 endl;//本来应该 it--_a1, 但是可读性不好因此编译器特殊处理, 省略了一个-cout it-_a1 it-_a2 endl;it;}cout endl;
}
list成员函数
构造函数
//空初始化, 后续代码可能会用到因此单独写出来
void empty_init()
{_head new Node;_head-_next _head;_head-_prev _head;_size 0;
}//构造函数
list()
{empty_init();
}
尾插
void push_back(const T x)
{//自己实现//Node* tail _head-_prev; //找到尾节点//Node* newnode new Node(x); //开辟新节点链接新节点//tail-_next newnode;//newnode-_prev tail;//newnode-_next _head;//_head-_prev newnode;//_size;//调用insert函数insert(end(), x);
}
头插
//头插
void push_front(const T x)
{insert(begin(), x);
}
头删
//头删
void pop_front()
{erase(begin());
}
尾删
//尾删
void pop_back()
{erase(--end());
}
任意位置插入
//insert
//在pos位置之前插入
//list的迭代器不存在失效的问题因为不涉及扩容
//参考库的实现还是给insert带上返回值
iterator insert(iterator pos, const T x)
{Node* cur pos._node; //当前节点指针Node* prev cur-_prev; //前一个节点指针Node* newnode new Node(x); //开辟新节点//链接prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;return iterator(newnode); //返回新插入节点位置的迭代器
} 任意位置删除
//erase之后迭代器pos失效因为当前节点已经被释放了!
//因此我们给erase带上返回值
iterator erase(iterator pos)
{Node* cur pos._node; //当前节点指针Node* prev cur-_prev; //前一个节点指针Node* next cur-_next; //后一个节点指针delete cur; //释放当前节点//链接前一个节点和后一个节点prev-_next next; next-_prev prev;--_size;return iterator(next); //返回释放节点的下一个位置
}
迭代器接口
iterator begin()
{//return iterator(_head-_next);return _head-_next; //单参数的构造函数支持隐式类型转化
}iterator end()
{//return iterator(_head);return _head; //单参数的构造函数支持隐式类型转化
}
清空数据
//清空数据(不清除带哨兵位的头节点)
void clear()
{iterator it begin();while (it ! end()){it erase(it);}
}
析构函数
//析构函数
~list()
{clear();delete _head;_head nullptr;
}
拷贝构造函数
//拷贝构造
list(listT lt)
{empty_init();for (auto e : lt){push_back(e);}
}
赋值重载函数
传统写法
//赋值重载传统写法
listT operator(const listT lt)
{if (this ! lt){clear(); for (auto e : lt){push_back(e);}}return *this;
}
现代写法
//赋值重载现代写法
void swap(listT lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}listT operator(listT lt)
{swap(lt);return *this;
}
const迭代器的设计
上述代码实现了非const迭代器本质就是封装了一个类提供了对应的接口而const迭代器本质就是迭代器指向的内容不可修改因此不可以直接写const iterator, 这个const修饰的是迭代器本身不能被修改那迭代器如何访问数据呢 因此非const迭代器应该是一个独立的类
//非const迭代器
template class T
struct __list_const_iterator //前加_表示内部的实现
{typedef list_nodeT Node;Node* _node;//构造函数__list_const_iterator(Node* node):_node(node){}//迭代器(前置)typedef __list_const_iteratorT self;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;}//迭代器解引用const T operator*() const{return _node-_data;}const T* operator-() const{return _node-_data;}//两个迭代器进行比较bool operator!(const self s){return _node ! s._node;}bool operator (const self s){return _node s._node;}
};list类中提供const迭代器的begin和end接口即可:
//list的类型
template class T
class list
{typedef list_nodeT Node;
public://提供迭代器typedef __list_iteratorT iterator;typedef __list_const_iteratorT const_iterator;const_iterator begin() const{//return iterator(_head-_next);return _head-_next; //单参数的构造函数支持隐式类型转化}const_iterator end() const{//return iterator(_head);return _head; //单参数的构造函数支持隐式类型转化}
};
但是上面的写法太冗余了非const迭代器和const迭代器都是封装了类类中的实现大同小异参考了STL库中的实现以后其实只需要一个类增加模板参数即可, 实现如下:
终极版正向迭代器的实现
//迭代器
template class T, class Ref, class Ptr
struct __list_iterator //前加_表示内部的实现
{typedef list_nodeT Node;Node* _node;typedef __list_iteratorT, Ref, Ptr self;//构造函数__list_iterator(Node* node):_node(node){}//迭代器(前置)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;}//迭代器解引用Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}//两个迭代器进行比较bool operator!(const self s){return _node ! s._node;}bool operator (const self s){return _node s._node;}
};
终极版反向迭代器的实现
反向迭代器完全可以再设计一个类在类内部把迭代器的操作都实现一遍但是没有必要因为我们已经有了正向迭代器因此只需要用正向迭代器适配出反向迭代器即可, 关于容器的适配器在我的下一篇博客中有提及, 大家可以参考一下stack 与 queue 与 priority_queue 与 仿函数 与 模板进阶-CSDN博客
反向迭代器的实现:
//用正向迭代器适配反向迭代器
template class Iterator, class Ref, class Ptr
class ReverseIterator
{
public:typedef ReverseIteratorIterator, Ref, Ptr Self;ReverseIterator(Iterator it):_it(it){}Self operator(){--_it;return *this;}Ref operator*(){return *_it;}Ptr operator-(){return _it.operator-();}bool operator!(const Self s){return _it ! s._it;}private:Iterator _it;
};list类: template class T
//list的类型
class list
{typedef list_nodeT Node;
public://提供迭代器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(end());}const_reverse_iterator rbegin() const{return const_reverse_iterator(--end());}const_reverse_iterator rend() const{return const_reverse_iterator(end());}iterator begin(){//return iterator(_head-_next);return _head-_next; //单参数的构造函数支持隐式类型转化}iterator end(){//return iterator(_head);return _head; //单参数的构造函数支持隐式类型转化}const_iterator begin() const{//return iterator(_head-_next);return _head-_next; //单参数的构造函数支持隐式类型转化}const_iterator end() const{//return iterator(_head);return _head; //单参数的构造函数支持隐式类型转化}
};
值得一说的是库中反向迭代器的实现和我们不一样不一样的地方在于库中反向迭代器的rbegin与rend位置和我们自己写的不一样下图rbegin和rend的位置是库中的实现是呈现对称结构的而库中迭代器解引用访问的是前一个数据也就是先让原生指针--, 然后解引用访问数据! 下面是我们模拟库中rbegin与rend的位置实现的反向迭代器:
反向迭代器的实现:
//用正向迭代器适配反向迭代器
template class Iterator, class Ref, class Ptr
class ReverseIterator
{
public:typedef ReverseIteratorIterator, Ref, Ptr Self;ReverseIterator(Iterator it):_it(it){}Self operator(){--_it;return *this;}Self operator--(){_it;return *this;}Ref operator*(){Iterator cur _it;return *(--cur);}Ptr operator-(){return (operator*());}bool operator!(const Self s){return _it ! s._it;}private:Iterator _it;
};
list类:
template class T
//list的类型
class list
{typedef list_nodeT Node;
public://提供迭代器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_reverse_iterator rbegin() const{return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}iterator begin(){//return iterator(_head-_next);return _head-_next; //单参数的构造函数支持隐式类型转化}iterator end(){//return iterator(_head);return _head; //单参数的构造函数支持隐式类型转化}const_iterator begin() const{//return iterator(_head-_next);return _head-_next; //单参数的构造函数支持隐式类型转化}const_iterator end() const{//return iterator(_head);return _head; //单参数的构造函数支持隐式类型转化}
};
迭代器扩充小知识
场景1想实现一个打印函数, 无论list的节点是什么类型都能打印
template class T
void Print(const listT lt)
{//listT为未实例化的类模板编译器不能直接去他里面去找//编译器无法识别listT::const_iterator是内嵌类型还是静态成员变量//前面加一个typename就是告诉编译器这里是一个类型等listT实例化再去类里面去取typename listT::const_iterator it lt.begin(); while (it ! lt.end()){cout *it ;it;}cout endl;
}void test_list5()
{listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);Print(lt1);//list不会存在浅拷贝的问题因为不涉及扩容liststring lt2;lt2.push_back(1111111111111111);lt2.push_back(1111111111111111);lt2.push_back(1111111111111111);lt2.push_back(1111111111111111);lt2.push_back(1111111111111111);Print(lt2);
}
场景2想实现一个打印函数, 无论是哪个STL都能使用同一个打印函数
//模板(泛型编程)本质: 本来应该由我们做的事情交给编译器去做了!
template typename Container
void print_container(const Container con)
{typename Container::const_iterator it con.begin();while (it ! con.end()){cout *it ;it;}cout endl;
}void test_list5()
{listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);print_container(lt1);//list不会存在浅拷贝的问题因为不涉及扩容liststring lt2;lt2.push_back(1111111111111111);lt2.push_back(1111111111111111);lt2.push_back(1111111111111111);lt2.push_back(1111111111111111);lt2.push_back(1111111111111111);print_container(lt2);vectorstring v;v.push_back(2222222222222222);v.push_back(2222222222222222);v.push_back(2222222222222222);v.push_back(2222222222222222);v.push_back(2222222222222222);print_container(v);
}
