C++之list(2)

list(2)

list的迭代器

const迭代器

根据我们之前学过的知识：

const int*p1;//修饰的是指向的内容
int *const p2;//修饰的是迭代器本身

我们写const迭代器，期望的是指向的内容不能修改。 所以更期望写上面p1的形式

const迭代器与普通迭代器的不同点在于普通迭代器既可以读也可以写，但是const修饰的迭代器只可以读

它的实现基本和普通迭代器一致：

template<class T>struct list_const_iterator{typedef list_node<T> Node;typedef list_const_iterator<T> Self;Node* _node;list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->_data;}const T* operator->(){return &_node->_data;}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 _node != s._node;}};

不同点在于返回值的不同，因为const不希望被修改，所以要用const修饰

		const T& operator*(){return _node->_data;}const T* operator->(){return &_node->_data;}

这样子写的代码会显得有些冗余和重复，我们看stl_list.h的源代码可以发现：

从这里看出来，const迭代器和普通迭代器在编译器中都是用一个模板写出来两个类，模板的本质是复用

可以这样写代码：

struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*()//引用{return _node->_data;}Ptr operator->()//指针{return &_node->_data;}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 _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};

typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> 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的增删查改

代码如下：

	list(size_t n, const T& val = T()){empty_init();for (size_t i = 0; i < n; i++){push_back(val);}}void push_back(const T& x){/*Node* new_node = new Node(x);Node* tail = _head->_prev;tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;*/insert(end(), x);//尾插是对插入的复用//因为list底层是双向循环链表，物理结构不连续，所以是在哨兵位附近的位置}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}
//插入不会涉及到迭代器的失效问题iterator insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;// prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);}iterator erase(iterator pos){assert(pos != end());Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;prev->_next = next;next->_prev = prev;delete del;--_size;return iterator(next);}private:Node* _head;size_t _size;

string和vector可能会出现迭代器失效的问题，但是string相比较失效的可能性更小一点，因为string会通过下标访问

析构：

~list(){clear();delete _head;_head = nullptr;}//clear只清理数据，不清理空间void clear(){auto it = begin();while (it != end()){//避免迭代器失效it = erase(it);}}

拷贝：

list()
{empty_init();
}// lt2(lt1)
list(const list<T>& lt)
{empty_init();
//这里是深拷贝，引用，不是引用的话，又会形成拷贝for (auto& e : lt){push_back(e);}
}

赋值：

// lt2 = lt3
//list& operator=(list lt)
list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}
void swap(list<T>& tmp)
{std::swap(_head, tmp._head);std::swap(_size, tmp._size);
}

交换：

template <class T>//这个是调用库里面的
void swap(T& a, T& b)
{T c(a); a = b; b = c;
}
//这个是针对list提炼出的一个模板
template <class T>
void swap(list<T>& a, list<T>& b)
{a.swap(b);
}

模板的话，编译器会更加优先匹配适配程度更高的模板，所以我们这里会调用下面的模板，效率会更加高效

模拟实现list的代码如下：

List.h

#pragma once
#include<assert.h>namespace soobin
{// 惯例// 全部都是公有，一般用structtemplate<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}};// typedef list_iterator<T, T&, T*> iterator;// typedef list_iterator<T, const T&, const T*> const_iterator;template<class T, class Ref, class Ptr>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}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 _node != s._node;}bool operator==(const Self& s){return _node == s._node;}};/*template<class T>struct list_const_iterator{typedef list_node<T> Node;typedef list_const_iterator<T> Self;Node* _node;list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->_data;}const T* operator->(){return &_node->_data;}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 _node != s._node;}};*/template<class T>class list{typedef list_node<T> Node;public:/*typedef list_iterator<T> iterator;typedef list_const_iterator<T> const_iterator;*/typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> 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);}void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;//有效个数大小，增加这个成员变量使其更高效}list(){empty_init();}// lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}// lt2 = lt3//list& operator=(list lt)list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void swap(list<T>& tmp){std::swap(_head, tmp._head);std::swap(_size, tmp._size);}void clear(){auto it = begin();while (it != end()){it = erase(it);}}list(size_t n, const T& val = T()){empty_init();for (size_t i = 0; i < n; i++){push_back(val);}}void push_back(const T& x){/*Node* new_node = new Node(x);Node* tail = _head->_prev;tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}iterator insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;// prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;//插入高效return iterator(newnode);}iterator erase(iterator pos){assert(pos != end());Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;prev->_next = next;next->_prev = prev;delete del;--_size;//删除元素高效return iterator(next);}private:Node* _head;size_t _size;};template <class T>void swap(T& a, T& b){T c(a); a = b; b = c;}template <class T>void swap(list<T>& a, list<T>& b){a.swap(b);}
}

Test.cpp

