铜川市网站建设_网站建设公司_React_seo优化

list.h

#pragma once #include<assert.h> #include"ReverseIterator.h" namespace bit { //... void func() { // 内置类型 //it::ListNode<int>* it1 = _head->_next; Node* it1 = _head->_next; // 自定义类型 //bit::__list_iterator<int, int&, int*> it2 = _head->next; iterator it2 = _head->_next; *it1; ++it1; *it2; ++it2; cout << sizeof(it1) << endl; cout << sizeof(it2) << endl; } private: Node* _head; }; }

test.cpp

#include<iostream> #include<list> #include<vector> #include<algorithm> #include<unordered_map> #include<map> using namespace std; #include"List.h" #include"vector.h" int main() { bit::list<int> lt; lt.push_back(1); lt.push_back(2); lt.func(); return 0; }

内置类型，解引用会拿地址找到地址指向的空间，开一个Node，按Node类型解引用，++下一个Node的大小
自定义类型，去调用对应的o运算符，解引用就是返回节点的value，++就是找到下一个节点

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; };

ReverseIterator.h

#pragma once // 适配器 // 提供list的iterator，适配出list的reverse_iterator // 提供vector的iterator，适配出vector的reverse_iterator template<class Iterator, class Ref, class Ptr> struct ReverseIterator { typedef ReverseIterator<Iterator, Ref, Ptr> Self; Iterator cur; ReverseIterator(Iterator it) :cur(it) {} Self& operator++() { --cur; return *this; } Self& operator++(int) { Self tmp(*this); --cur; return tmp; } Self& operator--() { ++cur; return *this; } Self& operator--(int) { Self tmp(*this); ++cur; return tmp; } Ref operator*() { Iterator tmp = cur; --tmp; return *tmp; } Ptr operator->() { return &(operator*()); } bool operator!=(const Self& s) { return cur != s.cur; } bool operator==(const Self& s) { return cur == s.cur; } }

list.h

#pragma once #include<assert.h> #include"ReverseIterator.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> 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 ReverseIterator<iterator, T&, T*> reverse_iterator; typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator; //typedef __list_const_iterator<T> const_iterator; reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } 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); } } void swap(list<T>& tmp) { std::swap(_head, tmp._head); } list<T>& operator=(list<T> lt) { swap(lt); return *this; } void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } 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; } void func() { // 内置类型 //it::ListNode<int>* it1 = _head->_next; Node* it1 = _head->_next; // 自定义类型 //bit::__list_iterator<int, int&, int*> it2 = _head->next; iterator it2 = _head->_next; *it1; ++it1; *it2; ++it2; cout << sizeof(it1) << endl; cout << sizeof(it2) << endl; } private: Node* _head; }; }

vector.h

