第二条：不要试图编写独立于容器类型的代码。#

STL 是以泛化原则为基础的：

• 数组被泛化为”以其包含的对象的类型为参数“的容器；
• 函数被泛化为”以其使用的迭代器的类型为参数“的算法；
• 指针被泛化为”以其指向的对象的类型为参数“的迭代器；
• 容器被泛化为”序列式和关联式“容器。

个人理解一句话：别给多个容器写一个通用的函数。没有意义而且效率低下。

第三条：确保容器中的对象副本正确而高效。#

• 当(通过如 insert 或 push_back 之类的操作)向容器中加入对象时，存入容器的是你所指定的对象的拷贝。
• 当(通过如front或back之类的操作)从容器中取出一个对象时，你所得到的是容器中所保存的对象的拷贝。

拷贝进来拷贝出去是STL的工作方式

在存在继承关系的情况下，拷贝动作会导致剥离(slicing)。也就是说，如果你创建了一个存放基类对象的容器，却向其中插入派生类的对象，那么在派生类对象(通过基类的拷贝构造函数)被拷贝进容器时，它所特有的部分(即派生类中的信息)将会丢失。”剥离”问题意味着向基类对象的容器中插入派生类对象几乎总是错误的。使拷贝动作高效、正确，并防止剥离问题发生的一个简单办法是使容器包含指针而不是对象。

上一句的例子：

1
class Base{
2
   //...
3
}
4
class Derived : public Base{
5
  //...
6
};
7
vector<Base> father; //容器类型为父类对象
8
Derived child;
9
father.push_back(child); //子类对象通过基类复制构造函数复制进类型为父类对象的容器时，子类独有的部分会丢失。

所以我们为了实现多态，必须是容器保存父类指针。不能是对象也不能是引用。因为指针是一样大的。对象不是一样大的。而且也没有引用容器。而且对象也没法多态。

1
vector<Base*> father;
2
Derived* child = new child(); //子类指针指向子类对象
3
Base* child = new child(); //父类指针指向子类对象两种都可以。
4
father.push_back(child);

第四条：调用empty而不是检查size()是否为0。#

个人理解：因为比如链表这种，size()需要线性时间查找一遍之后告诉你size。但是empty是O(1)。所以用empty不要用size更快速。

第五条：区间成员函数优先于与之对应的单元素成员函数。#

个人总结：能用区间函数的就不要使用循环一个一个拷贝。增加效率。尤其是序列容器的头插。一个一个插入到头部会造成大量的拷贝和析构。因为每插入一个，后面的元素都要移动一位。

那么，都有哪些区间成员函数？

• 区间创建函数、insert、erase、assign等。

第六条 C++非常煞笔的分析机制#

C++非常煞笔的分析机制。函数和函数指针。加括号不加括号

1
// 注意：围绕参数名的括号(比如对f2中d)与独立的括号的区别：围绕参数名的括号被忽略，而独立的括号则表明参数
2
// 列表的存在：它们说明存在一个函数指针参数
3
int f1(double d); // 声明了一个带double参数并返回int的函数
4
int f2(double(d)); // 同上，d两边的括号被忽略,可以给参数名加上圆括号
5
int f3(double); // 同上，参数名被忽略
6

7
int g1(double(*pf)()); // 参数是一个指向不带任何参数的函数的指针，该函数返回double值；g1以指向函数的指针为参数
8
int g2(double pf()); // 同上，pf为隐式指针
9
int g3(double()); // 同上，省去参数名

所以

1
list<int> data(istream_iterator<int>(dataFile), istream_iterator<int>());

这一行代码的解释是：这声明了一个函数data，其返回值是list<int>。这个data函数有两个参数：

■　第一个参数的名称是dataFile。它的类型是istream_iterator<int>。dataFile两边的括号是多余的，会被忽略。

■　第二个参数没有名称。它的类型是指向不带参数的函数的指针，该函数返回一个istream_iterator<int>。

经典错误

1
class Widget{
2
    //...假设Widget有默认构造函数
3
}
4
Widget w(); //这是声明了一个名字叫w的函数，该函数没有参数，返回一个Wedget

第七条：如果容器中包含了通过new操作创建的指针，切记在容器对象析构前将指针delete掉。#

前提是你真的希望容器内指针指向的对象被析构。在构建二叉树的时候我们并不希望容器内指针指向的对象被析构，因为我们会返回一个根节点。如果析构了东西就都没了。

1
class test;
2
class myfunc{
3
    public:
4
        void operator()(vector<int*>& vec, int p){
5
            vec.push_back(new int(p)); //新建一个指向int的指针并放入容器。
6
        }
7
};
8

9
struct DEL{
10
    template<typename T>
11
    void operator()(T* ptr){ //创建删除函数利用foreach释放tt容器内的每一个指针指向的资源
12
        delete ptr;
13
        ptr = nullptr;
14
    }
15
};
16

17

18

