STL--list(模拟实现)

实现list的接口

list的数据结构类型

list的数据结构其实就是一个带头结点的双向循环列表.?

因此,我们若要实现list,实现需要实现一个结点类,其中结点需要有:数据,保存前一个地址的变量和保存后一个地址的变量.

而对于该节点的成员函数,我们只需要实现一个构造函数,该节点的释放由list的析构函数来维护.?

list的模拟实现

模拟实现list类中结点

成员函数?

构造函数

?结点类的构造函数直接根据所给出的数据直接构造一个结点,构造出来的结点存储的数据就是给出的数据,而前继和后继指针置为空即可.

_list_node(const T& val = T())
			:_date(val)
			,_pre(nullptr)
			,_next(nullptr)
		{}

成员变量?

1. _date用来保存数据,类型为T
2. _pre用来保存前一个结点的地址的,所以给出的类型为_list_node<T>*
3. _next用来保存后一个结点的地址的,即给出的类型也是_list_node<T>*

T _date;
_list_node<T>* _pre;
_list_node<T>* _next;

模拟实现list迭代器

解释为何要设计迭代器?

之前我们模拟实现的string和vector都没有实现迭代器,为什么list要实现迭代器呢,因为list和vector对象将数据存放在一段连续的空间内,我们通过指针进行自增,自减解引用操作就可以对对应的数据进行一系列操作,因为string和vector的原生指针就是迭代器.?

?而list,其结点在内存中的位置是随机的,我们不能通过指针的自增,自减和解引用来找到对应的结点进行操作.

而迭代器的意义就是让我们不再关心容器的底层如何实现的,可以使用简单的方式对容器的数据进行访问.

而list迭代器,就是对结点指针进行封装,对各种操作符的重载,使我们可以使用++,--等操作符对其进行操作.?

迭代器的模板参数说明?

	template<class T,class Ptr,class Ref>

?在list的模拟实现中.我们typedef了两个迭代器,可修改迭代器和只读迭代器.

typedef _list_iterator<T,T*,T&> iterator;
typedef _list_iterator<T, const T*, const T&> const_iterator;

其中Ptr是指针类型,Ref是引用类型.当我们使用普通迭代器是,编译器就会实例化出一个普通迭代器对象,当我们使用const迭代器时,编译器就会实例化出一个const迭代器.?

成员函数?

构造函数?

迭代器是对结点指针进行封装,构造函数根据所给出的结点指针构造出一个迭代器对象即可.?

_list_iterator(Node* node)
			:_node(node)
		{}

重载前置++和--

?前置++原本是对数据自增,然后返回自增后的数据,我们封装的目的是让结点指针的行为看起来更新指针,对于前置++,就是先让该结点指向后一个结点,然后返回自增加后的结点指针.前置--也同理.

self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator--()
		{
			_node = _node->_pre;
			return *this;
		}

重载 后置++和--

而对于后置++和--我们要记录当前结点指针指向的位置,然后让结点指向后一个结点,然后返回自增前的结点指针.后置--也同理.

self operator++(int)
		{
			self temp(*this);
			_node = _node->_next;
			return temp;
		}
		self operator--(int)
		{
			self temp(*this);
			_node = _node->_pre;
			return temp;
		}

重载==和!=

使用==操作符比较两个迭代器时,我们实际上想知道这个的迭代器的是否处于同一个位置,也就是我们判断两个迭代器当中的结点指针是否相同.而!=操作符与==操作符的作用相反.

bool operator==(const self& s)
		{
			return _node == s._node;
		}
		bool operator !=(const self& s)
		{
			return _node != s._node;
		}

重载*

使用*操作符实际上我们想知道该位置的数据,因此我们直接返回当前结点指向的数据即可,但是这里需要使用引用返回,解引用后可能会对数据进行修改.?

Ref& operator*()
		{
			return _node->_date;
		}

?重载->

当list器中存储的不是内置类型的数据是我们拿到当前位置的迭代器是,我们使用->操作符访问器成员变量.

实现:

Ptr operator->()
		{
			return &(_node->_date);
		}

?使用:

struct AA
	{
		AA(int a1 = 0,int a2 =0)
			:_a1(a1)
			,_a2(a2)
		{}
		int _a1;
		int _a2;
	};
	void test5()
	{
		list<AA> l1;
		l1.push_back(AA(1, 2));
		l1.push_back(AA(1, 2));
		l1.push_back(AA(1, 2));
		l1.push_back(AA(1, 2));
		list<AA>::iterator it = l1.begin();
		while (it != l1.end())
		{
			cout << it->_a1 << " " << it->_a2;
			cout << endl;
			//cout << it.operator->()->_a1 << " " << it.operator->()->_a2;
			//cout << endl;
			it++;
		}
	}

成员变量?

_node?

typedef _list_node<T> Node;
		typedef _list_iterator<T,Ptr,Ref> self;
		Node* _node;

