# STL 概述

STL (Standard Template Library) 是一组 C++ 模板类，用来提供编程常见的数据结构和函数，包括链表、堆栈、数组等。STL 主要包括六部分：

• 算法 (Algorithms)
• 容器 (Containers)
• 迭代器 (Iterators)
• 仿函数 (Functor)
• 适配器
• 分配器 (Allocator)

# 迭代器

迭代器是 STL 中用于遍历容器中元素的算法，用途类似指针。按功能强弱，STL 迭代器可以分为以下五种：

• 输入迭代器 (input iterator)
• 输出迭代器 (output iterator)
• 前向迭代器 (forward iterator): 支持基本的解引用、相等 / 不等比较和递增操作。
• 双向迭代器 (bidirectional iterator): 在前向迭代器的基础上增加了递减操作。
• 随机访问迭代器 (random access iterator): 最完整，最强大的迭代器，可以提供与指针相同的功能。相比于双向迭代器，其增加了随机访问的功能，即可以在 $O(1)$ 时间内访问任意偏移位置的容器元素。 vector (可变数组) 和 deque (双端队列) 支持随机访问迭代器。

其中，输入迭代器和输出迭代器是对流操作的迭代器，平常使用较少。

下表是前向 (F)、双向 (B) 和随机访问迭代器 (R) 的使用范围简表。

下面是一个简单的例子 (注释为输出结果)：

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main(){

    vector<int> v = {1,2,3,4,5,6,7};

    vector<int>::iterator i1 = v.begin();

    vector<int>::iterator i2 = v.end();

    cout<<*i2<<endl; // 0

    i2 -= 3;

    sort(v.rbegin(), v.rend());

    cout<<(i1<=i2)<<endl; // 1

    cout<<*i2<<endl; // 3

    cout<<distance(i2, i1)<<endl; // -4

    iter_swap(i1, i2);

    cout<<i2-i1<<endl; // 4

    cout<<*i2-*i1<<endl; // 4

    return 0;

}

# 算法

STL 中的算法大多集成于 <algorithm> 头文件。

# 排序

STL 中的排序是快排、插入排序和堆排序的综合，可以保证时间复杂度在$O(n\log n)$ 级别内。

sort() 需要传入的参数包括两个必选参数 first , last 和一个可选参数 comp .

# 容器

# 分类

STL 容器可以分为以下几类：

• 序列式容器 (sequence container)
  • vector
  • list
  • deque
  • arrays
  • forward_list (C++ 11)
• 容器适配器 (container adaptor)
  • queue
  • priority_queue
  • stack
• 关联容器 (associative container)
  • set
  • multiset
  • map
  • multimap
• 无序关联容器 (unordered associative container)
  • unordered_set
  • unordered_multiset
  • unordered_map
  • unordered_multimap

# C++ pair

pair 是 STL 库中的一个结构体，用来表示一个有序数对，其定义于头文件 utility 及命名空间 std 中，具体定义为

template <class T1, class T2> struct pair;

其中， T1 和 T2 可以是不同的数据类型。两个元素依次为 first 及 second 。

# 基本操作

# 构造

下面是 pair 的三种构造方法。

pair <int, double> p1;          // 采用默认构造函数构造

pair <int, double> p2(1,0.5);   // 给出初始值的构造

pair <int, double> p3(p2);      // 拷贝构造

# 关系运算符

C++ STL 中已经重载了 pair 的关系运算符，它们的定义如下：

template <class T1, class T2>

  bool operator== (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)

{ return lhs.first==rhs.first && lhs.second==rhs.second; }

template <class T1, class T2>

  bool operator!= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)

{ return !(lhs==rhs); }

template <class T1, class T2>

  bool operator<  (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)

{ return lhs.first<rhs.first || (!(rhs.first<lhs.first) && lhs.second<rhs.second); }

template <class T1, class T2>

  bool operator<= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)

{ return !(rhs<lhs); }

template <class T1, class T2>

  bool operator>  (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)

{ return rhs<lhs; }

template <class T1, class T2>

  bool operator>= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)

{ return !(lhs<rhs); }

值得注意的是，在比较关系符中，默认的重载方式是优先比较第一个元素，之后再比较第二个元素。

# 交换

pair 中有 swap 函数提供交换操作。使用的前提是两个被交换的 pair 的对应数据类型相同。下面是一个简单的例子：

std::pair<int,char> lhs (10,'a');

std::pair<int,char> rhs (90,'z');

lhs.swap(rhs);

# C++ set

set 是 STL 中的结构体，用来实现集合的相关操作，其内部采用红黑树实现。

set 中常用的是多重集 multiset , 其具体用法可以参考 multiset 用法总结。

# 基本操作

# C++ map

# C++ String

• 【C++】-- STL 之 String 详解
• C++ STL 中 string 的详细总结

# Reference

本笔记的主要参考资料包括：

• C 语言中文网：C++ STL 快速入门
• C++ STL 详解超全总结 (快速入门 STL)
• Wikipedia: Standard Template Library
• Wikipedia: iterator
• cplusplus: Containers - C++ Reference
• GeekforGeeks: The C++ Standard Template Library (STL)
• 沉晓: 【C/C++】STL 详解
• zhangbw~: C++ Sort 函数详解