16. string类和标准模板库

string类

1. 1.构造字符串

size_type是一个依赖于实现的整型，是在头文件string中定义的。string类将string:: npos定义为字符串的最大长度，通常为unsigned int的最大值。另外，表格中使用缩写NBTS(null-terminated string)来表示以空字符结束的字符串一传统的C字符串。

img

指定分割字符：

string empty;
empty.capacity(); //字符串的容量
//字符串的容量比标准容量（16的倍数）小1

img

shared_ptr

unique_ptr

auto_ptr

左值与右值这两个概念是从 C 中传承而来的，左值指既能够出现在等号左边，也能出现在等号右边的变量；右值则是只能出现在等号右边的变量。

16.3 标准模板库

• STL提供了一组表示容器、迭代器、函数对象和算法的模板
• STL容器是同质的，即存储的值的类型相同

16.3.1 模板类vector

• 可以创建vector对象，将一个vector对象赋给另一个对象，使用[]运算符来访问vector元素。
• 要使类成为通用的，应将它设计为模板类，
• STL正是这样做的一在头文件vector(以前为vector..h)中定义了一个vector模板。
• 要创建vector模板对象，可使用通常的表示法来指出要使用的类型。另外，vector模板使用动态内存分配，因此可以用初始化参数来指出需要多少矢量：

#include vector
using namespace std;
vector<int> ratings(5);
int n;
cin >> n; 
vector<double> scores(n);

16.3.2 可对矢量执行的操作

• size()返回容器中元素数目
• swap()交换两个容器的内容
• begin()返回一个指向容器中第一个元素的迭代器
• end()返回一个表示超过容器尾的迭代器。

迭代器是一个广义指针

• vector模板类有push back()，是一个方便的方法，它将元素添加到矢量末尾
• erase()方法删除矢量中给定区间的元素。它接受两个迭代器参数，这些参数定义了要删除的区间。第一个迭代器指向区间的起始处，第二个迭代器位于区间终止处的后一个位置。scores.erase(scores.begin(),scores.begin()+2)
• insert()方法的功能与erase()相反。它接受3个迭代器参数，第一个参数指定了新元素的插入位置，第二个和第三个迭代器参数定义了被插入区间，该区间通常是另一个容器对象的一部分。old_v.insert(old_v.end(),new_v.begin()+1,new_v.end());

16.3.3 对矢量可执行的其他操作

• 3个具有代表性的STL函数：for_each() random_shuffle()和sort()

• for_each()

• • 它接受3个参数。前两个是定义容器中区间的迭代器，最后一个是指向函数的指针,最后一个参数是一个函数对象
  • for each()函数将被指向的函数应用于容器区间中的各个元素。被指向的函数不能修改容器元素的值。可以用for each()函数来代替for循环。

for_each(books.begin(),books.end(),ShowReview);

• Random shuffle()函数接受两个指定区间的迭代器参数，并随机排列该区间中的元素。例如，下面的语句随机排列books矢量中所有元素：

• • 该函数要求容器类允许随机访问，vector类可以做到这一点

random_shuffle(books.begin(),books.end());

• sort()函数也要求容器支持随机访问。该函数有两个版本，第一个版本接受两个定义区间的迭代器参数，并使用为存储在容器中的类型元素定义的<运算符，对区间中的元素进行操作。例如，下面的语句按升序对coolstuff的内容进行排序，排序时使用内置的<运算符对值进行比较：
• 如果容器元素是用户定义的对象，则要使用sort(),必须定义能够处理该类型对象的operator<()函数

16.3.4 基于范围的for循环

• 不同于for each(),基于范围的for循环可修改容器的内容，诀窍是指定一个引用参数。例如，假设有如下函数：

void InflateReview (Review &r){r.rating++;}

• 可使用如下循环对books的每个元素执行该函数：

for (auto &x : books)InflateReview(x);

16.4 泛型编程

STL是一种泛型编程

16.4.1 为何使用迭代器

