16.C++入门：list|手撕list|反向迭代器|与vector对比

list的模拟实现

list.h

#pragma once #include<assert.h> namespace bit { template<class T> struct ListNode { ListNode<T>* _next; ListNode<T>* _prev; T _data; ListNode(const T& x = T()) :_next(nullptr) ,_prev(nullptr) ,_data(x) {} }; template<class T, class Ref, class Ptr> struct __list_iterator { typedef ListNode<T> Node; typedef __list_iterator<T, Ref, Ptr> self; Node* _node; __list_iterator(Node* x) :_node(x) {} // ++it self& operator++() { _node = _node->_next; return *this; } // it++ self operator++(int) { //__list_iterator<T> tmp(*this); self tmp(*this); _node = _node->_next; return tmp; } self& operator--() { _node = _node->_prev; return *this; } 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; } }; //template<class T> //struct __list_const_iterator //{ // typedef ListNode<T> Node; // typedef __list_const_iterator<T> self; // Node* _node; // __list_const_iterator(Node* x) // :_node(x) // {} // // ++it // self& operator++() // { // _node = _node->_next; // return *this; // } // // it++ // self operator++(int) // { // self tmp(*this); // _node = _node->_next; // return tmp; // } // self& operator--() // { // _node = _node->_prev; // return *this; // } // self operator--(int) // { // self tmp(*this); // _node = _node->_prev; // return tmp; // } // const T& operator*() // { // return _node->_data; // } // bool operator!=(const self& s) // { // return _node != s._node; // } // bool operator==(const self& s) // { // return _node == s._node; // } //}; template<class T> class list { typedef ListNode<T> Node; public: typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; //typedef __list_const_iterator<T> const_iterator; iterator begin() { //return iterator(_head->_next); return _head->_next; } iterator end() { return _head; } const_iterator begin() const { return _head->_next; } const_iterator end() const { return _head; } void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; } list() { empty_init(); } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } ~list() { clear(); delete _head; _head = nullptr; } //list(const list<T>& lt) list(list<T>& lt) { empty_init(); for (const auto& e : lt) { push_back(e); } } // lt1 = lt2; // list<T>& operator=(const list<T>& lt) /*list<T>& operator=(list<T>& lt) { if (this != &lt) { clear(); for (const auto& e : lt) { push_back(e); } } return *this; }*/ void swap(list<T>& tmp) { std::swap(_head, tmp._head); } //list& operator=(list lt) list<T>& operator=(list<T> lt) { swap(lt); 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 push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } // vector insert会导致迭代器失效 // list会不会？不会 iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); // prev newnode cur prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; //return iterator(newnode); return newnode; } iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return next; } private: Node* _head; }; 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(); while (it != lt.end()) { //*it += 10; cout << *it << " "; ++it; } cout << endl; for (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); for (auto e : lt) { cout << e << " "; } cout << endl; lt.push_back(5); lt.push_front(0); for (auto e : lt) { cout << e << " "; } cout << endl; lt.pop_back(); lt.pop_front(); for (auto e : lt) { cout << e << " "; } cout << endl; lt.clear(); for (auto e : lt) { cout << e << " "; } cout << endl; lt.push_back(10); lt.push_back(20); for (auto e : lt) { cout << e << " "; } cout << endl; } void test_list3() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); for (auto e : lt) { cout << e << " "; } cout << endl; list<int> copy(lt); for (auto e : copy) { cout << e << " "; } cout << endl; list<int> lt1; lt1.push_back(10); lt1.push_back(20); lt1.push_back(30); lt1.push_back(40); lt = lt1; for (auto e : copy) { cout << e << " "; } cout << endl; } void print_list(const list<int>& lt) { list<int>::const_iterator it = lt.begin(); while (it != lt.end()) { //*it += 10; cout << *it << " "; ++it; } cout << endl; for (auto e : lt) { cout << e << " "; } cout << endl; } void test_list4() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); print_list(lt); list<int>::iterator it = lt.begin(); while (it != lt.end()) { *it += 10; cout << *it << " "; ++it; } cout << endl; } struct AA { int _a1; int _a2; AA(int a1 = 1, int a2 = 1) :_a1(a1) , _a2(a2) {} }; void test_list5() { list<AA> lt; AA aa1; lt.push_back(aa1); lt.push_back(AA()); AA aa2(2, 2); lt.push_back(aa2); lt.push_back(AA(2, 2)); list<AA>::iterator it = lt.begin(); while (it != lt.end()) { cout << (*it)._a1 << ":" << (*it)._a2 << endl; cout << it.operator*()._a1 << ":" << it.operator*()._a2 << endl; cout << it->_a1 << ":" << it->_a2 << endl; cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl; ++it; } cout << endl; } }

