标准库

标准库提供的设施可以分为以下几类：

运行时语言支持（例如，对资源分配和运行时类型信息的支持）
C 标准库（进行了微小的修改，以便尽量减少与类型系统的冲突）
字符串和 I/O 流（包括对国际字符集和本地化的支持）
- I/O 流是一个可扩展的输入输出框架，用户可向其中添加自己的流、缓冲策略和字符集。
一个包含容器（如 vector 和 map）和算法（如 find()、sort() 和 merge()）的框架
- 人们习惯上称这个框架为标准模板库(STL)，用户可向其中添加自己定义的容器和算法。
对数值计算的支持（例如标准数学函数、复数、支持算术运算的向量以及随机数发生器）
对正则表达式匹配的支持
对并发程序设计的支持，包括 thread 和 lock 机制
- 在此基础上，用户就能够以库的形式添加新的并发模型。
一系列工具，它们用于支持模板元编程（如类型特性）、STL-风格的泛型程序设计（如 pair）和通用程序设计（如 clock）
用于资源管理的“智能指针” （如 unique_ptr 和 shared_ptr）和垃圾收集器接口
特殊用途容器，例如 array、bitset 和 tuple

标准库通过若干头文件提供，并定义在 std 的名字空间中。

部分标准库头文件	功能描述
`<algorithm>`	`copy()`, `find()`, `sort()`
`<array>`	`array`
`<chrono>`	`duration`, `time_point`
`<cmath>`	`sqrt()`, `pow()`
`<complex>`	`complex`, `sqrt()`, `pow()`
`<fstream>`	`fstream`, `ifstream`, `ofstream`
`<future>`	`future`, `promise`
`<iostream>`	`istream`, `ostream`, `cin`, `cout`
`<map>`	`map`, `multimap`
`<memory>`	`unique_ptr`, `shared_ptr`, `allocator`
`<random>`	`default_random_engine`, `normal_distribution`
`<regex>`	`regex`, `smatch`
`<string>`	`string`, `basic_string`
`<set>`	`set`, `multiset`
`<sstream>`	`istrstream`, `ostrstream`
`<thread>`	`thread`
`<unordered_map>`	`unordered_map`, `unordered_multimap`
`<utility>`	`move()`, `swap()`, `pair`
`<vector>`	`vector`

字符串

string 对象是可变的，并且定义了移动构造函数，支持下标（[]）操作和子串操作：

string name="Niels Stroustrup";

void m3()
{
    string s= name.substr(6,10); // s="Stroustrup"（拷贝）
    name.replace(0,5,"nicholas"); //name变为"nicholas Stroustrup"
    name[0]=toupper(name[0]); //name变为"Nicholas Stroustrup"
}

string 之间可以相互比较，也可以与字符串字面常量比较：

#include <iostream>
#include <string>


int main() {
	std::string alice = "Alice";
	std::string bob = "Bob";

	if (alice == bob) {
		std::cout << "Alice = Bob" << std::endl;
	}
	else {
		std::cout << "Alice != Bob" << std::endl;
	}

	if (alice == "Alice") {
		std::cout << "Alice = Alice" << std::endl;
	}
	else {
		std::cout << "Alice != Alice" << std::endl;
	}

}

I/O 流

标准库 iostream 提供了格式化字符的输人输出功能，其中的输入操作类型敏感且能被扩展以处理用户自定义的类型。

输出

I/O 流库为所有内置类型都定义了输出操作。而且，用户自定义类型也可以定义输出操作。运算符 << 是输出运算符，它作用于 ostream 类型的对象；cout 是标准输出流，cerr 是报告错误的标准流。

输入

标准库提供了 istream 来实现输入。与 ostream 类似，istream 处理内置类型的字符串表示形式，并能被很容易地扩展以支持用户自定义的类型。

运算符 >>（“从…获取”）实现输人功能；cin 是标准输人流。>> 右侧的运算对象决定了输入什么类型的值，以及输人的值保存在哪里.

#include <iostream>
#include <string>

using namespace std;

int main() {
    cout << "Please enter your name\n";
    string str;
    cin >> str;
    cout << "Hello, " << str << "!\n";
    return 0;
}

如果你键入 Eric，程序将回应：

Hello, Eric!

默认情况下，空格等空白符会终止输入。因此，如果你键人 Eric Bloodaxe 冒充不幸的约克王，程序的回应仍会是：

Hello, Eric!

你可以用函数 getline() 来读取一整行（包括结束时的换行符），例如：

