《C++ PrimerPlus》 第十六章

发表于   |   更新于 | 分类于 | 评论数： | 阅读次数：
本文字数： 9.3k | 阅读时长 ≈ 8 分钟

第十六章 string类和标准模板库

16.1 string 类

头文件：

  • string：支持的是string类
  • string.h / cstring：　支持的是C-风格字符串的C库字符串函数

16.1.1 构造字符串

string类的构造函数如下（用ctor标识，这是传统C++中构造函数的缩写，表中的NBTS（null-terminated string）标识以空字符结束的字符串——传统的C字符串，size_type 是一个依赖于实现的整型，在头文件string中定义）：

构造函数 描述
string(const char *s) 将string对象初始化为s指向的NBTS
string(size_type n, char c) 创建一个包含n个元素的string对象，其中每个元素都被初始化为字符c
string(const string &str) 将一个string对象初始化为string对象str（复制构造函数）
string() 创建一个默认的string对象，长度为0（默认构造函数）
string(const char *, size_type n) 将string对象初始化为s指向的NBTS的前n个字符，即使超过了NBTS的结尾
template
string(Iter begin, Iter end)		 将string对象初始化为区间[begin,end)内的字符，其中begin和end的行为就像指针，用于指定位置，范围包括begin在内，但不包括end
string(const string &str, size_type pos = 0, size_type n = npos) 将一个stirng对象初始化为对象str从位置pos开始到结尾的字符，或从pos开始的n个字符
string(string && str) noexcept C++11新增，它将一个string对象初始化为对象str，并可能修改str（移动构造函数）
string(initializer_list il) C++11新增，它将一个string对象初始化为初始化列表il中的字符

在使用构造函数时都进行了简化，即隐藏了这样一个事实：string实际上是模板具体化basic_string<char>的一个typedef，同时省略了与内存管理相关的参数

16.1.2 string类输入

对于C-风格字符串，有3种方式：

1
2
3
4
5

char info[100];
cin >> info; //read a word 遇到空格换行停止
cin.getline(info, 100); // read a line, discard \n
cin.get(info, 100); // read a line, leave \n in queue

对于string对象，有两种方式：

1
2
3
string stuff;
cin >> stuff;  // read a word
getline(cin, stuff);  // read a line, discard \n

两个版本的getline都有一个可选参数，用于指定使用哪个字符来确定输入的边界。在功能上，它们之间主要的区别在于，string版本的getline()将自动调整目标string对象的大小，使之刚好能够存储输入的字符。

1
2
3
4
5
6
7

char fname[10];
string lname;
cin >> fname; // could be a problem if input size > 9 ch
cin >> lname; // can read a very,very long word
cin.getline(fname,10); // may truncate input
getline(cin, fname);  // no truncation

在设计方面的一个区别是，读取C-风格字符串的函数是istream类的方法，而string版本是独立的函数。这就是对于C-风格字符串输入，cin是调用对象；而对于string对象输入，cin是一个函数参数的原因。这种规则也适用于<<形式：1

1
2
3

cin.operator>>(fname);
operator>>(cin, lname);

string类可以自动调整对象的大小，使之与输入匹配，但也存在一些限制：

  • string对象的最大允许长度： 由常量string::npos 指定，通常是最大的unsigned int值
  • 程序可以使用的内存量

string版本的getline()函数从输入中读取字符，并将其存储到目标string中，知道发生下列三种情况之一：

  • 到达文件尾，在这种情况下，输入流的eofbit将被设置，这意味着方法fail()和eof()都将返回true；
  • 遇到分界字符（默认为\n），在这种情况下，将把分解字符从输入流中删除，但不存储它
  • 读取的字符数打到最大允许值（string::npos与可供分配的内存字节数中较小的一个），在这种情况下，将设置输入流的failbit，这意味着方法fail()返回true。

16.1.3 使用字符串

C++对每个关系运算符进行了重载，以便能够将string对象与另一个string对象或C-风格字符穿进行比较：

1
2
3
operator<(const string &, const string &);
operator==(const string &, const char *);
operator!=(const char *, const string &);

size()和length()方法都返回字符串中的字符数，二者没有区别，前者是为提供STL兼容性添加的，后者是较早版本的string类使用的方法名。

可以以多种不同的方式在字符串中搜索给定的子字符串或字符。下表描述是了find()方法的4个版本。