test.cpp

#include<iostream> #include<list> #include<vector> #include<algorithm> using namespace std; #include"List.h" //int main() //{ // list<int> lt; // lt.push_back(1); // lt.push_back(2); // lt.push_back(3); // lt.push_back(4); // lt.push_back(5); // // list<int>::iterator it = lt.begin(); // while (it != lt.end()) // { // *it += 10; // // cout << *it << " "; // ++it; // } // cout << endl; // // for (auto e : lt) // { // cout << e << " "; // } // cout << endl; // // lt.reverse(); // for (auto e : lt) // { // cout << e << " "; // } // cout << endl; // // return 0; //} void test_op1() { srand(time(0)); const int N = 1000000; list<int> lt1; list<int> lt2; vector<int> v; for (int i = 0; i < N; ++i) { auto e = rand(); 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; list<int> lt1; list<int> lt2; for (int i = 0; i < N; ++i) { auto e = rand(); lt1.push_back(e); lt2.push_back(e); } int begin1 = clock(); // vector vector<int> v(lt2.begin(), lt2.end()); // sort(v.begin(), v.end()); // lt2 lt2.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() //{ // list<int> lt; // lt.push_back(1); // lt.push_back(4); // lt.push_back(2); // lt.push_back(2); // lt.push_back(2); // lt.push_back(2); // lt.push_back(4); // lt.push_back(3); // // lt.push_back(5); // // for (auto e : lt) // { // cout << e << " "; // } // cout << endl; // // lt.sort(); // lt.unique(); // for (auto e : lt) // { // cout << e << " "; // } // cout << endl; // // //sort(lt.begin(), lt.end()); // test_op2(); // // return 0; //} //int main() //{ // // LRU // list<int> lt; // lt.push_back(1); // lt.push_back(2); // lt.push_back(3); // lt.push_back(4); // lt.push_back(5); // // for (auto e : lt) // { // cout << e << " "; // } // cout << endl; // // // 2תλȥ // lt.splice(lt.end(), lt, find(lt.begin(), lt.end(), 2)); // // for (auto e : lt) // { // cout << e << " "; // } // cout << endl; // // return 0; //} //struct AA //{ // int _a1; // int _a2; // // AA(int a1 = 1, int a2 = 1) // :_a1(a1) // ,_a2(a2) // {} //}; //int main() //{ // list<AA> lt; // AA aa1; // lt.push_back(aa1); // // lt.push_back(AA()); // // AA aa2(2,2); // lt.push_back(aa2); // // lt.push_back(AA(2, 2)); // // list<AA>::iterator it = lt.begin(); // while (it != lt.end()) // { // cout << (*it)._a1 << ":" << (*it)._a2 << endl; // cout << it->_a1 << ":" << it->_a2 << endl; // // ++it; // } // cout << endl; //} int main() { bit::test_list5(); return 0; }

list的反向迭代器

通过前面例子知道，反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。

template<class Iterator> class ReverseListIterator { // 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态成员变量 // 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量 // 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的 public: typedef typename Iterator::Ref Ref; typedef typename Iterator::Ptr Ptr; typedef ReverseListIterator<Iterator> Self; public: ////////////////////////////////////////////// // 构造 ReverseListIterator(Iterator it): _it(it){} ////////////////////////////////////////////// // 具有指针类似行为 Ref operator*(){ Iterator temp(_it); --temp; return *temp; } Ptr operator->(){ return &(operator*());} ////////////////////////////////////////////// // 迭代器支持移动 Self& operator++(){ --_it; return *this; } Self operator++(int){ Self temp(*this); --_it; return temp; } Self& operator--(){ ++_it; return *this; } Self operator--(int) { Self temp(*this); ++_it; return temp; } ////////////////////////////////////////////// // 迭代器支持比较 bool operator!=(const Self& l)const{ return _it != l._it;} bool operator==(const Self& l)const{ return _it != l._it;} Iterator _it; };

list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：