模拟实现list?

成员函数

默认成员函数

空构造

list是一个带头的双向循环列表,当我们构造一个空的list时也需要申请一个同结点.?

void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_pre = _head;
			_size = 0;
		}
		list()
		{
			empty_init();
		}

拷贝构造

拷贝构造根据给出的list容器,拷贝构造出一个对象.我们先申请一个头结点,然后将给出的list容器一个一个的推进当前容器.

list(const list<T>&lt)
		{
			empty_init();
			for (auto e : lt)
			{
				push_back(e);
			}
		}

=操作符的重载

传统写法:

我们先判断是不时给自己赋值,若时自己给直接赋值啥都不做,不是自己给自己赋值,前清空当前容器,然后遍历给出的容器一个一个推进当前容器.

list<T>& operator=(const list<T>& lt)
		{
			if (this != &lt)
			{
				clear();
				for (auto e : lt)
				{
					push_back(e);
				}
			}
			return *this;
		}

现代写法:

利用编译器,故意不使用接收参数,通过编译器自动调用list的拷贝构造函数,构造出来一个list对象,然后调用swap函数,将源容器与list对象进行交换.

	list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

析构函数

直接对头结点进行delete,然后将成员变量置为空即可.

~list()
		{
			delete[] _head;
			_head = nullptr;
			_size = 0;
		}

容量相关的

size

size返回的时容器中的有效数据的个数,直接返回成员变量size即可.

size_t size()
		{
			return _size;
		}

empty?

empty函数用于判断容器是否为空,我们直接判断该容器的begin是否等于end.(list为带头结点的循环链表)

bool empty()
		{
			return (begin() == end());
		}

迭代器相关的

end和begin

begin()函数返回的时第一个有效数据的迭代器,end函数返回的时最后一个有效数据的下一个迭代器的位置.第一个有效数据的迭代器就是头结点下一个结点的地址构造出来的迭代器,而最后一个有效数据的下一个位置则是使用头结点构造出来的迭代器.

iterator begin()
		{
			return _head->_next;
		}
iterator end()
		{
			return _head;
		}

cend和cbegin?

cbegin和cend则是不可修改的begin和end.

const_iterator begin() const
		{
			return _head->_next;
		}
const_iterator end() const
		{
			return _head;
		}

修改相关的

push_back和pop_back?

push_back和pop_back函数是对list容器进行尾插和尾删的,当然实现了erase和insert也可以复用erase和insert,这里将提供两种写法.

常规写法:

void push_back(const T& x)
		{
			Node* end = _head->_pre;
			Node* newnode = new Node(x);
			_head->_pre = newnode;
			newnode->_pre = end;
			newnode->_next = _head;
			end->_next = newnode;
		}
void pop_back()
		{
			Node* cur = _head->_pre;
			Node* pre = cur->_pre;
			pre->_next = _head;
			_head->_pre = pre;
			delete cur;
			_size--;
		}

?非常规写法:

void push_back(const T& x)
		{
			insert(end(), x);
		}
void pop_back()
		{
			erase(_head->_pre);
		}

push_front和pop_front

push_front和pop_front是对list容器进行头插和头删的,当然也可以复用erase和insert.

void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_front()
		{
			erase(--end());
		}

insert和erase

insert函数实在所给的迭代器之前插入一个新结点.先根据给出的迭代器得到该位置处的结点指针cur,然后通过cur指针找到前一个位置的结点指针pre,然后根据给出的数据构造出一个新的结点,然后把新构造的结点插入到cur前面.

iterator insert(iterator pos,const T& x)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(x);
			Node* pre = cur->_pre;
			pre->_next = newnode;
			newnode->_next = cur;
			cur->_pre = newnode;
			newnode->_pre = pre;
			++_size;
			return iterator(newnode);
		}

?eras则是删除给出的结点.先根据给出的结点迭代器得到指针cur,然后通过cur找到pre指针和next指针,然后释放当前结点,在pre和next之间建立双向关系.

iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* pre = cur->_pre;
			Node* next = cur->_next;
			pre->_next = next;
			next->_pre = pre;
			delete cur;
			--_size;
			return iterator(next);
		}

swap

swap函数是交换两个容器的内容的,直接使用std里的swap函数交换_head和_size即可.

void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

resize?

resize使用规则:

1. 若当前容器的size小于给出的n时,则进行尾插直到size等于n为止.
2. 若当前容器的size大于给出的n时,则进行尾删直到size等于n为止.?

实现:定义一个number变量,若size小于n时,number=n-size,然后进行尾插,直到size等于n为止.若size大于n时,则number = size-n,然后进行尾删直到size等于n为止.

void resize(size_t n, const T& val = T())
		{
			if (n >= size())
			{
				int number = n - size();
				for (int i = 0; i < number; i++)
				{
					push_back(val);
				}
				_size = n;
			}
			else
			{
				int rnumber = size() - n;
				for (int i = 0; i < rnumber; i++)
				{
					pop_back();
					_size = n;
				}
			}
		}

