C++list_c++ list find

  list是个双向链表。      

底层是带头双向循环链表。

元素访问没有[]了，意味着以后大部分需要使用迭代器进行访问。

 先试着写一下代码。

#include<list>
using namespace std;
void test1()
{
	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())
	{
		cout << *it << endl;
		it++;
	}
	for (auto c : lt)
	{
		cout << c << endl;
	}
}
int main()
{
	test1();
	return 0;
}

---

到着遍历可以用反向迭代器。

 const对象调用const迭代器。

---

没有reserve和resize了，因为链表是按需要申请和释放空间的。 

---

获取头和尾的数据 。

---

如果pop_back的数量大于结点数量，会报错。

---

list中没有find()模板，需要调用algorithm库中的find。

#include<iostream>
#include<algorithm>
#include<list>
using namespace std;
void test2()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	auto pos = find(lt.begin(), lt.end(), 3);
	if (pos != lt.end())
	{
		lt.insert(pos, 30);
	}
	for (auto i : lt)
	{
		cout << i <<" ";
	}
	cout << endl;
}
int main()
{
	test2();
	return 0;
}

 

不失效。 

 但erase后，pos会失效，因为此时pos位置结点已经没了。

---

底层是快速排序。 

链表sort底层是归并排序。

为什么链表有自己的sort？ 

 vector和string属于随机。 

底层是快速排序。 

它俩能够相减，需要迭代器是连续的，而链表迭代器不连续。

链表list要排序只能使用list的sort了。

用库里面sort对vector排序要比list中的sort对链表排序快。

。

平时头插和头删最好不用vector 。

---

remove一个对象中没有的数，不会报错。

---

利用unique进行去重，必须先保证链表数据有序。

---

合并

但在合并前，需要保证两个列表数据都是有序的，否则会报错。 

---

void test3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_front(5);
		lt.push_front(6);
 
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
 
		list<int> lt1(lt);
		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;
 
		lt.clear();
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}

这个代码，我们需要写个深拷贝构造函数，因为默认拷贝构造函数是个浅拷贝，lt被clear后，地址被释放了一次，lt1出函数时，地址又被释放了一次，它俩是相同的地址，被释放两次，所以会报错。

---

简单模拟实现下list 

#include<iostream>
#include<string>
#include<list>
#include<algorithm>
#include<assert.h>
 
namespace bit
{
	using namespace std;
 