#pragma once #include<assert.h> #include"ReverseIterator.h" namespace bit { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; typedef ReverseIterator<iterator, T&, T*> reverse_iterator; typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator; vector() {} /*vector(const vector<T>& v) { _start = new T[v.capacity()]; memcpy(_start, v._start, v.size()* sizeof(T)); _finish = _start + v.size(); _endofstorage = _start + v.capacity(); }*/ // v2(v1) vector(const vector<T>& v) { reserve(v.capacity()); for (const auto& e : v) { push_back(e); } } template <class InputIterator> vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); ++first; } } vector(size_t n, const T& val = T()) { resize(n, val); } vector(int n, const T& val = T()) { resize(n, val); } // 21:06 void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } // v1 = v3 vector<T>& operator=(vector<T> v) { swap(v); return *this; } ~vector() { if (_start) { delete[] _start; _start = _finish = _endofstorage = nullptr; } } iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } // 20: 10继续 void reserve(size_t n) { if (n > capacity()) { size_t old = size(); T* tmp = new T[n]; if (_start) { //memcpy(tmp, _start, old * sizeof(T)); for (size_t i = 0; i < old; i++) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + old; _endofstorage = _start + n; } } void resize(size_t n, T val = T()) { if (n > size()) { reserve(n); while (_finish < _start + n) { *_finish = val; ++_finish; } } else { _finish = _start + n; } } void push_back(const T& x) { if (_finish == _endofstorage) { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } *_finish = x; ++_finish; } void pop_back() { assert(size() > 0); --_finish; } iterator insert(iterator pos, const T& x) { assert(pos >= _start && pos <= _finish); if (_finish == _endofstorage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + len; } //memmove(pos + 1, pos, sizeof(T) * (_finish - pos)); iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; --end; } *pos = x; ++_finish; return pos; } iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator it = pos + 1; while (it < _finish) { *(it - 1) = *it; ++it; } _finish--; return pos; } size_t size() const { return _finish - _start; } size_t capacity() const { return _endofstorage - _start; } T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; } private: iterator _start = nullptr; iterator _finish = nullptr; iterator _endofstorage = nullptr; }; void print_vector(const vector<int>& v) { for (auto e : v) { cout << e << " "; } cout << endl; } void test_vector1() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(4); v.push_back(4); v.push_back(4); vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; for (auto e : v) { cout << e << " "; } cout << endl; v[0]++; for (size_t i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; v.insert(v.begin(), 100); print_vector(v); v.insert(v.begin(), 100); print_vector(v); int i = 0; int j = int(); int k = int(10); } void test_vector2() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(4); v.push_back(4); vector<int> v1 = v; for (auto e : v) { cout << e << " "; } cout << endl; for (auto e : v1) { cout << e << " "; } cout << endl; vector<int> v2; v2.push_back(11); v2.push_back(21); v2.push_back(31); v2.push_back(411); v2.push_back(41); v2.push_back(41); v1 = v2; for (auto e : v1) { cout << e << " "; } cout << endl; for (auto e : v2) { cout << e << " "; } cout << endl; } void test_vector3() { vector<int> v; v.reserve(10); v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); for (auto e : v) { cout << e << " "; } cout << endl; v.resize(8); for (auto e : v) { cout << e << " "; } cout << endl; v.resize(15, 1); for (auto e : v) { cout << e << " "; } cout << endl; v.resize(3); for (auto e : v) { cout << e << " "; } cout << endl; } void test_vector4() { vector<string> v; v.reserve(10); v.push_back("xxxx"); v.push_back("xxxx"); v.push_back("xxxx"); v.push_back("xxxx"); v.push_back("xxxx"); v.push_back("xxxx"); for (auto e : v) { cout << e << " "; } cout << endl; v.resize(8); for (auto e : v) { cout << e << " "; } cout << endl; v.resize(15, "yyyy"); for (auto e : v) { cout << e << " "; } cout << endl; v.resize(3); for (auto e : v) { cout << e << " "; } cout << endl; } void test_vector5() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); for (auto e : v) { cout << e << " "; } cout << endl; v.erase(v.begin()+3); for (auto e : v) { cout << e << " "; } cout << endl; } // 迭代器失效 void test_vector6() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(4); v.push_back(4); v.push_back(5); v.push_back(6); //v.push_back(7); for (auto e : v) { cout << e << " "; } cout << endl; // 要求删除所有的偶数 vector<int>::iterator it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { it = v.erase(it); } else { ++it; } } for (auto e : v) { cout << e << " "; } cout << endl; } void test_vector7() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); v.push_back(7); v.push_back(8); v.push_back(9); for (auto e : v) { cout << e << " "; } cout << endl; vector<string> vstr; vstr.push_back("1111"); vstr.push_back("1111"); vstr.push_back("1111"); vstr.push_back("1111"); vstr.push_back("1111"); for (auto e : vstr) { cout << e << " "; } cout << endl; } void test_vector8() { /*vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); vector<int> v2(v1.begin(), v1.end()); for (auto e : v2) { cout << e << " "; } cout << endl; list<int> lt; lt.push_back(10); lt.push_back(20); lt.push_back(30); lt.push_back(40); vector<int> v3(lt.begin(), lt.end()); for (auto e : v3) { cout << e << " "; } cout << endl; int a[] = { 100, 200, 300 }; vector<int> v4(a, a+3); for (auto e : v4) { cout << e << " "; } cout << endl;*/ } void test_vector9() { vector<string> v1(5, "1111"); for (auto e : v1) { cout << e << " "; } cout << endl; vector<int> v2(5, 1); for (auto e : v2) { cout << e << " "; } cout << endl; } }

list与vector的对比

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