方法原型 描述　
size_type find(const string &st ,size_type pos=0) const 从字符串的pos位置开始，查找子字符串str。如果找到，则返回该字符串首次出现时其首字符的索引；否则，返回string::npos
size_type find(const char* s, size_type pos=0) const 从字符串的pos位置开始，查找子字符串s。如果找到，则返回该字符串首次出现时其首字符的索引；否则，返回string::npos
size_type find(const char *s, size_type pos=0,size_type n) 从字符串的pos位置开始，查找s的前n个字符组成的子字符串。如果找到，则返回该子字符串首次出现时其首字符的索引；否则，返回string::npos
size_type find(char ch, size_type pos = 0) const 从字符串的pos位置开始，查找字符ch。如果找到，则返回该字符首次出现的位置；否则，返回string::npos

除此之外，string库还提供了其他相关的方法：rfind() ,find_first_of(), find_last_of(), find_first_not_of(), find_last_not_of()等等。

16.1.4 stirng类还提供了哪些功能

更详细的可以查看附录F.

capacity(): 返回当前分配给字符串的内存块大小
reserve(): 请求能够申请的最小的内存块
c_str(): 返回一个指向 C 风格字符串的指针(char *)

16.1.5 字符串种类

表面上看起来string类是基于char类型的，但是，实际上，string库是基于一个模板类的：

1
2
3
4
5
template<
    class CharT,
    class Traits = std::char_traits<CharT>,
    class Allocator = std::allocator<CharT>
> class basic_string;

模板basic_string有四个具体化，每个具体化都有一个typedef名称，如string对应basic_string<char>、wstring对应basic_string<wchar_t>、u16string对应basic_string<char16_t>等等。

16.2 智能指针模板类

智能指针是行为类似于指针的 类对象 。共有三种可以帮助管理动态内存分配的智能指针模板：

  • auto_ptr
  • unique_ptr
  • shared_ptr

模板auto_ptr是C++98提供的解决方案，C++11已将其摒弃，并提供了后两种解决方案。

16.2.1 使用智能指针

以上三个智能指针模板（auto_prt,unique_ptr,shared_ptr)都定义了类似指针的对象，可以将new获得的地址赋给这种对象。

当智能指针过期时，其析构函数将使用delete来释放内存，因此，如果将new返回的地址赋给这种对象，将无需记住稍后释放这些内存。（要创建智能指针，需包含头文件memory）

16.2.2 有关智能指针的注意事项

当多个指针对象指向同一个对象时，三种智能指针的区别：

  • auto_ptr：调用多次析构函数，执行多次delete，报错
  • unique_ptr：建立所有权（ownership）概念，对于特定的对象，只能有一个智能指针可拥有它，在删除后，会将所有权转让
  • shared_ptr：利用引用计数（reference counting），仅当最后一个指针过期时，才调用delete。

16.2.3 unique_ptr为何优于auto_prt

unique_ptr更安全： 它使用了C++11新增的移动构造函数和右值引用
unique_ptr可以用于数组的变体：auto_ptr智能使用new和delete，而unique_ptr可以还可以使用new []和delete []。

警告：

  • 使用new分配内存时，才能使用auto_ptr和shared_ptr，使用new[]分配内存时，不能使用它们
  • 不使用new分配内存时，不能使用auto_ptr和shared_ptr
  • 不使用new和new[]分配内存时，不能使用unique_ptr

16.2.4 选择智能指针

如果程序要使用多个指向同一个对象的指针，应选择shared_ptr。

16.3 标准模板库

STL提供了一组表示容器、迭代器、函数对象和算法的模板。

  • 容器：是一个与数组类似的单元，可以存储若干个值。STL容器是同质的，即存储的值的类型相同
  • 迭代器：能够用来遍历容器的对象，与能够遍历数组的指针类似，是广义指针
  • 函数对象：类似于函数的对象，可以是类对象或函数指针
  • 算法：完成特定任务（如find，verse等）。

STL不是面对对象的变成，而是一种不同的编程模式——泛型编程（generic programming）

关于更多个STL方法和函数可以看附录G

16.3.1 模板类vector

分配器：与string类相似，各种STL容器模板都接受一个可选的模板参数，该参数指定使用哪个分配器对象来管理内存。如果省略了该模板参数的值，则容器类模板将默认使用allocator<T>类，这个类使用new和delete。

