C++ list容器的底层实现

  • 开发
  • 18

一.list是什么

  list 是 C++容器中的带头双向链表，头结点不存储数据，头结点的下一个元素是第一个存储数据的元素，头结点的前一个元素连接着最后一个存储数据的元素。（结构如下图所示）

 其中链表里每一个节点的结构分为，数据部分，前指针和后指针构成（下面是结构图和代码）

二.list 代码实现和语法解析

2.1 定义结点的结构

链表中的数据和前后指针的类型都是模板生成的，可以适配内置类型和自定义类型。这里用struct来定义类的原因是struct默认的成员变量类型都是public，其他函数可以很方便的进行调用。在这里还有一个list_node的构造函数 T()是一个匿名变量，其作用不止是用于存放数据，此外如果调用list_node构造函数时没有写参数的话，这里也会有一个默认的值。

 2.2 定义链表的结构

 在list中，有两个成员变量的存在一个是节点类型的指针_node 和计算节点数量的_size。

template<class T>
class list
{
typedef list_node<T> Node;
void empty_init()
{
    _head = new Node;
    _head -> next = _head;
    _head -> prev = _head;
    _size = 0;
}
list()
{
    empty_init();
}
    private:
        Node* _node;
        size_t _size;
}

2.3 添加链表功能(插入 push_back)

 我们已经定义好了list的基础结构，下面我们就要添加一些基本的功能了，例如往list中插入数据，用迭代器来遍历list链表之类的操作。

Push_back 函数：首先构建一个新的节点newnode，然后把需要存放的数据X存到newnode中，找到尾结点并且将newnode插入到尾节点的下一个节点。

template<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)
	{

	}
};

template<class T>
class list
{
typedef list_node<T> Node;
void empty_init()
{
    _head = new Node;
    _head -> next = _head;
    _head -> prev = _head;
    _size = 0;
}
list()
{
    empty_init();
}
void push_back(const T& x)
{
    Node* newnode = new Node(x);
    Node* tail = _head->prev;

    tail->_next = newnode;
    newnode->prev = tail;

    newnode->_next = _head;
    _head->prev = newnode;
    
    _size++; 
}
    private:
        Node* _node;
        size_t _size;
}

2.4 添加链表功能(迭代器和迭代器的运算符重载)

和顺序表不同，因为链表的节点不是存放在一起的连续空间，所以指针的++和解引用都没有办法直接的获取到数据，因此在这里我们需要自己去重载 *  ->  ++ --等等的运算符。

template<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)
	{

	}
};
template<class T>
struct __list_iterator
{
    typedef list_node<T> Node;
    typedef __list_iterator self;

    Node* _node;
    __list_iterator(Node* node)
        :_node(node)
    {

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

    T* operator(Node * node)
    {
        return &_node->_data;
    }
    self& operator++()
    {
        _node = _node->next;
        return *this;
    }
    
    self& operator--()
    {
        _node = _node->prev;
        return *this;
    }

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

template<class T>
class list
{
typedef list_node<T> Node;
typedef __list_iterator<T> iterator;

iterator begin()
{
    return iterator(_head->next);
}

iterator end()
{
    return iterator(_head);
}

void empty_init()
{
    _head = new Node;
    _head -> next = _head;
    _head -> prev = _head;
    _size = 0;
}

list()
{
    empty_init();
}

void push_back(const T& x)
{
    Node* newnode = new Node(x);
    Node* tail = _head->prev;

    tail->_next = newnode;
    newnode->prev = tail;

    newnode->_next = _head;
    _head->prev = newnode;
    
    _size++; 
}
    private:
        Node* _node;
        size_t _size;
}

做完了以上的操作以后，我们就可以这样来调试程序了,虽然List并不是数组，但是我们可以用相似的方式来对List内部的元素进行访问。虽然迭代器迭代容器各个元素的方式是一样的，但是迭代器屏蔽了底层实现的细节，提供了统一访问的方式。

test_list()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    list<int>::iterator it = lt.begin();

    while(it != lt.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout<< endl;
}

2.5 添加链表功能（插入操作的升级 insert（）和 eraser（）删除）

首先我们可以写一个 insert（）插入的函数，这个函数可以被其他的函数所复用例如push_back和push_front ，也可以在任意的位置插入数据。

iterator insert(iterator pos , const T& x)
{
    Node* newnode = new Node(x);
    Node* cur = pos._node;
    Node* prev = cur ->_prev;
    
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;

    return newnode; 
}

iterator erase(iterator pos)
{
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;

    delete cur;
    prev->_next = next;
    next->_prev = prev;

    return next;
}

void push_back(const T& x)
{
    insert(this.end(),x);
}

void push_front(const T& x)
{
    insert(begin(),x);
}

void pop_back()
{
    erase(--end());
}

void pop_front()
{
    erase(begin());
}

2.6 添加链表功能（clear函数和析构函数）

因为erase函数的返回值是被删除数据的下一个位置，所以这里不写++ 也会有++的效果。

~list()
{
    clear();
    delete _head;
    _head = nullpre;
}

void clear()
{
    iterator it = begin();
    while(it != end())
    {
        it = erase(*it);
    }
}

2.7 添加链表功能（拷贝构造和赋值重载）

（1）拷贝构造

list( list<int> lt )
{
    empty_init();
    for(auto e : lt)
    {
        this.push_back(e);
    }
}

（2）赋值重载

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

2.8 const 类型的迭代器

对于const类型的迭代器，我们需要了解，const 类型的迭代器不可以修改迭代器所指向的数据，而不是迭代器本身不可修改，迭代器本身需要完成++，--等操作进行遍历操作，所以在写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;
	}
};

