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]这种语法格式,正确的做法是从容器中第一个元素或最后一个元素开始遍历容器,直到找到该位置。

相关文章
|
2天前
|
存储 编译器 C语言
【C++】list模拟实现
本文档介绍了C++ STL中`list`容器的模拟实现,包括`ListNode`节点类、迭代器类和`list`类的详细设计。`ListNode`模板类存储数据并维护前后指针;`ListIterator`是一个复杂的模板类,提供解引用、自增/自减以及比较操作。`list`类包含了链表的各种操作,如插入、删除、访问元素等,并使用迭代器作为访问接口。实现中,迭代器不再是简单的指针,而是拥有完整功能的对象。此外,文档还提到了迭代器的实现对C++语法的特殊处理,使得`it-&gt;_val`的写法成为可能。文章通过分步骤展示`list`的各个组件的实现,帮助读者深入理解STL容器的内部工作原理。
|
2天前
|
算法 搜索推荐 C++
【C++】list的使用(下)
`C++` 中 `std::list` 的 `merge()`、`sort()` 和 `reverse()` 操作: - `merge(x)` 和 `merge(x, comp)`: 合并两个已排序的`list`,将`x`的元素按顺序插入当前`list`,`x`清空。比较可自定义。 - `sort()` 和 `sort(comp)`: 对`list`元素排序,保持等价元素相对顺序。内置排序基于稳定排序算法,速度较慢。 -reverse(): 反转`list`中元素的顺序。 这些操作不涉及元素构造/销毁,直接移动元素。注意,`sort()`不适合`std::list`,因链表结构不利于快速排序
|
2天前
|
C++ 容器
【C++】list的使用(下)
这篇博客探讨了C++ STL中`list`容器的几个关键操作,包括`splice()`、`remove()`、`remove_if()`和`unique()`。`splice()`允许高效地合并或移动`list`中的元素,无需构造或销毁。`remove()`根据值删除元素,而`remove_if()`则基于谓词移除元素。`unique()`则去除连续重复的元素,可选地使用自定义比较函数。每个操作都附带了代码示例以说明其用法。
|
2天前
|
编译器 C++ 容器
【C++】list的使用(上)
迭代器在STL中统一了访问接口,如`list`的`begin()`和`end()`。示例展示了如何使用正向和反向迭代器遍历`list`。注意`list`的迭代器不支持加减操作,只能用`++`和`--`。容器的`empty()`和`size()`用于检查状态和获取元素数。`front()`和`back()`访问首尾元素,`assign()`重载函数用于替换内容,`push_*/pop_*`管理两端元素,`insert()`插入元素,`erase()`删除元素,`resize()`调整大小,`clear()`清空容器。这些接口与`vector`和`string`类似,方便使用。
|
2天前
|
C语言 C++ 开发者
C++基础知识(一:命名空间的各种使用方法)
C++在C的基础上引入了更多的元素,例如类,类的私密性要比C中的结构体更加优秀,引用,重载,命名空间,以及STL库,模板编程和更多的函数,在面向对象的编程上更加高效。C语言的优势则是更加底层,编译速度会更快,在编写内核时大多数都是C语言去写。 在C++中,命名空间(Namespace)是一种组织代码的方式,主要用于解决全局变量、函数或类的命名冲突问题。命名空间提供了一种封装机制,允许开发者将相关的类、函数、变量等放在一个逻辑上封闭的区域中,这样相同的名字在不同的命名空间中可以共存,而不会相互干扰。
|
2天前
|
存储 编译器 C语言
【C++】list的使用(上)
**C++ STL的list是一个基于双向循环链表的容器,支持常数时间内插入和删除,但不支持随机访问。默认构造函数、填充构造、迭代器范围构造和拷贝构造提供多种初始化方式。析构函数自动释放内存,赋值运算符重载用于内容替换。示例代码展示了构造和赋值操作。**
|
2天前
|
存储 算法 数据处理
【C++】STL简介
**STL是C++标准库的关键部分,源于Alexander Stepanov的泛型编程研究。它提供了数据结构(如vector、list)和算法,是高效、通用的软件框架。STL始于惠普,后由SGI发展,现已成为C++1998标准的一部分并不断进化。它包括容器、迭代器、算法、仿函数、配接器和分配器六大组件,带来高效性、通用性和可扩展性,但也存在性能开销和学习难度。学习STL涉及理解底层数据结构、用法、实现和实践。推荐[cplusplus.com](https://cplusplus.com)作为学习资源。**
|
2天前
|
C++
C++基础知识(二:引用和new delete)
引用是C++中的一种复合类型,它是某个已存在变量的别名,也就是说引用不是独立的实体,它只是为已存在的变量取了一个新名字。一旦引用被初始化为某个变量,就不能改变引用到另一个变量。引用的主要用途包括函数参数传递、操作符重载等,它可以避免复制大对象的开销,并且使得代码更加直观易读。
|
2天前
|
算法 编译器 C++
C++基础知识(三:哑元和内联函数和函数重载)
在C++编程中,"哑元"这个术语虽然不常用,但可以理解为在函数定义或调用中使用的没有实际功能、仅作为占位符的参数。这种做法多见于模板编程或者为了匹配函数签名等场景。例如,在实现某些通用算法时,可能需要一个特定数量的参数来满足编译器要求,即使在特定情况下某些参数并不参与计算,这些参数就可以被视为哑元。
|
2天前
|
C++
C++基础知识(四:类的学习)
类指的就是对同一类对象,把所有的属性都封装起来,你也可以把类看成一个高级版的结构体。

热门文章

最新文章