	template<class T>
	struct list_node
	{
		list_node* _next;
		list_node* _prev;
		T _data;
		list_node(const T& x)
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}
	};
	template<class T, class Ref>
	struct list_iterator
	{
		typedef list_node<T>  node;
		typedef list_iterator<T, Ref> self;
		node* _pnode;
		list_iterator(node* p)
			:_pnode(p)
		{}
		Ref operator*()
		{
			return _pnode->_data;
		}
		self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}
		self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}
		bool operator!=(const self& e)
		{
			return _pnode != e._pnode;
		}
	};
	template<class T>
	class list
	{
	public:
		typedef list_node<T> node;
		typedef list_iterator<T, T&> iterator;
		typedef list_iterator<T, const T&> const_iterator;
		list()
		{
			empty_initialize();
		}
 
		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end()const
		{
			return const_iterator(_head);
		}
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}
		iterator insert(iterator pos, const T& n)
		{
			node* newnode = new node(n);
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			newnode->_next = cur;
			newnode->_prev = prev;
			prev->_next = newnode;
			cur->_prev = newnode;
			return iterator(newnode);
		}
		iterator erase(iterator pos)
		{
			assert(pos != end());
 
			node* prev = pos._pnode->_prev;
			node* next = pos._pnode->_next;
			prev->_next = next;
			next->_prev = prev;
			delete pos._pnode;
 
			return iterator(next);
		}
		list<T>& operator=(const list<T>& lt)
		{
			if (this != &lt)
			{
				clear();
				for (const auto& e : lt)
				{
					push_back(e);
				}
			}
			return *this;
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void  pop_front()
		{
			erase(begin());
		}
		void pop_back()
		{
			erase(--end());
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		/*list(const list<T>& lt)
		{
			_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;
			for (const auto &e : lt)
			{
				push_back(e);
			}
		}*/
		void empty_initialize()
		{
			_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;
		}
		~list()
		{
			clear();
			delete _head;
			_head = NULL;
		}
		void push_back(const T& e)
		{
			/*node* NEW = new node(e);
			node* tail = _head->_prev;
			tail->_next = NEW;
			NEW->_next = _head;
			_head->_prev = NEW;
			NEW->_prev = tail;*/
			insert(end(), e);
 
		}
 
 
	private:
		node* _head;
	};
	void test1_1(const list<int>& lt1)
	{
		list<int>::const_iterator it1 = lt1.begin();
		cout << "lt1::";
		while (it1 != lt1.end())
		{
			cout << *it1 << " ";
			++it1;
		}
		cout << endl;
	}
	void test1()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		lt1.push_back(5);
 
		list<int>::iterator it = lt1.begin();
 
		cout << "lt1:";
		while (it != lt1.end())
		{
			cout << (*it)++ << " ";
			++it;
		}
		cout << endl;
		cout << "lt1:";
		for (auto e : lt1)
		{
			cout << e;
 
		}
 
		lt1.insert(lt1.end(), 7);
 
		cout << endl;
		cout << "lt1:";
		for (auto e : lt1)
		{
			cout << e;
		}
		cout << endl;
		list<int> lt2 = lt1;
		lt1.erase(--lt1.end());
		lt1.erase(--lt1.end());
		cout << "lt1::";
		for (auto e : lt1)
		{
			cout << e;
		}
		cout << endl;
		cout << "lt2::";
		for (auto e : lt2)
		{
			cout << e;
		}
		cout << endl;
 
		lt2 = lt1;
		cout << "lt1::";
		for (auto e : lt1)
		{
			cout << e;
		}
		cout << endl;
		cout << "lt2::";
		for (auto e : lt2)
		{
			cout << e;
		}
		cout << endl;
		test1_1(lt1);
		lt1.push_front(8);
		cout << "lt1::";
		for (auto e : lt1)
		{
			cout << e;
		}
		cout << endl;
 
		lt1.pop_front();
		cout << "lt1::";
		for (auto e : lt1)
		{
			cout << e;
		}
		cout << endl;
		lt1.pop_back();
		cout << "lt1::";
		for (auto e : lt1)
		{
			cout << e;
		}
		cout << endl;
		lt2.clear();
		cout << "lt2::";
		for (auto e : lt2)
		{
			cout << e;
		}
		cout << endl;
	}
 
}
int main()
{
	bit::test3();
	return 0;
}

---

 

构造函数名和类名相同，list是类名，所以不写list<int>，因为这是个类型。 

在类模板内部类型等同于类名，但了解就行，我们尽量不用。

---

 c++中的cout起到了针对自定义类型输出的作用。

---

因为这个，所以需要提供默认构造。

---

  

写两个箭头反而是错的。

 可以这样写

---

当我们用const迭代器对数据修改时，发现它可以修改。这就出现了问题。

 

 这是因为我们的->运算符重载返回的是T*，我们需要把返回值变为const T*，这样结构体内的数据就不能修改了。

注意T*const，时是指针指向不能修改，而指针指向的结构体中的数据能被修改。

我们再加个模板参数就能解决。

 

 

 从上述过程，我们也看出了typedef的优势。

来看下完整代码。

#include<iostream>
#include<string>
#include<list>
#include<algorithm>
#include<assert.h>
 
namespace bit
{
	using namespace std;
 