1
2
3

template <class T, class Allocator = allocator<T> >
class vector {...}

16.3.2 可对矢量执行的操作

每个容器类都定义了一个合适的迭代器，该迭代器的类型是一个名为iterator的typedef，其作用域为整个类。

1
vector<double>::iterator pd; // pd an iterator

超尾(past-the-end) ：一种迭代器，指向容器的最后一个元素的后面，就像是C-风格字符串最后一个字符后面的空字符一样，由end()成员函数标识。

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

对于搜索、排序、随机排序等等很常见的操作，矢量模板类并没有包含！！ 但是 ，STL从更广泛的角度定义了非成员（non-member）函数来执行这些操作，即不是为每个容器类定义find()函数，而是定义了一个适用于所有容器类的非成员函数find()。这种设计理念省去了大量重复的工作。

另一方面，STL有时也会定义一个功能相同的成员函数。这是因为对有些操作来说，类特定算法的效率比同于算法高，比如，vector的成员函数swap()的效率比非成员函数swap()高，但非成员函数可以交换冷儿类型不同的容器的内容。

16.3.4 基于范围的for循环（C++11）

第五章的示例：

1
2
3
double prices[5] = {4.99, 10.99, 6.87, 7.99, 8.48};
for (double x : prices)
  cout << x << std::endl;

在这种for循环中，先声明一个类型与容器内容类型相同的变量，然后写明容器名称，接下来就可以访问，如下面的代码可以写的更加精简：

1
2
3
4

for_each(books.begin(), books.end(), ShowReview); //for_each形式

for( auto x:books) ShowReview(x)); //

注意，for_each不能修改容器的容器，而基于范围的for循环可以通过指定一个引用参数来修改内容。例如，假设有如下函数：

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

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

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

16.4 泛型编程

面向对象编程关注的是编程的数据方面，而泛型编程关注的是算法。它们之间的共同点是抽象和创建可重用代码，但它们的理念决然不同。泛型编程旨在编写独立于数据类型的代码。

16.4.1 为何使用迭代器

模板使得算法独立于存储的数据类型，而迭代器使算法独立于使用的容器类型。

例如，在使用find函数时，可以用迭代器来实现不依赖于具体类型的查找。

