C++基础知识(八:STL标准库(Vectors和list))

简介: C++ STL (Standard Template Library标准模板库) 是通用类模板和算法的集合,它提供给程序员一些标准的数据结构的实现如 queues(队列), lists(链表), 和 stacks(栈)等.STL容器的提供是为了让开发者可以更高效率的去开发,同时我们应该也需要知道他们的底层实现,这样在出现错误的时候我们才知道一些原因,才可以更好的去解决问题。


目录

【1】Vectors容器

【2】list容器


C++ STL (Standard Template Library标准模板库) 是通用类模板和算法的集合,它提供给程序员一些标准的数据结构的实现如 queues(队列), lists(链表), 和 stacks(栈)等.

STL容器的提供是为了让开发者可以更高效率的去开发,同时我们应该也需要知道他们的底层实现,这样在出现错误的时候我们才知道一些原因,才可以更好的去解决问题。

C++ STL 提供给程序员以下三类数据结构的实现:

  • 顺序结构  C++ Vectors  
  • C++ Lists  
  • C++ Double-Ended Queues
  • 容器适配器  C++ Stacks  
  • C++ Queues  
  • C++ Priority Queues
  • 联合容器  C++ Bitsets  
  • C++ Maps  
  • C++ Multimaps  
  • C++ Sets  
  • C++ Multisets

【1】Vectors容器

vector的行为和数组类似,可以理解为顺序表

vector不需要判满,动态分配内存:如果存入新的数据,会再开辟一片更大的空间,把原来的内容拷贝过去

image.gif 编辑

begin和end成员函数,返回起始位置和结尾位置的迭代器

front和back函数,返回起始位置和结尾位置的引用

at(idx)      传回索引idx所指的数据,如果idx越界,抛出out_of_range。
back()       返回最后一个原始,不检查这个数据是否存在。
front()      返回第一个元素。
swap()      交换两个Vector。
push_back()     在Vector最后添加一个元素。
pop_back()      它从向量中删除最后一个元素。
empty()    判断Vector是否为空(返回true时为空)
insert()     它将在指定位置插入新元素。
erase()     删除指定的元素。
resize()     它修改向量的大小。
clear()      它从向量中删除所有元素。
size()        返回Vector元素数量的大小。
capacity() 返回vector所能容纳的元素数量(在不重新分配内存的情况下)
assign()    它将新值分配给向量。
operator=()      它将新值分配给向量容器。
operator[]()     它访问指定的元素。
end()        返回最末元素的迭代器(实指向最末元素的下一个位置)
emplace()        它将在位置pos之前插入一个新元素。
emplace_back()      它在末尾插入一个新元素。
rend()       它指向向量的第一个元素之前的元素。
rbegin()    它指向向量的最后一个元素。
begin()     返回第一个元素的迭代器。
max_size()       返回Vector所能容纳元素的最大数量(上限)。
cend()      它指向量中的last-last-element。
cbegin()   它指向量的第一个元素。
crbegin()  它指的是向量的最后一个字符。
crend()     它指的是向量的第一个元素之前的元素。
data()       它将向量的数据写入数组。
shrink_to_fit() 它减少了容量并使它等于向量的大小。

image.gif

找指定位置的迭代器:

由于容器类,只提供了找起始位置和结束位置的迭代器,所以找指定位置的迭代器,只能在已有迭代器的位置上自增,和指针的行为类似,访问元素需要解引用,但是不能和指针类型强转

容器名<数据类型> ::iterator  迭代器名;

vector会二倍扩容(代码中有详细注释)

【2】list容器

STL list 容器,又称双向链表容器,即该容器的底层是以双向链表的形式实现的。这意味着,list 容器中的元素可以分散存储在内存空间里,而不是必须存储在一整块连续的内存空间中。

1. begin()  
返回指向容器中第一个元素的双向迭代器。
2. end()  
返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。
3. rbegin() 
返回指向最后一个元素的反向双向迭代器。
4. rend() 
返回指向第一个元素所在位置前一个位置的反向双向迭代器。
5. cbegin() 
和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
6. cend() 
和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
7. crbegin()  
和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
8. crend()  
和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
9. empty()  
判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
10. size()  
返回当前容器实际包含的元素个数。
11. max_size()  
返回容器所能包含元素个数的最大值。这通常是一个很大的值,一般是 232-1,所以我们很少会用到这个函数。
12. front() 
返回第一个元素的引用。
13. back()  
返回最后一个元素的引用。
14. assign()  
用新元素替换容器中原有内容。
15. emplace_front() 
在容器头部生成一个元素。该函数和 push_front() 的功能相同,但效率更高。
16. push_front()  
在容器头部插入一个元素。
17. pop_front() 
删除容器头部的一个元素。
18. emplace_back()  
在容器尾部直接生成一个元素。该函数和 push_back() 的功能相同,但效率更高。
19. push_back() 
在容器尾部插入一个元素。
20. pop_back()  
删除容器尾部的一个元素。
21. emplace() 
在容器中的指定位置插入元素。该函数和 insert() 功能相同,但效率更高。
22. insert()  
在容器中的指定位置插入元素。
23. erase() 
删除容器中一个或某区域内的元素。
24. swap()  
交换两个容器中的元素,必须保证这两个容器中存储的元素类型是相同的。
25. resize()  
调整容器的大小。
26. clear() 
删除容器存储的所有元素。
27. splice()  
将一个 list 容器中的元素插入到另一个容器的指定位置。
28. remove(val)
删除容器中所有等于 val 的元素。
29. remove_if() 
删除容器中满足条件的元素。
30. unique()  
删除容器中相邻的重复元素,只保留一个。
31. merge() 
合并两个事先已排好序的 list 容器,并且合并之后的 list 容器依然是有序的。
32. sort()  
通过更改容器中元素的位置,将它们进行排序。
33. reverse() 
反转容器中元素的顺序。1