• 模板使得算法独立于存储的数据类型，而迭代器使算法独立于使用的容器类型。因此，它们都是STL通用方法的重要组成部分。
• 要实现find函数，迭代器应具备哪些特征呢？下面是一个简短的列表
• 为区分++运算符的前缀版本和后缀版本，C++将operator+-+作为前缀版本，将operator++(int)作为后缀版本：其中的参数永远也不会被用到，所以不必指定其名称。

• 

  img

• 

  img

16.4.2 迭代器类型

• 输入迭代器

• • 来自容器的信息被视为输入，输入迭代器可被程序用来读取容器中的信息。具体地说，对输入迭代器解除引用，将使程序能够读取容器中的值，但不一定能让程序修改值。因此，需要输入迭代器的算法将不会修改容器中的值。
  • 输入迭代器必须能够访问容器中所有的值，这是通过支持++运算符（前缀格式和后缀格式）来实现的。
  • 如果将输入迭代器设置为指向容器中的第一个元素，并不断将其递增，直到到达超尾位置，则它将依次指向容器中的每一个元素。顺便说一句，并不能保证输入迭代器第二次遍历容器时，顺序不变。
  • 另外，输入迭代器被递增后，也不能保证其先前的值仍然可以被解除引用。基于输入迭代器的任何算法都应当是单通行(single-pass)的，不依赖于前一次遍历时的迭代器值，也不依赖于本次遍历中前面的迭代器值。
  • 注意，输入迭代器是单向迭代器，可以递增，但不能倒退。

• 输出迭代器

• • STL使用术语“输出”来指用于将信息从程序传输给容器的迭代器，因此程序的输出就是容器的输入。
  • STL足够通用，其容器可以表示输出设备，因此容器也可能如此。另外，如果算法不用读取作容器的内容就可以修改它（如通过生成要存储的新值），则没有理由要求它使用能够读取内容的迭代器。

• 正向迭代器

• • 与输入迭代器和输出迭代器相似，正向迭代器只使用++运算符来遍历容器，
  • 与输入和输出迭代器不同的是，它总是按相同的顺序遍历一系列值
  • 将正向迭代器递增后，仍然可以对前面的迭代器值解除引用（如果保存了它），并可以得到相同的值。这些特征使得多次通行算法成为可能。
  • 正向迭代器既可以使得能够读取和修改数据，也可以使得只能读取数据：

• 双向迭代器

• • 假设算法需要能够双向遍历容器，情况将如何呢？例如，reverse函数可以交换第一个元素和最后一个元素、将指向第一个元素的指针加1、将指向第二个元素的指针减1，并重复这种处理过程。双向迭代器具有正向迭代器的所有特性，同时支持两种（前缀和后缀）递减运算符。

• 随机访问迭代器

• • 有些算法（如标准排序和二分检索）要求能够直接跳到容器中的任何一个元素，这叫做随机访问，需要随机访问迭代器。随机访问迭代器具有双向迭代器的所有特性，同时添加了支持随机访问的操作（如指针增加运算)和用于对元素进行排序的关系运算符。

  • 

    img

16.4.3 迭代器层次结构

img

注意，各种迭代器的类型并不是确定的，而只是一种概念性描述。正如前面指出的，每个容器类都定义了一个类级typedef名称-iterator,因此vector类的迭代器类型为vector<-int>:interator。.然而，该类的文档将指出，矢量迭代器是随机访问迭代器，它允许使用基于任何迭代器类型的算法，因为随机访问迭代器具有所有迭代器的功能。同样，list类的迭代器类型为list:iterator。STL实现了一个双向链表，它使用双向迭代器，因此不能使用基于随机访问迭代器的算法，但可以使用基于要求较低的迭代器的算法。

16.4.4 概念、改进和模型

• 将指针用作迭代器

• • 

    img

• • 

    img

• 其他有用的迭代器

• • 反向打印

• • • 

      img

• • 显式和隐式

• • • 

      img

• • 插入迭代器
• • • back insert iterator将元素插入到容器尾部，
    • 而front insert iterator将元素插入到容器的前端。
    • 最后，insert iterator将元素插入到insert iterator构造函数的参数指定的位置前面。这三个插入迭代器都是输出容器概念的模型。