实际上，作为一种编程风格，最好避免直接使用迭代器，而应尽可能使用STL函数(如for_each()）来处理细节。也可以使用C++11新增的基于范围的for循环。

16.4.2 迭代器类型

不同的算头对迭代器要求不同，有的只要求可读，有的要求可随机访问等等。STL定义了5种不迭代器，并根据所需的迭代器类型对算法进行了描述：

  • 输入迭代器
  • 输出迭代器
  • 正向迭代器
  • 双向迭代器
  • 随机访问迭代器

对于不同的算法，需要的迭代器不同，如下面两种算法分别需要输入迭代器和随机访问迭代器

1
2
3
4
5
template<typename InputIterator, typename T>
InputIterator find(InputIterator first, InputIterator last, const T &value);

template<typename RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

对于这5种迭代器，都可以执行解除引用操作（即*运算符），也可进行比较，看其是相等还是不相等（==，！=运算符）。如果两个迭代器相同，则对它们执行解除引用操作得到的值将相同。

  1. 输入迭代器

  术语“输入”是从程序的角度出发的，即来自容器的信息被视为输入（从迭代器传到程序中），因此，输入迭代器可被程序用来读取容器中的信息。需要输入迭代器的算法将不会修改容器中的值

  输入迭代器必须能做访问容器中所有的值，这是通过支持++运算符（前缀格式operator++和后缀格式operator++(int)）来实现的。

   注意： 并不能保证输入迭代器第二次遍历容器时，顺序不变。另外，输入迭代器被递增后，也不能保证其先前的值仍然可以被解除引用。基于输入迭代器的任何算法都应当是单通行（single-pass）的，不依赖于前一次便利时的迭代器值，也不依赖于本次遍历中前面的迭代器值。—— 输入迭代器是单向迭代器，可以递增，但不能倒退

  1. 输出迭代器

  同理，“输出”指用于将信息从程序传输给容器的迭代器（从程序输出到迭代器中），输出迭代器智能解除引用让程序修改容器值，而不能读取容器内的值。输出迭代器也是单通行的，只能写不能读。

  1. 正向迭代器

   只是用++运算符遍历容器，每次沿容器向前移动一个元素。与输入和输出迭代器不同的是，它总是按相同的顺序遍历一系列值，另外，将正向迭代器递增后，仍然可以对前面的迭代器值解除引用，并得到对应的值 。这些特征使得正向迭代器是多通行的（可以多次通行容器）。

  1. 双向迭代器

  双向迭代器具有正向迭代器的所有特性，且同时支持两种（前缀和后缀）递减运算符。

  1. 随机访问迭代器

  有些算法（如排序和二分检索）要求能够直接跳到容器中的任何一个元素（将想数组下标访问一样），因此就有了随机访问迭代器。该迭代器具有双向迭代器的所有特性，同时添加了支持随机访问的操作和用于对元素进行排序的关系运算符。

16.4.3 迭代器层次结构

可以看出，迭代器类型形成了一个层次结构。后面的迭代器不仅拥有之前迭代器的所有功能，同时还有自己的功能。

每个容器类都定义了一个类级typedef名称——iterator。（实际上这使用指针实现的，并不是一种新的类型）。

16.4.4 概念、改进和模型

STL有若干个用C++语言无法表达的特性，如迭代器种类。正向迭代器是一系列要求，而不是类型。（迭代器通常可以用常规指针实现，所以迭代器本身并不是一种类型）。

STL使用术语“概念（concept）”来描述一系列的要求。

概念可以具有类似继承的关系，就像双向迭代器继承了正向迭代器的功能。然而，不能将C++继承机制用于迭代器，但从概念上看，它确实能够继承，有些STL文献使用属于改进（refinement）来表示这种概念上的继承，因此，双向迭代器是对正向迭代器概念的一种改进。

概念的具体实现被称为模型（model）。因此，指向int的常规指针是一个随机访问迭代器模型，同时也是一个正向迭代器模型。

  1. 将指针用作迭代器

  迭代器是广义上的指针，其本身就是一种指针，因此，STL算法可以使用指针来对基于指针的非STL容器进行操作。例如，可将STL算法用于数组。

1
2
3
const int SIZE = 100;
double Receipts[SIZE];
sort(Receipts,Receipts+SIZE); //用STL的sort算法对数组进行排序

  STL提供了一些预定义迭代器，如ostream_iterator和istream_iterator模板等，都定义在iterator头文件中。

  1. 其他有用的迭代器

  头文件iterator还提供了其他一些专用的预定义迭代器类型，它们是reverse_iterator, back_insert_iterator, front_insert_iterator和insert_iterator等。

16.4.5 容器种类

  • 容器概念：概念是具有名称（如容器、序列容器、关联容器等）的通用类别
  • 容器类型：是可用于创建具体容器对象的模板。以前的11个容器类型为：deque, list, queue, priority_queue, stack, vector, map, multimap, set, multiset和bitset。 C++11新增了：forward_list, unordered_map, unordered_multimap, unordered_set和unordered_multiset，且不再将bitset视为容器，而将其视为一种独立的类别。
  1. 容器概念

  没有与基本容器概念对应的类型，但概念描述了所有容器类都通用的元素。存储在容器中的类型必须是可复制构造和可赋值的。STL特定操作的时间复杂度有三种，分别是：编译时间、固定时间和线性时间。

  1. C++11新增的容器要求

  下表列出了C++11新增的通用容器要求，其中，复制赋值和移动赋值之间的差别在于，复制操作保留源对象，而移动操作可修改源对象，还可能转让所有权，而不做任何复制。如果源对象是临时的，移动操作的效率将高于常规复制。

表达式 返回类型 说明 复杂度
X u(rv); 调用移动构造函数后，u和值和rv的原始值相同 线性
X u = rv; 作用同上
a = rv; X& 调用移动赋值运算符后，u的值和rv的原始值相同 线性
a.cbegin() const_iterator 返回指向容器第一个元素的const迭代器 固定
a.cend() const_iterator 返回超尾值的const迭代器 固定
  1. 序列

16.4.6 关联容器

16.4.7 无序关联容器

16.5 函数对象

函数对象也叫做仿函数 (funtor). 仿函数是可以以函数方式与()运算符结合使用的任意对象. 重载后的()运算符将使得能够响函数那样使用类对象.

16.5.1 仿函数概念

16.5.2 预定义的仿函数

16.5.3 自适应仿函数

16.7.3 使用initializer_list