1. Toy模板网首页
  2. > Toy博客

C++STL库中的list

9月前 作者：‘(尐儍苽-℡ 分类：Toy博客 阅读(29) 违法举报

这篇具有很好参考价值的文章主要介绍了C++STL库中的list。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

C++STL库中的list,C++初阶,c++,开发语言

文章目录

  • list的介绍及使用
  • list的常用接口
  • list的模拟实现
  • list与vector的对比

一、list的介绍及使用

  • 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
  • 2. list的底层是双向带头循环链表结构，双向带头循环链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
  • 3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
  • 4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
  • 5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间
  • 开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

C++STL库中的list,C++初阶,c++,开发语言

二、list的常用接口

1.list的构造函数

default (1) 
list();explicit list (const allocator_type& alloc);

  构造一个没有元素的空容器。
fill (2) 
explicit list (size_type n, const allocator_type& alloc = allocator_type());         

list (size_type n, const value_type& val, const allocator_type& alloc = allocator_type());

构造一个包含n个元素的容器。每个元素都是val。
range (3) 
template <class InputIterator>  
list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());

构造一个包含与范围[first，last]一样多的元素的容器，每个元素都以相同的顺序从该范围中的相应元素构造而成。
copy (4) 
list (const list& x);
list (const list& x, const allocator_type& alloc);

以相同的顺序构造一个包含x中每个元素的副本的容器。
move (5) 
list (list&& x);list (list&& x, const allocator_type& alloc);

 右值引用构造
initializer list (6) 
list (initializer_list<value_type> il, const allocator_type& alloc = allocator_type());

构造一个通过初始化列表的方式

 
#include <iostream>
#include <list>

int main()
{
    std::list<int> l1;                         // 构造空的l1
    std::list<int> l2(4, 100);                 // l2中放4个值为100的元素
    std::list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左闭右开的区间构造l3
    std::list<int> l4(l3);                    // 用l3拷贝构造l4

    // 以数组为迭代器区间构造l5
    int array[] = { 16,2,77,29 };
    std::list<int> l5(array, array + sizeof(array) / sizeof(int));

    // 列表格式初始化C++11
    std::list<int> l6{ 1,2,3,4,5 };

    // 用迭代器方式打印l5中的元素
    std::list<int>::iterator it = l5.begin();
    while (it != l5.end())
    {
        std::cout << *it << " ";
        ++it;
    }
    
    std::cout << std::endl;

    // C++11范围for的方式遍历
    for (auto& e : l5)
        std::cout << e << " ";

    std::cout << std::endl;


	return 0;
}

2.list iterator的使用

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

C++STL库中的list,C++初阶,c++,开发语言

【注意】
1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动 
#include <iostream>
#include <list>

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

	for (auto it = lt.begin(); it != lt.end(); it++)
		std::cout << *it << " ";
	std::cout << std::endl;

	for (auto x : lt)
		std::cout << x << " ";
	std::cout << std::endl;
	return 0;
}

3.list相关容量操作

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

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

	std::cout << lt.size() << std::endl;
	std::cout << lt.empty() << std::endl;
	return 0;
}

4.list相关访问操作

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

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

	std::cout << lt.front() << std::endl;
	std::cout << lt.back() << std::endl;
	return 0;
}

5.list相关修改操作

函数声明                                                                                接口说明
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中的有效元素 
#include <iostream>
#include <vector>
#include <list>

// list迭代器的使用
// 注意：遍历链表只能用迭代器和范围for
void PrintList(const std::list<int>& l)
{
    // 注意这里调用的是list的 begin() const，返回list的const_iterator对象
    for (std::list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
    {
        std::cout << *it << " ";
        // *it = 10; 编译不通过
    }

    std::cout << std::endl;
}

// list插入和删除
// push_back/pop_back/push_front/pop_front
void TestList3()
{
    int array[] = { 1, 2, 3 };
    std::list<int> L(array, array + sizeof(array) / sizeof(array[0]));

    // 在list的尾部插入4，头部插入0
    L.push_back(4);
    L.push_front(0);
    PrintList(L);

    // 删除list尾部节点和头部节点
    L.pop_back();
    L.pop_front();
    PrintList(L);
}

// insert /erase 
void TestList4()
{
    int array1[] = { 1, 2, 3 };
    std::list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));

    // 获取链表中第二个节点
    auto pos = ++L.begin();
    std::cout << *pos << std::endl;

    // 在pos前插入值为4的元素
    L.insert(pos, 4);
    PrintList(L);

    // 在pos前插入5个值为5的元素
    L.insert(pos, 5, 5);
    PrintList(L);

    // 在pos前插入[v.begin(), v.end)区间中的元素
    std::vector<int> v{ 7, 8, 9 };
    L.insert(pos, v.begin(), v.end());
    PrintList(L);

    // 删除pos位置上的元素
    L.erase(pos);
    PrintList(L);

    // 删除list中[begin, end)区间中的元素，即删除list中的所有元素
    L.erase(L.begin(), L.end());
    PrintList(L);
}

