开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 《Essential C++》读书笔记 -> 正文阅读

[数据结构与算法]《Essential C++》读书笔记

《Essential C++》是一本老书了，第一版应该是成书于1999年。这一点在其中文译本中似乎竟没有说明（也许是笔者遗漏了）。
此书作者便是大名鼎鼎的《C++ Primer》的作者 Stanley B. Lippman, 而中译本的作者也很有名，乃是宝岛台湾的侯捷。
相较于《C++ Primer》近千页（第5版）的厚重，《Essential C++》的中译本只有281页，若除去附录部分，则只有204页。
这其实是一本相对较简单的初级C++书籍。虽然年代久远，仍是珠玉难掩，其中一些东西还是值得一读。这篇读书笔记，只是笔者本人的一些喜好，可能并没有囊括此书所有的精华。读者还请见谅。

const_iterator

const_iterator 允许读入容器的元素，但不允许对容器进行写入操作；
而 const_iterator 本身是可以改变的。

vector<int>::const_iterator it = vec.begin();
for (; it != vec.end(); it++) cout << *it << " ";

泛型算法

一些常见的泛型算法如下：

搜索算法：
find(), count(), find_if(), count_if(), binary_search(), find_first_of()
排序/次序整理：
merge(), partial_sort(), partition(), random_shuffle(), reverse(), rotate(), sort()
关系算法：
equal(), includes(), mismatch()
generation/mutation:
fill(), for_each(), generate(), transform()
数值算法（numeric）：
accumulate(), partial_sum(), inner_product()
集合算法：
set_union(), set_difference()

所有容器的共同操作

equality （==）和 inequality （!=）运算符，返回 true 或 false
赋值运算符
empty()
size()
clear() // 删除所有元素

举例：

set<int> s1{1, 2, 3, 5, 6, 8};
set<int> s2{8, 6, 5, 3, 2, 1};
if (s1 == s2) cout << "Equal" << endl;  // hit

顺序容器

一些常用的顺序容器如下：

vector
list 双向链表
deque 双向队列，和vector很相似，不同的是：对于前端元素的插入和删除操作，deque效率非常高；
queue（单向队列）就是用deque实现的
头文件是 <deque>

定义顺序容器的方式有5种：

定义空的顺序容器，如： list<int> mylist;
产生特定size的容器，每个元素都用默认值来初始化。

vector<int> vec(100); 
list<int> mylist(1024);

产生特定size的容器，每个元素采用给定的值来统一初始化。

vector<int> vec(100, 10);
list<int> mylist(1024, 10);

通过一对iterator来初始化容器

int array[5] = {1, 2, 3, 4, 5};
vector<int> vec(array, array+5);

通过copy构造函数

几个常见的泛型算法

copy(vec.begin(), vec.end(), targetVec.begin());

copy(vec.begin(), vec.end(), back_inserter(targetVec));

sort(vec.begin(), vec.end());

sort(vec.begin(), vec.end(), greater<int>());

int element = 10;
vector<int>::iterator iter = find(vec.begin(), vec.end(), element);

bool bHit = binary_search(vec.begin(), vec.end(), element);

函数对象 (function object)

所谓函数对象（function object）, 就是某个class的实例，而该class对函数调用操作符做了重载（即重载了小括号运算符）。

为何使用函数对象而不用函数指针呢？一个原因是为了效率，即可以令函数调用操作符成为inline，从而消除了“通过函数指针来调用函数“的额外开销。

函数对象多用于STL泛型算法中的函数的参数。标准库事先定义了一组function object：

