c++|STL之List的模拟实现链表|数据结构|list

STL之List的模拟实现

List的模拟实现
- 重点

List的模拟实现

#include #include namespace nrf { template struct _list_node {_list_node* _next; _list_node* _prev; T _data; _list_node(const T& val = T()) :_next(nullptr) , _prev(nullptr) , _data(val) { } }; template struct _list_iterator {typedef _list_node Node; typedef _list_iterator Self; Node* _node; _list_iterator(Node* node) :_node(node) { }//*it,返回_data Ref operator*() {return _node->_data; } //it->date Ptr operator->() {return &_node->_data; } //it++,返回还是一个迭代器,前置++ Self& operator++() {_node = _node->_next; return *this; } //前置-- Self& operator--() {_node = _node->_prev; return *this; } //后置++ Self operator++(int) {Self tmp(*this); //创建临时变量返回，后置加加，加加之前不变 //_list_iteratortmp = *this; _node = _node->_next; //++（*this) return tmp; } //后置-- Self operator--(int) {Self tmp(*this); _node = _node->_prev; return tmp; }//== bool operator ==(const Self& it) {return _node = it._node; } //it!=end() bool operator!=(const Self& it) {return _node != it._node; } }; template class list { public: typedef _list_node Node; public: typedef _list_iterator iterator; typedef _list_iterator const_iterator; 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; } //l2(l1) list(const list& l1) {//链表的最初状态 _head = new Node; _head->_next = _head; _head->_prev = _head; //const_iterator it = l1.begin(); //构造一个const迭代器尾插到新的迭代器中 //while (it != l1.end()) //{// this->push_back(*it); // it++; //}for (auto e : l1) {push_back(e); } }list& operator=(const list& l1) {if (this != &l1) {clear(); for (auto e : l1) {push_back(e); } } return *this; }//现代版的拷贝构造 //list& operator=(list l1) //{// swap(_head, l1._head); // return *this; //} void clear() {iterator it = begin(); while (it != end()) {erase(it++); } } ~list() {clear(); //clear没有删除头结点 delete _head; _head = nullptr; } bool empty() const {return _head->_next == _head->_prev; } //T x如果T类型是vector或者是string就造成了深拷贝,那么就得传引用，传引用不改变x就加const void push_back(const T& x) {//Node* tail = _head->_prev; //Node* newnode = new Node(x); //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 insert(iterator pos, const T& x)//在pos这个迭代器的前面插入一个节点 {Node* newnode = new Node(x); //pos 是个迭代器,而迭代器又是节点的指针，所以可以通过迭代器找到这个节点 Node* cur = pos._node; Node* prev = cur->_prev; prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; //return iterator(newnode); }void pop_back() {erase(--end()); } void pop_front() {erase(begin()); //end是最后一个有效数据的下一个位置，所以end先--，删除end--的位置 } void erase(iterator pos) {//pos是一个迭代器，节点的指针，可以找到这个节点 //找到要删除的节点del assert(pos != end()); //头结点不能删除 Node* del = pos._node; Node* next = del->_next; //假设有1 2 3节点，要删除pos位置2节点， //先2节点的前一个节点1节点的下一个节点指向2指向的3节点 //然后要把3和1链接起来，把3的前一个节点指向1， //2的下一个节点3节点的前一个节点指向2的前一个节点 //删除2 del->_prev->_next = del->_next; del->_next->_prev = del->_prev; delete del; //return iterator(next); //返回节点的下一个位置 } private: Node* _head; }; void testlist1() {list lt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(10); lt1.push_back(20); lt1.pop_back(); list::iterator it = lt1.begin(); while (it != lt1.end()) {std::cout << *it << " "; ++it; } std::cout << std::endl; } struct Date {int _year = 0; int _month = 1; int _day = 1; }; void print_list(const list& lt1) {list::const_iterator it = lt1.begin(); while (it != lt1.end()) {std::cout << *it << " "; it++; } std::cout << std::endl; } void testlist2() {list lt1; lt1.push_back(Date()); lt1.push_back(Date()); list::iterator it = lt1.begin(); while (it != lt1.end()) {/*std::cout << *it << " "; */ //it->Date->_year std::cout << it->_year << ":" << it->_month << ":" << it->_day << std::endl; std::cout << (*it)._year << ":" << (*it)._month << ":" << (*it)._day << std::endl; ++it; } //print_list(lt1); } void testlist3() {list l1; l1.push_back(1); l1.push_back(2); l1.push_back(3); l1.push_back(4); listl2(l1); //拷贝构造，用l1拷贝构造l2 for (auto e : l1) {std::cout << e << " "; } std::cout << std::endl; for (auto e : l2) {std::cout << e << " "; } std::cout << std::endl; } }

重点 【c++|STL之List的模拟实现】1.由于List的底层是双向带头循环链表，与Vector,String不同的是，我们要单独创建一个List的节点。
2.迭代器的类的实现，与Vector,String不同的是，这两个容器是将对象存在了一块连续的内存空间，与指针类似，通过指针的自增和自减可以完成对象的访问，但List是一个链表，节点在内存中的位置是随机的，而迭代器的意义就是，让使用者可以简单统一的对容器内的数据进行访问。所以我们创建的迭代器类，通过封装，对各种运算符的重载，实现了和其他容器一样的访问方法。
3.