19
class test{
20
    public:
21
    int val;
22
    test(){}
23
    test(int x):val(x){};
24
    void getbug(vector<int>& vec){
25
        vector<int*> tt; //函数内创建指针容器
26
        for_each(vec.begin(), vec.end(), bind(myfunc(), ref(tt), placeholders::_1)); //使用foreach和bind。记得传入容器需要加ref
27
        for_each(tt.begin(), tt.end(), [](int* content){cout <<*content << endl; }); //使用lambda表达式打印tt容器的每一个值。[]捕获列表没有参数因为我们没有用到上下文变量
28
        for_each(tt.begin(), tt.end(), DEL()); //如果这里不用foreach搭配释放函数释放，那么tt容器在离开函数的时候会被销毁。里面的指针全部都会被移除，但是指向的资源没有释放。导致内存泄漏。因为tt是局部变量。不属于class。
29
    }
30
};
31

32
int main()
33
{
34

35
    vector<int> rrr = {1,2,3,4,5,6,7};
36
    test obj;
37
    obj.getbug(rrr);
38

39
}

这一条的个人解释：容器确实会调用容器内每个元素的析构。但是调用的是对应类型的析构。举个例子vector<int> a; 和 vector<int*> b。a析构的时候调用int的析构，b析构的时候调用int*的析构。但是指针不是类，它没有析构函数，所以什么都没做，仅仅是删掉了指针而没有释放指针所指向的元素。所以容器中所有指针指向的数据全部泄漏。

容器析构的时候会为每个元素调用destroy：

他为每个元素调用其析构函数。这里是因为传入的是迭代器。所以长这样。

所以我们普通的比如myclass可以有~myclass()这样的析构函数调用，但是myclass*这种指针类型是没有析构函数的，没有（其实是这种类型的析构函数是trivial的）~myclass*()。所以要谨记，容器析构的时候并不是delete，而是调用其对应类类型的析构函数！。

一个简单明显的例子

1
int main(){
2
    vector<int*>myvec;
3
    myvec.emplace_back(new int(6));
4
    myvec.emplace_back(new int(7));
5
    delete myvec[0]; //去掉这两行会内存泄漏。
6
    delete myvec[1];
7
    return 0;
8
}

所以，当容器储存的是普通对象的时候，并无大碍。但是如果储存的是指针，则必须要手动调用析构函数。

第 八 条：切勿创建包含 auto_ptr 的容器对象#

auto_ptr 的容器(简称COAP) 是被禁止的。当你拷贝一个 auto_ptr 时，它所指向的对象的所有权被移交到拷入的 auto_ptr 上，而它自身被置为 NULL。如果你的目标是包含智能指针的容器，这并不意味着你要倒霉，包含智能指针的容器是没有问题的。但 auto_ptr 非智能指针。顺带提一句，auto_ptr在c++11已被摒弃。应使用unique_ptr或shared_ptr做替代。

第 九 条：慎重选择删除元素的方法#

• 要删除容器中有特定值的所有对象：

  • 如果容器是vector、string或deque，则使用erase-remove习惯用法。

    • 1
      v.erase(remove(v.begin(), v.end(), VALUE), c.end);
      

      • 上面这句的要点是。remove仅是移除。他会把把每一个不和指定value相等的元素轮番赋值给first之后的空间。假设现在是112211要移除2，那么remove后应该是长成111111。最后两个数据是脏数据。remove返回的迭代器就指向倒数第二个1，也就是最开始的脏数据。然后erase使用这个迭代器为起点移除所有到结尾位置的数据。因为这一段全都是脏数据。记住，erase后，size改变，capacity不改变。如果需要改变capacity还需要配合swap或匿名对象。

  • 如果容器是list，则使用list::remove。

  • 如果容器是一个标准关联容器，则使用它的erase成员函数。

• 要删除容器中满足特定判别式（条件）的所有对象：

  • 如果容器是vector、string或deque，则使用erase-remove_if习惯用法。
  • 如果容器是list，则使用list::remove_if。
  • 如果容器是一个标准关联容器，则使用remove_copy_if和swap，或者写一个循环来遍历容器中的元素，记住当把迭代器传给erase时，要对它进行后缀递增。防止迭代器失效。

• 要在循环内部做某些（除了删除对象之外的）操作：

  • 如果容器是一个标准序列容器，则写一个循环来遍历容器中的元素，记住每次调用erase时，要用它的返回值更新迭代器。防止迭代器失效。
  • 如果容器是一个标准关联容器，则写一个循环来遍历容器中的元素，记住当把迭代器传给erase时，要对迭代器做后缀递增。防止迭代器失效。

第 十 条：了解分配子(allocator)的约定和限制 — 罄待深入了解#

• 你的分配子是一个模板，模板参数T代表你为它分配内存的对象的类型。

• 提供类型定义pointer和reference，但是始终让pointer为T* ，reference为T&。

• 千万别让你的分配子拥有随对象而不同的状态（per-object state）。通常，分配子不应该有非静态的数据成员。

• 记住，传给分配子的allocate成员函数的是那些要求内存的对象的个数，而不是所需的字节数。同时要记住，这些函数返回T* 指针（通过pointer类型定义），即使尚未有T对象被构造出来。

• 一定要提供嵌套的rebind模板，因为标准容器依赖该模板。

• 这里有一点 使用operator new的时候，给的大小是字节数。使用自定义allocator的时候，给的大小是对象的数量。

第 十二 条：切勿对STL容器的线程安全性有不切实际的依赖。#

