C++ list类

发布于:2025-03-15 ⋅ 阅读:(21) ⋅ 点赞:(0)

C++ list类

引言

在C++标准库中,list是一个非常重要的容器类,它实现了双向链表的数据结构。本文将详细介绍C++中list的使用方法,包括其构造函数、迭代器、容量操作、元素访问以及修改操作等。此外,我们还将探讨list的迭代器失效问题,并通过模拟实现一个简单的list类来深入理解其底层工作原理。最后,我们将对比listvector的优缺点,帮助读者在实际开发中根据需求选择合适的容器。

list的文档介绍

1.list的使用

1.1 list的构造

constructor构造函数 接口说明
list (size_type n, const value_type& val =value_type()) 构造的list中包含n个值为val的元素
list() 构造空的list
list (const list& x) 拷贝构造函数
list (InputIterator first, InputIterator last) 用**[first, last)**区间中的元素构造list

1.2 list的iterator的使用

可以先将迭代器理解为一个指针,该指针指向list中的某个节点

函数声明 接口说明
begin+end 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin+rend 返回第一个元素的reverse_iterator,即end位置**,**返回最后一个元素下一个位置的reverse_iterator,即begin位置

注意:

  1. begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动
  2. rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动

迭代器的分类

从功能可以分为四种 iterator,reverse_iterator,const_iterator,const_reverse_iterator

从性质上又可以分为三种

性质 使用的类 可用操作符
单向 (ForwardIterator) forward_list / unordered_map … ++
双向 (BidirectionalIterator) list / map / set… ++ / –
随机 (RandomAccessIterator) vector / string / deque… ++ / – / + / -

由迭代器的底层结构决定可以使用哪些算法


1.3 list capacity

函数声明 接口说明
empty 检测list是否为空,是返回true,否则返回false
size 返回list中有效节点的个数

1.4 list element acess

函数声明 接口说明
front 返回list的第一个节点中值的引用
back 返回list的最后一个节点中值的引用

1.5 list modifiers

函数声明 接口说明
push front 在list首元素前插入值为val的元素
pop front 删除list中第一个元素
push back 在list尾部插入值为val的元素
pop back 删除list中最后一个元素
insert 在list position位置中插入值为val的元素
erase 删除list position位置的元素
swap 交换两个list中的元素
clear 清空list中的有效元素

2. list的迭代器失效

迭代器失效即迭代器所指向的节点无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。

代码示例

void TestListIterator1()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array+sizeof(array)/sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
	// erase()函数执行后,it所指向的节点已被删除,因此it无效,在下一次使用it时,必须先给其赋值
	l.erase(it);
	++it;
	}
}
// 改正
void TestListIterator()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array+sizeof(array)/sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		l.erase(it++); // it = l.erase(it);
	}
}

3. list的模拟实现

3.1 List.h文件

#pragma once
#include<assert.h>

namespace jason
{
	template<class T>
	struct list_node
	{
		T _data;                // 节点存储的数据
		list_node<T>* _next;    // 指向下一个节点的指针
		list_node<T>* _prev;    // 指向前一个节点的指针

		// 构造函数,初始化节点的数据和指针
		list_node(const T& data = T())
			:_data(data)        // 初始化数据
			, _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)
		{}

		// 解引用操作符,返回当前节点的数据引用
		Ref operator*()
		{
			return _node->_data;
		}

		// 箭头操作符,返回当前节点数据的指针
		Ptr operator->()
		{
			return &_node->_data;
		}