访问相关的?

front和back

front和back函数分别返回的第一个有效数据和最后一个数据,因此返回时直接返回第一个和最后一个有效数据即可.

T& front()
		{
			return *begin();
		}
T& back()
		{
			return *(--end());
		}

const修饰的fornt和back?

const修饰的front和back效果一样,不过const修饰的是不可修改的.

const T front() const
		{
			return *begin();
		}
const T back() const
		{
			return *--(end());
		}

成员变量?

_head?

_head是指向头结点的指针.

_size

_size是记录容器结点的个数的.

list实现的完整代码?

namespace lzw
{
	template<class T>
	struct _list_node
	{
		T _date;
		_list_node<T>* _pre;
		_list_node<T>* _next;
		_list_node(const T& val = T())
			:_date(val)
			,_pre(nullptr)
			,_next(nullptr)
		{}
	};
	template<class T,class Ptr,class Ref>
	struct _list_iterator
	{
		typedef _list_node<T> Node;
		typedef _list_iterator<T,Ptr,Ref> self;
		Node* _node;
		_list_iterator(Node* node)
			:_node(node)
		{}
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator--()
		{
			_node = _node->_pre;
			return *this;
		}
		self operator++(int)
		{
			self temp(*this);
			_node = _node->_next;
			return temp;
		}
		self operator--(int)
		{
			self temp(*this);
			_node = _node->_pre;
			return temp;
		}
		Ref& operator*()
		{
			return _node->_date;
		}
		Ptr operator->()
		{
			return &(_node->_date);
		}
		bool operator==(const self& s)
		{
			return _node == s._node;
		}
		bool operator !=(const self& s)
		{
			return _node != s._node;
		}
	};
	template<class T>
	class list
	{
		typedef _list_node<T> Node;
	public:
		typedef _list_iterator<T,T*,T&> iterator;
		typedef _list_iterator<T, const T*, const T&> const_iterator;
		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_pre = _head;
			_size = 0;
		}
		list()
		{
			empty_init();
		}
		list(const list<T>&lt)
		{
			empty_init();
			for (auto e : lt)
			{
				push_back(e);
			}
		}
		//传统写法
		/*list<T>& operator=(const list<T>& lt)
		{
			if (this != &lt)
			{
				clear();
				for (auto e : lt)
				{
					push_back(e);
				}
			}
			return *this;
		}*/
		//现代写法
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}
		~list()
		{
			delete[] _head;
			_head = nullptr;
			_size = 0;
		}
		//容量相关的
		size_t size()
		{
			return _size;
		}
		bool empty()
		{
			return (begin() == end());
		}
		//迭代器相关的
		const_iterator begin() const
		{
			return _head->_next;
		}
		iterator begin()
		{
			return _head->_next;
		}
		const_iterator end() const
		{
			return _head;
		}
		iterator end()
		{
			return _head;
		}
		//常规写法
		/*void push_back(const T& x)
		{
			Node* end = _head->_pre;
			Node* newnode = new Node(x);
			_head->_pre = newnode;
			newnode->_pre = end;
			newnode->_next = _head;
			end->_next = newnode;
		}*/
		//非常规写法
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		//常规写法
	/*	void pop_back()
		{
			Node* cur = _head->_pre;
			Node* pre = cur->_pre;
			pre->_next = _head;
			_head->_pre = pre;
			delete cur;
			_size--;
		}*/
		//非常规的写法
		void pop_back()
		{
			erase(_head->_pre);
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_front()
		{
			erase(--end());
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		iterator insert(iterator pos,const T& x)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(x);
			Node* pre = cur->_pre;
			pre->_next = newnode;
			newnode->_next = cur;
			cur->_pre = newnode;
			newnode->_pre = pre;
			++_size;
			return iterator(newnode);
		}
		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* pre = cur->_pre;
			Node* next = cur->_next;
			pre->_next = next;
			next->_pre = pre;
			delete cur;
			--_size;
			return iterator(next);
		}
		void resize(size_t n, const T& val = T())
		{
			if (n >= size())
			{
				int number = n - size();
				for (int i = 0; i < number; i++)
				{
					push_back(val);
				}
				_size = n;
			}
			else
			{
				int rnumber = size() - n;
				for (int i = 0; i < rnumber; i++)
				{
					pop_back();
					_size = n;
				}
			}
		}
		//访问相关的函数
		T& front()
		{
			return *begin();
		}
		T& back()
		{
			return *(--end());
		}
		const T front() const
		{
			return *begin();
		}
		const T back() const
		{
			return *--(end());
		}
	private:
		Node* _head;
		size_t _size;
	};
	template<typename Container>
	void print_container(const Container& con)
	{
		typename Container::const_iterator it = con.begin();
		while (it != con.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}