对一个STL实现你最多只能期望：

• 多个线程读是安全的 。多个线程可以同时读同一个容器的内容，并且保证是正确的。自然地，在读的过程中，不能对容器有任何写入操作。
• 多个线程对不同的容器做写入操作是安全的 。多个线程可以同时对不同的容器做写入操作。

实现完全的容器线程安全性时可能采取的方式：

• 对容器成员函数的每次调用，都锁住容器直到调用结束。
• 在容器所返回的每个迭代器的生存期结束前，都锁住容器（比如通过begin或end调用）。
• 对于作用于容器的每个算法，都锁住该容器，直到算法结束。（实际上这样做没有意义。因为，如同在第32条中解释的，算法无法知道它们所操作的容器。尽管如此，在这里我们仍要讨论这一选择。因为即便这是可能的，我们也会发现这种做法仍不能实现线程安全性，这对于我们的讨论是有益的。）

个人理解：加锁就完事了。

下面的例子是一个不加锁也安全的例子。vec虽然是一个容器，但是这个容器里有10个小容器。我开了10个线程给这10个小容器进行多线程同时写入，是安全的。符合要求。也就是所谓的多个线程对不同的容器做写入操作。

1
void push(vector<int>& vec){
2
    for(int j = 0; j < 100; j++){
3
        vec.push_back(j);
4
    }
5
}
6
int main()
7
{
8
    vector<vector<int>> vec(10, vector<int>());
9
    thread th[10];
10
    for(int i = 0; i < 10; i++){
11
        th[i] = thread(push, ref(vec[i])); //注意，这里是核心。我vec虽然是一个容器，但是我这个容器里有10个小容器。我开了10个线程给这10个小容器进行多线程同时写入，是安全的。符合要求
12
    }
13
    for(int i = 0; i < 10; i++){
14
        th[i].join();
15
    }
16
    for(int i = 0; i < 10; i++){
17
        for(int j = 0; j < vec[i].size(); j++){
18
            cout << vec[i][j];
19
        }
20
        cout<<endl;
21
    }
22
    return 0;
23

24
}

第十四条：使用reserve来避免不必要的重新分配。#

对于 vector 和 string，增长过程是这样来实现的：每当需要更多空间时，就调用与 realloc类似的操作。这一类似于 realloc 的操作分为四部分：

• 分配一块大小为当前容量的某个倍数的新内存。在大多数实现中，vector 和 string 的容量每次以 2 的倍数增长，即，每当容器需要扩张时，它们的容量即加倍。
• 把容器的所有元素从旧的内存拷贝到新的内存中。
• 析构掉旧内存中的对象。
• 释放旧内存。

每当这些步骤发生时，vector或string中所有的指针、迭代器和引用都将变得无效。

通常有两种方式来使用reserve以避免不必要的重新分配。 第一种方式是，若能确切知道或大致预计容器中最终会有多少元素，则此时可以使用reserve。第二种方式是，先预留足够大的空间(根据你的需要而定)，然后，当把所有数据都加入以后，再去除多余的容量。

第十七条：使用“swap技巧”除去多余的容量#

讲过很多次了。不再赘述了。看下面杂记。

1
vector<typename>(container).swap(container);
2
vector<int>(c1).swap(c1);

表达式vector<typename>(container)创建一个临时的矢量，它是container的副本：这是由vector的复制构造函数来完成的。然而，vector的复制构造函数只为所复制的元素分配所需要的内存，所以这个临时矢量没有多余的容量。然后我们把临时矢量中的数据和container中的数据做swap操作，在这之后，container具有了被去除之后的容量，即原先临时变量的容量，而临时变量的容量则变成了原先container臃肿的容量。到这时（在语句结尾），临时vector被析构，从而释放了先前为container所占据的内存。

swap两个vector可简单理解为交换tag。

1
int main(){
2
    int a = 5;
3
    int b = 10;
4
    int c = 15;
5
    int*pa = &a;
6
    int*pb = &b;
7
    int*pc = &c;
8
    cout << &a << endl;     //0x61fdac
9
    cout << &*pa << endl;    //0x61fdac
10
    cout << &b << endl;      //0x61fda8
11
    cout << &*pb << endl;    //0x61fda8
12
    vector<int*> va = {pa, pb};
13
    vector<int*> vb = {pb, pc};
14
    cout << &va[0] << endl;    //0xde1490
15
    cout << &*va[0] << endl;  //0x61fdac
16
    cout << &vb[0] << endl;    //0xde14d0
17
    cout << &*vb[0] << endl;  //0x61fda8
18
    swap(va, vb);
19
    cout << &va[0] << endl;    //0xde14d0
20
    cout << &*va[0] << endl;  //0x61fda8
21
    cout << &vb[0] << endl;    //0xde1490
22
    cout << &*vb[0] << endl;  //0x61fdac
23
}

我们可以看到。VA和VB交换后，VA容器装的指针自己的地址由原来的0x61fdac换成了0xde1490。VB亦然。所以可理解为仅仅是把VA的铭牌摘下来换给了VB，VB换给了VA

第十八条：避免使用vector<bool>#

同时参考more effective 条款30。

作为一个STL容器，vector<bool>只有两点不对。首先，它不是一个STL容器。其次，它并不存储bool。除此以外，一切正常。

