list的接口
#pragma once #include<iostream> #include<assert.h> using namespace std; namespace zjw { template<class T> struct listnode { listnode* <T>_next; listnode* <T>_prev; T _data; listnode(const T& x = T()) :_prev(nulllptr) ,_next(nullptr) ,_data(x) { } }; template<class T> struct _list_iterator { typedef listnode <T>node; typedef _list_iterator<T>self; node* _node; _list_iterator(node* n) :_node(n) { } self& operator++() { } self& operator--() { } self operator++(int) { } self operator--(int) { } bool operator!=(const self& s) { } bool operator==(const self& s) { } T& operator() { } }; template <class T> class list { typedef listnode <T>node; public: typedef _list_iterator<T> iterator; list() { empty_init(); } void empty_init() { } iterator begin() { } iterator end() { } void clear() { } ~list { } list(const list<T>& it) { } void push_back(const T&x) { } void push_front(const T& x) { } void pop_back() { } void pop_front() { } void swap(list<T>& tmp) { } list<T>& operator=(list<T>it) { } iterator insert(iterator pos ,const T&x) { } iterator erase(iterator pos) { } private : node* _head; }; }
迭代器前置++，前置–，后置++，后置–
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 s._node != _node; } bool operator==(const self& s) { return s._node == _node; } T& operator*() { return _node->_data; }
链表的默认构造，以及尾插，获取链表的头和尾巴，以及测试尾插函数
list() { empty_init(); } void empty_init() { _head = new node(); _head->_prev = _head; _head->_next = _head; } iterator begin() { return _head->_next; } iterator end() { return _head; } void push_back(const T&x) { node* newnode = new node(x); node* tail = _head->_prev; newnode->_next = _head; newnode->_prev = tail; tail->_next = newnode; _head->_prev = newnode; }
尾插测试，以及迭代器测试
void test1() { list<int>res; res.push_back(1); res.push_back(2); res.push_back(3); res.push_back(4); list<int> ::iterator it = res.begin(); while (it != res.end()) { cout <<*it << " "; it++; } }
const迭代器的实现
我们就可以新增两个带const的begin(),end(),权限平移就可以调动。
iterator begin() const { return _head->_next; } iterator end() const { return _head; }
如果我们要修改迭代器所指向位置的值呢？？
我们应该如何模拟实现一个常量迭代器呢？？
如果按照以下的方式，可以实现吗？？
所以我们应该怎么实现呢？？
迭代器中的解引用函数，我们需要让他的返回值不被修改，所以 这个函数的返回值加const 就好了，所以我们在实现一个类，这个类基本和普通迭代器的类一样，只是在解引用函数上有区分。
template<class T> struct const_list_iterator { typedef listnode <T> node; typedef const_list_iterator<T> self; node* _node; const_list_iterator(node* n) :_node(n) { } 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 s._node != _node; } bool operator==(const self& s) { return s._node == _node; } const T operator*() { return _node->_data; } };
这样子，就实现了const 的迭代器，但是重新搞一个类好麻烦呀，于是有大佬就想出了在提供一个模板参数来解决这个问题
->运算符重载函数
我们可以想一下什么时候会用到->,当指针it指向的是结构体的话，我们可以访问使用
it->data,来访问数据，也可先对指针解引用*it,*it表示拿到这个结构体，然后使用.来访问（*it）.data;
T* operator->() { return &_node->_data; }
struct AA { int a1; int a2; AA(int _a1=0,int _a2=0) :a1(_a1) ,a2(_a2) { } };
测试->
void test3() { list<AA>res; res.push_back(AA(1,1)); res.push_back(AA(2, 2)); res.push_back(AA(3, 3)); res.push_back(AA(4, 4)); list<AA> ::iterator it = res.begin(); while (it != res.end()) { cout << it.operator->()->a1<<":" << it.operator->()->a2 << endl; it++; } }
这里有一个问题就是->访问也是取数据，但取到的数据能修改吗？这就面临和解引用取数据同样的问题。
我们现在需要做的是const迭代器的不能被将修改，普通的可以修改值
我发现这里和解引用那里不一样的是，解引用那里是值不可被修改，这里是地址不可被修改
=运算符重载赋值
void swap(list<T>& tmp) { std::swap(_head, tmp._head); } list<T>& operator=(list<T>it) { swap(it); return *this; }
赋值函数测试
void test4() { list<int>res; res.push_back(1); res.push_back(2); res.push_back(3); res.push_back(4); list<int> ret = res; list<int> ::iterator it = ret.begin(); while (it != ret.end()) { cout << *it << " "; it++; } }
