【C++】STL之list类源码剖析_stl list push_back源码

目录

概述

源码

iterator.h

MyList.h

test.cpp

测试结果

---

概述

STL标准库中的list类的本质是一个带头双向链表，支持头部增删和尾部增删，以及随机增删，但是不支持随机访问。

list的遍历是通过迭代器进行遍历，迭代器分为正向和反向迭代器，也有const迭代器，反向迭代器是通过正向迭代器实现的。

list的构造能通过迭代器进行构造，也是通过自定义swap函数利用临时变量简化代码完成构造。

源码

iterator.h

#pragma once
 
template<class T>
struct Node
{
	T _data;
	Node<T>* _next;
	Node<T>* _prev;
 
	Node(const T& x)
		: _data(x), _next(nullptr), _prev(nullptr)
	{}
};
 
template<class T, class Ref, class Ptr>
class ListIterator
{
public:
	typedef Node<T> node;
	typedef ListIterator<T, Ref, Ptr> Self;
	node* _pnode;
 
	ListIterator(node* p)
		: _pnode(p)
	{}
 
	Ref operator*()
	{
		return _pnode->_data;
	}
	Ptr 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;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		_pnode = _pnode->_prev;
		return tmp;
	}
 
	bool operator==(const Self& it)const
	{
		return _pnode == it._pnode;
	}
	bool operator!=(const Self& it)const
	{
		return _pnode != it._pnode;
	}
};
 
 
// 通过正向迭代器，构造出反向迭代器
template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
public:
	Iterator _it;
	typedef ReverseIterator<Iterator, Ref, Ptr> Self;
 
	ReverseIterator(Iterator it)
		: _it(it)
	{}
 
	Ref operator*()
	{
		Iterator tmp = _it;
		return *(--tmp);
	}
	Ptr operator->()
	{
		return &(operator*());
	}
 
	Self& operator++()
	{
		--_it;
		return *this;
	}
	Self operator++(int)
	{
		Self tmp(*this);
		--_it;
		return tmp;
	}
	Self& operator--()
	{
		++_it;
		return *this;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		++_it;
		return tmp;
	}
 
	bool operator==(const Self& s)const
	{
		return _it == s._it;
	}
	bool operator!=(const Self& s)const
	{
		return _it != s._it;
	}
};

MyList.h

#pragma once
 
#include <iostream>
#include <cassert>
#include "iterator.h"
 
template<class T>
class List
{
	typedef Node<T> node;
public:
	typedef ListIterator<T, T&, T*> iterator;
	typedef ListIterator<T, const T&, const T*> const_iterator;
	typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
	typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_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);
	}
 
	reverse_iterator rbegin()
	{
		return reverse_iterator(end());
	}
	reverse_iterator rend()
	{
		return reverse_iterator(begin());
	}
	const_reverse_iterator rbegin()const
	{
		return const_reverse_iterator(end());
	}
	const_reverse_iterator rend()const
	{
		return const_reverse_iterator(begin());
	}
 
	// 迭代器构造
	template<class InputIterator>
	List(InputIterator first, InputIterator last)
	{
		empty_initial();
		while (first != last)
		{
			push_back(*first);
			++first;
		}
	}
 
	void swap(List<T>& lt)
	{
		std::swap(_head, lt._head);
		std::swap(_size, lt._size);
	}
	void empty_initial()
	{
		_head = new node(T());
		_head->_next = _head;
		_head->_prev = _head;
		_size = 0;
	}
 
	List()
	{
		empty_initial();
	}
	List(const List<T>& lt)
	{
		empty_initial();
		List<T> tmp(lt.begin(), lt.end());
		swap(tmp);
	}
	List<T>& operator=(List<T> lt)
	{
		swap(lt);
		return *this;
	}
 
	~List()
	{
		clear();
		delete _head;
		_head = nullptr;
	}
	void clear()
	{
		iterator it = begin();
		while (it != end())
		{
			it = erase(it);
		}
	}
 
	size_t size()const
	{
		return _size;
	}
	bool empty()const
	{
		return _size == 0;
	}
 
	void push_back(const T& x)
	{
		insert(end(), x);
	}
	void push_front(const T& x)
	{
		insert(begin(), x);
	}
	void pop_back()
	{
		erase(--end());
	}
	void pop_front()
	{
		erase(begin());
	}
 
	// 在pos处前插
	iterator insert(iterator pos, const T& x)
	{
		node* newNode = new node(x);
		node* cur = pos._pnode;
		node* prev = cur->_prev;
		prev->_next = newNode;
		newNode->_prev = prev;
		newNode->_next = cur;
		cur->_prev = newNode;
		++_size;
		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 = nullptr;
		--_size;
		return iterator(next);
	}
 