// resize/swap/clear
void TestList5()
{
    // 用数组来构造list
    int array1[] = { 1, 2, 3 };
    std::list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
    PrintList(l1);

    // 交换l1和l2中的元素
    std::list<int> l2;
    l1.swap(l2);
    PrintList(l1);
    PrintList(l2);

    // 将l2中的元素清空
    l2.clear();
    std::cout << l2.size() << std::endl;
}

int main()
{
    TestList3();
    TestList4();
    TestList5();
	return 0;
}

6.list容器相关独特操作

 splice                                     将元素从一个链表转移到另一个链表（公共成员函数）



 remove                                  删除具有特定值的元素（公共成员函数）

remove_if                                 删除满足条件的元素（公共成员函数模板）

unique                                                  删除重复值（公共成员函数）

mergemerge                                   合并已排序的列表（公共成员功能）


sort                                                对容器中的元素排序（公共成员函数）

reverse                                     颠倒元素的顺序（公共成员函数）

三、list的模拟实现

1.list的节点结构

template<class T>
	struct list_node
	{
		T _data;//数据域
		list_node<T>* _prev;//前驱指针
		list_node<T>* _next;//后继指针

		list_node(const T& val=T())
			:_data(val)
			,_prev(nullptr)
			,_next(nullptr)
		{}
	};

2.list的常用接口模拟

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;

		const_iterator begin()const;

		const_iterator end()const;

		iterator begin();

		iterator end();

		list();
        template<class InputIterator>
        list(InputIterator first,InputIterator last);
        list(const list<T>& lt);
        list<T>& operator=(list<T> lt);
        ~list();
        
        size_t size();
        bool empty();

		void push_back(const T& val);

		void push_front(const T& val);

		iterator insert(iterator pos, const T& x);

		iterator erase(iterator pos);

		void pop_back();

		void pop_front();
        
        void clear();
	private:
		Node* _head;
	};

3.list的迭代器

1.迭代器相关结构组成

C++STL库中的list,C++初阶,c++,开发语言

	// 像指针一样的对象
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> iterator;

		typedef bidirectional_iterator_tag iterator_category;
		typedef T value_type;
		typedef Ptr pointer;
		typedef Ref reference;
		typedef ptrdiff_t difference_type;


		Node* _node;

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

		bool operator!=(const iterator& it) const;

		bool operator==(const iterator& it) const;

		Ref operator*();
 
		Ptr operator->();

		iterator& operator++();

		iterator operator++(int);
		
		iterator& operator--();

		iterator operator--(int);
	};

2.迭代器结构实现

template<class T,class Ref,class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> iterator;

		typedef  std::bidirectional_iterator_tag iterator_category;
		typedef T value_type;
		typedef Ptr pointer;
		typedef Ref reference;
		typedef ptrdiff_t difference_type;

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

		Ref operator*()
		{
			return _node->_data;
		}

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

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

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

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

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

4.list的成员函数

1.list的构造函数

// 默认构造函数
list()
{
    // 构造头节点，自己指向自己
    _head = new Node;
    _head->_prev = _head;
    _head->_next = _head;
}

// 用迭代器区间初始化[first,last)
template<class InputIterator>
list(InputIterator first, InputIterator last)
    :_head(new Node) 
{
	_head->_prev = _head;
	_head->_next = _head;
        

	while (first != last)
	{
		push_back(*first);
		first++;
	}
}

2.list的拷贝构造函数

//拷贝构造函数（深拷贝）
// lt2(lt1)
list(const list<T>& lt)
    :_head(new Node) 
{
    _head->_prev = _head;
    _head->_next = _head;
 
    for (const auto& e : lt)
    {
    	push_back(e);
    }
}

// 拷贝构造函数（深拷贝）
list(const list<T>& lt)
    :_head(new Node) 
{
    _head->_prev = _head;
    _head->_next = _head;

	list<T> tmp(lt.begin(), lt.end());
	std::swap(_head, tmp._head); 
}

3.list的赋值运算符重载函数

//深拷贝
list<T>& operator=(const list<T>& lt)
{
    if (this != &lt) 
    {

        clear();


        for (const auto& e : lt)
        {
            push_back(e);
        }
    }

    return *this; 
}


list<T>& operator=(list<T> lt) 
{
    std::swap(_head, lt._head);

    return *this; 
}

4.list的析构函数

~list()
{
	//方法一
    Node* cur = _head->_next;

    while (cur != _head) 
    {
        Node* next = cur->_next; 

        delete cur; 

        cur = next;
    }

    delete _head; 
    _head = nullptr;
	

    //方法二：复用 clear 函数的代码

    clear();
    delete _head;
    _head = nullptr;
}

