8.IO库
IO类
三个头文件：
iostream 定义了用于读写流的基本类型
fstream 定义了读写命名文件的类型
sstream 定义了读写内存 string 对象的类型
| 头文件 | 类型 |
|---|---|
| iostream | istream, ostream, iostream |
| fstream | ifsream, ofstream, fstream // 读写文件 |
| sstream | istringstream, ostringstream, stringstream |
可以添加一个 w 在前面，表示对应的宽字符版本。
>> 可以从不同的来源读取数据，是通过继承实现的。
！！IO对象无拷贝或者赋值
IO操作可能发生错误，一些函数和标志可以帮助访问和操纵流的条件状态：(其中strm是一种IO类型)
:-:|:-:
strm::iostate | iostate是一种机器相关的类型，提供了表达条件状态的完整功能
strm::badbit | 指出流已经崩溃
strm::failbit | 指出一个IO操作失败了
strm::eofbit | 指出流到达了文件结束
strm::goodbit | 指出流未处于错误状态，此值保证为0
s.eof() | 若流 s 的 eofbit 置位，则返回 true
s.fail() | 若 s 的 badbit 或 failbit 置位，则返回 true
s.bad() | badbit 置位，则返回 true
s.good() | 流处于有效状态则返回 true
s.clear() | 将流 s 中所有条件状态复位
endl 完成换行并刷新缓冲区的工作
flush 刷新缓冲区，但不输出任何额外的字符
ends 向缓冲区插入一个空字符，然后刷新缓冲区
如果想在每次输出操作后都刷新缓冲区，可以使用 unitbuf 操作符:
cout << unitbuf; // 所有输出后都会立即刷新缓冲区
// 任何输出都立即刷新，无缓冲
cout << nounitbuf; // 回到正常的缓冲方式
！！ 如果程序崩溃，输出缓冲区是不会被刷新的
文件输入输出
fstream 特有的操作：
:-:|:-:
fstrm; | 创建一个未绑定的文件流
fstrm(s); | 创建一个 fstream ，并打开名为 s 的文件
fstrm(s, mode); | 按指定 mode 打开文件
fstrm.opem(s) | 打开名为 s 的文件，并与 fstrm 绑定，返回 void
fstrm.close() | 关闭文件，返回 void
fstrm.is_open() | 返回 bool 值，是否成功打开且尚未关闭
打开的文件名既可以是 string 对象，也可以是 C 风格的字符数组。
ofstream out
... // 打开文件
if(out) // 检查open是否成功
文件模式：
- in 以读方式打开
- out 以写方式打开，会清空当前文件
- app 每次写操作前均定位到文件末尾
- ate 打开文件后立即定位到文件末尾
- trunc 截断文件
- binary 以二进制方式进行 IO
！！保留 ofstream 打开的文件中已有的数据的唯一方式是，显式指定 app 或 in 模式。
每次调用 open 时都会确定文件模式，例如：
ofstream out;
out.open("sadqw"); // 模式隐含设置为输出和截断
out.close();
out.open("repw", ofstream::app); // 模式为输出和追加
out.close();
string 流
:-:|:-:
sstream strm | strm 是一个未绑定的 stringstream 对象
sstream strm(s) | strm 是一个保存了 string s 的一个拷贝的 sstream 对象
strm.str() | 返回 strm 所保存的 string 的拷贝
strm.str(s) | 将 string s 拷贝到 strm 中，返回 void
读取：
while(getline(cin, line)){
PersonInfo info;
istringstream record(line);
record >> info.name;
while(record >> word)
info.phones.push_back(word);
}
输出：
ostringstream formatted, badNums;
...
badNums << " " << nums; // 将 nums 的字符串形式存入 badNums
formatted << " " << nums;
if(badNums.str().empty())
os << "empty!!" << endl;
else
cerr << "some errors:" << badNums.str() << endl;
9.顺序容器
顺序容器中，元素的顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。
顺序容器类型：
- vector 可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢。
- deque 双端队列。支持快速随机访问。在头尾位置插入/删除很快。
- list 双向链表。只支持双向顺序访问。在 list 中任何位置插入/删除都很快。
- forward_list 单向链表。只支持单向顺序访问。在任何位置插入/删除都很快。
- array 固定大小数组。支持快速随机访问。不能添加或删除元素。
- string 与vector相似的容器，但专门用于保存字符。随机访问快，在尾部插入/删除速度很快。
挑选容器的基本原则：
-
除非有很好的理由，否则都用 vector
-
如果程序有很多小的元素，且空间的额外开销很重要，则不要使用 list 或 forward_list
-
如果程序要求在容器中插入或删除元素，应使用 list 或 forward_list
-
如果程序要求在头尾位置插入或删除元素，但不会在中间位置进行插入删除，则用 deque
-
如果只有在读取输入时才需要在容器中间位置插入元素，随后需要随机访问元素，则
- 首先确定是否一定要在中间添加元素，如果可以排序避免，vector很好
- 如果一定要在中间位置插入元素，考虑在输入阶段使用 list，输入完成后拷贝到一个 vector 中
概览
容器库上的操作有三个层次：
- 所有容器类型都提供的
- 仅针对顺序容器、关联容器或无序容器的
- 只使用于一小部分容器的
容器操作：
:-:|:-:
类型别名|
iterator | 迭代器类型
const_iterator | 只读，不可修改的迭代器类型
size_type | 无符号整数类型，足够保存最大可能的容器大小
difference_type | 带符号整数类型，保存迭代器距离
value_type | 元素类型
reference | 元素的左值类型；等价于 value_type&
const_reference | const左值类型
构造函数|
C c; | 默认构造函数
C c1(c2); | 拷贝
C c(b, e); | 构造 c ，将迭代器 b 和 e 指定的范围内的元素拷贝到 c (array不支持)
C c{a, b, c,..}; | 列表初始化 c
赋值与swap |
c1 = c2 |
c1 = {a, b, c,...}; |
a.swap(b) | 交换 a 和 b 的元素
swap(a, b) | 与 a.swap(b) 等价
大小 |
c.size() | c 中元素的数目
c.max_size() | 最大元素数目
c.empty() | c 为空？
添加/删除元素 |
c.insert(args) | 将 args 中的元素拷贝进 c
c.emplace(inits) | 使用 inits 构造 c 中的一个元素
c.erase(args) | 删除 args 指定的元素
c.clear() | 删除所有元素
关系运算符 |
==, != | 所有容器都支持
<, <=, >, >= | 无序关联容器不支持！！！
获取迭代器 |
c.begin(), c.end() | 返回指向 c 的首元素和尾后元素的指针
c.cbegin(), c.cend() | const_iterator
反向容器的额外成员 |
reverse_iterator | 逆序寻址元素的迭代器
const_reverse_iterator|
c.rbegin(), c.rend()|
c.crbegin(), c.crend()|
迭代器的算术运算只能用于 string 、 vector 、 deque 和 array 。迭代器的范围是一个左闭合区间 [begin, end)
- 如果 begin 和 end 相等，则范围为空
- 如果 begin 和 end 不等，则范围至少包含一个元素
- 可以通过反复递增 begin 来到达 end
可以按如下方式处理元素范围：
while(begin != end){
*begin = val;
++begin;
}
！！ 带 r 的迭代器版本返回反向迭代器，带 c 的版本返回 const 迭代器。
当不需要访问时，用 cbegin 和 cend
容器的定义和初始化：
C c(b, e) 迭代器 b 和 e 指定范围中的元素的拷贝，类型必须相容。
只有顺序容器才能接受大小参数
C seq(n) 包含 n 个元素，每个都是值初始化的
C seq(n, t) 包含 n 个初始化值为 t 的元素
！！标准库 array 具有固定大小，大小是 array 类型的一部分
array<int, 10>
array<string, 42>
交换容器中的元素：swap 通常比拷贝元素快的多
swap(c1, c2); // c1 和 c2 必须具有相同的类型
c1.swap(c2);
assign操作，仅顺序容器，不适用于关联容器和 array：
seq.assign(b, e); // 将 seq 中的元素替换为 b 和 e 迭代器表示范围中的元素
seq.assign(il); // 将 seq 中的元素替换为初始化列表 il 中的元素
seq.assign(n, t); // 将 seq 中的元素替换为 n 个值为 t 的元素
！！赋值运算会使指向左边容器内部的迭代器、引用和指针失效，而swap不会。
顺序容器操作
添加元素(非 array )：
c.push_back(t);
c.emplace_back(args); //在尾部创建一个值为 t 或由 args 创建的元素，返回 void
c.push_front(t);
c.emplace_front(args); //在头部创建一个值为 t 或由 args 创建的元素，返回 void
c.insert(p, t);
c.emplace(p, t); //在迭代器 p 之前创建一个值为 t 的元素，返回指向新元素的迭代器
c.insert(p, n, t); //....n个值为 t 的元素，返回指向新添加的第一个元素的迭代器
c.insert(p, b, e); //迭代器 b 和 e 之间的元素插入 p 指向的元素之前
c.insert(p, il); //将花括号包围的元素列表 il 插入 p 指向的元素之前
向 vector 、 string 、 deque插入元素会使所有指向容器的迭代器、引用失效
除了 array 和 forward_list 之外，每个顺序容器都支持 push_back
list 、 forward_list 、deque 还支持 push_front
使用 insert 的返回值的技巧：
list<string> lst;
auto iter = lst.begin();
while(cin >> word)
iter = lst.insert(iter, word);
访问元素：
c.back() // 尾元素的引用
c.front() // 首元素的引用！！不可以对空容器使用 back 和 front
c[n] // 下标为 n 的元素的引用
c.at(n) // 下标为 n 的元素的引用
c[n] 操作如果下标越界，则是未定义的，而如果使用 c.at(n) ，会返回一个 out_of_range 异常。
删除元素：
c.pop_back(); // 删除尾元素，若c为空则函数行为未定义。函数返回 void
c.pop_front();
c.erase(p); // 删除迭代器p指定的元素，返回被删元素之后的元素的迭代器，不能删除尾后迭代器！
c.erase(b, e); // 删除迭代器 b 和 e 之间的值
c.clear();
删除 deque 中除首位元素之外的任何元素都会使所有迭代器、引用、指针失效； vector 或 string 中，删除点之后的会失效。
pop 操作没有返回值，因此如果要这些值的话，要先保存。
循环删除一个 list 中的所有奇数元素：
list<int> lst = {0,1,2,3,4,5,6,7,8,9};
auto it = lst.begin();
while(it != lst.end())
if (*it % 2)
it = lst.erase(it); // 删除当前迭代器指向的元素，并把 it 移到下一个位置
else
++it;
删除一个范围内的元素：
elem1 = slist.erase(elem1, elem2); // 调用后 elem1 == elem2
！特殊的 forward_list 操作：
单向链表中，插入和删除操作都是通过前驱元素完成的，所以函数名不同：
lst.insert_after(p,...) // 在迭代器 p 之后插入元素
emplace_after(p, args)
lst.erase_after(...) // 删除 p 之后的元素，或删除从 b 之后到 e 之间(不包括 e ) 的元素
如果要删除第一个元素，要用到首元素之前不存在的元素的迭代器： lst.before_begin()
删除一个 forward_list<int> 中所有的偶数:
forward_list<int> lst = { 1,2,3,4,5,6,7,8,9,0 };
auto prev = lst.before_begin();
auto curr = lst.begin();
while (curr != lst.end()){
if (*curr % 2){
++curr;
prev = lst.erase_after(prev);
}
else{
prev = curr;
++curr;
}
}
改变容器大小 resize ：
如果当前大小大于所要求的大小，则容器后部的元素会被删除；
如果当前大小小于新大小，会将新元素添加到容器后部。
c.resize(n); // 调整 c 的大小为 n ，若必须添加新元素，则进行值初始化
c.resize(n, t); // 任何新添加的元素都初始化为值 t
！！如果在一个循环中插入/删除 deque 、 string 或 vector 中的元素，不要缓存 end 返回的迭代器。必须在每次插入后重新调用 end()
vector 对象的增长
vector 将元素连续存储。
当添加元素时，如果没有空间容纳新元素，容器必须分配新的内存空间来保存已有元素和新元素，将已有元素从旧位置移动到新空间中，然后添加新元素，释放旧存储空间。
标准库的实现：当不得不获取新的内存空间时， vector 和 string 通常会分配比新的空间需求更大(多50%)的内存空间。使得其扩张操作通常比 list 和 deque 更快。
容器大小的管理操作：
c.shrink_to_fit() // 将 capacity() 减少为与 size() 相同的大小
c.capacity() // 不重新分配内存的话，c 可以保存多少个元素
c.reserve(n) // 分配至少能容纳 n 个元素的空间
一个空的 vector 的 size 为 0， capacity 也为 0
当添加元素时，size 与添加的元素数目相等，capacity 至少与 size 一样大
string 的操作
修改 string 的操作：
s.insert(pos, args) 在 pos 之前插入 args 指定的字符，pos 可以是一个下标或一个迭代器。
s.erase(pos, len) 删除从位置 pos 开始的 len 个字符，如果 len 被省略，则删除 pos 开始到末尾的所有字符，返回一个指向 s 的引用
s.append(args) +=
s.assign(args) 将 s 中的字符替换为 args
s.replace(range, args) 删除 s 中范围 range 内的字符，替换为 args 指定的字符。range 或者是一个下标和一个长度，或者是一对迭代器。
例如：
s.insert(s.size(), 5, '!'); // 在s末尾插入5个感叹号
s.erase(s.size() - 5, 5); // 删除末尾5个元素
const char *cp = "Stately, plump Buck";
s.assign(cp, 7); // s = "Stately"
s.insert(s.size(), cp + 7) // s = "Stately, plump Buck"
substr 操作：
s.substr(pos, n) //返回一个 string，包含从 pos 开始的 n 个字符的拷贝，如果不写 n，默认值为 s.size() - pos
replace 操作：
s.replace(range, args) //删除 s 中范围 range 内的字符，替换为 args 指定的字符。 例如:
s.replace(i, size_old, newVal); // 将 i 开始的 size_old 个字符替换为 newVal
搜索操作：
返回值均为 string::size_type，或匹配失败时 string::npos(这个值初始化为 -1，由于是 unsigned 的，所以相当于 string 的最大可能的大小)
s.find(args) // 查找 s 中 args 第一次出现的位置
s.rfind(args) // 查找 s 中 args 最后一次出现的位置
s.find_first_of(args) // 在 s 中查找 args 中任何一个字符第一次出现的位置
s.find_last_of(args) // 在 s 中查找 args 中任何一个字符最后一次出现的位置
s.find_first_not_of(args) // 在 s 中查找第一个不在 args 中的字符
s.find_last_not_of(args) // 在 s 中查找最后一个不在 args 中的字符
args 必须是以下形式：
c, pos 从位置 pos (默认为0)开始查找字符 c
s2, pos 从位置 pos (默认为0)开始查找字符串 s2
cp, pos 从位置 pos 开始查找C风格字符串 cp
cp, pos, n 从位置 pos 开始查找指针 cp 指向的数组的前 n 个字符
！！循环检测所有的子字符串出现的位置：
string::size_type pos = 0;
while((pos = name.find_first_of(numbers, pos)) != string::npos){
cout << "found number at index: " << pos
<< " element is " << name[pos] << endl;
++pos; // 移动到下一个字符，递增必不可少！！
}
compare 函数：
s.compare(pos1, n1, s2, pos2, n2) // 从 pos1 开始的 n1 个字符和 s2 中从 pos2 开始的 n2 个字符比较，返回0、正数、负数
s.compare(s2)
s.compare(pos1, n1, s2)
s.compare(pos1, n1, cp, n2) // 从 pos1 开始的 n1 个字符与指针 cp 指向的地址开始的 n2 个字符进行比较
s.compare(cp)
s.compare(pos1, n1, cp)
字符串数值转换：
string s = to_string(i) // 将任意算术类型的数 i 转化为字符串 s
double d = stod(s); // 字符串 s 转化为浮点数 d
stoi.. stol.. stoul..
stof.. stod.. stold..
在字符串中查找到第一个可能是浮点数的字符位置：
string s2 = "pi = 3.141";
d = stod(s2.substr(s2.find_first_of("+-.0123456789")));
10.泛型算法
generic algorithm 泛型算法大多数定义在 algorithm 中，头文件 numeric 中也还有一些数值泛型算法。一般情况下，算法遍历两个迭代器之间的范围，而不是直接操作容器。
！！迭代器令算法不依赖于容器，但算法依赖于元素类型的操作。
算法只运行于迭代器之上，本身不会执行容器的操作，永远不会改变底层容器的大小，可能改变容器中保存元素的值，也可能在容器内移动元素，但永远不会直接添加或删除元素。
只读算法：
find， accumulate(定义在 numeric 中) 和 equal
int sum = accumulate(vec.cbegin(), vec.cend(), 0);
// sum 为 vec 中元素的和，和的初值设为 0
假定元素能执行 + 操作，并且能够加到 初值 上。
string sum = accumulate(v.cbegin(), v.cend(), string(""));
// 把 vector 中所有的 string 连接起来
string sum = accumulate(v.cbegin(), v.cend(), "");
// 错误，const char * 上没有定义 + 运算符
equal 判断相等，接受3个参数，前两个表示第一个序列的范围，第三个表示第二个序列的首元素。
equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());
// roster2 中元素应该至少和 roster1 中一样多
// 只要能用 == 判断就可以，roster1 可以是 vector<string>, roster2 是 list<const char*>
！！那些只接受单一迭代器表示第二个序列的算法，都假定第二个序列至少和第一个序列一样长。
写容器元素的算法
将新值赋予序列中的元素。必须确保原序列大小至少不小于要写入的元素数目。
fill ：把第三个参数写入范围内的每一个元素
fill(vec.begin(), vec.end(), 0);
fill(vec.begin(), vec.begin() + vec.size()/2, 10);
fill_n :一个迭代器，一个长度，一个值
fill_n(vec.begin(), vec.size(), 0);
操作两个序列的算法一般接受 4 个迭代器，分别表示两个序列的范围，而 equal 只接受 3个迭代器。
！！注意算法不检查写操作，向目的位置迭代器写入数据的算法假定目的位置足够大，能容纳写入的元素。 不要向空容器写！！！
vector<int> vec;
fill_n(vec.begin(), vec.size(), 0); // 将所有元素置 0，这个调用是安全的
fill_n(vec.begin(), 10, 0); // 错误！！！ vec中并没有10个元素
插入迭代器：向容器中添加元素的迭代器。
函数 back_inserter (头文件 inerator):接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。
vector<int> vec; // 空向量
auto it = back_inserter(vec); // 通过它赋值会将元素添加到 vec 中
*it = 42; // vec 中现在有一个元素 42
！！！通常使用 back_inserter 来创建一个迭代器：
vector<int> vec;
fill_n(back_inserter(vec), 10, 0); // 添加 10 个元素到 vec
拷贝算法 copy： 将输入范围中的元素拷贝到目标序列中
int a1[] = {0, 1, 2, 3, 4, 5};
int a2[sizeof(a1)/sizeof(*a1)]; // a2 的大小与 a1 一致
auto ret = copy(begin(a1), end(a1), a2); // 把 a1 的内容拷贝给 a2
// ret 指向拷贝到 a2 的尾元素之后的位置。
多数算法都有 copy 版本，不覆盖原值，而是放到第三个迭代器参数指定的容器中：
replace(ilst.begin(), ilst.end(), 0, 42); // 将所有0替换为42
replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42); // 把替换后的值放到 ivec 中， ilst 并没有改变
重排元素
sort：按 < 排序。
unique：使不重复的元素出现在开始部分。(只排序，不会删除)
删除重复单词的例子：
void elimDups(vector<string> &words){ // 按字典序排序，删除重复单词
sort(words.begin(), words.end());
// unique 返回一个指向不重复区域之后一个位置的迭代器
auto end_unique = unique(words.begin(), words.end());
// 删除重复单词
words.erase(end_unique, words.end());
}
定制操作
向算法传递函数
谓词(predicate)：是一个可调用的表达式，返回结果是一个能用作条件的值。有两种：一元谓词，二元谓词。
bool isShorter(const string &s1, const string &s2){
return s1.size() < s2.size(); // 按长度排序
}
elimDups(words); // 按字典序排序，删除重复单词
stable_sort(words.begin(), words.end(), isShorter);
// stable_sort 会维持相等的元素原有的顺序
lambda表达式
四种可调用对象： 函数、函数指针、重载了函数调用运算符的类、lambda表达式
lambda 表达式可以用于给一元谓词传递一个可调用表达式。
一个 lambda 表达式可以理解为一个未命名的内联函数：
[capture list](parameter list) -> return type { function body }
capture list (捕获列表) 是 lambda 表达式所在函数中定义的局部变量的列表；
return type、parameter list、function body 和正常函数一样，是返回类型、参数列表、函数体。
参数列表和返回类型可以忽略，但是必须要有捕获列表和函数体：
auto f = []{ return 42; };
//调用：
cout << f() << endl;
lambda 实参和形参类型必须匹配，且不能有默认参数，所以形参数与实参数相等。
改进 stable_sort 函数：
stable_sort(words.begin(), words.end(),
[](const string &a, const string &b) { return a.size() < b.size(); });
通过 find_if 调用:
auto wc = find_if(words.begin(), words.end(),
[sz](const string &a) { return a.size() >= sz; });
// 从函数体中捕获 sz，返回 wc 为指向第一个长度不小于 sz 的元素的迭代器。
通过 for_each 打印：
for_each(wc, words.end(),
[](const string &s){ cout << s << ' '; };
cout << endl;
lambda 的捕获：
-
值捕获
被捕获的变量的值是在 lambda 创建时被拷贝，而不是调用时。
-
引用捕获
当以引用方式捕获时，必须保证在 lambda 执行时变量是存在的。例如传递 ostream 对象时，不能拷贝，唯一的方法是捕获其引用。
for_each(words.begin(), words.end(), [&os, c](cosnt string &s) { os << s << c;}); -
隐式捕获
[=] 表示值捕获，[&] 表示引用捕获，或者：
[=, identifier_list] 表示默认用值捕获，指定的几个用引用捕获，一定要加&
[&, identifier_list] 表示默认用引用方式捕获，指定的几个用值捕获，不能用&
指定 lambda 的返回类型：
必须使用尾置的返回类型，例如：
transform(vi.begin(), vi.end(),
[](int i) -> int
{ if (i < 0) return -i; else return i; });
参数绑定：
!!如果一个 lambda 的捕获列表为空，通常可以用一个函数来代替它。
标准库 bind 函数一般形式为
auto newCallable = bind(callable, arg_list);
newCallable 本身是个可调用对象，当调用它时，会调用 callable，并传递给它 arg_list 中的参数。
arg_list 中可能包含 _n，占据传递给 newCallable 的参数的“位置”。_1 为 newCallable 的第一个参数，_2为第二个参数。
bool check_size(const string &s, string::size_type sz){
return s.size() >= sz;
}
auto check6 = bind(check_size, _1, 6); //check6是一个可调用对象
占位符出现在参数列表第一个位置，且只有一个，表示 check6 的此参数对应 check_size 的第一个参数，并且 check6 只接受单一参数。
string s = "hello";
bool b1 = check6(s); // 调用 bind
！！将 lambda 表达式替换为 bind:
auto wc = find_if(words.begin(), words.end(),
bind(check_size, _1, sz));
placeholder 名字都在 std::placeholder 中，定义在头文件 functional 中
using namespace std::placeholder
bind 的参数也可以进行顺序改变，例如将 g(_1, _2) 绑定到 f(a, b, _2, c, _1) 可以改变参数的顺序。调用 g(X, Y) 会调用 f(a, b, Y, c, X)
！！利用这一点可以把 isShorter 改变成 isLonger。
迭代器
- 插入迭代器(insert iterator)
- 流迭代器(stream iterator)
- 反向迭代器(reverse iterator)
- 移动迭代器(move iterator)
插入迭代器
插入迭代器是一种容器适配器，接受一个容器，生成一个迭代器。
it = t 在当前位置插入值 t，具体调用的函数依赖于插入迭代器的不同种类。
有三种插入迭代器，差异在于元素插入的位置：
back_insertrer: 使用 push_back 的迭代器
front_inserter: 使用 push_front 的迭代器
inserter: 使用 insert 的迭代器
使用迭代器：
auto it = inserter(c, iter); // 创建一个插入迭代器 it
*it = val; // 在 iter 前插入 val
//等价于下面的代码
it = c.insert(it, val);
++it;
auto it = front_inserter(c);
*it = val; // c.push_front(val);
iostream 迭代器
iostream 不是容器，但是也定义了迭代器。
istream_iterator 读取输入流
ostream_iterator 向输出流写数据
从标准输入读取数据的例子：
istream_iterator<int> in_iter(cin);
istream_iterator<int> eof; // 尾后迭代器
while(in_iter != eof){
vec.push_back(*in_iter++);
}
！！ 将输入数据求和：
istream_iterator<int> in(cin), eof;
cout<< accumulate(in, eof, 0) << endl;
ostream_iterator 可以提供一个(可选的)第二参数，是一个C风格的字符串，每次输出后都会打印这个字符串。输出值的序列：
ostream_iterator<int> out_iter(cout, " ");
for(auto e : vec)
*out_iter++ = e; // 等价于直接写 out_iter = e; * 和 ++ 没有任何作用
cout << endl;
// 或者直接调用 copy
copy(vec.begin(), vec.end(), out_iter);
cout << endl;
！！*out ++out out++ 这些运算符是存在的，但是不会对 out 做任何事情；而输入流的迭代器，这些运算符是有效的，可以返回流里的值、读取下一个。
反向迭代器
++it会移动到前一个元素，--it会移动到后一个元素。
逆序打印一个数组：
for(auto r_iter = vec.crbegin(); r_iter != vec.crend(); ++r_iter){
cout << *r_iter;
}
sort本身是递增顺序，可以使用反向迭代器获得递减：
sort(vec.rbegin(), vec.rend())
！！不可以在 forward_list 或一个流迭代器上创建反向迭代器。
！！反向迭代器的目的是表示元素范围，这个范围是不对称的，左闭右开。所以当从一个普通迭代器初始化一个反向迭代器时，结果指向的和原迭代器不是同一个元素。
泛型算法结构
迭代器分为5个类型：
:-:|:-:
输入迭代器|只读，不写；单遍扫描，只能递增
输出迭代器|只写，不读；单遍扫描，只能递增
前向迭代器|可读写；多遍扫描，只能递增
双向迭代器|可读写；多遍扫描，可递增递减
随机访问迭代器|可读写；多遍扫描，支持全部迭代器运算
算法的 _if 版本：接受一个谓词替代元素值。
find(beg, end, val);
find_if(beg, end, pred); // 查找第一个令 pred 为真的元素
拷贝元素的版本 _copy ：
reverse(beg, end);
reverse_copy(beg, end, dest); // 元素逆序拷贝到 dest 中
链表的特殊操作
因为存储形式的不同，list 和 forward_list 类型定义了几个不同的算法。
:-:|:-:
lst.merge(lst2)| 将来自 lst2 的元素合并入 lst。两个list都必须是有序的
lst.merge(lst2, comp) | 元素将从 lst2 中删除，合并之后 lst2 为空
lst.remove(val) | 调用 erase 删除每一个 ==val 的元素
lst.remove_if(pred)|或使一元谓词为真的每个元素
lst.reverse() | 翻转 lst
lst.sort() | 使用 < 或给定比较操作排序
lst.sort(comp)|
lst.unique()| 删除同一个词的连续拷贝
lst.unique(pred)| 按给定谓词删除连续拷贝
splice 算法：
lst.splice(args);
lst.splice_after(args);
//args = :
(p, lst2) // p 是一个指向 lst 的迭代器，将 lst2 中所有元素移动到 p 之前的位置
(p, lst2, p2) // 将 p2 指向的元素移动到 lst 中， _after版本则是将 p2 之后的移动到 lst 中
(p, lst2, b, e) // b e 表示 lst2 中的合法范围。将给定范围移动到 lst 中
11.关联容器
map: 关键字-值(key-value)对，关联数组
set: 支持高效的关键字查询操作，只包含一个关键字
有序集合：
:-:|:-:
map | 关联数组；保存关键字-值对
set | 关键字即值，只保存关键字的容器
multimap | 关键字可重复出现的map
multiset | 关键字可重复出现的set
无序集合：unordered_ 版本，都是哈希组织的
定义关联容器
map<string, size_t> word_count; // 空容器
set<string> exclude = {"the", "an", "a", "A", "The"}; // 列表初始化
map<string, string> authors = { {"Joyce", "James"},
{"Austen", "Jane"} };
用一个关键字-值对去初始化，{key, value}
有序容器的关键字类型
可以提供一个自定义的操作来代替 < 运算符，但是必须是严格弱序的
- 两个关键字不能同时“小于等于”对方
- 如果 k1 “小于等于” k2 ，且 k2 “小于等于” k3，那么 k1 必须“小于等于” k3
- 如果存在两个关键字，任何一个都不“小于等于”另一个，那么这两个关键字是“等价”的，“等价”的关键字之间必须能传递等价性
pair类型
pair类型定义在头文件 utility 中，保存两个数据成员，类似容器，它是一个用来生成特定类型的模板。
pair<string, string> anon;
pair<string, size_t> word_count;
pair<string, vector<int>> line; // 默认进行值初始化
pair的操作：
pair<T1, T2> p; // 值初始化
pair<T1, T2> p(v1, v2);
pair<T1, T2>p = {v1, v2}; // 等价于上一句
make_pair(v1, v2); // 返回一个 pair
p.first, p.second;
// 关系运算符
p1 == p2; // 当 first 和 second 分别相等才为真
比较运算： 只有当 p1.first < p2.first || !(p2.first < p1.first) && p1.second < p2.second 成立时 p1 < p2 才为真。即先比较 first，如果相等时再比较 second。
// < 运算符：
return (_Left.first < _Right.first ||
!(_Right.first < _Left.first) && _Left.second < _Right.second);
关联容器的操作
额外的类型别名：
key_type 关键字类型
mapped_type 每个关键字关联的类型，只适用于 map
value_type 对于 set ，与 key_type 相同；对于 map ，为 pair<const key_type, mapped_type>
关键字部分是 const 的，因为不能改变 key 的值！！
map 的迭代器解引用得到的是一个 pair ！！
set 的迭代器是 const 的，虽然有 iterator 和 const_iterator 类型，但是都不能修改。
！！由于关联容器的关键字是 const 的，所以一般不对关联容器用泛型算法。查找操作一般用关联容器自己定义的 find
添加元素：
vector<int> ivec = {2, 4, 6, 8, 2, 4, 6};
set<int> set2;
set2.insert(ivec.cbegin(), ivec.cend()); // 插入了 2 4 6 8
set2.insert({1, 3, 5, 7, 1}); // 现在有 12345678
word_map.insert({word, 1}); // 插入的必须是一个 pair 类型
word_map.insert(make_pair(word, 1));
word_map.insert(pair<string, size_t>(word, 1));
word_map.insert(map<string, size_t>::value_type(word, 1));
添加单一元素的 insert 和 emplace 版本返回一个 pair ，告诉我们插入操作是否成功。这个 pair 返回值的 first 是一个迭代器，指向给定关键字的元素； second 成员是一个 bool 值，指出元素是插入成功还是已经存在于容器中。如果已经在容器中，则 insert 什么也不做，且返回值的 second 成员是一个 false。
// 插入一个元素，关键字为 word，值为 1
auto ret = word_count.insert({word, 1});
if (!ret.second) // 插入失败则什么都不做
++ret.first->second; // 等价于 ++((ret.first)->second);
ret 的类型是： pair<map<string, size_t>::iterator, bool>
删除元素:
erase 操作，接受一个 key_type 参数。也可以按迭代器删除。
对于保存不重复关键字的容器，erase 的返回值总是 0 或 1。 0 表示想要删除的元素不在容器中，1 表示成功删除元素；对于保存重复关键字的容器，返回值是一个 size_type 值，指出删除元素的数量。
下标操作：
set、multimap、unordered_multimap 不可以使用下标操作。const 的 map 也不可以，因为下标操作返回的是左值！
c[k] // 返回关键字为 k 的元素，如果 k 不在 c 中，则添加一个关键字为 k 的元素并进行值初始化
c.at(k) // 访问关键字为 k 的元素，带参数检查；若不在 c 中，抛出一个 out_of_range 异常
访问元素：
find 和 count：find 返回指向第一个关键字为 k 的元素的迭代器，找不到则返回尾后迭代器。 count 不仅是查找，返回关键字为 k 的元素的数量。
c.find(k); // 返回的是迭代器
c.count(k); // 返回的是数量
c.lower_bound(k); // 返回第一个关键字不小于 k 的元素的迭代器 >=
c.upper_bound(k); // 返回第一个关键字大于 k 的元素的迭代器 >
c.equal_range(k); // 返回一个迭代器 pair ，表示关键字等于 k 的元素的范围 ==
在 multi 版本的关联容器中，相等的关键字的元素是相邻存储的。
三种方法在 multimap 中输出所有给定关键字的 second：
1、count + find 的方法
string search_item("Alain de Botton"); // 要搜索的 key
auto entries = authors.count(search_item); // 元素的数量
auto iter = authors.find(search_item); // 指向第一个元素的迭代器
while(entries){
cout<< iter->second << endl;
++iter;
--entries;
}
2、迭代器方法，结果的范围是 [lower_bound, upper_bound)
for(auto beg = authors.lower_bound(search_item), end = authors.upper_bound(search_item);
beg != end; ++beg){
cout << beg->second << endl;
}
3、equal_range 函数，返回值和lower、upper_bound的返回值是一样的。
[equal_range.first, equal_range.second)
for(auto pos = authors.equal_range(search_item);
pos.first != pos.second; ++pos.first){
cout << pos.first->second << endl;
}
无序容器
关键字没有明显的序关系的情况下，无序容器是非常有用的。通常无序容器更为简单，也具有更好的性能。
！！如果关键字类型固有就是无序的，或者性能测试发现问题可以用哈希技术解决，就可以使用无序容器。
无序容器在存储上组织为一组桶，每个桶保存 0 或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，先计算元素的哈希值，它指出应该搜索那个桶。无序容器的性能依赖于哈希函数的质量和桶的数量和大小。
桶的管理操作：
:-:|:-:
桶接口|
c.bucket_count()| 正在使用的桶的数目
c.max_bucket_count() | 能容纳的最多的桶的数目
c.bucket_size(n) | 第 n 个桶有多少个元素
c.bucket(k) | 关键字为 k 的元素在哪个桶中
桶迭代|
local_iterator| 访问桶中元素的迭代器类型
const_local_iterator | 桶迭代器的 const 版本
c.begin(n), c.end(n), c.cbegin(n), c.cend(n) | 桶 n 的首元素迭代器和尾后迭代器
哈希策略|
c.load_factor()|每个桶的平均元素数量，返回 float 值
c.max_load_factor() | c 试图维护的平均桶大小，返回 float 值
c.rehash(n) | 重新存储，使得 bucket_count>=n,且bucket_count>size/max_load_factor
c.reserve(n) | 重新存储，使得 c 可以保存 n 个元素且不必 rehash
12.动态内存
目前的程序都使用静态内存或栈内存。对于栈对象，仅在其定义的程序块运行时才存在; static 对象在使用之前分配，在程序结束时销毁。
除了静态内存和栈内存，还有一个自由空间(或称为堆 heap)，用于存储动态分配的对象。
通过一对运算符 new 和 delete 来管理动态内存。
c++11的两种智能指针： shared_ptr 允许多个指针指向同一个对象； unique_ptr “独占”所指向的对象； weak_ptr 弱引用。三个都定义在 memory 头文件中。
shared_ptr类
shared_ptr 也是一个模板类，
shared_ptr<string> p1;
shared_ptr<list<int>> p2;
shared_ptr 和 unique_ptr 都支持的操作：
shared_ptr<T> sp; unique_ptr<T> up; // 空智能指针
p // 将指针用作条件判断，若 p 指向一个对象则为 true
*p // 解引用
p->mem // (*p).mem
p.get() // 返回 p 中保存的指针，如果释放了其对象，则返回的指针所指向的对象也消失了
swap(p, q); p.swap(q); // 交换 p 和 q 中的指针
shared_ptr 独有的操作：
make_shared<T> (args) // 返回一个 shared_ptr，指向一个动态分配的类型为 T 的对象
shared_ptr<T> p(q) // p 是 q 的拷贝，q 中的指针必须能转换成 T*，此操作会递增 q 中的计数器。
p = q // 赋值语句，会递减 q 的引用计数，递增 p 的引用计数。若 p 的引用计数变为 0 ，则将其管理的原内存释放
p.unique() // 若 p.use_count() 为 1，返回 true；否则返回 false
p.use_count() // p 共享对象的智能指针数量，这句比较慢，主要用于调试
最安全的分配和使用动态内存的方法是使用 make_shared 函数。
每个 shared_ptr 都有一个引用计数，每当发生拷贝时，计数器都会递增；当给 shared_ptr 赋一个新值或是 shared_ptr 被销毁时，计数器就会递减。一旦一个 shared_ptr 的计数器变为 0 ，它就会自动释放自己所管理的对象。
析构函数(destructor)完成销毁工作。
！！如果把 shared_ptr 存放于一个容器之中，而后不再需要全部元素，只使用一部分，要记得把不需要的那些 erase 删除掉。
使用动态内存的三个原因：
- 程序不知道自己要使用多少个对象
- 程序不知道所需对象的准确类型
- 程序需要在多个对象间共享数据
！！最常见的原因是允许多个对象共享相同的状态
直接管理内存
new 分配内存， delete 释放内存。
new 无法为其分配的对象命名，而是返回一个指向该对象的指针，一般情况下，动态分配的对象是默认初始化的。
int *pi = new int;
直接初始化方式：
int *pi = new int(1024); // pi 指向的对象值是 1024
string *ps = new string(10, '9'); // *ps 为 "9999999999"
vector<int> *pv = new vector<int>{0,1,2,3,4,5}; // 列表初始化
值初始化方式，在类型名之后跟一对空括号的方式：
string *ps1 = new string; // 默认初始化为空 string
string *ps2 = new string(); // 值初始化为空 string
int *pi1 = new int; // 默认初始化， *pi1 未定义
int *pi2 = new int(); // 值初始化，*pi2 为 0
！！对于内置类型，值初始化的对象有着良好定义的值，而默认初始化的对象的值则是未定义的。
也可以用 auto 自动推断：
auto p1 = new auto(obj); // p1 指向一个与 obj 类型相同的对象，并用 obj 进行初始化
动态分配的 const 对象：new 返回的是一个指向 const 的指针（底层cosnt）
const int *pci = new const int(1024);
内存耗尽：会返回一个 bad_alloc 异常，可以阻止它抛出这个异常。
int *p1 = new int; // 如果分配失败，new 抛出 std::bad_alloc
int *p2 = new (nothrow) int; // 如果失败，new 返回一个空指针
！！由内置指针管理的动态内存，在被显式释放前一直都会存在，不释放会内存泄漏。
指针被 delete 后，就变成空悬指针，指向一块曾经保存数据对象但是现在已经无效的内存的指针。可以将 p 再置为 nullptr
用 new 的返回值来初始化 shared_ptr
shared_ptr<int> p(new int(42)); // p 指向一个值为42的 int
！！不要把普通指针转化成智能指针，有可能导致指针被 delete 掉变成空悬指针。如果把一个普通指针交给了智能指针，就不要再继续用这个普通指针了。
！！get函数返回值是普通指针，永远不要用它给智能指针赋值，也不要 delete 掉这个普通指针
shared_ptr<int> p(new int(42));
int *q = p.get(); // 正确，但是使用时要注意不要释放 q 指向的内存
shared_ptr<int> qq = p.get(); // 错误，千万不要这么做！！！！！！
调用 reset 给智能指针赋一个新的值：
p = new int(1024); // 错误，不能将一个指针赋予 shared_ptr
p.reset(new int(1204)); // 正确，p 指向新的对象，更新引用计数，必要时会删除原来的对象
！！！改变底层对象的时候，最好结合 unique 一起用：
if (!p.unique())
p.reset(new string(*p)); // 我们不是唯一的用户；分配新的拷贝
*p += newVal; // 我们是唯一的用户，可以改变对象的值
注意以下几点：
- 不使用相同的内置指针值初始化(或 reset )多个智能指针
- 不 delete get() 返回的指针
- 不使用 get() 初始化或 reset 另一个智能指针
- 如果使用 get() 返回的指针，记住当最后一个对应的智能指针销毁后，它就无效了
- 如果使用智能指针管理的资源不是 new 动态分配的，记住传给他一个删除器
unique_ptr
和 shared_ptr 不同，没有类似的 make_share，在初始化时必须采用直接初始化的形式：
unique_ptr<double> p1; //可以指向一个 double 的 unique_ptr
unique_ptr<int> p2(new int(42)); // p2 指向一个值为 42 的 int
！！unique_ptr 不支持拷贝，也不支持赋值。
操作：
u.release(); u 放弃对指针的控制权，返回指针，将 u 置为空
u.reset(); 释放 u 指向的对象
u.reset(q); 释放 u ，如果提供了内置指针 q ，则会令 u 指向这个对象，否则置为空
虽然不能直接拷贝和赋值，但是可以用 release 和 reset 实现指针的所有权的交换：
unique_ptr<string> p2(p1.release()); // release 将 p1 置为空，所有权交给 p2
unique_ptr<string> p3(new string("Trex"));
p2.reset(p3.release()); // p3 交给了 p2，释放了原来 p2 指向的内存
调用 release 会切断智能指针和对象之间的联系，但是没有释放内存！！要记得用返回值 delete 掉：
auto p = p2.release(); // 直接 p2.release() 不会释放内存，会丢失指针
delete p;
！！我们可以拷贝或赋值一个将要被销毁的 unique_ptr ，例如从函数返回：在这种返回情况下，执行的是一种特殊的“拷贝”，可以允许这样拷贝 unique_ptr
unique_ptr<int> clone(int p) {
return unique_ptr<int>(new int (p));
}
// 或者返回一个局部对象的拷贝
unique_ptr<int> clone(int p) {
unique_ptr<int> ret(new int (p));
...
return ret;
}
动态数组
称 new T[] 分配的内存为“动态数组”，然而实际上这个数组并不可见，返回的是一个指针，并不是数组类型！！！
一些初始化方式：
int *pia = new int[10]; // 10 个未初始化的 int
int *pia2 = new int[10](); // 10 个值初始化为 0 的 int
int *pia3 = new int[10]{0, 1, 2, 3, 4}; // 列表初始化
可以动态分配一个长度任意的数组，长度甚至可以是 0,但是这样的动态分配的数组不能解引用。
释放动态数组，添加一个 [] ，数组中的元素按逆序销毁，先是最后一个，再依次往前。
delete p; // p 必须指向一个动态分配的对象或为空
delete [] pa; // pa 必须指向一个动态分配的数组或为空
！！指向数组的 unique_ptr，不支持成员访问运算符，点和箭头
unique_ptr<int[]> up(new int[10]);
up.release(); // 会自动调用 delete []
网友评论