编程之禅
0%

C++ STL标准模版库总结

发表于 更新于 分类于 阅读次数： Disqus：

STL 的组成部分

模版是C++程序设计语言的一个重要特征，STL 正是基于这一特征，STL 具有强大的功能，同时兼具良好的可扩展性。

STL 分为 3 类：Algorithm（算法）、Container（容器）和Iterator（迭代器），容器和算法通过迭代器可以进行无缝地连接。

STL 由 6 部分组成：容器(Container)、算法（Algorithm）、 迭代器（Iterator）、仿函数（Function object）、适配器（Adaptor）、空间配制器（Allocator）。

（1）容器(Container)

是一种数据结构，使用模版类实现。分为序列容器：vector, list, ,forward_list, deque, array 和关联容器：map, set，及其它们的变种。

（2）算法（Algorithm）

用来操作容器中数据的模版函数：例如 sort 可以用来对支持随机访问的容器进行排序，例如：vector,array,deque 和普通数组。find 可以搜索容器内的元素，只要容器支持迭代器和容器元素支持 “==” 运算符。

（3）迭代器（Iterator）

提供了访问容器元素的方法，它的功能类似于指针，支持 ++，–，-> , * 等运算符，它封装了指针，提供了比指针更强大的功能。迭代器也可以指那些定义了operator*()运算符以及类似于指针操作运算符的对象。

（4）仿函数（Function object）

定义了operator() 运算符的类或结构体。例如，以下函数就是仿函数，也叫函数对象。

等于：equal_to<T>
不等于：not_equal_to<T>
大于：greater<T>
大于等于：greater_equal<T>
小于：less<T>
小于等于：less_equal<T>

（5）适配器（Adaptor）

封装了一些基本的容器，使之具备了某些特性的新容器，比如把deque封装一下变为一个具有stack功能的数据结构。得到的数据结构就叫适配器。STL 最常用的适配器是 stack, queue 和 priority_queue。适配器本质上还是容器，只不过大量使用已经写好的其它容器的代码，有必要的话可以添加其它代码。STL 使用的基础容器并不是固定的，可以根据实际情况选择。

容器适配器 基础容器筛选条件 默认使用的基础容器
stack 需要支持的成员函数： empty() ，size()， back()， push_back()， pop_back()，满足条件的基础容器有 vector、deque、list。 deque
queue 需要支持的成员函数：empty()，size()，front()，back()，push_back()，pop_front()，满足条件的基础容器：deque, list deque
priority_queue 需要支持的成员函数：empty()，size()，front()，push_back()，pop_back()，满足条件的基础容器：vector, deque vector

（6）空间配制器（Allocator）

为 STL 容器分配空间的系统，主要包括两部分：

  • 对象的创建与销毁；

  • 内存的获取与释放。

STL 常用容器及其实现原理

顺序容器

容器类型 实现原理 时间复杂度
vector 动态数组，元素在内存中连续存放，在尾端增删元素具有较佳的性能。 随机存取：O(1)，插入：O(n)，删除：O(n)
deque 双向队列。所有适用于vector的操作都适用于deque，在两端增删元素具有较佳的性能。随机存取任何元素在常数时间内完成，仅次于vector，因为 deque底层是由数段内存组成，每一段的内存地址是连续的。 随机存取：O(1)，插入：O(n)，删除：O(n)
list 双向链表，元素在内存中不连续存放。 随机存取：O(n)，插入：O(1)，删除，O(1)
forward_list 单向链表，元素在内存中不连续存放。 随机存取：O(n)，插入：O(1)，删除，O(1)

关联容器

关联容器主要有：map，set

根据关键字是否可重复：multiset，multimap，上述容器的底层实现都是红黑树，插入，查找，删除的时间复杂度都是O(lgn)

元素是否有序又可细分为：unordered_set，unordered_map，上述容器的底层实现是哈希表，插入，查找，删除的平均时间复杂度是O(1)，最坏情况下时间复杂度是O(n)

容器类型 关键字是否可重复，元素是否有序
map 不可重复，升序
set 不可重复，升序
multiset 可重复，升序
multimap 可重复，升序
unordered_set 不可重复，无序
unordered_map 不可重复，无序
unordered_multiset 可重复，无序
unordered_multimap 可重复，无序

容器适配器

容器类型 底层实现 时间复杂度
stack 栈，dqeue 入栈和弹栈：O(1)
queue 队列，dqeue 入队和出队：O(1)
priority_queue 优先队列，vector 入队：O(n)，出队：O(1)

STL 空间配置器

三种内存分配方式

静态存储区分配：内存空间在编译阶段就已确定，如全局变量，静态变量等。

栈空间分配：程序运行期间，函数开始时自动在栈上预留足够的空间(栈帧)，函数结束后自动释放。如：局部变量。

堆空间分配：程序运行期间，使用 malloc 或 new 在堆空间为对象分配空间，使用 free 或 delete释放内存，这部分空间需要程序员手动管理内存，如果一个持续运行的程序分配了大量的堆内存，没有及时释放，就可能造成内存泄漏。

