【STL】顺序容器与容器适配器

简介: 【STL】顺序容器与容器适配器

1顺序容器概述

给出以下顺序容器表:

顺序容器类型 作用
vector 可变大小的数组,支持快速访问,除尾元素的插入或者删除很慢
string 与vector相似,只不过专门用来存字符
list 双向链表。只能双向顺序访问,插入删除的效率都很高
forward_list 单向链表。只能单向顺序访问,插入删除的效率都很高
deque 双端队列 。 支持快速随机访问。在头尾位置插入删除很快,中间则很慢
array 固定大小的数组。支持快速随机访问。不能删除和添加元素

由于前面已经对vector、string、list有了较为详细的讲解,下面只介绍部分容器:

1.1array

除了array之外,其他容器都支持灵活的内存管理方式。根据实际情况可以自由调节容器的容量大小。这使得array的引用场景受到了限制。因为一旦初始化了array的大小,后面就不能在被改变了。

虽然看起来array的限制很多,但是array也因此变得更加安全,也更容易使用

1.2forward_list

forward_list和array都是新C++标准增加的类型。forward_list的设计目标是达到与最好的手写的单向链表数据结构相当的性能。因此,forward_list没有size操作,因为保存或者计算其大小就会比手写链表多出时间或者空间上面的开销。

值得注意的是,由于forward_list是单向链表,也就不具备反向遍历的功能,也就没有反向迭代器。相比于list,其删除节点的操作也会稍微复杂一些。

1.3deque

deque是一个更为复杂的数据结构。与string和vecotr类似,deque支持快速的随机访问,在中间位置添加或者删除元素的代价可能很高。当时与string和vector不同的是,deque首尾插入或者删除的效率很高,这一点相当于list或者forward_list。我们可以把deque看成是首插元素高效的vector。

2.如何确定使用哪种顺序容器呢?

以下是选择使用顺序容器的参考:

1.如果没有其他的理由,那就优先考虑vector。

2.如果你的程序有很多的小元素,且不想要产生额外的空间开销,那就不要用list和forward_list.

3.要支持快速随机访问,用array或者vector。

4.如果程序要求频繁的在容器中间插入或者删除元素,那就使用list或者forward_list.

5.如果程序要求在首尾插入或者删除元素,但是不在中间插入删除元素,那就选择deque。

6.如果只是在读取输入的时候需要在中间插入元素,可以考虑读取时用list或者forward_list,之后再拷贝到vector容器中。

3.容器适配器的概念

除了顺序容器外,标准库还定义了三个顺序容器适配器:stack、queue和priority_queue。适配器是标准库中的一个概念,容器、迭代器、函数都有适配器。适配器可以使某种事物的行为看起来像是另外一回事。一个容器适配器用一个已有的容器类型,使其行为看上去像一种不同的类型。例如,stack适配器可以接受vector类型,在vector的基础上重新定义其成员函数,使得整体看上去是一个stack。有点借鸡生蛋的意思。所有的适配器都要有添加删除以及访问尾元素的能力。

不同的适配器可以接受的容器类型会有区别。例如stack需要有直接访问尾元素的能力,就不能构造于forward_list之上。queue要求弹出首元素,就不能构造于vector之上。priority_queue要求随机访问的能力,就不能构造于list和forward_list之上。

4.如何定义适配器呢?

每一个适配器都应该要有两个构造函数:默认构造创建一个空对象。接受一个容器的构造函数拷贝该容器来初始化适配器。

stack和queue默认是用deque实现的,priority_queue默认用vector实现的。

我们可以显示的指定适配器用什么类型的容器去构建

  stack<int> st1;//用deque构建
  stack<int,vector<int>> st2;//用vecor<int> 构建
  stack<string, vector<string>>s3;//用string构建

其它适配器的的用法也跟上面类似。

相关文章
|
19天前
|
存储 算法 编译器
8.STL中Vector容器的常见操作(附习题)
8.STL中Vector容器的常见操作(附习题)
|
6天前
|
算法 前端开发 Linux
【常用技巧】C++ STL容器操作:6种常用场景算法
STL在Linux C++中使用的非常普遍,掌握并合适的使用各种容器至关重要!
33 10
|
25天前
|
存储 算法 C语言
从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)(下)
从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)
31 2
|
30天前
|
存储 C++ 容器
黑马c++ STL部分 笔记(7) list容器
黑马c++ STL部分 笔记(7) list容器
|
30天前
|
C++ 容器
黑马c++ STL部分 笔记(5) stack容器
黑马c++ STL部分 笔记(5) stack容器
|
25天前
|
算法 C语言 C++
从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)(中)
从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)
21 0
|
25天前
|
缓存 算法 C语言
从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)(上)
从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)
22 0
|
30天前
|
C++ 索引 容器
黑马c++ STL部分 笔记(9) map/multimap容器
黑马c++ STL部分 笔记(9) map/multimap容器
|
30天前
|
C++ 容器
黑马c++ STL部分 笔记(8) set/ multiset 容器
黑马c++ STL部分 笔记(8) set/ multiset 容器
|
30天前
|
C++ 容器
黑马c++ STL部分 笔记(6) queue 容器
黑马c++ STL部分 笔记(6) queue 容器

热门文章

最新文章