list的简单实现

前言

    STL中的list是一个双向链表容器，适用于需要频繁插入和删除操作的场景, 这次我们来简单实现一下list

list接口介绍

构造函数

    list也提供了许多种类的构造函数, 和之前的vector, string都有类型的构造

list();//默认构造
explicit list (const allocator_type& alloc);//指定内存分配器构造
explicit list (size_type n, const allocator_type& alloc = allocator_type());//相当于插入n个元素, 每个元素是这个类型的默认构造
list (size_type n, const value_type& val,const allocator_type& alloc = allocator_type());//同上, 只不过指定插入元素
template <class InputIterator>
list (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());//经典迭代器构造
list (const list& x);//拷贝构造
list (const list& x, const allocator_type& alloc);
list (list&& x);//右值引用构造
list (list&& x, const allocator_type& alloc);
list (initializer_list<value_type> il,const allocator_type& alloc = allocator_type());//经典列表初始化

迭代器

    list也提供迭代器来访问元素

//返回普通或常量迭代器，指向 vector 的第一个元素的位置
iterator begin() noexcept;
const_iterator begin() const noexcept;
//返回普通或常量迭代器，指向 vector 的最后一个元素的位置
iterator end() noexcept;
const_iterator end() const noexcept;
//返回反向迭代器，指向 vector 第一个元素的反向迭代器。
reverse_iterator rbegin() noexcept;
const_reverse_iterator rbegin() const noexcept;
//返回反向迭代器，指向 vector 最后一个元素的反向迭代器。
reverse_iterator rend() noexcept;
const_reverse_iterator rend() const noexcept;`

    很多容器都封装迭代器, 它们的实现可能都不相同, 但经过封装, 使用起来非常类似, 这次就不在过多说明使用

常用容量操作

size_type size() const noexcept;//获取当前元素个数
void resize (size_type n, value_type val = value_type());//调整容器的大小，使其包含 n 个元素
bool empty() const noexcept;//判断是否为空

注意

• 在resize中如果 n 小于当前的 size()，则 vector 将被缩小，多余的元素将被移除

元素访问

    list只提供了访问头部和尾部的接口, 和vector不同, 没有提供[]等一系列接口

reference front();
const_reference front() const;
reference back();
const_reference back() const;

插入删除

    list提供了许多插入的接口

头插尾插

void push_front (const value_type& val);//头插
void push_front (value_type&& val);//右值头插
template <class... Args>
void emplace_front (Args&&... args);//头插, 直接拿模板参数构造对象
template <class... Args>
void emplace_back (Args&&... args);//模板参数尾插
void push_back (const value_type& val);//尾插
void push_back (value_type&& val);//右值尾插

任意位置插入

iterator insert (const_iterator position, const value_type& val);//一个迭代器位置插入一个值
iterator insert (const_iterator position, size_type n, const value_type& val);//迭代器位置插入n个值
template <class InputIterator>
iterator insert (const_iterator position, InputIterator first, InputIterator last);//范围插入
iterator insert (const_iterator position, value_type&& val);//右值插入
iterator insert (const_iterator position, initializer_list<value_type> il);//列表插入

删除

iterator erase (const_iterator position);//删除一个迭代器位置的值
iterator erase (const_iterator first, const_iterator last);//删除一个范围的值
void remove (const value_type& val);//删除容器中所有等于val的值

注意

• list也有迭代器失效的问题, erase操作会返回一个有效的迭代器

其他常用操作

void unique();//去重
template <class BinaryPredicate>
void unique (BinaryPredicate binary_pred);//自定义去重

注意

• unique只会比较相邻的两个值, 来判断是否需要去重

void merge (list& x);//合并俩list
void sort();//排序
template <class Compare>
void sort (Compare comp);//自定义排序
void reverse() noexcept;//反转list

list简单实现

    我们已经熟悉了list的基本操作, list本质是一个带头双循环链表, 现在我们来简单实现一下
完整代码

框架

    这里只介绍常用重点功能实现, 具体可以看我的仓库
首先是ListNode的封装

	template<class T>
	struct ListNode
	{
		ListNode<T>* _prev;
		ListNode<T>* _next;
		T _val;
		ListNode(const T& val=T());//默认构造
		ListNode(T&& val);//右值构造
		template<class ...Args>
		ListNode(Args&& ...args);//模板参数构造
	};

ListNode这个就不用在细说了
在list这里, 普通的指针已经不能满足需求, 所以需要自己封装一个

	template<class T,class CIT,class PTR>
	struct List_iterator
	{
		typedef ListNode<T> Node;
		typedef List_iterator<T,CIT,PTR> self;
		Node* _node;
		List_iterator(Node* node);
		List_iterator(const self& s);
		self& operator++();
		self& operator--();
		CIT operator*() const;
		bool operator!=( const self& li) const;
		bool operator==(const self& li) const;
		PTR operator->() const;
	};

• 迭代器的功能就是实现元素的顺序访问,

self& operator++()
{
	_node = _node->_next;//重载++
	return *this;
}
self& operator--()
{
	_node = _node->_prev;//重载--
	return *this;
}
CIT operator*() const
{
	return _node->_val;//返回一个元素的引用
}
bool operator!=( const self& li) const
{
	return _node != li._node;
}
bool operator==(const self& li) const
{
	return _node == li._node;
}
PTR operator->() const
{
	return &_node->_val;
}

list是链表结构, 元素的储存不是线性的, 在内存中是分散的, 指针++并不能达到下一个数据, 反而会越界

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();
	list(const list<T>& li);
	list(list<T>&& li);
	list(std::initializer_list<T> li);
	~list();
    //插入删除操作
	void push_back(const T& val);
	void push_front(const T& val);
	void pop_back();
	void pop_front();
	template<class ... Args>
    iterator emplace(iterator it, Args&&... args)
    template<class ...Args>
    void emplace_back(Args&&...args)
    template<class ...Args>
    void emplace_front(Args&&...args)
	iterator insert(iterator it,const T& val);
	iterator insert(iterator it,T&& val);
	iterator erase(iterator it);
    //迭代器
	iterator begin();
	iterator end();
	const_iterator begin() const;
	const_iterator end() const;
	void clear();
	void swap(list& li);
	void resize(size_t n, const T& val = T());
	bool empty();
	int size();
    //操作符重载
	list& operator=(const list& li);
	list& operator=(list&& li);
private:
	Node* _head;
	void empty_init();//初始化
};

构造析构

void empty_init()
{
	_head = new ListNode<T>();
	_head->_next = _head;
	_head->_prev = _head;
}
void clear()
{
	iterator b = begin();
	while (b != end())
	{
		b=erase(b);
	}
}
list()
{
	empty_init();
}
list(const list<T>& li)
{
	empty_init();
	for (auto& l : li)
	{
		push_back(l);
	}
}
list(list<T>&& li)
{
	swap(li);
}
list(std::initializer_list<T> li)
{
	empty_init();
	for (auto& i : li)
	{
		push_back(i);
	}
}
~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

初始化和之前的vector基本一个套路
注意

• list为带头双向链表, 要先初始化头节点和指针指向
• 析构删除所有节点, 不要忘记头节点

插入

emplace插入

template<class ... Args>
iterator emplace(iterator it, Args&&... args)
{
	Node* prev = it._node->_prev;
	Node* node = it._node;
	Node* newnode = new Node(std::forward<Args>(args)...);
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = node;
	node->_prev = newnode;
	return newnode;
}
template<class ...Args>
void emplace_back(Args&&...args)
{
	emplace(end(), std::forward<Args>(args)...);
}
template<class ...Args>
void emplace_front(Args&&...args)
{
	emplace(begin(), std::forward<Args>(args)...);
}

注意

• 右值被右值引用后的属性会变成左值, 使用万能引用要跟上完美转发
• Node也要支持模板参数构造

insert插入

iterator insert(iterator it,const T& val)
{
	Node* prev = it._node->_prev;
	Node* node = it._node;
	Node* newnode = new Node(val);
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = node;
	node->_prev = newnode;
	return newnode;
}
iterator insert(iterator it,T&& val)
{
	Node* prev = it._node->_prev;
	Node* node = it._node;
	Node* newnode = new Node(std::forward<T>(val));
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = node;
	node->_prev = newnode;
	return newnode;
}

删除

iterator erase(iterator it)
{
	Node* node = it._node;
	Node* next = node->_next;
	node->_prev->_next = next;
	next->_prev = node->_prev;
	delete node;
	node = nullptr;
	return next;
}

注意

• 释放内存, 返回下一个有效的迭代器

迭代器

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

注意

• 这里将头节点的下一个为第一个元素, 头节点为最后一个位置的下一个, 满足[begin,end)

操作符重载

list& operator=(const list& li)
{
	empty_init();
	for (auto&i : li)
	{
		push_back(i);
	}
}
list& operator=(list&& li)
{
	swap(li);
	return *this;
}