#include <iostream>
#include <string>

using namespace std;

void hello_line() {
    cout << "Please enter your name\n";
    string str;
    getline(cin, str);
    cout << "Hello, " << str << "!\n";
}

运行这个程序，再输输入 Eric Bloodaxe 就会得到想要的输出：

Hello,Eric Bloodaxe!

行尾的换行符被丢弃掉了，因此接下来再 cin 的话会从下一行开始。

标准库字符串有一个很好的性质一可以自动扩充空间来容纳你存入的内容。这样，你就无须预先计算所需的最大空间。

用户自定义类型的 I/O

#include <iostream>
#include <string>

struct Entry {
    std::string name;
    int number;
};

// 重载输出流操作符 <<
std::ostream& operator<<(std::ostream& os, const Entry& entry) {
    os << "Name: " << entry.name << ", Number: " << entry.number;
    return os;
}

// 重载输入流操作符 >>
std::istream& operator>>(std::istream& is, Entry& entry) {
    std::cout << "Enter name: ";
    is >> entry.name;
    std::cout << "Enter number: ";
    is >> entry.number;
    return is;
}

int main() {
    Entry entry;
    std::cout << "Enter entry details:" << std::endl;
    std::cin >> entry; // 使用重载的输入流操作符
    std::cout << "You entered:" << std::endl;
    std::cout << entry; // 使用重载的输出流操作符
    return 0;
}

容器

vector

给定类型元素的序列，在内存中连续存储
动态扩展
支持拷贝和移动
不进行范围检查
vector 的 at() 函数同样负责下标操作，但它会在参数越界时抛出一个类型为 out_of_range 的异常

list

双向链表
支持范围 for

添加和删除元素

void f(const Entry& ee, list<Entry>::iterator p, list<Entry>::iterator q) {
    phone_book.insert(p, ee); // 将ee添加到p指向的元素之前
    phone_book.erase(q);       // 删除q指向的元素
}

map

map 通常使用平衡二叉树实现。

具体使用方法如下：

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap { 
        { 0, "zero" } 
    };

    // 插入元素
    myMap[1] = "one";
    myMap[2] = "two";
    myMap.insert(std::make_pair(3, "three"));
    myMap[4]; // 插入一个键为4，值为空的元素。因此如果想要找元素是否存在，使用 find 函数。

    // 遍历元素
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 查找元素
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Found: " << it->second << std::endl;
    }

    // 删除元素
    myMap.erase(1);

    return 0;
}

输出：

0: zero
1: one
2: two
3: three
4:
Found: two

搜索的时间代价：$O\left(\log\left(n\right)\right)$

unordered_map

哈希 Map

具体使用方法如下（与 map 基本一致）：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myMap {
        { 0, "zero" } 
    };

    // 插入元素
    myMap[1] = "one";
    myMap[2] = "two";
    myMap.insert(std::make_pair(3, "three"));
    myMap[4]; // 插入一个键为4，值为空的元素。因此如果想要找元素是否存在，使用 find 函数。

    // 遍历元素
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 查找元素
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Found: " << it->second << std::endl;
    }

    // 删除元素
    myMap.erase(1);

    return 0;
}

输出：

0: zero
1: one
2: two
3: three
4:
Found: two

容器概述

标准库容器名称	概述
`vector<T>`	可变大小向量
`list<T>`	双向链表
`forward_list<T>`	单向链表
`deque<T>`	双端队列
`set<T>`	集合
`multiset<T>`	允许重复值的集合
`map<K,V>`	关联数组
`multimap<K,V>`	允许重复关键字的 map
`unordered_map<K,V>`	采用哈希搜索的 map
`unordered_multimap<K,V>`	采用哈希搜索的 multimap
`unordered_set<K,V>`	采用哈希搜索的 set
`unordered_multiset<K,V>`	采用哈希搜索的 multiset

算法

// 定义一个函数，接受一个引用类型的vector<Entry>作为参数
list<Entry> f(vector<Entry>& vec) {
    // 创建一个空的list<Entry>用于存储结果
    list<Entry> res;

    // 对输入的vector进行排序
    sort(vec.begin(), vec.end());

    // 使用unique_copy将排序后的vector中的唯一元素复制到res中
    // back_inserter(res)用于将元素追加到res中（back_inserter 会调用 lst.push_back() 方法，将元素添加到 lst 的末尾。）
    unique_copy(vec.begin(), vec.end(), back_inserter(res));

    // 返回结果list
    return res;
}