6个算术运算：
plus, minus, negate, multiplies, divides, modules
6个关系运算：
less, less_equal, greater, greater_equal, equal_to, not_equal_to
3个逻辑运算(分别对应于 &&, ||, !）：
logical_and, logical_or, logical_not

使用举例：

sort(vec.begin(), vec.end(), greater<int>());

其中，greater<int>()会产生一个未命名的 class template object, 传给sort.

binary_search(vec.begin(), vec.end(), element, greater<int>());

auto iter = find_if( vec.begin(), vec.end(), less<int>());

函数对象适配器 (function object adapter)

函数对象适配器，用来对函数对象进行修改操作。标准库提供了2个binder适配器：

bind1st将指定值绑定到第一操作数；
bind2nd将指定值绑定到第二操作数；

另一种适配器是negator，它会对function object的真伪值取反。

not1可对 unary function object 的真伪取反
not2可对 binary function object 的真伪取反

示例程序：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    vector<int> vec{10, 20, 30, 5, 6, 7, 8, 99, 100, 101};
    vector<int> new_vec;
    less<int> lt;
    auto iter = vec.begin();
    while ((iter = find_if(iter, vec.end(), not1(bind2nd(lt, 10)))) != vec.end()) {
        new_vec.push_back(*iter);
        iter ++;
    }
    
    for(auto i : new_vec) cout << i << " ";  // 10 20 30 99 100 101
    cout << endl;
    return 0;
}

标准库提供了3个插入型适配器（insertion adapter），这些适配器使得我们可以避免使用容器的赋值运算符。
要使用以下3种adapter，就要 #include <iterator>

back_inserter(container)：相当于调用容器的 push_back , 因此其参数就是容器本身

copy(vec.begin(), vec.end(), back_inserter(target_vec));    // 将 vec 的内容追加到 target_vec 的后面

front_inserter(container): 与back_inserter 类似，只是相当于调用了容器的push_front()
inserter()相当于调用容器的 insert()函数

使用iostream iterator

标准库定义有供输入和输出使用的 iostream iterator 类，称为 istream_iterator和 ostream_iterator, 分别支持单一类型的元素的读取和写入。
要使用这2个iterator class，先要包含头文件 <iterator>

istream_iterator<string> is(std::cin);

以上为我们提供了一个 first iterator ，它将is定义为一个”绑定至标准输入设备“的 istream_iterator.
对于标准输入设备而言，end-of-file 代表结束。只要在定义 istream_iterator 的时候不为它指定 istream 对象，便代表了 end-of-file.

istream_iterator<string> eof;

以下是示例程序：

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main()
{
    istream_iterator<string> is(cin);
    istream_iterator<string> eof;
    
    vector<string> text;
    copy(is, eof, back_inserter(text)); // Ctrl+D to end inputting
    
    sort(text.begin(), text.end());
    
    ostream_iterator<string> os(cout, " ");
    copy(text.begin(), text.end(), os);
    
    return 0;
}

一般情况下，我们不会读标准设备，而是希望从文件读，然后写到文件去。此时，只需将 istream_iterator绑定至 ifstream对象，将 ostream_iterator绑定至 ofstream对象即可。
示例程序如下：

#include <iostream>
#include <fstream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main()
{
    ifstream in_file("./2.cpp");
    ofstream out_file("./2.txt");
    
    if (! in_file || ! out_file) {
        cerr << "Unable to open the necessary file!\n";
        return -1;
    }
    
    istream_iterator<string> is(in_file);
    istream_iterator<string> eof;
    
    vector<string> text;
    copy(is, eof, back_inserter(text));
    
    sort(text.begin(), text.end());
    
    ostream_iterator<string> os(out_file, " ");
    copy(text.begin(), text.end(), os);
    
    return 0;
}

maximal munch 编译规则

每个符号序列总是以 “合法符号序列”种最长的那个来解释。
比如：a+++p会被解释为 a++ + p

这个规则也是导致在C++11之前，以下写法被编译器解析为 >>的原因：
vector<vector<int>>
从而在C++11之前，必须写成
vector< vector<int> >

派生类中的虚函数

如果要用派生类中新定义的虚函数覆盖基类的虚函数，那么派生类中虚函数的定义必须完全符合基类所声明的函数原型，包括：

参数列表
返回类型
常量性

