admin管理员组

文章数量:1794759

STL

List

• list的迭代器
• list链表
• list的功能函数
• list测试
• • 函数主体

要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现
在我们来模拟实现list。

list的迭代器

List 的迭代器
迭代器有两种实现方式，具体应根据容器底层数据结构实现：

1. 原生态指针，比如：vector
2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下
   方法：
3. 指针可以解引用，迭代器的类中必须重载operator*()
4. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
5. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
   至于operator–()/operator–(int)释放需要重载，根据具体的结构来抉择，双向链表可
   以向前 移动，所以需要重载，如果是forward_list就不需要重载–
6. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()
   */
   迭代器实现原理简要框架
   

说明：因为list的迭代器会指向下一个节点，所以我们创建一个迭代器结构体，这个结构体成员函数就是一个一个节点的指针_node。该构造函数会通过一个传递过来的节点来构造对象
迭代器代码

   // <T, T&, T*> iterator// <T, const T&, const T*> const_iterator// 类设计的复用
template<class T, class Ref, class Ptr>struct _list_iterator {typedef _list_node<T> node;typedef _list_iterator<T, Ref, Ptr> self;//自己node* _node;//节点的指针_list_iterator(node* node):_node(node){}//用传过来的节点的指针构造一个对象//浅拷贝  不需要拷贝构造和析构//两个迭代器进行比较的时候比较的是节点的指针，两个指针指向的是同一个位置说明迭代器相等bool operator!=(const self& s) const {return _node != s._node;}bool operator==(const self& s) const{return !(*this != s);}//实现运算符的重载，比如++，节点的指针++之后就指向连续空间的下一个了，就找不到下一个节点的指针了//因此需要运算符的重载//如节点的指针++就让他指向下一个节点，并且返回这个迭代器Ref operator*() {//返回的是节点里数据的引用：为了保证可读可写，返回引用的话我也可以改变这个节点的值return _node->_date;//返回的是节点的数据}//前置++it.operator(&it)构成函数重载self& operator++() {_node = _node->_next;return *this;}//后置++it.operator(&it,0)构成函数重载self& operator++(int) {self tmp(*this);_node = _node->_next;return tmp;}//前置--it.operator(&it)构成函数重载//++it; -->it.operator++()self& operator--() {//前置++返回++之后的_node = _node->_prev;//指向下一个位置return *this;//返回下一个迭代器}//后置--it.operator(&it,0)构成函数重载self& operator--(int) {//后置++返回++之前的,出了作用域不在了，所以不能返回引用self tmp(*this);//保存之前的迭代器_node = _node->_prev;return tmp;}//返回data的指针，data的指针里才会有数据Ptr operator->() const{return &_node->_date;}};

析构不需要写，因为节点的生命周期是跟着链表走的，链表销毁了节点才会销毁
迭代器不是管理一个节点，它是封装这个节点之后让我们用同样的方式去遍历这个链表，而不暴露里面的东西
我们可以理解为迭代器就像是一个隔离层，屏蔽了里面实现的东西，但是外面的使用都是一样的

list链表

（1）空容器构造函数（默认构造函数）
构造一个空容器，不包含任何元素。
（2）填充构造函数
构造一个包含n个元素的容器。每个元素都是val的副本。
（3）范围构造器
构造一个包含范围为[first，last）的元素的容器，每个元素由该范围内其对应元素以相同的顺序构造。
（4）复制构造函数
用相同的顺序构造一个容器，其中包含x中每个元素的副本。

template<class T>class list {typedef _list_node<T> node;//节点public://迭代器   typedef _list_iterator<T, T&, T*> iterator;//const迭代器typedef _list_iterator<T,  const T&,const T*> const_iterator;constlist() {_head = new node();_head->_next = _head;_head->_prev = _head;}//析构函数~list() {clear();//清除所有数据delete _head;//释放头节点}//将迭代器输入到范围中的初始位置和最终位置。使用的范围是//[first，last），它包括first和last之间的所有元素，包//括first指向的元素，但last指向的元素。
//函数模板参数InputIterator应该是一个输入迭代器类型，该类//型指向可以从其构造value_type对象的类型的元素template<class InputIterator>list(InputIterator first, InputIterator last){_head = new node;_head->_next = _head;_head->_prev = _head;while (first != last)//把first到last区间的数据拷贝到this链表{push_back(*first);++first;}}list(const list<T>& lt){_head = new node;_head->_next = _head;_head->_prev = _head;//调用list范围构造器填充tmplist<T> tmp(lt.begin(), lt.end());//把this和tmp除头节点外交换，出了作用域tmp释放std::swap(_head, tmp._head);}//lt1 = lt2list<T>& operator=(list<T> lt){//假设l1 = l2//l1就是l2拷贝构造出来的，因此交换this和l两个链表的头节点即可//交换过后l1原来的值会在l里，l出了作用域会自动释放（临时对象）std::swap(_head, lt._head);return *this;}//拷贝构造一般写法/*list(const list<T>& it) {)//拷贝构造（拷贝构造要支持深拷贝，否则析构的时候会有问题）//申请头节点_head = new node();_head->_prev = _head;_head->_next = _head;//将it的每个数据尾插到this链表中const_iterator i = it.begin();while (i != it.end()) {push_back(*i);i++;}}*///将链表中所有数据清除void clear () {iterator it = begin();while (it != end()) {erase(it++);//不用++这里删除自动往后移动}}//const迭代器const_iterator begin() const {return _head->_next;}const_iterator end() const {return _head->prev;}//一般迭代器//begin是第一个位置的迭代器，有节点的指针就能构造迭代器，只有链表才有节点的指针//begin和end都是链表实现的，迭代器是我传过去一个节点，他构造一个迭代器结构体的对象iterator begin() {//迭代器不是节点的指针，它是一个该结构体的自定义类型//可以用节点的指针构造一个对象return iterator(_head->_next);//调用构造}iterator end() {return _head;}private://带头双向循环链表node* _head;};

list的功能函数

		 //在pos前边插入iterator insert(iterator pos,const T&x) {node* newnode = new node(x);node* cur = pos._node;node* prev = cur->_prev;cur->_prev = newnode;newnode->_next = cur;newnode->_prev = prev;prev->_next = newnode;return newnode;}iterator erase(iterator pos1) {assert(pos1 != end());node* pos = pos1._node;node* cur = pos->_next;node* prev = pos->_prev;cur->_prev = prev;prev->_next = cur;delete pos;return cur;}//头插void push_front(const T& x){insert(begin(), x);}//尾删void pop_back(){erase(--end());//--end尾节点}//头删void pop_front(){erase(begin());}void push_back(const T& x){node* newnode = new node(x);node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}

list测试

函数主体

acc.h

#pragma once
#include<iostream>
#include<algorithm>
#include<assert.h>
using namespace std;
namespace td {template<class T>struct _list_node {T _date;_list_node<T>* _next;_list_node<T>* _prev;_list_node(const T& x = T()):_date(x), _next(nullptr), _prev(nullptr){}};//迭代器template<class T, class Ref, class Ptr>struct _list_iterator {typedef _list_node<T> node;typedef _list_iterator<T, Ref, Ptr> self;//自己node* _node;_list_iterator(node* node):_node(node){}//浅拷贝  不需要拷贝构造和析构Ref operator*()const {return _node->_date;}//前置++it.operator(&it)构成函数重载self& operator++() {_node = _node->_next;return *this;}//后置++it.operator(&it,0)构成函数重载self& operator++(int) {self tmp(*this);_node = _node->_next;return tmp;}//前置--it.operator(&it)构成函数重载self& operator--() {_node = _node->_prev;return *this;}//后置--it.operator(&it,0)构成函数重载self& operator--(int) {self tmp(*this);_node = _node->_prev;return tmp;}Ptr operator->() const{return &_node->_date;}bool operator!=(const self& s) const {return _node != s._node;}bool operator==(const self& s) const{return !(*this != s);}};template<class T>class list {typedef _list_node<T> node;public:typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T,  const T&,const T*> const_iterator;list() {_head = new node();_head->_next = _head;_head->_prev = _head;}~list() {clear();delete _head;}void push_back(const T& x){node* newnode = new node(x);node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}template<class InputIterator>list(InputIterator first, InputIterator last){_head = new node;_head->_next = _head;_head->_prev = _head;while (first != last){push_back(*first);++first;}}list(const list<T>& lt){_head = new node;_head->_next = _head;_head->_prev = _head;list<T> tmp(lt.begin(), lt.end());std::swap(_head, tmp._head);}//lt1 = lt2list<T>& operator=(list<T> lt){std::swap(_head, lt._head);return *this;}/*list(const list<T>& it) {_head = new node();_head->_prev = _head;_head->_next = _head;const_iterator i = it.begin();while (i != it.end()) {push_back(*i);i++;}}*/void clear () {iterator it = begin();while (it != end()) {erase(it++);//不用++这里删除自动往后移动}}const_iterator begin() const {return _head->_next;}const_iterator end() const {return _head->prev;}iterator begin() {return _head->_next;}iterator end() {return _head;}//在pos前边插入iterator insert(iterator pos,const T&x) {node* newnode = new node(x);node* cur = pos._node;node* prev = cur->_prev;cur->_prev = newnode;newnode->_next = cur;newnode->_prev = prev;prev->_next = newnode;return newnode;}iterator erase(iterator pos1) {assert(pos1 != end());node* pos = pos1._node;node* cur = pos->_next;node* prev = pos->_prev;cur->_prev = prev;prev->_next = cur;delete pos;return cur;}//头插void push_front(const T& x){insert(begin(), x);}//尾删void pop_back(){erase(--end());//--end尾节点}//头删void pop_front(){erase(begin());}private:node* _head;};
}

源.cpp

#include"acc.h"
namespace td
{void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(0);// 遍历方式1list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";++rit;}cout << endl;// 遍历方式2for (auto e : lt){cout << e << " ";}cout << endl;}void test_list2(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator pos = std::find(lt.begin(), lt.end(), 2);if (pos != lt.end()){lt.insert(pos, 20);}list<int>::iterator it = lt.begin();while (it != lt.end()){if (*it % 2 == 0){it = lt.erase(it);}else{++it;}}// 遍历方式2for (auto e : lt){cout << e << " ";}cout << endl;}
}namespace bit
{void print_list(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){// const T& it.operator*()//*it = 1;cout << *it << endl;++it;}cout << endl;}void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();list<int>::const_iterator it = lt.begin();while (it == lt.end()){*it = 1;cout << *it << endl;++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}struct Point{int x;int y;};void test_list2(){list<Point> lt;lt.push_back({ 1, 2 });lt.push_back({ 3, 3 });lt.push_back({ 5, 6 });list<Point>::iterator it = lt.begin();list<Point>::const_iterator it = lt.begin();while (it != lt.end()){cout << it->x << ":" << it->y << endl;//cout << (*it).x << ":" << (*it).y << endl;++it;}cout << endl;}void test_list3(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int> copy = lt;for (auto e : copy){cout << e << " ";}cout << endl;}
}int main()
{bit::test_list3();return 0;
}

本文标签： STL