拷贝构造函数
list(const list<T>& it) { empty_init(); for (auto e : it) { push_back(e); } }
这里与赋值不一样的地方是赋值的话,之前的空间不用放着也没用,就在原空间操作了;拷贝构造是重新开的空间,然后将原来数据尾插到新空间
拷贝构造函数测试
void test5() { 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++; } }
insert函数和earse函数
因为之前写的双向链表就是借鉴的这里,如果逻辑不清楚,可以去看一下双向链表那一篇文章
(insert)
iterator insert(iterator pos ,const T&x) { node* cur = pos._node; node* prev = cur->_prev; node* newnode = new node(x); newnode->_next = cur; newnode->_prev = prev; prev->_next = newnode; cur->_prev = newnode; return newnode; }
(earse)
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; }
这里insert函数迭代器不会失效,而earse函数迭代器会失效,最好earse完,给迭代器传下一个位置的地址。
析构函数
void clear() { iterator it = begin(); while (it != end()) { it = earse(it);//释放完一个结点,返回下一个结点地址 } } ~list() { clear();//完成后只剩头节点 delete _head;//释放头节点 _head = nullptr;//防止野指针 cout<<"析构完成“<<endl; }
析构测试
void test8() { 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++; } res.~list(); }
push_front函数,pop_back()函数,pop_front()函数
因为实现了insert和earse,所以这三个就简单了。
void push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); }
注意这里的end()是最后一个数据的下一个位置,所以要先–
测试头插
void test6() { 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++; } cout << endl; res.push_front(1000); list<int> ::iterator num = res.begin(); while (num != res.end()) { cout << *num << " "; num++; } }
测试头删和尾删
void test7() { 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++; } cout << endl; res.pop_front(); res.pop_back(); list<int> ::iterator num = res.begin(); while (num != res.end()) { cout << *num << " "; num++; } }
测试这三个间接测试了insert和erase
源码展示
list.h
#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(nullptr) ,_next(nullptr) ,_data(x) { } }; template<class T ,class res,class ptr> struct _list_iterator { typedef listnode <T> node; typedef _list_iterator<T,res,ptr> self; node* _node; _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; } res operator*() { return _node->_data; } ptr operator->() { return &_node->_data; } }; 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; list() { empty_init(); } void empty_init() { _head = new node(); _head->_prev = _head; _head->_next = _head; } iterator begin() { return _head->_next; } iterator end() { return _head; } const_iterator begin() const { return _head->_next; } const_iterator end() const { return _head; } 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 clear() { iterator it = begin(); while (it != end()) { it=erase(it); } } ~list() { clear(); delete _head; _head = nullptr; cout << "析构完成" << endl; } list(const list<T>& it) { empty_init(); for (auto e : it) { push_back(e); } } 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 push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } void swap(list<T>& tmp) { std::swap(_head, tmp._head); } list<T>& operator=(list<T>it) { swap(it); return *this; } iterator insert(iterator pos ,const T&x) { node* cur = pos._node; node* prev = cur->_prev; node* newnode = new node(x); newnode->_next = cur; newnode->_prev = prev; prev->_next = newnode; cur->_prev = newnode; return newnode; } private : node* _head; }; struct AA { int a1; int a2; AA(int _a1 = 0, int _a2 = 0) :a1(_a1) , a2(_a2) { } }; void print_list(const list<AA>it) { list<AA>::const_iterator res =it.begin(); while (res!=it.end()) { cout << res.operator->()->a1 << ":" << res->a2 << endl; res++; } } /* 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++; } }*/ //void test2() //{ // list<int>res; // res.push_back(1); // res.push_back(2); // res.push_back(3); // res.push_back(4); // print_list(res); // // // // // //} /* 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)); print_list(res); }*/ /* 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++; } }*/ /* void test5() { 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++; } }*/ /* void test6() { 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++; } cout << endl; res.push_front(1000); list<int> ::iterator num = res.begin(); while (num != res.end()) { cout << *num << " "; num++; } }*/ /* void test7() { 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++; } cout << endl; res.pop_front(); res.pop_back(); list<int> ::iterator num = res.begin(); while (num != res.end()) { cout << *num << " "; num++; } }*/ void test8() { 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++; } res.~list(); } }
.cpp
#include"list.h" int main() { zjw::test8(); }