一个对象并不因为有人说它是一个STL容器，所以它就是了。一个对象要成为STL容器，就必须满足C++标准的第23.1节列出的所有条件。其中的一个条件是，如果c是包含对象T的容器，而且c支持operator[]，那么下面的代码必须能够被编译：

1
T* P = &C[0];

换句话说，如果你用operator[]取得了Container<T>中的一个T对象，那么你可以通过取它的地址得到一个指向该对象的指针。（这里假定T没有用非常规的方式对operator&做重载。）所以，如果vector<bool>是一个容器，那么下面这段代码必须可以被编译：

1
vector<bool>v;
2
bool* pb = &v[0];

但是它不能编译。不能编译的原因是，vector<bool>是一个假的容器，它并不真的储存bool，相反，为了节省空间，它储存的是bool的紧凑表示。在一个典型的实现中，储存在vector中的每个bool仅占一个二进制位，一个8位的字节可容纳8个bool。在内部，vector<bool>使用了与位域（bitfield）一样的思想，来表示它所存储的那些bool；实际上它只是假装存储了这些bool。位域与bool相似，它只能表示两个可能的值，但是在bool和看似bool的位域之间有一个很重要的区别:你可以创建一个指向bool的指针，而指向单个位的指针则是不允许的。所以你以为vector存了bool，但其实他储存的不是bool，自然使用[]下标访问返回的也不会是bool*类型的指针，自然无法给bool*类型的变量赋值

我们在more effective 条款30的笔记中写的例子就和这个差不多，类内套了一个类。同时operator[]返回的是代理类对象。所以现在我们可以很好的理解这个例子了。

当你需要 vector时，标准库提供了两种选择，可以满足绝大多数情况下的需求。

• 第一种是 deque。deque 几乎提供了 vector 所提供的一切(没有reserve和capacity)，但deque 是一个 STL 容器，而且它确实存储 bool。当然 deque 中元素的内存不是连续的，所以你不能把 deque 中的数据传递给一个期望 bool 数组的 C API。
• 第二种可以替代 vector 的选择是 bitset。bitset 不是 STL 容器，但它是标准 C++ 库的一部分。与 STL 容器不同的是，它的大小(即元素的个数)在编译时就确定了，所以它不支持插入和删除元素。

1
void func1() {
2
    std::vector<bool> v;
3
    v.push_back(false);
4
    std::cout << v[0] << " ";  // 0
5
    const auto b = v[0];
6
    auto c = b;
7
    c = true;
8
    std::cout << c << " " << b << endl;       // 1 1
9
    cout << &c << " " << &b << endl;          // 0x7ffd1f5c73c0 0x7ffd1f5c73b0
10
    cout << c._M_p << " " << b._M_p << endl;  // 0x5578bbd8eeb0 0x5578bbd8eeb0
11
}
12
void func2() {
13
    std::vector<int> v;
14
    v.push_back(0);
15
    std::cout << v[0] << " ";  // 0
16
    const auto b = v[0];
17
    auto c = b;
18
    c = 1;
19
    std::cout << c << " " << b << endl;  // 1 0
20
    cout << &c << " " << &b << endl;     // 0x7ffdc06bffac 0x7ffdc06bffa8
21
}
22
void func3() {
23
    std::vector<int*> v;
24
    v.push_back(new int(0));
25
    std::cout << *v[0] << " ";  // 0
26
    const auto b = v[0];
27
    auto c = b;
28
    *c = 1;
29
    std::cout << *c << " " << *b << endl;  // 1 1
30
    cout << &c << " " << &b << endl;       // 0x7ffdc06bffa8 0x7ffdc06bffa0
31
    cout << c << " " << b << endl;         // 0x563d96d19eb0 0x563d96d19eb0
32
    auto del = [](int* p) {
33
        delete p;
34
        p = nullptr;
35
    };
36
    std::for_each(v.begin(), v.end(), del);
37
}
38
int main() {
39
    func1();
40
    func2();
41
    func3();
42
}

第十九条：理解相等（equality）和等价（equivalence）的区别。#

标准关联容器（如set, map）总是保持排列顺序的，所以每个容器必须有一个比较函数（默认为less）来决定保持怎样的顺序。等价的定义正是通过该比较函数而确定的，因此，标准关联容器的使用者要为所使用的每个容器指定一个比较函数（用来决定如何排序）。如果该关联容器使用相等来决定两个对象是否有相同的值，那么每个关联容器除了用于排序的比较函数外，还需要另一个比较函数来决定两个值是否相等。（默认情况下，该比较函数应该是equal_to，但有趣的是，equal_to从来没有被用作STL的默认比较函数。当STL中需要相等判断时，一般的惯例是直接调用operator==。

个人理解：假如我们让使用set去忽略大小写地插入字符串。则我们会基于set一个仿函数告知他这一点。随后我们插入"abc" 和"ABC"

会发现只有第一个可以插入。是因为在这时候，"abc" 和"ABC"是等价的。但是"abc" 和"ABC"并不相等。等价是我们认为告知的。

第二十条：为包含指针的容器（关联或序列式容器）指定自定义比较器。#