换句话说，以上3个特性的任何一个和基类中的虚函数不一致，则被认为是一个新的虚函数，而不是能覆盖基类虚函数的的虚函数。
(笔者注：C++11之后，还要加上更多的东西，比如 - noexcept的有无，也影响到编译器判断这是否属于同一个虚函数）

运行时类型鉴定

RTTI，即 Run-Time Type Identification, 运行时类型鉴定
示例程序如下：（注意，需 #include <typeinfo>）


#include <iostream>
#include <typeinfo>
using namespace std;

class MyClass {
public:
    void name() {
        cout << typeid(*this).name() << endl;
    }
};

int main()
{
    MyClass mine;
    cout << typeid(mine).name() << endl;
    mine.name();
    
    return 0;
}

dynamic_cast也是一个 RTTI 运算符，它会进行运行时检验操作。

class B : public A {...}; 
A * pa = new A;
B * pb = dynamic_cast<B *>(pa);

如果 pa 所指对象属于 B class，则转换操作便会发生，pb 将指向该 B 对象；
否则，dynamic_cast返回 NULL; 若是针对引用类型，则会抛出 bad_cast异常。
注意：这里有一个前提条件，class A 中必须有虚函数，否则 dynamic_cast<B *>(pa)这一句编译不会通过。

示例程序如下：

#include <iostream>
#include <typeinfo>
using namespace std;

class A {
    virtual void func() {
        cout << "A" << endl;
    }
};
class B : public A {
    virtual void func() {
        cout << "B" << endl;
    }
};
class C : public B {
    virtual void func() {
        cout << "C" << endl;
    }
};
class D {};

int main()
{
    A * pa = new A;
    B * pb = new B;
    C * pc = new C;
    D * pd = new D;
    
    B * pb1 = dynamic_cast<B *>(pa);
    B * pb2 = dynamic_cast<B *>(pb);
    B * pb3 = dynamic_cast<B *>(pc);
    
    if (pb1 == NULL) cout << "pb1 is NULL" << endl;  // hit
    if (pb2 == NULL) cout << "pb2 is NULL" << endl;
    if (pb3 == NULL) cout << "pb3 is NULL" << endl;
    
    return 0;
}

关于dynamic_cast, 更多内容可以参见另一篇博客《简介dynamic_cast》。

模板以常量表达式为参数

模板的参数并不一定是某种类型，也可以是常量表达式。

示例代码如下：

#include <iostream>
using namespace std;

template <int d, int x=5>
class MyClass {
private:
    int data;
public:
    MyClass(int dd=d) : data(dd) {}
    int get_data() {return data;}
    void print() {
        for (int i=0; i<x; i++) cout << data << " ";
        cout << endl;
    }
};

int main()
{
    MyClass<99> m1;
    cout << m1.get_data() << endl;  // 99
    m1.print();  // 99 99 99 99 99
    return 0;
}

异常

C++保证：

在异常处理机制终结某个函数之前，函数中的所有局部对象的析构函数都会被调用。

catch表达式中可以写：

异常的对象
异常对象的引用
异常的类型，如： catch(std::bad_alloc)

标准库定义了一套异常体系，其根是名为 exception的抽象基类。
exception声明了一个 what()虚函数，返回 const char *, 用以文字描述异常。
内存耗尽时申请内存所抛出的异常 std::bad_alloc派生自 exception 基类下的runtime_error类，但定义了自己的 what().
要定义自己的异常类，首先要包含标准头文件 <exception>, 然后要提供自己的 what().

示例程序：

#include <iostream>
#include <string>
#include <exception>
using namespace std;

class MyException : public std::exception
{
private:
    const char * desp = "This is MyException";
    
public:
    const char * what() const noexcept { return desp; }
};

int main()
{
    try {
        throw MyException();
    }
    catch (exception& ex) {
        cerr << ex.what() << endl;    // This is MyException
        return -1;
    }
    return 0;
}