private:
	node* _head;
	size_t _size;
};

test.cpp

#include "MyList.h"
 
template<class T>
void print_list(const List<T>& lt)
{
	std::cout << "size=" << lt.size() << ": ";
	for (auto& e : lt)
	{
		std::cout << e << ' ';
	}
	std::cout << std::endl;
}
 
void test()
{
	std::cout << "构建lt1 ";
	List<int> lt1;
	lt1.push_back(2);
	lt1.push_back(4);
	lt1.push_back(6);
	lt1.push_back(8);
	lt1.push_front(1);
	lt1.push_front(3);
	lt1.push_front(5);
	lt1.push_front(7);
	print_list(lt1);
 
	std::cout << "lt1前删/后删 ";
	lt1.pop_front();
	lt1.pop_back();
	print_list(lt1);
 
	std::cout << "拷贝构造lt2/迭代器 ";
	List<int> lt2(lt1);
	List<int>::iterator it2 = lt2.begin();
	while (it2 != lt2.end())
	{
		std::cout << *it2 << ' ';
		++it2;
	}
	std::cout << std::endl;
 
	std::cout << "赋值构造lt3/反向迭代器 ";
	List<int> lt3 = lt1;
	List<int>::reverse_iterator rit3 = lt3.rbegin();
	while (rit3 != lt3.rend())
	{
		std::cout << *rit3 << ' ';
		++rit3;
	}
	std::cout << std::endl;
 
	std::cout << "清空lt3 ";
	lt3.clear();
	print_list(lt3);
 
	std::cout << "自定义结构体链表 ";
	struct Pos
	{
		int _row, _col;
		Pos(int row = 0, int col = 0)
			: _row(row), _col(col)
		{}
	};
	List<Pos> lt4;
	lt4.push_back(Pos(1, 1));
	lt4.push_back(Pos(2, 2));
	lt4.push_back(Pos(3, 3));
	lt4.push_front(Pos(0, 0));
	std::cout << "size=" << lt4.size() << ": ";
	List<Pos>::iterator it4 = lt4.begin();
	while (it4 != lt4.end())
	{
		++(it4->_row);
		std::cout << "(" << it4->_row << "," << it4->_col << ")" << " ";
		++it4;
	}
	std::cout << std::endl;
 
	std::cout << "拷贝自定义结构体链表 ";
	const List<Pos> lt5(lt4);
	std::cout << "size=" << lt5.size() << ": ";
	List<Pos>::const_iterator cit5 = lt5.begin();
	while (cit5 != lt5.end())
	{
		std::cout << "(" << cit5->_row << "," << cit5->_col << ")" << " ";
		++cit5;
	}
	std::cout << std::endl;
 
	std::cout << "反向迭代器 ";
	List<Pos>::const_reverse_iterator rcit5 = lt5.rend();
	while (rcit5 != lt5.rbegin())
	{
		--rcit5;
		std::cout << "(" << rcit5->_row << "," << rcit5->_col << ")" << " ";
	}
	std::cout << std::endl;
}	
 
int main()
{
	test();
 
	return 0;
}

测试结果