如下代码，我们有一个装有指针的容器。如果按照默认排序 当我们使用如下代码

1
vector<string*> myvec;
2
sort(myvec.begin(), myvec.end());

其实会被隐含地推导为如下代码：

1
sort(myvec.begin(), myvec.end(), less<string*>);

是明显错误的。此处会对指针排序。所以必须自定义比较器。如下。顺便练习删除器。

1
void deleter(string* item){ //自定义删除器。
2
    if (item!=nullptr){
3
        delete item;
4
        item = nullptr;
5
    }
6
}
7

8
class mydeleter{ //自定义删除器。
9
    public:
10
        bool operator()(string* item){
11
            if(item != nullptr){
12
                delete item;
13
                item = nullptr;
14
            }
15
        }
16
};
17
class mysort{
18
    public:
19
        bool operator()(const string* a, const string* b) const{
20
            if(*a < *b){
21
                return true;
22
            }
23
            return false;
24
        }
25
};
26

27
int main(){
28
    vector<string*> myvec;
29
    myvec.push_back(new string("bcd"));
30
    myvec.push_back(new string("cde"));
31
    myvec.push_back(new string("abc"));
32

33

34
    sort(myvec.begin(), myvec.end()); //这种排序方式是错误的。这会按照指针的值来排序。错误的。
35
    sort(myvec.begin(), myvec.end(), mysort()); //必须使用自定义比较器。
36

37
    for_each(myvec.begin(), myvec.end(), mydeleter()); //记住释放指针容器内的指针。上下两种都可以
38
    for_each(myvec.begin(), myvec.end(), deleter); //记住释放指针容器内的指针。
39

40
    return 0;
41
}

• 尤其是关联容器在创建之时就需要提供比较器。而默认创建的指针关联式容器的比较器是对指针排序，这明显不是我们希望的。所以创建指针关联式容器的时候就必须指定好我们的自定义比较器。
• 包含智能指针或迭代器的容器亦如此。

第二十一条：总是让比较函数在等值情况下返回false。#

1
class myfunc{
2
    public:
3
    bool operator()(const int&a, const int& b) const{
4
        return a<=b; //注意这里
5
    }
6
};
7

8

9
int main(){
10
    set<int, myfunc> s;
11
    s.insert(10);
12
    s.insert(10);
13
    s.insert(11);
14
    for(auto i:s){
15
        cout << i << endl;
16
    }
17
}

这个set会储存两个10和一个11。这破坏了规则。

因为set会先判断两个参数是否等价。这意味着是根据我们的规则来的

他会这么判断：

1
!(10 <= 10) && !(10 >= 10);
2
!(true) && !(true);
3
false && false;
4
false;

这样他会返回不等价。于是就塞进去了。这不应该。

所以永远记住，在任何情况下都要让自定义比较函数在两个变量相等的情况下返回false。术语叫严格弱序化。

第二十二条：切勿直接修改set或multiset中的键。#

• 我们已经知道了无法修改map和multimap的key。是因为保存至红黑树的pair里面的key是const的。(下面提到了)。
• set不允许更改值是因为迭代器返回的是常量迭代器也就是const iterator

假设我们现在有个student，里面包含了id和name。我们有个装有它的set。并且使用ID来进行排序。

假设我们想更改名字，可以吗？可以。因为针对set的排序是student的id。也就是说，实际上，student的ID是这个set中元素的键(key), 而其他数据比如name只不过和这个键绑在一起而已。所以没有理由不能更改非key的部分。

但是实际做起来有些麻烦。

1
class student{
2
    public:
3
        student(int x, const string& y):id(x), name(y){};
4
        int id;
5
        string name;
6

7
        void change_name(const string& s){
8
            name = s;
9
        }
10
};
11

12
class mycomp{
13
    public:
14
        bool operator()(const student a, const student b) const{
15
            if(a.id < b.id){
16
                return true;
17
            }
18
            return false;
19
        }
20
};
21

22

23
int main(){
24

25
    set<student, mycomp> my_set;
26
    my_set.insert(student(1,"miku"));
27
    my_set.insert(student(2,"luka"));
28
    my_set.insert(student(3,"nozomi"));
29

30
    auto t = my_set.begin();
31
    cout << t->name << endl; //输出miku
32
    const_cast<student&>(*t).change_name("changedmiku"); //1
33
    static_cast<student>(*t).change_name("changedmiku"); //2
34
    cout << t->name << endl; //经过1输出changedmiku, 经过2不变，输出miku。
35

36

37

38
    return 0;
39

40

41
}

• 这里的1是对的。2是错的。我来解释为什么。
• 首先，我们提到了，set拿到的迭代器是常量迭代器也就是const iterator。所以我们需要把它的const弄掉才行。
  • 注意为什么我们使用了student&做为新的类型？第一是因为const_cast只接受指针或引用类型的转换。不支持转换对象。
  • 其次，我们需要作用到原来的对象上。所以必须使用引用的方式。来让这个临时cast出来的对象是一个原对象的引用，这样才能施加操作到原来的对象上。
  • 记得我们在杂记2说的，四种cast不改变原对象，会生成一个新的对象。
• 如果使用2的方式，我们会cast出一个临时的匿名对象出来。然后把change_name施加到了临时对象上。所以没用。

