导图社区 C＋＋第16章：string类和标准模板库
- 198
- 6
- 3
- 举报
C＋＋第16章：string类和标准模板库
《C Primer Plus》第十六章同步思维导图，主要介绍了string类、智能指针和标准模板库STL。其中前两者讲解较为详细，后者STL侧重于介绍与入门，具体的学习还需读者深入了解。
编辑于2021-01-20 23:24:19
- 相似推荐
- 大纲
第16章 string类和标准模板库
16.1 string类
16.1.1 构造字符串
1. string类构造函数
2. 程序说明
（1）初始化C-风格字符串
string one("Lottery Winner!");
（2）初始化重复字符
string two(20, '$');
（3）复制构造
string three(two);
（4）字符串拼接
one += " Oops!"; one += two; one += '!';
（5）赋值字符串
two = "Sorry! That was "; two = one; two = '?';
（6）默认构造空字符串
string four;
（7）复制字符串数组
char alls[] = "All's well that ends well"; string five(alls, 20);
（8）复制指定地址的字符串
string six(alls + 6, alls + 10); string seven(&five[6], &five[10]);
（9）复制string对象的部分内容
string eight(four, 7, 16);
3. C++11新增的构造函数
string(string&& str); 构造函数string（string&& str）类似于复制构造函数，导致新创建的string为str的副本。但与复制构造函数不同的是，它不保证将str视为const。这种构造函数被称为移动构造函数（move constructor）。在有些情况下，编译器可使用它而不是复制构造函数，以优化性能
16.1.2 string类输入
1. 方法
（1）C-风格字符串
cin >> info; // read a word
cin.getline(info, 100); // read a line, discard '\n'
cin.getline(info, 100, ':'); // read a line, discard ':'
':'为输入边界
cin.get(info, 100); // read a line, leave '\n' in queue
（2）string
cin >> stuff; // read a word
getline(cin, stuff); // read a line, discard '\n'
getline(cin, stuff, ':'); // read a line, discard ':'
':'为输入边界
2. 深入探讨
（1）string的输入限制
· string最大长度
string对象的最大允许长度由常量string::npos指定。这通常是最大的unsigned int值，因此对于普通的交互式输入，这不会带来实际的限制；但如果您试图将整个文件的内容读取到单个string对象中，这可能成为限制因素
· 程序使用内存量
（2）string版本的getline()
string版本的getline()函数从输入中读取字符，并将其存储到目标string中，直到发生下列三种情况之一： · 到达文件尾，在这种情况下，输入流的eofbit将被设置，这意味着方法fail()和eof()都将返回true； · 遇到分界字符（默认为\n），在这种情况下，将把分界字符从输入流中删除，但不存储它； · 读取的字符数达到最大允许值（string::npos和可供分配的内存字节数中较小的一个），在这种情况下，将设置输入流的failbit，这意味着方法fail()将返回true。
输入流对象有一个统计系统，用于跟踪流的错误状态。在这个系统中，检测到文件尾后将设置eofbit寄存器，检测到输入错误时将设置failbit寄存器，出现无法识别的故障（如硬盘故障）时将设置badbit寄存器，一切顺利时将设置goodbit寄存器
（3）string版本的>>输入
string版本的operator>>()函数的行为与此类似，只是它不断读取，直到遇到空白字符并将其留在输入队列中，而不是不断读取，直到遇到分界字符并将其丢弃。空白字符指的是空格、换行符和制表符，更普遍地说，是任何将其作为参数来调用isspace()时，该函数返回ture的字符
16.1.3 使用字符串
1. string.size()和string.length()
二者都返回字符串中的字符数。length()成员来自较早版本的string类，而size()则是为提供STL兼容性而添加的
2. string.find()
3. string.rfind()
查找子字符串或字符最后一次出现的位置
4. string.find_first_of() string.find_last_of()
find_first_of()方法在字符串中查找参数中任何一个字符首次出现的位置 find_last_of()方法的功能与此相同，只是它查找的是最后一次出现的位置
5. string.first_first_not_of() string.find_last_not_of()
find_first_not_of()方法在字符串中查找第一个不包含在参数中的字符 find_last_not_of()方法在字符串中查找最后一个不包含在参数中的字符
16.1.4 string还提供了哪些功能
1. string的内存分配
每当程序将一个字母附加到字符串末尾时将发生什么呢？不能仅仅将已有的字符串加大，因为相邻的内存可能被占用了。因此，可能需要分配一个新的内存块，并将原来的内容复制到新的内存单元中。如果执行大量这样的操作，效率将非常低，因此很多C++实现分配一个比实际字符串大的内存块，为字符串提供了增大空间。然而，如果字符串不断增大，超过了内存块的大小，程序将分配一个大小为原来两倍的新内存块，以提供足够的增大空间，避免不断地分配新的内存块
2. 一些方其他方法
（1）string.capacity()
返回当前分配给字符串的内存块的大小
（2）reserve()
请求内存块的最小长度
（3）string.c_str()
返回一个指向C-风格字符串的指针，该C-风格字符串的内容与用于调用c_str()方法的string对象相同。例如：open()方法要求使用一个C-风格字符串作为参数，可以用以下代码实现： fout.open(filename.c_str());
16.1.5 字符串种类
本节将string类看作是基于char类型的。事实上，正如前面指出的，string库实际上是基于一个模板类的： template < class charT, class traits = char _traits<charT>, class Allocator = allocator<charT> > basic_string { ... }; 模板basic_string有4个具体化，每个具体化都有一个typedef名称： typedef basic_string<char> string; typedef basic_string<wchar_t> wstring; typedef basic_string<char16_t> u16string; // C++11 typedef basic_string<char32_t> u32string; // C++11
16.2 智能指针模板类
概述
· 问题的提出
在申请动态内存分配时，往往容易疏忽而导致内存泄漏。而即使程序员能够做到有意识地释放内存，但在某些情况下由于某些语法的限制，也难以实现内存的释放： void remodel(std::string& str) { std::string* ps = new std::string(str); ... if (wired_thing()) throw exception(); str = *ps; delete ps; return; } 如上述代码，当出现异常时，由于ps将可能还会被使用，因此不方便直接释放，这又导致了一个问题：delete将不被执行，而又找不到合适释放内存的位置，因此也将可能导致内存泄漏
· 解决思路
如果ps有一个析构函数，该析构函数将在ps过期时释放它指向的内存。因此，ps的问题在于，它只是一个常规指针，不是有析构函数的类对象。如果它是对象，则可以在对象过期时，让它的析构函数删除指向的内存。这正是auto_ptr、unique_ptr和shared_ptr背后的思想。模板auto_ptr是C++98提供的解决方案，C++11已将其摒弃，并提供了另外两种解决方案。然而，虽然auto_ptr被摒弃，但它已使用了多年；同时，如果您的编译器不支持其他两种解决方案，auto_ptr将是唯一的选择
16.2.1 使用智能指针
1. 介绍（以auto_ptr为例）
（1）头文件
#include <memory>
（2）构造函数
template <class X> class auto_ptr { public: explicit auto_otr(X* p = 0) throw(); ... }
（3）创建auto_ptr
auto_ptr<double> pd(new double); // pd an auto_ptr to double auto_ptr<string> ps(new string); // ps an auto_ptr to string unique_ptr<double> pdu(new double); // pdu an auto_ptr to double shared_ptr<string> pss(new string); // pss an auto_ptr to string
2. 说明
（1）智能指针的显示转换
所有智能指针类都一个explicit构造函数，该构造函数将指针作为参数。因此不需要自动将指针转换为智能指针对象： shared_ptr<double> pd; double* p_reg = new double; pd = p_reg; // not allowed (implicit conversion) pd = shared_ptr<double> (p_reg); // allowed (explicit conversion) shared_ptr<double> pshared = p_reg; // not allowed (implicit conversion) shared_ptr<double> pshared(p_reg); // allowed (explicit conversion)
（2）使用与new搭配
对全部三种智能指针都应避免的一点： string vacation("I wandered lonely as a cloud."); shared_ptr<string> pvac(&vacation); // NO!!! pvac过期时，程序将把delete运算符用于非堆内存，这是错误的
16.2.2 有关智能指针的注意事项
概述
· 问题再现：智能指针的赋值问题
先来看下面的赋值语句： auto_ptr<string> ps(new string("I reigned lonely as a cloud.")); auto_ptr<string> vocation; vocation = ps; 如果ps和vocation仅仅是常规指针而没有加上任何新的处理，则两个指针将指向同一个string对象，程序最终将试图删除同一个对象两次 ———— 一次是ps过期时，另一次是vocation过期时，这明显是不允许的。因此，三种智能指针都提供了各自的解决办法
1. auto_ptr和unique_ptr解决策略
建立所有权（ownership）概念，对于特定的对象，只能有一个智能指针可拥有它，这样只有拥有对象的智能指针的构造函数会删除该对象。然后，让赋值操作转让所有权。但相比而言，unique_ptr的策略更严格
2. shared_ptr解决策略
创建智能更高的指针，跟踪引用特定对象的智能指针数。这称为引用计数（reference counting）。例如，赋值时，计数将加1，而指针过期时，计数将减1。仅当最后一个指针过期时，才调用delete
3. 新的问题
上述代码对于三种智能指针来说都可运行通过。但是如果加上一段代码，要求用ps对vacation赋值后ps仍有用处： auto_ptr<string> ps(new string("I reigned lonely as a cloud.")); auto_ptr<string> vocation; vocation = ps; *ps = ...; 那么这时，对于auto_ptr来说，程序会在运行阶段崩溃，因为ps指向的位置为空；对于unique_ptr来说，程序会在编译阶段报错；对于shared_ptr来说，程序能够正常运行
16.2.3 unique_ptr为何优于auto_ptr
概述
给出如下定义，使智能指针能够直接指向C-风格字符串： unique_ptr<string> demo(const char* s) { unique_ptr<string> temp(new string(s)); return temp; }
1. 能够识别非法赋值
对于下列代码： auto_ptr<string> p1(new string("auto")); auto_ptr<string> p2; p2 = p1; 程序在编译阶段不报错，在运行阶段崩溃，因为p1不再指向有效的数据。
对于下列代码： unique_ptr<string> p3(new string("auto")); unique_ptr<string> p4; p4 = p3; 程序在编译阶段会直接报错（unique_ptr使用了C++11新增的移动构造函数和右值引用来进行识别）
2. 允许临时对象的暂时存在
假设编写了一下代码： unique_ptr<string> ps; ps = demo("Uniquely special"); demo()返回一个临时unique_ptr，然后ps接管了原本归返回的unique_ptr所有的对象，而返回的unique_ptr被销毁。这没有问题，因为ps拥有了string对象的所有权。但这里的另一个好处是，demo()返回的 临时unique_ptr很快被销毁，没有机会使用它来访问无效的数据。换句话说，没有理由禁止这种赋值。神奇的是，编译器确实允许这种赋值！
总之，程序试图将一个unique_ptr赋给另一个时，如果源unique_ptr是个临时右值，编译器允许这样做；如果源unique_ptr将存在一段时间，编译器将禁止这样做
16.2.4 选择智能指针
1. 三种智能指针的析构函数
（1）unique_ptr
有使用new[]和delete[]的版本： std::unique_ptr<double[]> pda(new double(5)); // will use delete[] 即，可以用于指向数组类指针
（2）auto_ptr和shared_ptr
有使用new[]和delete[]的版本，只能与new配套使用。即，不能用于指向数组类指针
2. 使用原则
（1）使用shared_ptr
程序需要使用多个指向同一对象的指针，包括： · 使用辅助指针来进行数据处理 · 两个对象都包含指向第三个对象的指针 · STL容器包含指针 · ...
（2）使用unique_ptr
· 程序不需要使用多个指向同一对象的指针 · 函数按引用传递智能指针（按值传递相当于允许存在两个指向同一对象的智能指针）
3. unique_ptr的接管
在unique_ptr为右值时，可将其赋给shared_ptr，这与将一个unique_ptr赋给另一个需要满足的条件相同。在下面的代码中，make_int()的返回类型为unique_ptr<int>： unique_ptr<int> pup(make_int(rand() % 100)); // ok shared_ptr<int> spp(pup); // not allowed, pup is an lvalue shared_ptr<int> spr(make_int(rand() % 100)); // ok 模板shared_ptr包含一个显式构造函数，可用于将右值unique_ptr转换为shared_ptr。shared_ptr将接管原来归unique_ptr所有的对象
16.3 标准模板库
16.3.1 模板类vector
1. 介绍
在计算中，矢量（vector）对应数组，而不是第11章介绍的数学矢量。计算矢量存储了一组可随机访问的值，即可以使用索引来直接访问矢量的第10个元素，而不必首先访问前面第9个元素。所以vector类可以创建vector对象，将一个vector对象赋给另一个对象，使用[]运算符来访问vector元素。要使类成为通用的，应 将它设计为模板类，STL正是这样做的 —— 在头文件vector（以前为vector.h）中定义了一个vector模板
2. 存储方式
vector模板使用动态内存分配
3. 分配器
与string类相似，各种STL容器模板都接受一个可选的模板参数，该参数指定使用哪个分配器对象来管理内存。例如，vector模板的开头与下面类似： template < class T, class Allocator = allocator<T> > class vector { ... }; 如果省略该模板参数的值，则容器模板将默认使用allocator<T>类。这个类使用new和delete
16.3.2 可对矢量执行的操作
1. STL通用方法
（1）vector.size()
返回容器中元素数目
（2）vector.swap()
交换两个容器的内容
（3）vector.begin()
返回一个指向容器中第一个元素的迭代器
（4）vector.end()
返回一个表示超过容器尾的迭代器
（5）vector::iterator
每个容器类都定义了一个合适的迭代器，该迭代器的类型是一个名为iterator的typedef，其作用域为整个类。例如，要为vector的double类型规范声明一个迭代器，可以这样做： vector<double>::iterator pd; // pd an iterator
2. vector特有方法
（1）vector.push_back()
将元素添加到矢量末尾。这样做时，它将负责内存管理，增加矢量的长度，使之能够容纳新的成员。这意味着可以编写这样的代码： vector<double> scores; // create an empty vector double temp; while (cin >> temp && temp >= 0) scores.push_back(temp); cout << "You entered " << scores.size() << " scores.\n"; 每次循环都给scores对象增加一个元素。在编写或运行程序时，无需了解元素的数目。只要能够取得足够的内存，程序就可以根据需要增 加scores的长度
（2）vector.erase()
erase()方法删除矢量中给定区间的元素。它接受两个迭代器参数，这些参数定义了要删除的区间。了解STL如何使用两个迭代器来定义区间至关重要。第一个迭代器指向区间的起始处，第二个迭代器位于区间终止处的后一个位置。例如，下述代码删除第一个和第二个元素，即删除begin()和begin() + 1指向的元素（由于vector提供了随机访问功能，因此vector类迭代器定义了诸如begin() + 2等操作）： scores.erase(scores.begin(), scores.begin() + 2);
（3）vector.insert()
insert()方法的功能与erase()相反。它接受3个迭代器参数，第一个参数指定了新元素的插入位置，第二个和第三个迭代器参数定义了被插入区间，该区间通常是另一个容器对象的一部分。例如，下面的代码将矢量new_v中除第一个元素外的所有元素插入到old_v矢量的第一个元素前面： vector<int> old_v; vector<int> new_v; ... old_v.insert(old_v.begin(), new_v.begin() + 1, new_v.end());
16.3.3 对矢量可执行的其他操作
概述
STL从更广泛的角度定义了非成员（non-member）函数来执行这些操作，即不是为每 个容器类定义find()成员函数，而是定义了一个适用于所有容器类的非成员函数find()。这种设计理念省去了大量重复的工作
1. for_each()
for_each()函数可用于很多容器类，它接受3个参数。前两个是定义容器中区间的迭代器，最后一个是指向函数的指针（更普遍地说，最后一个参数是一个函数对象，函数对象将稍后介绍）。for_each()函数将被指向的函数应用于容器区间中的各个元素。被指向的函数不能修改容器元素的值。可以用for_each()函数来代替for循环。例如，可以将代码： vector<Review>::iterator pr; for (pr = books.begin(); pr != books.end(); pr++) ShowReview(*pr); 替换为： for_each(books.begin(), books.end(), ShowReview);
2. Random_shuffle()
Random_shuffle()函数接受两个指定区间的迭代器参数，并随机排列该区间中的元素。例如，下面的语句随机排列books矢量中所有元素： random_shuffle(books.begin(), books.end()); 与可用于任何容器类的for_each不同，该函数要求容器类允许随机访问，vector类可以做到这一点
3. sort()
sort()函数也要求容器支持随机访问。该函数有两个版本，第一个版本接受两个定义区间的迭代器参数，并使用为存储在容器中的类型元素定义的<运算符，对区间中的元素进行操作。例如，下面的语句按升序对coolstuff的内容进行排序，排序时使用内置的<运算符对值进行比较： vector<int> coolstuff; ... sort(coolstuff.begin(), coolstuff.end()); 如果容器元素是用户定义的对象，则要使用sort()，必须定义能够处理该类型对象的operator<()函数
如果想按降序或是按rating排序，该如何办呢？可以使用另一种格式的sort()。它接受3个参数，前两个参数也是指定区间的迭代器，最后一个参数是指向要使用的函数的指针（函数对象），而不是用于比较的operator<()。返回值可转换为bool，false表示两个参数的顺序不正确。下面是一个例子： bool WorseThan(const Review& r1, const Review& r2) { if (r2.rating < r2.rating) return true; else return false; } 有了这个函数后，就可以使用下面的语句将包含Review对象的books矢量按rating升序排列： sort(books.begin(), books.end(), WorseThan);
16.3.4 基于范围的for循环（C++11）
在这种for循环中，括号内的代码声明一个类型与容器存储的内容相同的变量，然后指出了容器的名称。接下来，循环体使用指定的变量依次访问容器的每个元素。例如，对于下述语句： for_each(books.begin(), books.end(), ShowReview); 可将其替换为下述基于范围的for循环： for (auto X : books) ShowReview(x); 不同于for_each()，基于范围的for循环可修改容器的内容，诀窍是指定一个引用参数。例如，假设有如下函数： void InflateReview(Review& r) { r.rating++; } 可使用如下循环对books的每个元素执行该函数： for (auto& x : books) InflateReview(x);
16.6 算法
16.6.1 算法组
（1）非修改式序列操作（<algorithm>）
非修改式序列操作对区间中的每个元素进行操作。这些操作不修改容器的内容。例如，find()和for_each()就属于这一类
（2）修改式序列操作（<algorithm>）
修改式序列操作也对区间中的每个元素进行操作。然而，顾名思义，它们可以修改容器的内容。可以修改值，也可以修改值的排列顺序。transform()、random_shuffle()和copy()属于这一类
（3）排序和相关操作（<algorithm>）
排序和相关操作包括多个排序函数（包括sort()）和其他各种函数，包括集合操作
（4）通用数字运算（<numeric>）
数字操作包括将区间的内容累积、计算两个容器的内部乘积、计算小计、计算相邻对象差的函数。通常，这些都是数组的操作特性，因此vector是最有可能使用这些操作的容器
16.6.2 算法的通用特征(*)
16.6.3 STL和string类
string类虽然不是STL的组成部分，但设计它时考虑到了STL。例如，它包含begin()、end()、rbegin()和rend()等成员，因此可以使用STL接口
16.6.4 函数和容器方法
有时可以选择使用STL方法或STL函数。通常方法是更好的选择。首先，它更适合于特定的容器；其次，作为成员函数，它可以使用模板类的内存管理工具，从而在需要时调整容器的长度
16.5 函数对象
概述
· 函数符介绍
很多STL算法都使用函数对象——也叫函数符（functor）。函数符是可以以函数方式与()结合使用的任意对象。这包括函数名、指向函数的指针和重载了()运算符的类对象（即定义了函数operator()()的类）。例如，可以像这样定义一个类： class Linear { private: double slope; double y0; public: Linear(double s1_ = 1, double y_ = 0) : slope(s1_), y0(y_) {} double operator()(double x) { return y0 + slope * x; } }; 这样，重载的()运算符将使得能够像函数那样使用Linear对象： Linear f1; Linear f2(2.5, 10.0); double y1 = f1(12.5); // right-hand side is f1.operatot()(12.5) double y2 = f2(0.4); 其中y1将使用表达式0 + 1 * 12.5来计算，y2将使用表达式10.0 + 2.5 * 0.4来计算。在表达式y0 + slope * x中，y0和slope的值来自对象的构造函数，而x的值来自operator()()的参数
· STL中有关函数符的参数声明
如何声明第3个参数呢？不能把它声明为函数指针，因为函数指针指定了参数类型。由于容器可以包含任意类型，所以预先无法知道应使用哪种参数类型。STL通过使用模板解决了这个问题。for_each的原型看上去就像这样： template<class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f); ShowReview()的原型如下： void ShowReview(const Review&); 这样，标识符ShowReview的类型将为void(*)(const Review &)，这也是赋给模板参数Function的类型。对于不同的函数调用，Function参数可以表示具有重载的()运算符的类类型。最终，for_each()代码将具有一个使用f()的表达式。在ShowReview()示例中，f是指向函数的指针，而f()调用该函数。如果最后的for_each()参数是一个对象，则f()将是调用其重载的()运算符的对象
16.5.1 函数符概念
1. 函数符的概念
（1）生成器
不用参数就可以调用的函数符
（2）一元函数
用一个参数可以调用的函数符
（3）二元函数
用两个参数可以调用的函数符
（4）谓词
返回bool值的一元函数
（5）二元谓词
返回bool值的二元函数
2. 举例说明
· sort()
将二元谓词作为其第3个参数： bool WorseThan(const Review& r1, const Review& r2); ... sort(books.begin(), books.end(), WorseThan);
· remove_if()
list模板有一个将谓词作为参数的remove_if()成员，该函数将谓词应用于区间中的每个元素，如果谓词返回true，则删除这些元素。下面的代码删除链表three中所有大于100的元素： bool tooBig(int n) { return n > 100; } list<int> scores; ... scores.remove_if(tooBig);
3. 双参转单参
假设已经有了一个接受两个参数的模板函数： template <class T> bool tooBig(const T& val, const T& lim) { return val > lim; } 则可以使用类将它转换为单个参数的函数对象： template <class T> class TooBig2 { private: T cutoff; public: TooBig2(const T& t) : cutoff(t) {} bool operator()(const T& v) { return toooBig<T>(v, cutoff); } }; 即可以这样做： TooBig2<int> tB100(100); int x; cin >> x; if (tB100(x)) // same as if (tooBig(x, 100)) ...
16.5.2 预定义的函数符
1. transform()
· 第一个版本接受4个参数，前两个参数是指定容器区间的迭代器，第3个参数是指定将结果复制到哪里的迭代器，最后一个参数是一个函数符，它被应用于区间中的每个元素，生成结果中的新素。例如，请看下面的代码： const int LIM = 5; double arr1[LIM] = { 36, 39, 42, 45, 48 }; vector<double> gr8(arr1, arr1 + LIM); ostream_iterator<double, char> out(cout, " "); transform(gr8.begin(), gr8.end(), out, sqrt); 上述代码计算每个元素的平方根，并将结果发送到输出流。目标迭代器可以位于原始区间中。例如，将上述示例中的out替换为gr8.begin()后，新值将覆盖原来的值。很明显，使用的函数符必须是接受单个参数的函数符
· 第2种版本使用一个接受两个参数的函数，并将该函数用于两个区间中元素。它用另一个参数（即第3个）标识第二个区间的起始位置。例如，如果m8是另一个vector<double>对象，mean（double，double）返回两个值的平均值，则下面的的代码将输出来自gr8和m8的值的平均值： transform(gr8.begin(), gr8.end(), m8.begin(), out, mean);
2. 完成内置运算的函数符
头文件functional（以前为function.h）定义了多个模板类函数对象，其中包括plus<>()。可以用plus<>类来完成常规的相加运算： #include <functional> ... plus<double> add; // create a plus<double> object double y = add(2.2, 3.4); // using plus<double>::operator()() 它使得将函数对象作为参数很方便： transform(gr8.begin(), gr8.end(), m8.begin(), out, plus<double>()); 这里，代码没有创建命名的对象，而是用plus<double>构造函数构造了一个函数符，以完成相加运算
3. STL定义的函数符
16.5.3 自适应函数和函数适配器（*）
16.4 泛型编程
16.4.1 为何使用迭代器
1. 介绍
理解迭代器是理解STL的关键所在。模板使得算法独立于存储的数据类型，而迭代器使算法独立于使用的容器类型。因此，它们都是STL通用方法的重要组成部分。 泛型编程旨在使用同一个find函数来处理数组、链表或任何其他容器类型。即函数不仅独立于容器中存储的数据类型，而且独立于容器本身的数据结构。模板提供了存储在容器中的数据类型的通用表示，因此还需要遍历容器中的值的通用表示，迭代器正是这样的通用表示
2. 迭代器应具备的特征
（1）能够通过访问其引用的值：*p
（2）能够进行迭代器之间的赋值：p = q
（3）能够有迭代器之间的比较：p == q和p != q
（4）能够遍历容器的所有元素：++p和p++
3. 容器与迭代器
· 首先，每个容器类（vector、list、deque等）定义了相应的迭代器类型。对于其中的某个类，迭代器可能是指针；而对于另一个类，则可能是对象。不管实现方式如何，迭代器都将提供所需的操作，如*和++（有些类需要的操作可能比其他类多）。
· 其次，每个容器类都有一个超尾标记，当迭代器递增到超越容器的最后一个值后，这个值将被赋给迭代器。每个容器类都有begin()和end()方法，它们分别返回一个指向容器的第一个元素和超尾位置的迭代器。每个容器类都使用++操作，让迭代器从指向第一个元素逐步指向超尾位置，从而遍历容器中的每一个元素
4. 良好的编程风格
实际上，作为一种编程风格，最好避免直接使用迭代器，而应尽可能使用STL函数（如for_each()）来处理细节。也可使用C++11新增的基于范围的for循环： for (auto x : scores) cout << x << endl;
16.4.2 迭代器类型
概述
不同的算法对迭代器的要求也不同。例如，查找算法需要定义++运算符，以便迭代器能够遍历整个容器；它要求能够读取数据，但不要求能够写数据（它只是查看数据，而并不修改数据）。而排序算法要求能够随机访问，以便能够交换两个不相邻的元素。如果iter是一个迭代器，则可以通过定义+运算符来实现随机访问，这样就可以使用像iter + 10这样的表达式了。另外，排序算法要求能够读写数据
1. 输入迭代器
· p++、++p
能够遍历容器的所有元素
· *p（读取）
可以读取容器值
注意： 并不能保证输入迭代器第二次遍历容器时，顺序不变。输入迭代器被递增后，也不能保证其先前的值仍然可以被解除引用。输入迭代器是单向迭代器，可以递增，但不能倒退
2. 输出迭代器
· p++、++p
能够遍历容器的所有元素
· *p（写入）
可以写入容器值
3. 正向迭代器
· p++、++p
能够遍历容器的所有元素，且每次遍历顺序相同
· *p
可以读写容器值，并且可以对上一次的迭代器解除引用（如果保存了的话）
4. 双向迭代器
· p++、++p p--、--p
能够遍历容器的所有元素，且每次遍历顺序相同
· *p
可以读写容器值，并且可以对上一次的迭代器解除引用（如果保存了的话）
5. 随机访问迭代器
· p++、++p p--、--p
能够遍历容器的所有元素，且每次遍历顺序相同
· *p
可以读写容器值，并且可以对上一次的迭代器解除引用（如果保存了的话）
· p[n]、p +/- n p +=/-= n
可以随机访问容器值
16.4.3 迭代器层次结构
各种迭代器的类型并不是确定的，而只是一种概念性描述
16.4.4 概念、改进和模型
概述
· 概念
正向迭代器是一系列要求，而不是类型。所设计的迭代器类可以满足这种要求，常规指针也能满足这种要求。STL算法可以使用任何满足其要求的迭代器实现。STL文献使用术语概念（concept）来描述一系列的要求
· 改进
概念可以具有类似继承的关系。例如，双向迭代器继承了正向迭代器的功能。然而，不能将C++继承机制用于迭代器。例如，可以将正向迭代器实现为一个类，而将双向迭代器实现为一个常规指针。因此，对C++而言，这种双向迭代器是一种内置类型，不能从类派生而来。然而，从概念上看，它确实能够继承。有些STL文献使用术语改进（refinement）来表示这种概念上的继承，因此，双向迭代器是对正向迭代器概念的一种改进
· 模型
概念的具体实现被称为模型（model）。因此，指向int的常规指针是一个随机访问迭代器模型，也是一个正向迭代器模型，因为它满足该概念的所有要求
1. 将指针用作迭代器
（1）说明
迭代器是广义指针，而指针满足所有的迭代器要求。迭代器是STL算法的接口，而指针是迭代器，因此STL算法可以使用指针来对基于指针的非STL容器进行操作
（2）STL函数使用指针
· sort()
STL算法可以使用指针来对基于指针的非STL容器进行操作。例如，可将STL算法用于数组。假设Receipts是一个double数组，并要按升序对它进行排序： const int SIZE = 100; double Receipts[SIZE]; STL sort()函数接受指向容器第一个元素的迭代器和指向超尾的迭代器作为参数。&Receipts[0]（或Receipts）是第一个元素的地址，&Receipts[SIZE]（或Receipts + SIZE）是数组最后一个元素后面的元素的地址。因此，下面的函数调用对数组进行排序： sort(Receipts, Receipts + SIZE);
· copy()
有一种算法（名为copy()）可以将数据从一个容器复制到另一个容器中。这种算法是以迭代器方式实现的，所以它可以从一种容器到另一种容器进行复制，甚至可以在数组之间复制，因为可以将指向数组的指针用作迭代器。 int casts[10] = {6, 7, 2, 9, 4, 11, 8, 7, 10, 5}; vector<int> dice[10]; copy(casts, casts + 10, dice.begin()); // copy array to vector copy()的前两个迭代器参数表示要复制的范围，最后一个迭代器参数表示要将第一个元素复制到什么位置。前两个参数必须是（或最好是）输入迭代器，最后一个参数必须是（或最好是）输出迭代器。Copy()函数将覆盖目标容器中已有的数据，同时目标容器必须足够大，以便能够容纳被复制的元素。因此，不能使用copy()将数据放到空矢量中
· ostream_iterator
通过包含头文件iterator（以前为iterator.h）并作下面的声明来创建这种迭代器： #include <iterator> ... ostream_iterator<int, char> out_iter(cout, " "); out_iter迭代器现在是一个接口，让您能够使用cout来显示信息。第一个模板参数（这里为int）指出了被发送给输出流的数据类型；第二个模板参数（这里为char）指出了输出流使用的字符类型（另一个可能的值是wchar_t）。构造函数的第一个参数（这里为cout）指出了要使用的输出流，它也可以是用于文件输出的流；最后一个字符串参数是在发送给输出流的每个数据项后显示的分隔符。
可以这样使用迭代器： *out_iter++ = 15; // works like cout << 15 << " "; 对于常规指针，这意味着将15赋给指针指向的位置，然后将指针加1。但对于该ostream_iterator，这意味着将15和由空格组成的字符串发送到cout管理的输出流中，并为下一个输出操作做好了准备。可以将copy()用于迭代器，如下所示： copy(dice.begin(), dice.end(), out_iter); // copy vector to output stream 这意味着将dice容器的整个区间复制到输出流中，即显示容器的内容。
· istream_iterator
iterator头文件还定义了一个istream_iterator模板，使istream输入可用作迭代器接口。它是一个输入迭代器概念的模型，可以使用两个istream_iterator对象来定义copy()的输入范围： copy(istream_iterator<int, char>(cin), istream_iterator<int, char>(), dicce.begin()); 与ostream_iterator相似，istream_iterator也使用两个模板参数。第一个参数指出要读取的数据类型，第二个参数指出输入流使用的字符类型。使用构造函数参数cin意味着使用由cin管理的输入流，省略构造函数参数表示输入失败，因此上述代码从输入流中读取，直到文件结尾、类型不匹配或出现其他输入故障为止
2. 其他有用的迭代器
概述
· 适配器
一个类或函数，可以将一些其他接口转换为STL使用的接口
（1）reverse_iterator
对reverse_iterator执行递增操作 将导致它被递减。为什么不直接对常规迭代器进行递减呢？主要原因是为了简化对已有的函数的使用。 现在假设要反向打印容器的内容。vector类有一个名为rbegin()的成员函数和一个名为rend()的成员函数，前者返回一个指向超尾的反向迭代器，后者返回一个指向第一个元素的反向迭代器。因为对迭代器执行递增操作将导致它被递减，所以可以使用下面的语句来反向显示内容： copy(dice.rbegin(), dice.rend(), out_iter); // display in reverse order
注意： 假设rp是一个被初始化为dice.rbegin()的反转指针。那么*rp是什么呢？因为rbegin()返回超尾，因此不能对该地址进行解除引用。同样，如果rend()是第一个元素的位置，则copy()必须提早一个位置停止，因为区间的结尾处不包括在区间中。 反向指针通过先递减，再解除引用解决了这两个问题。即*rp将在*rp的当前值之前对迭代器执行解除引用。也就是说，如果rp指向位置6，则*rp将是位置5的值，依次类推
（2）back_insert_iterator
back_insert_iterator将元素插入到容器尾部，但只能用于允许在尾部快速插入的容器
（3）front_insert_iterator
front_insert_iterator将元素插入到容器的前端，但只能用于允许在起始位置做时间固定插入的容器类型
（4）insert_iterator
insert_iterator将元素插入到insert_iterator构造函数的参数指定的位置前面，并且没有上述这些限制，因此可以用它把信息插入到矢量的前端。然而， 上述迭代器对于那些支持它的容器来说，完成任务的速度更快
16.4.5 容器种类
1. 容器概念
容器概念指定了所有STL容器类都必须满足的一系列要求。
其中： · X表示容器类型，如vector； · T表示存储在容器中的对象类型； · a和b表示类型为X的值； · r表示类型为X&的值； · u表示类型为X的标识符（即如果X表示vector<int>，则u是一个vector<int>对象）。 从快到慢依次为： 编译时间 -> 固定时间 -> 线性时间。
2. C++11新增的容器要求
rv表示类型为X的非常量右值，如函数的返回值
3. 序列
1. 序列的必备要求
· t表示类型为T（存储在容器中的值的类型）的值 · n表示整数 · p、q、i和j表示迭代器。
2. 序列的可选要求
3. 7种序列的介绍
（1）vector
· 头文件：vector（数组类）
· 是数组的一种类表示，提供了自动内存管理的功能
· 能够随机访问元素
· 是可反转容器，具有rbegin()和rend()类方法
（2）deque
· 头文件：deque（双端队列）
· 类似于vector，支持随机访问
· 但是对于两端的插入删除操作速度更快
（3）list
· 头文件：list（双向链表）
· 强调元素的快速插入和删除，其时间都是固定的
· 是可反转容器，但不支持随机访问和数组表示法
· 具有专用的成员函数
（4）forward_list
· 头文件：forward_list（单链表）
· 不可反转，相比list更简单、紧凑，但功能更少
（5）queue
· 头文件：queue（队列）
· 不允许随机访问元素，不允许遍历队列
· 操作和普通队列一样
（6）priority_queue
· 头文件：priority_queue（优先队列）
· 最大的元素被移到队首
（7）stack
· 头文件：stack（栈）
· 不允许随机访问元素，不允许遍历栈
· 操作和普通栈一样
16.4.6 关联容器
1. 关联容器的含义
关联容器（associative container）是对容器概念的另一个改进。关联容器将值与键关联在一起，并使用键来查找值。关联容器的优点在于，它提供了对元素的快速访问。与序列相似，关联容器也允许插入新元素，但不能指定元素的插入位置。原因是关联容器通常有用于确定数据放置位置的算法，以便能够快速检索信息。（关联容器通常是使用某种树实现的）
2. 关联容器的种类
（1）set
（2）multiset
（3）map
（4）multimap
3. set示例
（1）定义
可反转，是排好序的关联集合，值与键相同，键不重复
（2）创建
与vector和list相似，set也使用模板参数来指定要存储的值类型： set<string> A; // a set of string objects 第二个模板参数是可选的，可用于指示用来对键进行排序的比较函数或对象。默认情况下，将使用模板less<>： set< string, less<string> > A;
（3）简单使用
请看下面的代码： const int N = 6; string s1[N] = {"buffoon", "thinkers", "for", heavy", "can", "for"}; set<string> A(s1, s1 + N); // initialize set A using a range from array ostream_iterator<string, char> out(cout, " "); copy(A.begin(), A.end(), out); 与其他容器相似，set也有一个将迭代器区间作为参数的构造函数。请记住，区间的最后一个元素是超尾，s1 + N指向数组s1尾部后面的一个位置。上述代码片段的输出表明，键是唯一的（字符串“for”在数组中出现了2次，但在集合中只出现1次），且集合被排序： buffoon can for heavy thinkers
（4）交并集、集合的差
· 方法
求并集：set_union()
求交集：set_intersection()
求集合差：set_difference()
· 使用
set_union()函数接受5个迭代器参数。前两个迭代器定义了第一个集合的区间，接下来的两个定义了第二个集合区间，最后一个迭代器是输出迭代器，指出将结果集合复制到什么位置。例如，要显示集合A和B的并集，可以这样做： set_union(A.begin(), A.end(), B.begin(), B.end(), ostream_iterator<string, char> out(cout, " ")); 假设要将结果放到集合C中，而不是显示它，则最后一个参数应是一个指向C的迭代器： set_union(A.begin(), A.end(), B.begin(), B.end(), insert_iterator< set<string> >(C, C.begin())); 函数set_intersection()和set_difference( 分别查找交集和获得两个集 合的差，它们的接口与set_union()相同
不直接使用C.bigin()的原因有两个： · 关联集合将键看作常量，所以C.begin()返回的迭代器是常量迭代器，不能用作输出迭代器 · set_union()将覆盖容器中已有的数据，并要求容器有足够的空间容纳新信息。C是空的，不能满足这种要求 模板insert_iterator可以解决这两个问题。它可以将复制转换为插入。另外，它还模拟了输出迭代器概念，可以用它将信息写入容器
（5）确定子区间
· 方法
lower_bound()
upper_bound()
· 使用
方法 lower_bound()将键作为参数并返回一个迭代器，该迭代器指向集合中第 一个不小于键参数的成员。同样，方法upper_bound()将键作为参数，并返回一个迭代器，该迭代器指向集合中第一个大于键参数的成员。例如，如果有一个字符串集合，则可以用这些方法获得一个这样的区间，即包含集合中从“b”到“f”的所有字符串
（6）插入方法的区别
因为排序决定了插入的位置，所以这种类包含只指定要插入的信息，而不指定位置的插入方法。例如，如果A和B是字符串集合，则可以这样做： string s("tennis"; A.insert(s); // insert a value B.insert(A.begin(), A.end()); // insert a range
4. multimap示例
（1）定义
可反转的，经过排序的关联容器，键和值的类型不同，且一个键可能与多个值相关联
（2）创建
基本的multimap声明使用模板参数指定键的类型和存储的值类型。例如，下面的声明创建一个multimap对象，其中键类型为int，存储的值类型为string： multimap<int, string> codes; 第3个模板参数是可选的，指出用于对键进行排序的比较函数或对象。在默认情况下，将使用模板less< >
（3）插入值
为将信息结合在一起，实际的值类型将键类型和数据类型结合为一对。为此，STL使用模板类pair<class T, class U>将这两种值存储到一个对象中。如果keytype是键类型，而datatype是存储的数据类型，则值类型为pair<const keytype, datatype>。例如，前面声明的codes对象的值类型为pair<const int, string> 例如，假设要用区号作为键来存储城市名（这恰好与codes声明一致，它将键类型声明为int，数据类型声明为string），则一种方法是创建一个pair，再将它插入： pair<const int, string> item(213, "Los Angeles"); codes.insert(item); 因为数据项是按键排序的，所以不需要指出插入位置
（4）访问键值对
对于pair对象，可以使用first和second成员来访问其两个部分了： pair<const int, string> item(213, "Los Angeles"); cout << item.first << ' ' << item.second << endl;
（5）获得对象信息
成员函数count()接受键作为参数，并返回具有该键的元素数目。成员函数lower_bound()和 upper_bound()将键作为参数，且工作原理与处理set时相同。成员函数equal_range()用键作为参数，且返回两个迭代器，它们表示的区间与该键匹配。为返回两个值，该方法将它们封装在一个pair对象中，这里pair 的两个模板参数都是迭代器。例如，下面的代码打印codes对象中区号为718的所有城市： pair<multimap<KeyType, string>::iterator, multimap<KeyType, string>::iterator> range = codes.equal_range(718); cout << "Cities with area code 718:\n"; std::multimap<KeyType, string>::iterator it; for (it = range.first; it != range.second; ++it) cout << (8it).second << endl;
16.4.7 无序关联容器（C++11）
无序关联容器是对容器概念的另一种改进。与关联容器一样，无序关联容器也将值与键关联起来，并使用键来查找值。但底层的差别在于，关联容器是基于树结构的，而无序关联容器是基于数据结构哈希表的，这旨在提高添加和删除元素的速度以及提高查找算法的效率。有4种无序关联容器，它们是unordered_set、unordered_multiset、unordered_map和unordered_multimap。在这里不做详细的介绍