image.gif

由此可以理解,list 容器中各个元素的前后顺序是靠指针来维系的,每个元素都配备了 2 个指针,分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为 null,因为它前面没有元素;同样,尾部元素的后向指针也总为 null。

image.gif 编辑

这大概就是双向链表的样子,正常的链表只有一个指针指向他的下一个元素,而双向就是再单向的前提上加上一个指针,指向他前面的元素。


基于这样的存储结构,list 容器具有一些其它容器(array、vector 和 deque)所不具备的优势,即它可以在序列已知的任何位置快速插入或删除元素(时间复杂度为O(1))。并且在 list 容器中移动元素,也比其它容器的效率高。


使用 list 容器的缺点是,它不能像 array 和 vector 那样,通过位置直接访问元素。举个例子,如果要访问 list 容器中的第 6 个元素,它不支持容器对象名[6]这种语法格式,正确的做法是从容器中第一个元素或最后一个元素开始遍历容器,直到找到该位置。

相关文章
|
4月前
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
108 2
|
4月前
|
存储 算法 C++
【c++丨STL】map/multimap的使用
本文详细介绍了STL关联式容器中的`map`和`multimap`的使用方法。`map`基于红黑树实现,内部元素按键自动升序排列,存储键值对,支持通过键访问或修改值;而`multimap`允许存在重复键。文章从构造函数、迭代器、容量接口、元素访问接口、增删操作到其他操作接口全面解析了`map`的功能,并通过实例演示了如何用`map`统计字符串数组中各元素的出现次数。最后对比了`map`与`set`的区别,强调了`map`在处理键值关系时的优势。
218 73
|
4月前
|
存储 算法 C++
【c++丨STL】set/multiset的使用
本文深入解析了STL中的`set`和`multiset`容器,二者均为关联式容器,底层基于红黑树实现。`set`支持唯一性元素存储并自动排序,适用于高效查找场景;`multiset`允许重复元素。两者均具备O(logN)的插入、删除与查找复杂度。文章详细介绍了构造函数、迭代器、容量接口、增删操作(如`insert`、`erase`)、查找统计(如`find`、`count`)及`multiset`特有的区间操作(如`lower_bound`、`upper_bound`、`equal_range`)。最后预告了`map`容器的学习,其作为键值对存储的关联式容器,同样基于红黑树,具有高效操作特性。
153 3
|
5月前
|
存储 缓存 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`),全面解析它们的特点、用法
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
|
4月前
|
机器学习/深度学习 文字识别 开发者
使用OCR库Pix2Text执行p2t.recognize()时出现list index out of range的错误信息(附有Pix2Text识别图片内容和laTex公式的代码)
有时候报错并不是你代码有问题,源码出错也是很常见的情况,比如之前使用mxgraph也出现了不知名bug,最后也是修改的源码解决的。有疑问欢迎交流~ 博客不应该只有代码和解决方案,重点应该在于给出解决方案的同时分享思维模式,只有思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
5月前
|
算法 C++ 容器
模拟实现c++中的list模版
模拟实现c++中的list模版
|
5月前
|
存储 算法 C++
【c++丨STL】priority_queue(优先级队列)的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`(优先级队列)。`priority_queue`根据严格的弱排序标准设计,确保其第一个元素始终是最大元素。它底层使用堆结构实现,支持大堆和小堆,默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`,通过仿函数控制堆的类型,并调用封装容器的接口实现功能。最后,感谢大家的支持与关注。
207 1
|
5月前
|
存储 算法 C++
深入浅出 C++ STL:解锁高效编程的秘密武器
C++ 标准模板库(STL)是现代 C++ 的核心部分之一,为开发者提供了丰富的预定义数据结构和算法,极大地提升了编程效率和代码的可读性。理解和掌握 STL 对于 C++ 开发者来说至关重要。以下是对 STL 的详细介绍,涵盖其基础知识、发展历史、核心组件、重要性和学习方法。
|
5月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
1月前
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
43 0