迭代器

所有迭代器类型的语义及其操作的命名都是相似的。例如，对任何选代器使用 ++ 运算符都会得到一个指向下一个元素的选代器，而 * 运算符则得到选代器所指的元素

流迭代器

输入输出流，容纳一个值得序列，所以有流迭代器。

下面是利用 ostream_iterator 输出到标准输出的简单例子：

#include <iostream>
#include <iterator>
#include <string>
using namespace std;

int main() {
    ostream_iterator<string> oo{ cout };
    *oo = "Hello,"; // 等价于 cout << "Hello,"
    ++oo; // 类似于用指针向数组中写入值
    *oo = "world!\n"; // 等价于 cout << "world!\n"
}

下面是一个更复杂的例子。其中，ifstream 是一个可以绑定到文件的 istream，而 ofstream 就是一个可以绑定到文件的 ostream。其中，ostream_iterator 的第 2 个参数指定输出的间隔符。

#include <iostream>
#include <fstream>
#include <iterator>
#include <vector>
#include <algorithm>

int main() {
    std::string from, to;
    std::cin >> from >> to;

    std::ifstream is{ from }; // 对应文件“from”的输入流

    std::istream_iterator<std::string> ii{ is }; // 输入流的迭代器
    std::istream_iterator<std::string> eos{}; // 输入哨兵（相当于容器的end()）

    std::ofstream os{ to }; // 对应文件“to”的输出流

    std::ostream_iterator<std::string> oo{ os, "\n" }; // 输出流的迭代器， "\n" 是指定的分隔符

    std::vector<std::string> b{ ii, eos }; // b是一个vector，用输入进行初始化

    std::sort(b.begin(), b.end()); // 排序缓冲区中的单词

    std::unique_copy(b.begin(), b.end(), oo); // 将不重复的单词拷贝到输出，丢弃重复值

    return !is.eof() || !os; // 返回错误状态
}

from.txt 的内容

she sea saw see

运行程序得到输出 to.txt 的内容

saw
sea
see
she

谓词

利用函数对象或者 lambda 表达式作为参数，传入（标准库的）算法中，作为策略。

struct Greater_than {
    int val;

    Greater_than(int v) : val{v} {}

    bool operator()(const pair<string, int>& r) { return r.second > val; }
};

void f(map<string, int>& m) 
{
    auto p = find_if(m.begin(), m.end(), Greater_than{42});
    // ...
}

算法概述

标准库提供了很多算法，它们都定义在头文件 <algorithm> 中且属于名字空间 std。这些标准库算法的输入都是序列。一个从 b 到 e 的半开序列表示为 [b:e)。下面是一些特别有用的算法的简介。

操作	描述
`p=find(b,e,x)`	`p` 是 `[b:e)` 中第一个满足 `*p==x` 的迭代器
`p=find_if(b,e,f)`	`p` 是 `[b:e)` 中第一个满足 `f(*p)==true` 的迭代器
`n=count(b,e,x)`	`n` 是 `[b:e)` 中满足 `q==x` 的元素 `q` 的数目
`n=count_if(b,e,f)`	`n` 是 `[b:e)` 中满足 `f(q)==true` 的元素 `q` 的数目
`replace(b,e,v,v2)`	将 `[b:e)` 中满足 `q==v` 的元素 `q` 替换为 `v2`
`replace_if(b,e,f,v2)`	将 `[b:e)` 中满足 `f(q)==true` 的元素 `q` 替换为 `v2`
`p=copy(b,e,out)`	将 `[b:e)` 拷贝到 `[out:p)`
`p=copy_if(b,e,out,f)`	将 `[b:e)` 中满足 `f(q)==true` 的元素 `q` 拷贝到 `[out:p)`
`p=unique_copy(b,e,out,f)`	将 `[b:e)` 拷贝到 `[out:p)`, 不拷贝连续的重复元素
`sort(b,e)`	排序 `[b:e)` 中的元素，用 `<` 作为排序标准
`sort(b,e,f)`	排序 `[b:e)` 中的元素，用谓词 `f` 作为排序标准
`(p1,p2)=equal_range(b,e,v)`	`[p1:p2)` 是已排序序列 `[b:e)` 的子序列，其中元素的值都等于 `v`，本质上等价于二分搜索 `v`
`p=merge(b,e,b2,e2,out)`	将两个序列 `[b:e)` 和 `[b2:e2)` 合并，结果保存到 `[out:p)`

‍

标准库

字符串