	template<class T>
	struct list_node
	{
		list_node* _next;
		list_node* _prev;
		T _data;
		list_node(const T& x)
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}
	};
	template<class T, class Ref,class Ptr>
	struct list_iterator
	{
		typedef list_node<T>  node;
		typedef list_iterator<T, Ref,Ptr> self;
		node* _pnode;
		list_iterator(node* p)
			:_pnode(p)
		{}
		Ref operator*()
		{
			return _pnode->_data;
		}
		self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}
		self& operator++(int)
		{
			self tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}
		self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}
		Ptr operator->()
		{
			return &_pnode->_data;
		}
		bool operator!=(const self& e)
		{
			return _pnode != e._pnode;
		}
	};
	template<class T>
	class list
	{
	public:
		typedef list_node<T> node;
		typedef list_iterator<T, T&,T*> iterator;
		typedef list_iterator<T, const T&,const T*> const_iterator;
		list()
		{
			empty_initialize();
		}	
 
		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end()const
		{
			return const_iterator(_head);
		}
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}
		iterator insert(iterator pos, const T& n)
		{
			node* newnode = new node(n);
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			newnode->_next = cur;
			newnode->_prev = prev;
			prev->_next = newnode;
			cur->_prev = newnode;
			return iterator(newnode);
		}
		iterator erase(iterator pos)
		{
			assert(pos != end());
 
			node* prev = pos._pnode->_prev;
			node* next = pos._pnode->_next;
			prev->_next = next;
			next->_prev = prev;
			delete pos._pnode;
			pos._pnode;
			return iterator(next);
		}
		/*list<T>& operator=(const list<T>& lt)
		{
			if (this != &lt)
			{
				clear();
				for (const auto& e : lt)
				{
					push_back(e);
				}
			}
			return *this;
		}*/
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void  pop_front()
		{
			erase(begin());
		}
		void pop_back()
		{
			erase(--end());
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		/*list(const list<T>& lt)
		{
			_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;
			for (const auto &e : lt)
			{
				push_back(e);
			}
		}*/
		template <class inter>
		list(inter begin, inter end)
		{
			_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;
			while (begin != end)
			{
				push_back(*begin);
				++begin;
			}	
		}
		void swap(list<T>& tmp)
		{
			std::swap(_head, tmp._head);
		}
		list(const list<T>& lt)
		{
			empty_initialize();
			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}
		list<T> operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}
		void empty_initialize()
		{
			_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;
		}
		~list()
		{
			clear();
			delete _head;
			_head = NULL;
		}
		void push_back(const T& e)
		{
			/*node* NEW = new node(e);
			node* tail = _head->_prev;
			tail->_next = NEW;
			NEW->_next = _head;
			_head->_prev = NEW;
			NEW->_prev = tail;*/
			insert(end(), e);
 
		}
 
 
	private:
		node* _head;
	};
	struct Pos
	{
		
		Pos(int row = 0, int col = 0)
			:row(row)
			, col(col)
		{}
		int row;
		int col;
	};
	void test1_2(const list<Pos>& lt1)
	{
		list<Pos>::const_iterator it1 = lt1.begin();
		cout << "lt1::";
		while (it1 != lt1.end())
		{
			cout << it1->row << ":" << (*it1).col;
			cout << endl;
			++it1;
		}
		
	}
	void testpos()
	{
		list<Pos> p1;
		p1.push_back(Pos(1, 1));
		p1.push_back(Pos(2, 2));
		p1.push_back(Pos(3, 3));
		p1.push_back(Pos(4, 4));
		list<Pos>::iterator it = p1.begin();
		while (it != p1.end())
		{
			//cout << (*it).row << ":" << (*it).col;
			cout << it->row << ":" << (*it).col;
 
			cout << endl;
			++it;
		}
		test1_2(p1);
	}
	
 
	
}
int main()
{
	bit::testpos();
	return 0;
}

---

初始化列表如果不显示初始化， 自定义类型会调用默认构造函数，内置类型需要自己给缺省值，或在初始化列表显示初始化，否则会被初始化为随机值。

对于析构而言，编译器对自定义类型调用析构函数，对于内置类型不处理。编译器也不敢处理。

比如list的头指针。因为list它不仅有头结点。只处理头结点会出错。

---

迭代器我们没有写析构函数，_pnode也不会自动释放。 

另外之前我们自己模拟实现的迭代器的拷贝构造 其实是浅拷贝。

两个容器指向同一个空间。因为_pnode并不释放，所以浅拷贝不会出问题。

不需要显示写析构，就不需要显示写拷贝构造和赋值。