三.完整代码

#pragma once
#include<iostream>
using namespace std;
namespace hjy
{
	template<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)
		{

		}
	};
	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)
		{

		}
		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;
		}
		Ref operator *()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
		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)
		{

		}
		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;
		}
		const T& operator *()
		{
			return _node->_data;
		}
		const T* operator->()
		{
			return &_node->_data;
		}
		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;
		//typedef __list_const_iterator<T> const_iterator;

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

		iterator begin()
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}
		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
		list()
		{
			empty_init();
		}
		//list<int>& operator=(const list<int>& lt) 传统写法
		//{
		//	if (this != &lt)
		//		clear();
		//	for (auto e : lt)
		//	{
		//		push_back(e);
		//	}
		//	return *this;
		//}
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		list<int>& operator=(list<int> lt)
		{
			swap(lt);
			return *this;
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		//list(const list<T>& lt)//没有const迭代器所以这样写不行
		//{
		//	empty_init();
		//	for (auto e : lt)
		//	{
		//		push_back(e);
		//	}
		//}
		list( list<T>& lt)
		{
			empty_init();
			for (auto e : lt)
			{
				push_back(e);
			}
		}
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		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);
			}
		}
		iterator insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(val);
			Node* prev = cur->_prev;
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			++_size;
			return iterator(newnode);
		}
		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			delete cur;
			prev->_next = next;
			next->_prev = prev;
			--_size;
			return iterator(next);
		}
		size_t size()
		{
			return _size;
		}
	private:
		Node* _head;
		size_t _size;
	};
	void test_list1()
	{
		list<int>lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		for (auto e : lt)
			cout << e << " ";
		cout << endl;

		list<int>lt1 = lt;
		for (auto e : lt1)
			cout << e << " ";
		cout << endl;

	}
	/*void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}*/
	template<typename T>
	void print_list(const list<T>& lt)
	{
		typename list<T>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
	void test_list2()
	{
		list<string>lt;
		lt.push_back("111");
		lt.push_back("111");
		lt.push_back("111");
		print_list(lt);
	}
}

阅读全部

相关推荐

  4. 简单说一下STL中的map容器的特点、底层实现和应用场景【面试】

    2024-07-12 08:52:03       31 阅读

  7. MFC CList＜CRect, CRect&＞ m_listRect；的用法

    2024-07-12 08:52:03       27 阅读

  9. 详解Qml的底层实现

    2024-07-12 08:52:03       52 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-12 08:52:03       70 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-12 08:52:03       74 阅读

  9. 在Django里面运行非项目文件

    2024-07-12 08:52:03       62 阅读

  19. Python语言-面向对象

    2024-07-12 08:52:03       72 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-12 08:52:03       66 阅读

热门阅读

  1. Postman超时设置全指南：掌控请求等待的艺术

    2024-07-12 08:52:03       38 阅读

  9. 时间复杂度

    2024-07-12 08:52:03       29 阅读

  10. 735. 小行星碰撞

    2024-07-12 08:52:03       31 阅读

  18. HTTP3.0

    2024-07-12 08:52:03       26 阅读

  19. notes for datawhale 2th summer camp NLP task1

    2024-07-12 08:52:03       30 阅读

  22. 配置 Node.js 内存限制

    2024-07-12 08:52:03       26 阅读

  23. tomcat的安装和解析

    2024-07-12 08:52:03       27 阅读

  24. Sentieon应用教程：本地使用-Quick_start

    2024-07-12 08:52:03       28 阅读

  27. Django ORM中的Q对象

    2024-07-12 08:52:03       29 阅读

  28. 基于python实现并编译提升cpu与内存使用率的脚本

    2024-07-12 08:52:03       27 阅读