如果我们想自由，安全的对四种关联容器进行元素修改。应使用如下几步：

1. 找到你想修改的容器的元素。如果你不能肯定最好的做法，第45条介绍了如何执行一次恰当的搜索来找到特定的元素。
2. 为将要被修改的元素做一份副本。在map或multimap的情况下，请记住，不要把该副本的第一个部分声明为const。毕竟，你想要改变它。
3. 修改该副本，使它具有你期望它在容器中的值。
4. 把该元素从容器中删除，通常是通过调用erase来进行的（见第9条）。
5. 把新的值插入到容器中。如果按照容器的排列顺序，新元素的位置可能与被删除元素的位置相同或紧邻，则使用“提示”（hint）形式的insert，以便把插入的效率从对数时间提高到常数时间。把你从第1步得来的迭代器作为提示信息。

1
student target(2,"luka"); //目标对象
2
auto t = my_set.find(target); // 1 寻找目标对象
3
if(t != my_set.end()){ //如果找到了
4
    student temp(*t);  // 2 获取一个目标副本
5
    temp.change_name("changed_luka"); //3 对副本施加更改操作
6
    t = my_set.erase(t); //4 把容器内的对应源元素删除。注意set的erase会返回一个指向删除的元素后面的第一个元素的迭代器。
7
    my_set.insert(t, temp); //5 在指定位置插入。
8
}

第二十三条：考虑使用排序的vector替换关联容器#

这个建议的前提是这个容器会有如下三个阶段：

• 创建一个新的数据结构，并插入大量元素，在这个阶段，几乎所有的操作都是插入和删除操作。很少或几乎没有查找操作。
• 查找阶段：查询该数据结构找到特点的信息，在这个阶段，几乎所有的操作都是查找很少或几乎没有删除。
• 重组阶段：改变数据结构的内容。

为什么这样的容器最好使用vector？

• 关联式容器针对保存的每一个对象都需要额外的指针。比如map和set使用红黑树，unordered使用哈希表。都需要额外指针。这也就导致需要更多的内存。
• 关联式容器不保证是否在物理内存中相邻，所以在进行如二分查找时，会遇到更多的缺页错误。

但是这里必须保证vector有序，但是在插入或删除元素的时候，或重新分配内存的时候都会进行移动或拷贝。这开销极大，但是关联容器却没有这个缺点。所以对数据结构的使用方式是：查找操作几乎从不跟插入和删除操作混在一起”时，再考虑使用排序的vector而不是关联容器才是合理的。

第四十五条：正确区分count、find、binary_search、lower_bound、upper_bound和equal_range。#

• 在使用序列容器和multimap, multiset的时候，find效率比count快。因为count总是会遍历完整个区间 或 检查容器中的每一个对象。而find找到后就可以返回。
  • 但是在set和map里面不是问题，因为set不允许重复值，map不允许重复键。所以count总是会返回0或1

针对花括号初始化器的问题#

• 不推导语境在模板笔记
• std::initializer_list的笔记在杂记3

1
int main() {
2
    vector<vector<int>> myvec;
3
    myvec.push_back({1, 3}); // OK
4
    myvec.emplace_back({1, 3}); //不行.
5
}

为什么这个地方用emplace_back不可以? 因为你以为{1,3}是initializer_list, 但是其实它啥都不是. 因为看见这种花括号列表, 想让它变成initializer_list是有条件的. 要么是我们在做函数调用且该函数入参恰好需要个initializer_list, 要么是用auto推导一下.

同时, push_back是函数, 而emplace_back是函数模板. 所以说它需要依照类型推导来合成. 也就是emplace_back接受一个以initializer_list为入参的前提是{1,3}是一个initializer_list. 但是{1,3}变成initializer_list的前提是emplace_back有接受一个initializer_list的版本. 然后就死锁了.

顺带一提, 形参非initializer_list的时候且实参是花括号初始化器列表的时候, 这个是不推导语境.

所以应该怎么办? 有三种办法.

1
myvec.emplace_back(initializer_list<int>{1, 3}); // 手动构造initializer_list
2
myvec.emplace_back<initializer_list<int>>({1, 3}); // 显式指明模板参数, 放弃自动推导
3
auto input = {1,3}; // 使用auto推导, 此时auto类型推导为initializer_list<int>
4
myvec.emplace_back(input); // 利用游戏规则

总结#

所以上面我们发现了，emplace_back 和push_back主要的使用场景区别就在于是否可以被原地构造。也就是可以被原地构造的时候（直接传入对象构造函数所需要的参数的时候）使用emplace_back。其余场合没有区别。另外就是需要注意用花括号初始化器的问题.

一句话：push_back总是先创建对象，然后拷贝/移动到容器。emplace则可以选择直接在容器内构造对象。所以只有当我们想原地构造（直接放入容器 （直接传入构造函数参数，调用构造函数来直接构建对象））的时候选用emplace才是最佳方法。如果是想要移入一个已存在的对象，则没有区别。因为二者遇到右值对象的时候都会调用移动构造。

std::piecewise_construct#

