8.IO库

IO类

三个头文件：

iostream 定义了用于读写流的基本类型

fstream 定义了读写命名文件的类型

sstream 定义了读写内存 string 对象的类型

可以添加一个 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 删除掉。

使用动态内存的三个原因：

1. 程序不知道自己要使用多少个对象
2. 程序不知道所需对象的准确类型
3. 程序需要在多个对象间共享数据

！！最常见的原因是允许多个对象共享相同的状态

直接管理内存

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;  // 我们是唯一的用户，可以改变对象的值

注意以下几点：

1. 不使用相同的内置指针值初始化(或 reset )多个智能指针
2. 不 delete get() 返回的指针
3. 不使用 get() 初始化或 reset 另一个智能指针
4. 如果使用 get() 返回的指针，记住当最后一个对应的智能指针销毁后，它就无效了
5. 如果使用智能指针管理的资源不是 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 []