5.list其他相关结构函数

		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 newnode cur
			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);
		}

5.list的迭代器失效

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

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

int main()
{
	testlistiterator1();
	return 0;
}

四、list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

C++STL库中的list,C++初阶,c++,开发语言文章来源地址https://www.toymoban.com/news/detail-612892.html

到了这里，关于C++STL库中的list的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【C++初阶10-stack&queue】STL中的栈和队列（附优先级队列

    本期分享：STL中的栈和队列。 在数据结构初阶时，我们已经学习这来那个两种数据结构，如今来看STL中的，不过是更加标准化。而实现起来，会简单得超乎你想象！ 文中不足错漏之处望请斧正！ STL中的栈和队列是容器适配器。容器适配器是对某种已有容器的再次封装。 比如

    2024年02月06日
    浏览(43)
  • 【C++初阶】8. STL初阶 + String类

    【C++初阶】8. STL初阶 + String类

    STL(standard template libaray-标准模板库)：是C++标准库的重要组成部分，不仅是一个可复用的组件库，而且是一个包罗 数据结构与算法的软件框架 。 原始版本 Alexander Stepanov、Meng Lee 在 惠普实验室 完成的原始版本，本着开源精神，他们声明允许任何人任意运用、拷贝、修改、传播

    2023年04月08日
    浏览(44)
  • 【数据结构初阶】五、线性表中的栈（C语言 -- 顺序表实现栈）

    【数据结构初阶】五、线性表中的栈（C语言 -- 顺序表实现栈）

    ========================================================================= 相关代码gitee自取 ： C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 ： 【数据结构初阶】四、线性表里的链表（带头+双向+循环 链表 -- C语言实现）_高高的胖子的博客

    2024年02月08日
    浏览(42)
  • 【数据结构初阶】六、线性表中的队列（C语言 -- 链式结构实现队列）

    【数据结构初阶】六、线性表中的队列（C语言 -- 链式结构实现队列）

    ========================================================================= 相关代码gitee自取 ： C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 ： 【数据结构初阶】五、线性表中的栈（C语言 -- 顺序表实现栈）_高高的胖子的博客-CSDN博客  

    2024年02月08日
    浏览(41)

  • C 语言实现 C# 中的 List 泛型列表

    //下面是一个简单的用 C 语言实现 C# 中的 List 泛型列表的示例代码，代码中有详细的注释，帮助你理解代码的实现细节。 人工智能生成的. 以后可以用人工智能实现很多代码了. 简单的活让它来干.

    2024年02月10日
    浏览(45)
  • [C++]模板初阶与STL简介

    [C++]模板初阶与STL简介

    目录 模板初阶与STL简介：：                                         1.泛型编程                                         2.函数模板                                         3.类模板                                         4.什么是STL                  

    2023年04月25日
    浏览(33)
  • C++初阶之模板和STL简介

    C++初阶之模板和STL简介

    泛型编程是一种编程范式，旨在实现可重用、通用和高度抽象的代码。它允许程序员编写与数据类型无关的代码，以便在不同的数据类型上进行操作，而无需为每种数据类型重复编写代码。 在传统的编程中，通常需要为每种数据类型编写特定的代码。例如，如果要实现一个排

    2024年02月16日
    浏览(39)
  • 【c++】初阶模版与STL简单介绍

    【c++】初阶模版与STL简单介绍

    🔥个人主页 ： Quitecoder 🔥 专栏 ： c++笔记仓 朋友们大家好，本篇文章介绍一下模版和对STL进行简单的介绍，后续我们进入对STL的学习！ 泛型编程是一种编程范式，它强调的是在编写代码时能够使得算法、数据结构或函数能够对各种数据类型都能工作，而 无需因数据类型的

    2024年04月09日
    浏览(46)
  • 【C++初阶】STL之学习string的用法

    【C++初阶】STL之学习string的用法

    STL是C++的标准模板库 ，里面包含了许多 算法和数据结构 ，例如我们熟悉的顺序表、链表、栈和队列以及一些常见的算法等等，编程者想使用这些就可以直接从库中调用，不必再自己造轮子了。 下面为STL内容的一张图： 接下来，我们要学习STL中的string。 string 是C++的一个类模

    2024年02月04日
    浏览(44)
  • 【C++初阶】STL详解（四）vector的模拟实现

    【C++初阶】STL详解（四）vector的模拟实现

    本专栏内容为：C++学习专栏，分为初阶和进阶两部分。 通过本专栏的深入学习，你可以了解并掌握C++。 💓博主csdn个人主页：小小unicorn ⏩专栏分类：C++ 🚚代码仓库：小小unicorn的代码仓库🚚 🌹🌹🌹关注我带你学习编程知识 注：为了防止与标准库当中的vector产生命名冲突

    2024年02月05日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包