std::piecewise_construct_t 是一个空类标签类型，用于区分接受两个元组实参的不同函数。也就是说，这个tag表明后面的两个 tuple 应当被分别传递给 std::pair 的两个成员的构造函数（first 和 second），而不是将整个tuple 作为一个单独的参数传递。

这个东西会匹配到一个pair针对tuple的特化：

1
template <class _T1, class _T2>
2
template <typename... _Args1, typename... _Args2>
3
_GLIBCXX20_CONSTEXPR inline pair<_T1, _T2>::pair(piecewise_construct_t, tuple<_Args1...> __first,
4
                                                 tuple<_Args2...> __second)
5
    : pair(__first, __second, typename _Build_index_tuple<sizeof...(_Args1)>::__type(),
6
           typename _Build_index_tuple<sizeof...(_Args2)>::__type()) {} // 委托构造给下面的
7

8
template <class _T1, class _T2>
9
template <typename... _Args1, size_t... _Indexes1, typename... _Args2, size_t... _Indexes2>
10
_GLIBCXX20_CONSTEXPR inline pair<_T1, _T2>::pair(tuple<_Args1...>& __tuple1,
11
                                                 tuple<_Args2...>& __tuple2,
12
                                                 _Index_tuple<_Indexes1...>,
13
                                                 _Index_tuple<_Indexes2...>)
14
    : first(std::forward<_Args1>(std::get<_Indexes1>(__tuple1))...),
15
      second(std::forward<_Args2>(std::get<_Indexes2>(__tuple2))...) {}
16
// stl_pair.h
17
template <typename... _Args1, typename... _Args2>
18
_GLIBCXX20_CONSTEXPR pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>);

std::forward_as_tuple#

这个东西很简单，就是把一对参数包装为一个tuple。该元组在以右值为实参时拥有右值引用数据成员，否则拥有左值引用数据成员。

1
template< class... Types >
2
tuple<Types&&...> forward_as_tuple( Types&&... args ) noexcept;

注意，不可以和make_tuple混用，下面的是绝对错误的

1
auto tup = forward_as_tuple(1, 2, std::string("abc"));
2
string a = get<2>(tup);
3
cout << a << endl;
4
static_assert(std::is_same_v<decltype(tup), std::tuple<int&&, int&&, string&&>>); // true

这个tuple内的所有对象全是临时对象的引用。

总结#

所以整体来说，就是我们遇到无参或多参构造的时候，也就是需要把构造函数参数传递给emplace但是受限于语法支持时，我们选择用forward_as_tuple包装一下。第一个参数是tag，第二个参数是key的构造函数参数包装成的tuple，第三个参数是value的构造函数参数包装成的tuple。然后在构造pair的时候把第一个tuple的参数解包转发给key的构造函数，第二个tuple的参数解包转发给value的构造函数。这样一来就可以解决多参或无参的问题，来原地构造。 所有pair的情况，包括其他容器内存pair的情况都可以用这个方法进行原地构造

1
std::tie(it, inserted) = map.insert({x, y});  // tuple unpacking 更多解释查看cppreference
2
std::tie(x1, y1, z1) == std::tie(x2, y2, z2); // component-wise comparison

使用emplace_back的语法：#

1
vector<vector<int>>temp;
2
temp.emplace_back(vector<int>{...,...});

在vector中判断特定元素是否存在的方法：#

• find
  • find会在查找到指定值后立即返回，所以它一般比count更快（因为count总是要遍历整个容器）。
• find_if
  • 支持判别式（复杂查找）,返回第一个元素的迭代器
• count
  • 查找元素个数
• any_of
  • 和find_if类似，但是返回bool
• binary_search
  • 可以先排序再查找。

总结

• 对于已经排序的vector，使用binary_search
• 仅判断是否存在某元素，使用find
• 需要某元素总个数时，使用count
• 支持复杂条件的查找时，使用any_of(仅知道是否存在)/find_if(返回了第一个元素的迭代器)

使用哈希表的容器，增删改查都是O(1)。使用红黑树的容器，增删改查都是O(nlogn)#

• map, set, multimap, multiset 上述四种容器采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为:

  • 插入: O(logN)
  • 查看:O(logN)
  • 删除:O(logN)

• unordered_map,unordered_set,unordered_multimap, unordered_multiset 上述四种容器采用哈希表实现，不同操作的时间复杂度为：

  • 插入:O(1)，最坏情况O(N)。
  • 查看:O(1)，最坏情况O(N)。
  • 删除:O(1)，最坏情况O(N)。

map和unordered map区别#

右下角那句话：要求结果有序（按key排序）

关键点：#

指针容器的复制是浅拷贝。不能正确复制指针指向的内容。#

举例：

1
vector<int*> v1 = ...;
2
vector<int*> v2 = v1;

此时不会调用拷贝构造。因为和析构一样，容器调用的拷贝构造或拷贝赋值是帮助你调用。意思就是他会帮助你调用容器内储存的类型的对应的拷贝构造或拷贝赋值。所以说深拷贝浅拷贝完全依赖于你的拷贝构造和拷贝赋值的实现方式。

这也是为什么指针容器无法深拷贝。因为指针容器储存的是指针，任何类型的指针的类型都是指针。指针类型的拷贝构造和拷贝赋值都是浅拷贝，所以他无法调用到int类型的拷贝构造，只会调用指针类型的拷贝构造。

