STL初步

STL初步

泛型程序设计（generic programming）

设计思想

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

模板机制

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

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

标准模板库（Standard Template Library）

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

STL的基本概念

  • 容器：可容纳各种数据类型的通用数据结构，是类模板
  • 迭代器：可用于依次存取容器中元素，类似于指针
    • 普通的C++指针就是一种迭代器
  • 算法：用来操作容器中的元素的函数模板
  • sort() 来对一个数组中的数据进行排序
  • find() 来搜索一个数组中的对象
    算法本身与他们操作的数据的类型无关，
    因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用
1
2
int array[100];    // 该数组就是容器，而int* 类型的指针变量就可以作为迭代器
sort(array, array+70);  // sort 算法可以作用于该容器上，对其进行排序

迭代器

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

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

  • 使用方法：

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

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

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

    • 强弱

      1
      2
      3
      4
      5
      6
      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 交换容器内容
第一类容器特有的成员函数
顺序容器特有成员函数

详细介绍

顺序容器
vector
  • 头文件<vector>
  • 动态数组
  • 随机存取→常数时间完成
  • 尾端增删性能极佳
  • 特有操作：