C++容器篇——list容器

1 list的介绍和使用

1.1 list的介绍

list的参考文档

list是C++的容器之一,其本质是双向链表。它是可以在常数时间复杂度内进行插入和删除的序列式容器。

listforword_list非常相似,其中forword_list是单链表,并且只能朝前迭代。

它的缺陷在于不支持随机访问。而且list还需要一些额外空间,来保存每个结点相关联的信息。

在这里插入图片描述

1.2 list的使用

list必须包含头文件#include <list>,并且属于std命名空间里面。

#include <list>
#include <iostream>
using namespace std;

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	for (auto it = lt.begin(); it != lt.end(); ++it)
	{
		cout << *it << endl;
	}
}

这是一个简单的使用list容器的案例,首先先创建一个list容器,<int>这里表示我这个容器存放的是int类型的数据。然后通过push_back()来在这个容器末尾插入元素,由于list不支持随机访问,我们使用迭代器来进行访问,auto是自动获取类型,也可以使用list<int>::iterator

1.2.1 list的定义

list的构造函数

构造函数接口说明
list();无参构造
list(size_type n,const value_type& val = value_type());构造n个val值
list(const list& x);拷贝构造
list(InputIterator first,Inputiterator last);迭代器构造
  • 第一个是无参构造,这个时候容器里面并没有存放任何数据。但是需要通过<>来指定容器存放的类型。
  • 第二个是构造并初始化,初始化n个为val的容器。其实构造函数还有一个空间适配器allocator,这里暂时先忽略。
  • 第三个是拷贝构造。
  • 第四个可能暂时很难理解,其实是通过迭代器来构造并初始化。
int main()
{
	list<int> lt1;
	list<int> lt2(10, 1);
	list<int> lt3(lt2);
	list<int> lt4(lt2.begin(), lt2.end());
}
1.2.2 list的迭代器

迭代器其实本质上是指针,但是是对指针进行了封装。我们在使用C语言的时候,常常因为指针,甚至多级指针,导致代码异常复杂难看。容器里的迭代器对指针进行改造之后,使用起来更加方便。list的迭代器操作其实就是对链表的结点操作。

那么,迭代器带来的便利是什么呢,我们在使用的过程中,访问列表下一个结点,只需要采用++操作,而如果是自己使用链表,可能还需要了解链表的细节。

list获取迭代器

迭代器的使用使用说明
begin()返回指向开始位置的迭代器
end()返回指向末尾元素的下一个位置的迭代器
cbegin()返回指向开始并且为常量的迭代器
cend()返回指向末尾元素的下一个位置的并且为常量的迭代器
rbegin()返回逆置迭代器,指向末尾元素下一个位置,操作都是往相反反向
rend()返回逆置迭代器,指向开头元素的位置,操作都是往相反反向
crbegin()返回逆置迭代器,指向末尾元素下一个位置,操作都是往相反反向,并且为常量属性
crend()返回逆置迭代器,指向开头元素的位置,操作都是往相反反向,并且为常量属性

在这里插入图片描述

  1. list()返回指向开始位置的迭代器,end()返回指向容器最后一个元素下一个位置的迭代器。list中是有个头结点,并且end()指向的就是这个位置,它的下一个元素指向头结点。
  2. rbegin()和rend()与begin()和end()相反。
  3. 这里先把迭代器当成指向对应位置的指针,通过对迭代器进行解引用,获取对应的值。
int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	auto it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}
1.2.3 list的大小
容量说明接口说明
size获取容器中实际的个数
empty判断是否为空
1.2.4 list增删改查
增删改查接口说明
push_front头部插入一个元素
pop_front头部删除一个元素
push_back尾插一个元素
pop_back尾删一个元素
insert在指定位置插入val
erase删除指定位置的数据
swap交换两个list的数据空间
clear清除list的有效元素

list的增删改查,从名字上也能够很好猜测其含义,对于vector,也只是可以进行头插和头删,下面是相关代码演示:

template<typename T>
void print_list(const list<T> &v)
{
    for (const auto &i : v)
        cout << i << " ";
    cout << endl;
}

int main()
{
    list<int> lt;

    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);

    print_list(lt); // 1 2 3 4

    lt.pop_back();
    lt.pop_back();

    print_list(lt); // 1 2

    auto it = find(v.begin(), v.end(), 1);

    it.insert(it, 3);
    it.insert(it, 4);
    print_list(lt); // 4 3 1 2


    lt.erase(it);
    print_list(lt);  // 3 1 2

    list<int> lt2{1, 3, 5, 7, 9};
    lt.swap(lt2);
    print_list(lt); // 1 3 5 7 9
    print_list(lt2); // 3 1 2

    cout << endl;
}
1.2.5 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);
    }
}

2 list的深度解剖及模拟实现

2.1 list的模拟实现代码

我们在实现list的基础上迭代器的时候,加上了反向迭代器,其实反向迭代器就是对正向迭代器的包装。

// list.hpp
//
// Created by CHAKMING on 2022/10/2.
//
#pragma once
#include <cassert>
#include <iostream>
#include "reverse_iterator.h"

namespace ming
{
	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> iterator;

		Node* _node;

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

		bool operator!=(const iterator& it) const
		{
			return _node != it._node;
		}

		bool operator==(const iterator& it) const
		{
			return _node == it._node;
		}

		// *it  it.operator*()
		// const T& operator*()
		// T& operator*()
		Ref operator*()
		{
			return _node->_data;
		}

		//T* operator->() 
		Ptr operator->()
		{
			return &(operator*());
		}

		// ++it
		iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		// it++
		iterator operator++(int)
		{
			iterator tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		// --it
		iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		// it--
		iterator operator--(int)
		{
			iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
	};

	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 __reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

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

		const_iterator end() const
		{
			return const_iterator(_head);
		}

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

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

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		list()
		{
			empty_initialize();
		}

		template<class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			empty_initialize();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

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

		list(const list<T>& lt)
		{
			empty_initialize();
			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 empty_initialize()
		{
			// 创建并初始化哨兵位的头结点
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

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

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

			 _head ... tail newnode
			//tail->_next = newnode;
			//newnode->_prev = tail;
			//newnode->_next = _head;
			//_head->_prev = newnode;
			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);

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			return iterator(newnode);
		}

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

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


		iterator erase(iterator pos)
		{
			assert(pos != end());

			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			prev->_next = next;
			next->_prev = prev;
			delete cur;

			return iterator(next);
		}

	private:
		Node* _head;
	};
}
// reverse_iterator.hpp
//
// Created by CHAKMING on 2022/10/2.
//

#pragma once

namespace ming
{
	template<class Iterator, class Ref,class Ptr>
	struct __reverse_iterator
	{
		Iterator _cur;
		typedef __reverse_iterator<Iterator,Ref,Ptr> RIterator;

		__reverse_iterator(Iterator it)
			:_cur(it)
		{}

		RIterator operator++()
		{
			--_cur;
			return *this;
		}

		RIterator operator--()
		{
			++_cur;
			return *this;
		}

		Ref operator*()
		{
			auto tmp = _cur;
			return *--tmp;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		bool operator!=(const RIterator& it)
		{
			return _cur != it._cur;
		}

		bool operator==(const RIterator& it)
		{
			return _cur == it._cur;

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

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