		// 前置++操作符,迭代器指向下一个节点
		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;  // 返回自减前的迭代器
		}

		// 不等于操作符,判断两个迭代器是否指向不同的节点
		bool operator!=(const Self& s) const
		{
			return _node != s._node;
		}

		// 等于操作符,判断两个迭代器是否指向相同的节点
		bool operator==(const Self& s) const
		{
			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;

        // 返回指向链表第一个元素的迭代器
        iterator begin()
        {
            return _head->_next;
        }

        // 返回指向链表末尾的迭代器(哨兵节点)
        iterator end()
        {
            return _head;
        }

        // 返回指向链表第一个元素的常量迭代器
        const_iterator begin() const
        {
            return _head->_next;
        }

        // 返回指向链表末尾的常量迭代器(哨兵节点)
        const_iterator end() const
        {
            return _head;
        }

        // 初始化空链表
        void empty_init()
        {
            _head = new Node;  // 创建哨兵节点
            _head->_next = _head;  // 哨兵节点的下一个节点指向自己
            _head->_prev = _head;  // 哨兵节点的前一个节点指向自己
            _size = 0;  // 初始化链表大小为0
        }

        // 默认构造函数,初始化空链表
        list()
        {
            empty_init();
        }

        // 使用初始化列表构造链表
        list(initializer_list<T> il)
        {
            empty_init();
            for (auto& e : il)
            {
                push_back(e);  // 将初始化列表中的元素逐个插入链表
            }
        }

        // 拷贝构造函数
        list(const list<T>& lt)
        {
            empty_init();
            for (auto& e : lt)
            {
                push_back(e);  // 将另一个链表中的元素逐个插入当前链表
            }
        }

        // 赋值操作符
        list<T>& operator=(list<T> lt)
        {
            swap(lt);  // 交换当前链表和传入链表的内容
            return *this;
        }

        // 析构函数,释放链表内存
        ~list()
        {
            clear();  // 清空链表
            delete _head;  // 删除哨兵节点
            _head = nullptr;
        }

        // 清空链表
        void clear()
        {
            auto it = begin();
            while (it != end())
            {
                it = erase(it);  // 逐个删除链表中的节点
            }
        }

        // 交换两个链表的内容
        void swap(list<T>& lt)
        {
            std::swap(_head, lt._head);  // 交换哨兵节点
            std::swap(_size, lt._size);  // 交换链表大小
        }

        // 在链表末尾插入元素
        void push_back(const T& x)
        {
            insert(end(), x);  // 在链表末尾插入元素
        }

        // 在链表头部插入元素
        void push_front(const T& x)
        {
            insert(begin(), x);  // 在链表头部插入元素
        }

        // 在指定位置插入元素
        iterator insert(iterator pos, const T& x)
        {
            Node* cur = pos._node;  // 当前节点
            Node* prev = cur->_prev;  // 前一个节点
            Node* newnode = new Node(x);  // 创建新节点

            // 将新节点插入到前一个节点和当前节点之间
            newnode->_next = cur;
            cur->_prev = newnode;
            newnode->_prev = prev;
            prev->_next = newnode;

            ++_size;  // 链表大小加1

            return newnode;  // 返回指向新节点的迭代器
        }

        // 删除链表末尾的元素
        void pop_back()
        {
            erase(--end());  // 删除链表末尾的元素
        }

        // 删除链表头部的元素
        void pop_front()
        {
            erase(begin());  // 删除链表头部的元素
        }

        // 删除指定位置的元素
        iterator erase(iterator pos)
        {
            assert(pos != end());  // 确保不删除哨兵节点

            Node* prev = pos._node->_prev;  // 前一个节点
            Node* next = pos._node->_next;  // 下一个节点

            // 将前一个节点和后一个节点连接起来
            prev->_next = next;
            next->_prev = prev;
            delete pos._node;  // 删除当前节点

            --_size;  // 链表大小减1

            return next;  // 返回指向下一个节点的迭代器
        }

        // 返回链表的大小
        size_t size() const
        {
            return _size;
        }

        // 判断链表是否为空
        bool empty() const
        {
            return _size == 0;
        }

    private:
        Node* _head;  // 哨兵节点
        size_t _size;  // 链表大小
    };

	struct AA
	{
		int _a1 = 1;
		int _a2 = 1;
	};

	// 按需实例化
	// T* const ptr1
	// const T* ptr2
	template<class Container>
	void print_container(const Container& con)
	{
		// const iterator -> 迭代器本身不能修改
		// const_iterator -> 指向内容不能修改
		typename Container::const_iterator it = con.begin();
		//auto it = con.begin();
		while (it != con.end())
		{
			//*it += 10;

			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : con)
		{
			cout << e << " ";
		}
		cout << endl;
	}


}


3.2 List的反向迭代器

由于反向迭代器的++就是正向迭代器的–,反向迭代器的–就是正向迭代器的++,因此反向迭代器的实现可以借助正向迭代器,即:反向迭代器内部可以包含一个正向迭代器,对正向迭代器的接口进行包装即可

template<class Iterator>
class ReverseListIterator
{
	// 注意:此处typename的作用是明确告诉编译器,Ref是Iterator类中的类型,而不是静态成员变量
	// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
	// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:
	typedef typename Iterator::Ref Ref;
	typedef typename Iterator::Ptr Ptr;
	typedef ReverseListIterator<Iterator> Self;
public:
	//
	// 构造
	ReverseListIterator(Iterator it): _it(it){}
	//
	// 具有指针类似行为
	Ref operator*(){
		Iterator temp(_it);
		--temp;
		return *temp;
	}
	Ptr operator->(){ return &(operator*());}
	//
	// 迭代器支持移动
	Self& operator++(){
		--_it;
		return *this;
	}
	Self operator++(int){
		Self temp(*this);
		--_it;
		return temp;
	}
	Self& operator--(){
		++_it;
		return *this;
	}
	Self operator--(int)
	{
		Self temp(*this);
		++_it;
		return temp;
	}
	//
    // 迭代器支持比较
	bool operator!=(const Self& l)const{ return _it != l._it;}
	bool operator==(const Self& l)const{ return _it != l._it;}
	Iterator _it;
};

4.list与vector的对比

vector list
底层结构 动态顺序表,一段连续空间 带头结点的双向循环链表
随机访问 支持随机访问,访问某个元素效率O(1) 不支持随机访问,访问某个元素效率O(N)
插入和删除 任意位置插入和删除效率低,需要搬移元素,时间复杂度为O(N),插入时有可能需要增容,增容:开辟新空间,拷贝元素,释放旧空间,导致效率更低 任意位置插入和删除效率高,不需要搬移元素,时间复杂度为O(1)
空间利用率 底层为连续空间,不容易造成内存碎片,空间利用率高,缓存利用率高 底层节点动态开辟,小节点容易造成内存碎片,空间利用率低,缓存利用率低
迭代器 原生态指针 对原生态指针(节点指针)进行封装
迭代器失效 在插入元素时,要给所有的迭代器重新赋值,因为插入元素有可能会导致重新扩容,致使原来迭代器失效,删除时,当前迭代器需要重新赋值否则会失效 插入元素不会导致迭代器失效,删除元素时,只会导致当前迭代器失效,其他迭代器不受影响
使用场景 需要高效存储,支持随机访问,不关心插入删除效率 大量插入和删除操作,不关心随机访问