【C++修行之道】STL(初识list、stack)

简介: 【C++修行之道】STL(初识list、stack)



一、list

1.1list的定义和结构

  • list的使用频率不高,在做题时极少遇到需要使用list的情景。
  • ist是一种双向链表容器,它是标准模板库(STL)提供的一种序列容器。
  • list容器以节点(node)的形式存储元素,并使用指针将这些节点链接在一起,形成一个链表结构。
  • list容器的定义和结构如下:
template <class T, class Allocator = std::allocator<T>>class list;

list容器模板接受两个参数:

  1. T:指定容器中存储的元素类。
  2. Allocator (可选):指定用于分配内存的分配器类型,默认为std::allocator<T>。

list容器的特点包括:

  • 双向性:每个节点都包含指向前一个节点和后一个节点的指针,因此可以在常数时间内在链表中的任意位置进行插入、删除和访问操作。
  • 动态大小: 链表的大小可以根居需要动态扩展或收缩,不需要预先指定容器的大小
  • 不连续存储:链表中的节点可以在内存中的任意位置分布,不要求连续存储因此插入和删除操作不会导致元素的移动。
  • list与其他标准序列容器(array,vector和deque)相比,list通常可以在容器内的任何位置插入、提取和移动元素。
  • list与其他标准序列容器(array,vector和deque)相比,list和forward_list(单链表实现)的主要缺点是他们不能通过位置直接访问元素;例如,要访问列表中的第五个元素,必须从已知位置(开始或结束)迭代到该位置,需要线性时间开销。
  • 存储密度低,list要使用一些额外的内容空间(next,prev)来保持与每个元素相关联(前后续的线性)的链接信息,从而导致存储小元素类型(如char,short,int等)的列表的存储密度低。

list容器提供了一系列成员函数和迭代器来操作和访问链表中的元素,包括插入、删除、访问、反转等操作。可以使用迭代器来遍历链表中的元素。

以下是一个示例,展示如何使用list容器:

#include<iostream>
#include<list>
using namespace std;
int main()
{
  list<int> myList;
  //在链表尾部插入元素
  myList.push_back(1);
  myList.push_back(2);
  myList.push_back(3);
  //在链表头不插入元素
  myList.push_front(0);
  //遍历链表并输出元素
  for (int num : myList) {
    cout << num << " ";
  }
  cout << endl;
  return 0;
}

  • 在上述示例中,我们首先创建了一个list容器myList,然后使用push_back()和push_front()函数分别在链表尾部和头部插入元素。最后,使用范围基于范围的for循环遍历链表并输出元素。
  • 需要注意的是,由于list是双向链表,因此插入和删除操作的时间复杂度是常量时间O(1),但访问和查找操作的时间复杂度是线性时间O(n),其中n是链表的大小。因此,如果需要频繁进行随机访问操作,可能更适合使用支持随机访问的容器,如vector或deque。

随机访问:begin()+idex,得到迭代器

1.2list的常用函数

list容器提供了多个常用的成员函数来操作和访问链表中的元素以下是一些常用的list函数的解释:

  1. push _back():将元素插入到链表的末尾。
  2. push front():将元素插入到链表的开头。
  3. pop back():移除链表末尾的元素。
  4. pop_front():移除链表开头的元素。
  5. size():返回链表中元素的个数。
  6. empty():检查链表是否为空。
  7. clear():清空链表中的所有元素。
  8. front():返回链表中第一个元素的引用。
  9. back():返回链表中最后一个元素的引用。
  10. begin(): 返回指向链表第一个元素的迭代器。
  11. end(): 返回指向链表末尾的下一个位置的迭代器。
  12. insert():在指定位置之前插入一个或多个元素。
  13. .erase():从链表中移除指定位置的一个或多个元素。

1.3list代码示例

在代码中,我们向myList的尾部添加了5个元素,从1到5。