因为此时假设

1
v1[0] = 0x100;
2
*v1[0] = 0x999;
3
//我们复制
4
v2[0] = 0x200;
5
*v2[0] = 0x999;

vector可以复制每一个元素。就好比int x = y一样。但是这个元素如果是指针的话，他不会进行深拷贝。

指针给指针赋值仅仅是将一个指针指向的地址，复制给了另一个指针，导致两个指针指向一个地址。但是并没有生成新的对象。因为对象和对象指针不一样。

指向对象的指针本质是指针。遵循指针的一般规则。

1
vector<int*>vec1;
2
int* b = new int(5);
3
vec1.push_back(b);
4
delete b;
5
delete vec1[0];

再次强调序列式容器的erase是覆盖式删除#

erase是覆盖式删除，也就是把要删除数据位置后面的数据依次拷贝至要删除的数据位置和后面的位置上，并且调用脏数据的析构，但是调用析构函数不代表数据会被真正意义上的删除或内存释放。比如指针容器。指针容器只会调用指针类型自己的析构而不会调用指针指向对象的析构。内存释放依靠的是delete。

erase调整的是size，就是调整end迭代器位置。

1
class myclass{
2
    public:
3
    int val;
4
    myclass(int x):val(x){};
5
    ~myclass(){
6
        val = 8964;
7
    }
8
};
9
int main() {
10
    vector<myclass> myvec{0,1,2,3,4,5,6};
11
    myvec.erase(myvec.begin());
12
    myvec.erase(myvec.begin());
13
    myvec.erase(myvec.begin());
14
    myvec.erase(myvec.begin());
15
    for(auto i:myvec){
16
        cout << i.val << endl; //输出4 5 6
17
    }
18
    cout << (*myvec.end()).val << endl;   //输出8964
19
    cout << (*(myvec.end()+1)).val << endl;  //输出8964
20
    cout << (*(myvec.end()+2)).val << endl;  //输出8964
21
    cout << (*(myvec.end()+3)).val << endl;  //输出8964
22
    cout << (*(myvec.end()+4)).val << endl; //已经越界。所以是非法数据。
23
    return 0;
24

25
}

我们分析一下过程

1
0 1 2 3 4 5 6 覆盖式删除
2
1 2 3 4 5 6 6 删除后，调用最末尾元素的析构。注意我们的析构，只是进行一个值的覆盖。因为是栈对象，又没有delete所以依旧能访问到元素
3
1 2 3 4 5 6 8964 调用析构后。

以上这一部分是调用了一次erase的情况。如果我们扩展下就是

1
1 2 3 4 5 6 8964
2
2 3 4 5 6 8964 8964
3
3 4 5 6 8964 8964 8964
4
4 5 6 8964 8964 8964 8964
5
    ↑end 在这

这个期望很符合我们上面代码的注释部分。

看一下vector在erase的情况下的迭代器失效到底是什么意思#

先看代码，这是for循环删除的代码。

1
class myclass{
2
    public:
3
    int val;
4
    myclass(int x):val(x){};
5
    ~myclass(){
6
        val = 8964;
7
    }
8
};
9
int main() {
10
    vector<myclass> myvec{ 0,1,2,3,4,5,6 };
11
    //for(auto iter = myvec.begin(); iter != myvec.end(); iter++){ //注意这一行
12
    for(auto iter = myvec.begin(); iter < myvec.end(); iter++){
13
        myvec.erase(iter);
14
    }
15
    for(auto i:myvec){
16
        cout << i.val << endl; //输出 1 3 5
17
    }
18
    return 0;
19

20
}

注意！随机访问迭代器支持>和<比较！！

过程：

1
0 1 2 3 4 5 6 开始
2
↑iter
3
1 2 3 4 5 6 8964 删除后
4
↑iter
5

6
1 2 3 4 5 6 8964 第二次for循环，iter++
7
  ↑iter
8
1 3 4 5 6 8964 8964 删除后
9
  ↑iter
10

11
1 3 4 5 6 8964 8964  第三次for循环，iter++
12
  ↑iter
13
1 3 5 6 8964 8964 8964 删除后
14

15
1 3 5 6 8964 8964  第三次for循环，iter++
16
    ↑iter
17
1 3 5 8964 8964 8964 8964 删除后
18
    ↑end

我们已经通过上面的删除样例了解了，删除后数据会被覆盖过来，然后再进行iter++就会跨越一个数据。就会出现迭代器失效。

假如我们用的不是大小比较，用的是end比较，那么会出现大问题。for循环一直到天荒地老合法内存的尽头。

因为我们在最后一次删除的时候，由于是先删除的，所以end会往前缩一格，会缩到第四位也就是当前iter的位置。然后iter++移动到第五位。这时候进入for循环判断++后的iter，这时候发现 iter在第五位，end在第四位，当然不相等。于是就会一直走下去。

各种容器迭代器失效场景#

迭代器失效的自增操作#

1
student target(2,"luka");
2
auto t = my_set.find(target);
3
if(t != my_set.end()){
4
    student temp(*t);
5
    temp.change_name("changed_luka");
6
    my_set.erase(t++); //注意这里
7
    my_set.insert(t, temp);
8
}