• 这里存在一些限制。

• • back insert iterator只能用于允许在尾部快速插入的容器（快速插入指的是一个时间固定的算法，将在本章后面的“容器概念”一节做进一步讨论)，vector类符合这种要求。
  • front insert iterator只能用于允许在起始位置做时间固定插入的容器类型，vector类不能满足这种要求，但queue满足。
  • insert iterator没有这些限制，因此可以用它把信息插入到矢量的前端。然而，front insert iterator对于那些支持它的容器来说，完成任务的速度更快。

16.4.5 容器种类

• 序列中的元素具有确定的顺序，因此可以执行诸如将值插入到特定位置、删除特定区间等操作

img

因为模板类deque、list、queue、priority_queue、stack和vector都是序列概念的模型，所以它们都支持16.7

img

• a[n]和a.at(n)都返回一个指向容器中第n个元素（从0开始编号）的引用。它们之间的差别在于，如果n落在容器的有效区间外，则a.atn)将执行边界检查，并引发out of range异常。

• vector

• • vector是数组的一种类表示，它提供了自动内存管理功能，可以动态地改变vector对象的长度，并随着元素的添加和删除而增大和缩小。它提供了对元素的随机访问。在尾部添加和删除元素的时间是固定的，但在头部或中间插入和删除元素的复杂度为线性时间。
  • 除序列外，vector还是可反转容器(reversible container)概念的模型。这增加了两个类方法：rbegin()和rend(),前者返回一个指向反转序列的第一个元素的迭代器，后者返回反转序列的超尾迭代器。因此，如果dice是一个vector<-int>容器，而Show(int)是显示一个整数的函数，则下面的代码将首先正向显示dice的内容，然后反向显示：

• deque

• • deque模板类（在deque头文件中声明）表示双端队列(double-ended queue),通常被简称为deque
  • 支持随机访问
  • 主要区别在于，从deque对象的开始位置插入和删除元素的时间是固定的，而不像vector中那样是线性时间的。所以，如果多数操作发生在序列的起始和结尾处，则应考虑使用deque数据结构。
  • 为实现在deque两端执行插入和删除操作的时间为固定的这一目的，deque对象的设计比vector对象更为复杂。因此，尽管二者都提供对元素的随机访问和在序列中部执行线性时间的插入和删除操作，但vector容器执行这些操作时速度要快些。

• list

• • list模板类（在list头文件中声明）表示双向链表。除了第一个和最后一个元素外，每个元素都与前后的元素相链接，这意味着可以双向遍历链表。
  • list和vector之间关键的区别在于，list在链表中任一位置进行插入和删除的时间都是固定的(vector模板提供了除结尾处外的线性时间的插入和删除，在结尾处，它提供了固定时间的插入和删除)。因此，vector强调的是通过随机访问进行快速访问，而list强调的是元素的快速插入和删除。
  • 与vector相似，list也是可反转容器。与vector不同的是，list不支持数组表示法和随机访问。
  • 与矢量迭代器不同，从容器中插入或删除元素之后，链表迭代器指向元素将不变。

  • 

    img

  • (6)forward list (C++11)C+11新增了容器类forward list,它实现了单链表。在这种链表中，每个节点都只链接到下一个节点，而没有链接到前一个节点。因此forward_list只需要正向迭代器，而不需要双向迭代器。因此，不同于vector和Iist,forward list是不可反转的容器。相比于list,forward list更简单、更紧凑，但功能也更少。

• queue

• • 

    img

• priority_queue

• • priority_.queue模板类（在queue头文件中声明）是另一个适配器类，它支持的操作与queue相同。两者之间的主要区别在于，在priority_queue中，最大的元素被移到队首（生活不总是公平的，队列也一样）。内部区别在于，默认的底层类是vector。可以修改用于确定哪个元素放到队首的比较方式，方法是提供一个可选的构造函数参数：

priority_queue<int>pql; //default version
priority_queue<int>pq2(greater<int>);//use greater<int>to order

• • greater<>()函数是一个预定义的函数对象，本章稍后将讨论它。

img

img