STL

C++语言的核心优势之一：便于软件的重用 体现重用的两个方面： 1. 面向对象的思想：继承、多态，标准类库 2. 泛型程序设计的思想：模板、标准类库 标准类库（STL）：包括了通用数据结构和基本算法，提供统一标准的公共接口，使用方便快捷

组成结构

容器

• 用来容纳各种数据类型的数据结构
• 三大类：
  • 顺序容器
    • vector：可随机访问，后部插入删除
    • deque：可随机访问，前后插入删除
    • list：双向链表，任意位置插入删除
  • 关联容器（使用红黑树实现，插入、检索的时间均为\(O(\log{N})\)
    • (milti)set：快速查找，（有）无重复元素
    • (multi)map：一一对应，（有）无重复元素
  • 适配容器
    • stack
    • queue
    • priority_queue：优先队列
• 共有的成员函数：
  • 基本运算符：=、<、<=、== 、……
  • empty()
  • max_size()
  • size()
  • swap()
  • begin()、end()、insert()、erase()等

    对于使用红黑树实现的STL容器，可以通过自定义比较结构体，对数据类型做特殊的排序操作或者是自定义的数据结构，构造方式如下（以set为例）： - set<类型,比较结构体> 对象名 比较结构体的声明： struct comp{ bool operator()(const type &a, const type &b){ 比较机制:return true/false } }

迭代器

• 类似传统C的指针，可依次存取容器中元素的对象
• 范围表示：
• 存在const与非const两种：非const可以修改其指向的元素
• 定义容器类的方法：容器类名::iterator 变量名或容器类名::const_iterator 变量名
• 访问迭代器指向元素的方式：与指针相同：*iterator
• 功能由弱到强可分为五种：
  1. 输入：提供对数据的只读访问（cout）
  2. 输出：提供对数据的只写访问（cin）
  3. 正向：提供读写操作，并能一次一个向前推进
  4. 双向：提供读写操作，并能一次一个向前或后推进
  5. 随机访问：提供读写操作，并随机移动
• 对迭代器的限制越少越好
  • 能够支持大部分的场景
  • 特殊的场景可以自行添加限制

对于cin、cout，可以通过如下的方式使用 ostream_iterator<int> inwriter(cout, " "); copy(begin(), end(), inwriter); 构造函数的第一个参数为要输出的目的地，第二个参数为间隔符

算法

• 通过迭代器来才做容器中元素的函数模板

适配器

• 利用基础容器对象，加以包装、改变接口，以适应另一种需求

函数对象

• 较为低阶的对象，用来替代传统的函数指针
• 匿名对象仅存在于构造该对象的那一行代码