STL初步

泛型程序设计（generic programming）

设计思想

• C++语言的核心优势之一 —— 软件的重用
• C++中有两个方面体现重用:
  1. 面向对象的思想：继承和多态，标准类库
  2. 泛型程序设计的思想：
     • 模板机制
     • 标准模板库 STL

模板机制

• 将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板

• 以后不论数据结构里放的是什么对象，算法针对什么样的对象
  → 都不必重新实现数据结构，重新编写算法

标准模板库（Standard Template Library）

• 常用数据结构和算法的模板的集合
• 无需写过多的标准数据结构和算法
• 同时可获得非常高的性能

STL的基本概念

• 容器：可容纳各种数据类型的通用数据结构，是类模板
• 迭代器：可用于依次存取容器中元素，类似于指针
  • 普通的C++指针就是一种迭代器
• 算法：用来操作容器中的元素的函数模板

• sort() 来对一个数组中的数据进行排序
• find() 来搜索一个数组中的对象
  算法本身与他们操作的数据的类型无关，
  因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用

int array[100];    // 该数组就是容器，而int* 类型的指针变量就可以作为迭代器
sort(array, array+70);  // sort 算法可以作用于该容器上，对其进行排序

迭代器

• 用于指向第一类容器的元素

  • 可以读取指向元素
  • 非const迭代器可以修改指向元素

• 使用方法：

  /定义一个容器类的迭代器的方法：
  容器类名::iterator 变量名;
  容器类名::const_iterator 变量名;
  //访问一个迭代器指向的元素：
  * 迭代器变量名

• 不同容器支持的迭代器功能强弱不同→决定支持的算法

  • 只有第一类容器可以使用迭代器遍历

  • 强弱

    flowchart LR
            direction LR
            A[输入迭代器<br>只读访问<br><br>++p, p++<br>value=*p, p=p1<br>p==p1, p!=p1] --> B[输出迭代器<br>只写访问<br>*p=value, p=p1]
            B --> C[正向迭代器<br>读写 + 单向步进前进]
            C --> D[双向迭代器<br>读写 + 双向步进移动<br><br>--p, p--]
            D --> E[随机访问迭代器<br>读写 + 随机跳转<br><br>移动i个单元（+=i or -=i）<br>大小比较<br>取下标]

    →表示包含前者功能

  • 容器对应的迭代器类别

    容器	迭代器类别
    vector	随机
    deque	随机
    list	双向
    set/multiset	双向
    map/multimap	双向
    stack	不支持迭代器
    queue	不支持迭代器
    priority_queue	不支持迭代器

    备注：如图中提示，像 sort、binary_search 等算法要求随机访问迭代器，因此 list 以及 set/multiset、map/multimap 等关联容器无法直接使用这些算法，通常需要借助成员函数或手动实现。

    ⚠️书写应严格按照表格支持的类别，例如list不能使用it<l.end()和it+=2和l[i]语法

容器

分类

• 顺序容器/序列容器

  vector, deque, list

• 关联容器/有序容器

  set, multiset, map multimap

• 容器适配器

  stack, queue, priority_queue

其中前两类属于第一类容器

容器概述

• 插入的是对象的一个复制品
• 往往需要重载 == 和 < 运算符以比较→进而实现查找、排序……

成员函数概述

共有成员函数

• 按照词典序比较两个容器的运算符==, !=, >, <, >=, <=
• empty 判断是否为空
• max_size 容器最多能装元素个数（常上万）
• size 容器中元素个数
• swap 交换容器内容

第一类容器特有的成员函数

函数	说明
begin() / end()	首/尾后迭代器
rbegin() / rend()	反向迭代器
erase(iter)	删除迭代器指向元素
erase(begin, end)	删除区间
clear()	清空
insert(iter, val)	在迭代器位置前插入

顺序容器特有成员函数

函数	说明
push_back(val)	尾插
pop_back()	尾删
front() / back()	首/尾元素引用
resize(n)	调整大小
assign(n, val)	赋 n 个 val

详细介绍

顺序容器

vector

• 头文件<vector>
• 动态数组，内存连续
• 随机存取→常数时间
• 尾端增删性能佳，中间增删 O(n)
• 扩容时重新分配内存，原迭代器失效

vector<int> v;
v.push_back(1);               // 尾插
v.pop_back();                 // 尾删
v.insert(v.begin()+i, val);   // 位置 i 前插入
v.erase(v.begin()+i);         // 删除位置 i
sort(v.begin(), v.end());     // 排序（随机迭代器）

deque

• 头文件<deque>
• 双向队列，首尾增删 O(1)
• 支持 [] 下标、随机迭代器
• 内存分段，sort 效率略低于 vector

deque<int> dq;
dq.push_back(1);  dq.push_front(2);
dq.pop_back();    dq.pop_front();

list

• 头文件<list>
• 双向链表，任意位置增删 O(1)
• 仅双向迭代器：不支持 []、it+=n、it<end
• 自带 sort()、reverse()、merge()、remove(val) 成员函数

list<int> lst;
lst.push_back(1);   lst.push_front(0);
lst.insert(it, val);   // it 前插入
lst.erase(it);          // 删除 it
lst.sort();             // 成员 sort（非全局 sort）

频繁中间增删用 list；需随机访问用 vector。