int main()
{
  //创建一个List<int>对案myList
  list<int> myList;
  //向myList尾部添加元素
  for (int i = 1; i <= 5; ++i)
  {
    myList.push_back(i);
  }

然后,我们使用范围for循环遍历myList并输出其中的元素。输出结果为:1 2 3 4 5 。

// 从头到尾输出myList中的元素
  for (const auto& i : myList)cout << i << ' ';
  cout << '\n';

使用reverse函数将myList中的元素反转,并输出反转后的结果。输出为:5 4 3 2 1 。

//将myList中的元素反转
  reverse(myList.begin(), myList.end());
  for (const auto& i : myList)cout << i << ' ';
  cout << '\n';

再使用myList.begin()获取链表的第一个迭代器,然后使用++操作符将其移动到第二个元素的位置。接着,我们使用insert函数在这个位置插入元素0。输出结果为:5 0 4 3 2 1 。

//在第一个元素的后一个位置加上元素0
  myList.insert(++myList.begin(), 0);

删除链表中的一部分元素。++++myList.begin()将迭代器移动到链表的第三个元素,而--myList.end()将迭代器移动到链表的倒数第二个元素之前的位置。因此,这行代码将删除从第三个元素到倒数第二个元素之间的所有元素。

for (const auto& i : myList)cout << i << ' ';
  cout << '\n';
  myList.erase(++++myList.begin(), -- myList.end());
  //输出myList的大小
  cout << "链表大小为: " << myList.size() << '\n';
  //从头到尾输出myList中的元素
  for (const auto& i : myList)cout << i << ' ';
  cout << '\n';
int main()
{
  //创建一个List<int>对案myList
  list<int> myList;
  //向myList尾部添加元素
  for (int i = 1; i <= 5; ++i)
  {
    myList.push_back(i);
  }
  // 从头到尾输出myList中的元素
  for (const auto& i : myList)cout << i << ' ';
  cout << '\n';
  //将myList中的元素反转
  reverse(myList.begin(), myList.end());
  for (const auto& i : myList)cout << i << ' ';
  cout << '\n';
  //在第一个元素的后一个位置加上元素0
  myList.insert(++myList.begin(), 0);
  for (const auto& i : myList)cout << i << ' ';
  cout << '\n';
  myList.erase(++++myList.begin(), -- myList.end());
  //输出myList的大小
  cout << "链表大小为: " << myList.size() << '\n';
  //从头到尾输出myList中的元素
  for (const auto& i : myList)cout << i << ' ';
  cout << '\n';
}

二、stack

2.1stack的定义和结构

在C++中,stack是一个标准库容器,它提供了后进先出(LIFO, Last In First Out)的数据结构。stack容器只允许在序列的同一端(称为栈顶)进行插入和删除操作。stack没有迭代器,因此你不能像遍历其他容器(如vector或list)那样遍历stack。相反,你只能查看栈顶元素、向栈中添加元素或从栈中移除元素。

stack提供了一组函数来操作和访问元素,但它的功能相对较简单。stack的定义和结构如下 (仅作了解即可):

template <class T, class Container = deque<T>>
class stack;

T:表示存储在stack中的元素的类型

Container: 表示底层容器的类型,默认为deque。也可以使用其他容器类型,如vector或list、stack的内部实现使用了底层容器来存储元素,并且只能通过特定的函数来访问和操作元素。

stack的常用定义

//stack的定义 
stack<int>s1; //定义一个储存数据类型为int的stack容器s1 
stack<double>s2; //定义一个储存数据类型为double的stack容器s2
stack<string>s3; //定义一个储存数据类型为string的stack容器s3
stack<结构体类型>s4; //定义一个储存数据类型为结构体类型的stack容器s4
stack<int> s5[N]; //定义一个储存数据类型为int的stack容器数组,N为大小 
stack<int> s6[N]; //定义一个储存数据类型为int的stack容器数组,N为大小

2.2常用函数

stack不能遍历

函数 描述 时间复杂度
push(x) 在栈顶插入元素 x 0(1)
pop 弹出栈顶元素
0(1)
top 返回栈顶元素
0(1)
empty 检查栈是否为空
0(1)
size 返回栈中元素的个数 0(1)

小tips: 如果将一个数组的元素依次放入栈,再依次取出,则可以将数组翻转。

2.3stack代码示例

#include<iostream>
#include<stack>
using namespace std;
int main()
{
  stack<int>myStack;
  //向栈中插入元素
  myStack.push(10);
  myStack.push(20);
  myStack.push(30);
  myStack.push(40);
  //获取栈顶元素
  cout << "栈顶元素" << myStack.top() << endl;
  //弹出栈顶元素
  myStack.pop();
  //再次获取栈顶元素
  cout << "弹出一个元素后的栈顶元素" << myStack.top() << endl;
  //检查栈是否为空
  if (myStack.empty()) {
    cout << "栈为空" << endl;
  }
  else {
    cout << "栈不为空" << endl;
  }
  //获取栈的大小
  cout << "栈的大小" << myStack.size() << endl;
  return 0;
}

今天就先到这了!!!

看到这里了还不给博主扣个:

⛳️ 点赞☀️收藏 ⭐️ 关注!

你们的点赞就是博主更新最大的动力!

有问题可以评论或者私信呢秒回哦。

相关文章
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
516 2
|
缓存 算法 程序员
C++STL底层原理:探秘标准模板库的内部机制
🌟蒋星熠Jaxonic带你深入STL底层:从容器内存管理到红黑树、哈希表,剖析迭代器、算法与分配器核心机制,揭秘C++标准库的高效设计哲学与性能优化实践。
1036 3
C++STL底层原理:探秘标准模板库的内部机制
|
存储 算法 C++
【c++丨STL】map/multimap的使用
本文详细介绍了STL关联式容器中的`map`和`multimap`的使用方法。`map`基于红黑树实现,内部元素按键自动升序排列,存储键值对,支持通过键访问或修改值;而`multimap`允许存在重复键。文章从构造函数、迭代器、容量接口、元素访问接口、增删操作到其他操作接口全面解析了`map`的功能,并通过实例演示了如何用`map`统计字符串数组中各元素的出现次数。最后对比了`map`与`set`的区别,强调了`map`在处理键值关系时的优势。
1011 73
|
存储 缓存 C++
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
C++ 标准模板库(STL)提供了一组功能强大的容器类,用于存储和操作数据集合。不同的容器具有独特的特性和应用场景,因此选择合适的容器对于程序的性能和代码的可读性至关重要。对于刚接触 C++ 的开发者来说,了解这些容器的基础知识以及它们的特点是迈向高效编程的重要一步。本文将详细介绍 C++ 常用的容器,包括序列容器(`std::vector`、`std::array`、`std::list`、`std::deque`)、关联容器(`std::set`、`std::map`)和无序容器(`std::unordered_set`、`std::unordered_map`),全面解析它们的特点、用法
1199 1
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
|
存储 算法 C++
【c++丨STL】set/multiset的使用
本文深入解析了STL中的`set`和`multiset`容器,二者均为关联式容器,底层基于红黑树实现。`set`支持唯一性元素存储并自动排序,适用于高效查找场景;`multiset`允许重复元素。两者均具备O(logN)的插入、删除与查找复杂度。文章详细介绍了构造函数、迭代器、容量接口、增删操作(如`insert`、`erase`)、查找统计(如`find`、`count`)及`multiset`特有的区间操作(如`lower_bound`、`upper_bound`、`equal_range`)。最后预告了`map`容器的学习,其作为键值对存储的关联式容器,同样基于红黑树,具有高效操作特性。
886 3
|
存储 算法 C++
【c++丨STL】priority_queue(优先级队列)的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`(优先级队列)。`priority_queue`根据严格的弱排序标准设计,确保其第一个元素始终是最大元素。它底层使用堆结构实现,支持大堆和小堆,默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`,通过仿函数控制堆的类型,并调用封装容器的接口实现功能。最后,感谢大家的支持与关注。
1150 1
|
存储 算法 C++
深入浅出 C++ STL:解锁高效编程的秘密武器
C++ 标准模板库(STL)是现代 C++ 的核心部分之一,为开发者提供了丰富的预定义数据结构和算法,极大地提升了编程效率和代码的可读性。理解和掌握 STL 对于 C++ 开发者来说至关重要。以下是对 STL 的详细介绍,涵盖其基础知识、发展历史、核心组件、重要性和学习方法。
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
编译器 C++ 容器
【c++11】c++11新特性(上)(列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式)
C++11为C++带来了革命性变化,引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式,initializer_list简化了容器多元素初始化;右值引用和移动语义优化了资源管理,减少拷贝开销;类新增移动构造和移动赋值函数提升性能;lambda表达式提供匿名函数对象,增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展,提升了开发效率与程序性能。
738 12
|
编译器 C语言 C++
类和对象的简述(c++篇)
类和对象的简述(c++篇)

热门文章

最新文章