文章目录

• list的介绍
• list的模拟实现
• • 成员变量
  • Member functions
  • • constructor
    • destructor
    • operator=
  • Iterators
  • • 正向迭代器
    • 反向迭代器
    • begin
    • end
    • rbegin
    • rend
  • Modifiers
  • • push_front
    • pop_front
    • push_back
    • pop_back
    • insert
    • erase
    • clear
• 完整版代码
• • list.h
  • reverse_iterator.h
  • test.cpp

list的介绍

list是STL库里面的一个重要容器，它分为一下几个部分
Member functions

Iterators

Capacity

Element access

Modifiers

Operations

Observers

Non-member function overloads

list的模拟实现

我们重点实现list的下面几个部分，其余部分有的还没学到，有的比较简单也不是特别常用大家可以自己去完善。
我们实现的链表结构为带头双向循环链表

_head为哨兵位头节点，是不存储数据的

成员变量

_head为哨兵位头节点
节点指针

节点
_prev记录前一个节点的位置
_next记录下一个节点的位置

Member functions

constructor

_head为哨兵位头节点

_head为哨兵位头节点

_head为哨兵位头节点

_head为哨兵位头节点

_head为哨兵位头节点

destructor

_head为哨兵位头节点

operator=

_head为哨兵位头节点

Iterators

链表的正向迭代器和反向迭代器和之前学的string、vector不同，因为它们的物理空间连续可以++、–随机访问它们的各个位置所以它们的迭代器为原生指针，而list的物理空间不连续，不能++、–的随机访问任意位置，所以我们要对list的迭代器进行封装。

正向迭代器

反向迭代器

begin

_head为哨兵位头节点

_head为哨兵位头节点
const迭代器和普通迭代器的区别在于只可读，不可写

end

_head为哨兵位头节点

_head为哨兵位头节点
const迭代器和普通迭代器的区别在于只可读，不可写

rbegin

const迭代器和普通迭代器的区别在于只可读，不可写

rend

const迭代器和普通迭代器的区别在于只可读，不可写

Modifiers

push_front

复用insert，因为begin（）是第一个数据的位置，头插就是要在第一个数据位置的前面插入数据。

pop_front

复用erase，因为begin（）是第一个数据的位置，头删是要删除第一个数据的位置。

push_back

复用insert，因为end（）是头节点的位置，尾插就是要在头节点前插入数据。（注释部分为不复用的实现方法）

pop_back

复用erase，因为end（）是头节点的位置，尾删是要删除头节点的前一个位置，所以要–

insert

erase

clear

完整版代码

list.h

#pragma once
#include"reverse_iterator.h"
namespace lzf
{templatestruct ListNode{public:T _data;ListNode* _prev;ListNode* _next;ListNode(const T& val = T()):_data(val), _prev(nullptr),_next(nullptr){}};templatestruct list_iterator{typedef list_iterator self;typedef ListNode Node;Node* _node;list_iterator(Node* x):_node(x){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self temp(_node);_node = _node->_next;return temp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self temp(_node);_node = _node->_prev;return temp;}/*bool operator!=(self& it){return _node != it._node;}bool operator==(self& it){return _node == it._node;}*//*bool operator!=(self it){return _node != it._node;}bool operator==(self it){return _node == it._node;}*/bool operator!=(const self& it)const{return _node != it._node;}bool operator==(const self& it)const{return _node == it._node;}};templateclass list{typedef ListNode Node;public:typedef list_iterator iterator;typedef list_iterator const_iterator;typedef reverse_iterator const_reverse_iterator;typedef reverse_iterator 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);}iterator end(){return iterator(_head);}const_iterator begin()const{return const_iterator(_head->_next);}const_iterator end()const{return const_iterator(_head);}list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(int n,const T& val = T()){_head = new Node;_head->_next = _head;_head->_prev = _head;for (int i = 0; i < n; i++){push_back(val);}}list(size_t n, const T& val = T()){_head = new Node;_head->_next = _head;_head->_prev = _head;for (size_t i = 0; i < n; i++){push_back(val);}}templatelist(Inputiterator first, Inputiterator last){_head = new Node;_head->_next = _head;_head->_prev = _head;while (first != last){push_back(*first);++first;}}list(const list& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;/*const_iterator it = lt.begin();while (it != lt.end()){push_back(*it);++it;}*/list temp(lt.begin(), lt.end());std::swap(_head, temp._head);}list& operator=(list lt){/*_head = new Node;_head->_next = _head;_head->_prev = _head;*/std::swap(_head, lt._head);return *this;}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;*/insert(end(), x);}void pop_back(){erase(--end());}void push_front(const T& x){insert(begin(),x);}void pop_front(){erase(begin());}iterator insert(iterator pos, const T& x){Node* newnode = new Node(x);Node* prev = pos._node->_prev;//Node* next = pos._node->_next;prev->_next = newnode;newnode->_prev = prev;pos._node->_prev = newnode;newnode->_next = pos._node;return iterator(newnode);}iterator erase(iterator pos){assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;delete pos._node;prev->_next = next;next->_prev = prev;return iterator(next);}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}private:Node* _head;};void test_list1(){list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}//list }void test_list2(){list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);//list lt2(5,1);//list lt2(lt.begin(), lt.end());//list lt2(lt);list lt2;lt2.push_back(7);lt2.push_back(8);lt2.push_back(9);lt2.push_back(10);//lt.operator=(lt2);//list::iterator it = lt.begin();/*while (it != lt.end()){cout << *it << " ";it++;}*///list }void test_list3(){list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.insert(lt.begin(), 1);lt.insert(lt.begin(), 2);lt.insert(lt.begin(), 3);lt.insert(lt.begin(), 4);lt.insert(lt.end(), 4);lt.insert(lt.end(), 3);lt.insert(lt.end(), 2);lt.insert(lt.end(), 1);list::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;lt.erase(lt.begin());lt.erase(lt.begin());lt.erase(lt.begin());lt.erase(lt.begin());lt.erase(--lt.end());lt.erase(--lt.end());lt.erase(--lt.end());lt.erase(--lt.end());it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}}void test_list4(){list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.clear();list::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}}void test_list5(){list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list::reverse_iterator it = lt.rbegin();while (it != lt.rend()){cout << *it << " ";//++it;it++;}}void test_list6(){list lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list lt1;list lt2;lt2 = lt1 = lt;list::reverse_iterator it = lt2.rbegin();while (it != lt2.rend()){cout << *it << " ";//++it;it++;}}
}

reverse_iterator.h

#pragma once
namespace lzf
{templateclass reverse_iterator{public:typedef reverse_iterator self;reverse_iterator(iterator it):_it(it){}Ref operator*(){iterator temp(_it);return *--temp;}Ptr operator->(){iterator temp(_it);return &(*--temp);}self& operator++(){--_it;return *this;}self& operator--(){++_it;return *this;}self operator++(int){self temp(_it);--_it;return temp;}self operator--(int){self temp(_it);++_it;return temp;}bool operator!=(const self& it)const{return _it != it._it;}bool operator==(const self& it)const{return _it == it._it;}private:iterator _it;};
}

test.cpp

#include
#include
using namespace std;
#include"list.h"
int f()
{int a = 10;//double& b = a;return a;
}
int main()
{//int& b = f();lzf::test_list6();return 0;
}