C++容器篇，list容器

介绍了C++的list容器，介绍了底层原理和基本的接口使用。介绍了list迭代器失效的问题，最后简易的实现了list，并实现了反向迭代器。对比了vector和list的区别。

CHAKMING1

3819人浏览 · 2022-11-23 16:10:38

CHAKMING1 · 2022-11-23 16:10:38 发布

C++容器篇——list容器

1 list的介绍和使用

1.1 list的介绍

list的参考文档

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

list和forword_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()	返回逆置迭代器，指向开头元素的位置，操作都是往相反反向，并且为常量属性

在这里插入图片描述

list()返回指向开始位置的迭代器，end()返回指向容器最后一个元素下一个位置的迭代器。list中是有个头结点，并且end()指向的就是这个位置，它的下一个元素指向头结点。
rbegin()和rend()与begin()和end()相反。
这里先把迭代器当成指向对应位置的指针，通过对迭代器进行解引用，获取对应的值。

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的对比

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

向您推荐>>Eolink开发者社区

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

更多推荐

ELK实现containerd的容器日志采集展示【基于logging的全栈监测】

企业级ELK Stack构建介绍

云原生

深入理解 Mocha 测试框架：从零实现一个 Mocha

前言什么是自动化测试自动化测试在很多团队中都是Devops环节中很难执行起来的一个环节，主要原因在于测试代码的编写工作很难抽象，99%的场景都需要和业务强绑定，而且写测试代码的编写工作量往往比编写实际业务代码的工作量更多。在一些很多业务场景中投入产出比很低，适合写自动化测试的应该是那些中长期业务以及一些诸如组件一样的基础库。自动化测试是个比较大的概念，其中分类也比较多，比如单元测试，端对端测试，集

云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...

云原生

所有评论(0)

查看更多评论

CHAKMING1

@CHAKMING1

已为社区贡献1条内容