#include<iostream>
#include<algorithm>
#include<list>
#include<vector>
using namespace std;//int main()
//{
//	list<int> lt1;
//	lt1.push_back(1);
//	lt1.push_back(1);
//	lt1.push_back(1);
//	lt1.push_back(1);
//	lt1.emplace_back(10);
//
//	list<int> lt2 = {1,2,3,4,5};
//
//	list<int>::iterator it1 = lt1.begin();
//	while (it1 != lt1.end())
//	{
//		cout << *it1 << " ";
//		++it1;
//	}
//	cout << endl;
//
//	for (auto e : lt2)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	return 0;
//}class Pos
{
public:int _row;int _col;Pos(int row = 0, int col = 0):_row(row), _col(col){cout << "Pos(int row, int col)" << endl;}Pos(const Pos& p):_row(p._row), _col(p._col){cout << "Pos(const Pos& p)" << endl;}
};//int main()
//{
//	list<Pos> lt;
//
//	// 构造+拷贝构造
//	Pos p1(1, 1);
//	lt.push_back(p1);
//	lt.push_back(Pos(2, 2));
//	lt.push_back({3,3});
//
//	lt.emplace_back(p1);
//	lt.emplace_back(Pos(2, 2));
//	//lt.emplace_back({ 3,3 });
//
//	// 直接构造
//	lt.emplace_back(3, 3);
//
//	return 0;
//}//int main()
//{
//	list<int> lt1 = { 1,2,3,4,5 };
//
//	for (auto e : lt1)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	int x;
//	cin >> x;
//	auto it = find(lt1.begin(), lt1.end(), x);
//	if (it != lt1.end())
//	{
//		lt1.erase(it);
//	}
//
//	for (auto e : lt1)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	return 0;
//}//int main()
//{
//	list<int> lt1 = { 1,2,3,4,5 };
//	// LRU
//	int x;
//	
//	while (cin >> x)
//	{
//		auto pos = find(lt1.begin(), lt1.end(), x);
//		if (pos != lt1.end())
//		{
//			lt1.splice(lt1.begin(), lt1, pos);
//		}
//
//		for (auto e : lt1)
//		{
//			cout << e << " ";
//		}
//		cout << endl;
//	}
//
//	cout << "xxxxxxxxxxxxxxxxxxxxxx" << endl;
//
//	return 0;
//}//int main()
//{
//	list<int> lt1 = { 1,20,3,-4,5 };
//	for (auto e : lt1)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	// <
//	//lt1.sort();
//	// >
//	/*greater<int> gt;
//	lt1.sort(gt);*/
//	lt1.sort(greater<int>());
//
//	// 不能用
//	//sort(lt1.begin(), lt1.end(), greater<int>());
//	for (auto e : lt1)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	vector<int> v1 = { 1,20,3,-4,5 };
//	for (auto e : v1)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	//sort(v1.begin(), v1.end());
//	sort(v1.begin(), v1.end(), greater<int>());
//	for (auto e : v1)
//	{
//		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() + i;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();// 拷贝vectorvector<int> v(lt2.begin(), lt2.end());// 排序sort(v.begin(), v.end());// 拷贝回lt2lt2.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()
//{
//	test_op1();
//	test_op2();
//
//	return 0;
//}#include"List.h"//int main()
//{
//	bit::list<int> lt1;
//	lt1.push_back(1);
//	lt1.push_back(1);
//	lt1.push_back(1);
//	lt1.push_back(1);
//
//	soobin::list<int>::iterator it1 = lt1.begin();
//	while (it1 != lt1.end())
//	{
//		*it1 = 2;
//
//		cout << *it1 << " ";
//		++it1;
//	}
//	cout << endl;
//
//	for (auto e : lt1)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	soobin::list<Pos> lt2;
//	Pos p1(1, 1);
//	lt2.push_back(p1);
//	lt2.push_back(Pos(2, 2));
//	lt2.push_back({3,3});
//
//	soobin::list<Pos>::iterator it2 = lt2.begin();
//	while (it2 != lt2.end())
//	{
//		//cout << (*it2)._row << ":" << (*it2)._col << endl;
//		// 为了可读性，特殊处理，省略了一个->
//		cout << it2->_row << ":" << it2->_col << endl;
//		cout << it2.operator->()->_row << ":" << it2.operator->()->_col << endl;
//
//		++it2;
//	}
//	cout << endl;
//}//int main()
//{
//	const soonbin::list<int> lt1(10, 1);
//
//	// const int* p1  
//	// int* const p2
//	soobin::list<int>::const_iterator it1 = lt1.begin();
//	while (it1 != lt1.end())
//	{
//		//*it1 = 2;
//		cout << *it1 << " ";
//		++it1;
//	}
//	cout << endl;
//
//	for (auto e : lt1)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	return 0;
//}//int main()
//{
//	soobin::list<int> lt1;
//	lt1.push_back(1);
//	lt1.push_back(2);
//	lt1.push_back(3);
//	lt1.push_back(4);
//	lt1.push_front(0);
//	lt1.push_front(-1);
//
//	soobin::list<int>::iterator it1 = lt1.begin();
//	while (it1 != lt1.end())
//	{
//		cout << *it1 << " ";
//		++it1;
//	}
//	cout << endl;
//
//	lt1.pop_front();
//	lt1.pop_back();
//
//	for (auto e : lt1)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	soobin::list<int> lt2(lt1);
//	for (auto e : lt2)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	soobin::list<int> lt3(10, 1);
//	lt2 = lt3;
//	for (auto e : lt2)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//}int main()
{bit::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_front(0);lt1.push_front(-1);soobin::list<int> lt2(10, 1);//lt1.swap(lt2);int i = 1, j = 2;soobin::swap(i, j);soobin::swap(lt1, lt2);for (auto e : lt1){cout << e << " ";}cout << endl;for (auto e : lt2){cout << e << " ";}cout << endl;return 0;
}