举个例子：Test 是一个类，Test test(); 和 Test *p = new Test; 对于前者，如果 test 位于函数内，那么它直接通过调用构造函数来构造对象。对于后者，则先使用 new 分配空间，然后调用构造函数。关于释放，前者是自动释放，后者需要使用 delete 来手动释放。

STL 空间配置器

关于内存分配，STL 完全可以使用 new 或 malloc 来分配内存空间，但是 new 和 malloc 效率低还容易产生内存碎片。为了最大化提升效率，SGI STL采取了一定的措施，采用了更加高效复杂的空间分配策略。在SGI STL中，将对象的构造切分开来，分成空间配置和对象构造两部分。SGI STL 采用两级空间配置策略，一级主要考虑大块内存空间的分配，使用malloc 和 free 实现。二级主要考虑小块内存的分配，这样就大大减少了 malloc 的次数，提高了运行效率。使用 malloc 申请到的一大块内存构成一个内存池，使用链表free_list来维护。free_list通过union结构实现，空闲的内存块互相挂接在一块，内存块一旦被使用，则被从链表中剔除，易于维护。

内存配置操作: 通过allocate()实现
内存释放操作: 通过deallocate()实现
对象构造操作: 通过construct()实现
对象释放操作: 通过destroy()实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <memory>

using namespace std;

class Test{
int num;
public:
    Test(int _num):num(_num){
        cout<<"Test is construct,num = " <<num<<endl;
    }

    ~Test(){
        cout << "Test is destroy" << endl;
    }
};

int main(){
    allocator<Test> alloc;
    Test *p = alloc.allocate(5);    // 分配存放 5 个T对象的内存空间，不调用构造函数
    alloc.construct(p,12);          // 构造第一个对象
    alloc.construct(p+1, 12);       // 构造第二个对象

    alloc.destroy(p);               // 调用第一个对象的析构函数(不释放内存)
    alloc.destroy(p + 1);           // 调用第二个对象的析构函数(不释放内存)

    alloc.deallocate(p,5);          // 释放占用 5 个Test对象大小的内存空间
    return 0;
}
1
2
3
4
5
6
$ g++ allocator.cpp -o allocator
$ ./allocator 
Test is construct,num = 12
Test is construct,num = 12
Test is destroy
Test is destroy

迭代器

什么是迭代器

迭代器是类模版，本质上封装了原生指针，是指针概念的一种提升，提供了比指针更高级的行为。重载了指针的一些操作符，例如：++, –, *, ->。迭代器返回对象的引用。

迭代器的作用

用于访问顺序容器和关联容器内的元素

通过非const迭代器还可以修改其指向的元素

迭代器产生原因

Iterator类的访问方式就是把不同容器的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到操作容器元素的目的。

迭代器失效问题

迭代器失效主要原因为：erase和insert

对于顺序容器vector，deque来说，使用erase后，后边的每个元素的迭代器都会失效，后边每个元素都往前移动一位，erase返回下一个有效的迭代器。在中间插入元素时，会使插入位置之后的元素的迭代器失效，不能使用迭代器在循环中插入。

对于关联容器map, set及其变种，因为底层使用红黑树，使用erase 删除一个元素后不会改变其它元素的迭代器，在删除之前记录下一个元素的迭代器即可。 插入不会使得任何元素的迭代器失效。

对于list来说，它使用了不连续分配的内存，并且它的 erase 方法也会返回下一个有效的迭代器，因此上面两种方法都可以使用。插入不会改变其它元素的迭代器。

resize 和 reserve 区别

先明白两个概念：capacity 和 size

某些容器为了支持动态扩充，在初始化时会申请一段连续的内存，这个容量用capacity表示，表示该容器此时最大能容纳的对象个数，此时是无法通过下标访问的，因为还没有创建对象。创建完对象后，才可以用下标访问，实际创建对象的数量用 size 表示。

区别

resize 即修改了capacity 的大小，也修改了 size 的大小。带两个参数，一个表示容器的大小，一个表示构造函数参数(如果有的话)。

reserve 只修改capacity的大小，相当于给容器扩容。带一个参数，表示容器的大小。

共同点

两者都保证了 vector 的空间最少达到它的参数所指定的大小。例如给定参数 size=10，则大于等于10的下标都无效。

STL 容器动态链接可以产生的问题

可能产生的问题

容器是一种动态分配内存空间的一个变量。在一般的程序函数里，参数传递容器指针都是可以正常运行的，而在动态链接库函数内部使用容器也是没有问题的，但是给动态库函数传递容器的对象本身，则会出现内存堆栈破坏的问题。

产生问题的原因

容器和动态链接库相互支持不够好，动态链接库函数中使用容器时，参数中只能传递容器的引用，并且要保证容器的大小不能超出初始大小，否则导致容器自动重新分配，就会出现内存堆栈破坏问题。

push_back 和 emplace_back 的区别

使用push_back()插入元素， 需要先构造临时对象，再将这个对象拷贝到容器的末尾，而emplace_back()则直接在容器的末尾构造对象，这样就省去了拷贝的过程。