C++ 巩固基础之六

发表于 阅读次数： 评论数： 本文字数： 2.7k 阅读时长 ≈ 2 分钟

大纲

近容器

概念介绍

在 C++ 中，常见的近容器有以下几种：

  • 数组
  • string
  • bitset

迭代器

概念介绍

在 C++ 中，常见的迭代器有以下几种：

  • iterator 和 const_iterator
  • reverse_iterator 和 const_reverse_iterator

提示

在 C++ 中，iterator 迭代器是从 const_iterator 迭代器继承而来的。

案例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

int main() {
    // 设置随机种子
    srand(time(nullptr));

    vector<int> v1;

    for (int i=0; i< 10; i++) {
        v1.push_back(rand() % 100  + 1);
    }

    // 正向迭代器
    for (vector<int>::iterator it = v1.begin(); it!= v1.end(); ++it){
        if (*it % 2 ==0 ){
            // 可以赋值
            *it = *it + 1;
        }
        cout << *it << " ";
    }
    cout << endl;

    // 常量的正向迭代器
    for (vector<int>::const_iterator it = v1.begin(); it!= v1.end(); ++it){
        if (*it % 2 ==0 ){
            // 错误写法，不可以赋值
            // *it = *it + 1;
        }
        cout << *it << " ";
    }
    cout << endl;

    // 反向迭代器
    for (vector<int>::reverse_iterator it = v1.rbegin(); it!= v1.rend(); ++it){
        if (*it % 2 ==0 ){
            // 可以赋值
            *it = *it + 1;
        }
        cout << *it << " ";
    }
    cout << endl;

    // 常量的反向迭代器
    for (vector<int>::const_reverse_iterator it = v1.rbegin(); it!= v1.rend(); ++it){
        if (*it % 2 ==0 ){
            // 错误写法，不可以赋值
            // *it = *it + 1;
        }
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

程序运行输出的结果如下：

1
2
3
4
25 93 69 85 75 19 79 39 13 19
25 93 69 85 75 19 79 39 13 19
19 13 39 79 19 75 85 69 93 25
19 13 39 79 19 75 85 69 93 25

函数对象

概念介绍

  • C++ 中的函数对象，其作用类似 C 语言中的函数指针。
  • 在 C++ 中，将拥有 operator() 小括号运算符重载函数的对象称作 “函数对象”，或者称作 “仿函数”。
  • 通过函数对象调用 operator ()，会产生内联的效果，其执行效率比较高，因为没有函数调用的开销。
  • 由于函数对象是使用类生成的，因此函数对象可以拥有相关的成员变量，比如可以通过成员变量来记录函数对象的使用次数。
  • 在 C++ 中，常见的函数对象有：less、greater。

案例代码一

这里主要演示 C++ 中函数指针的使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>

using namespace std;

template<typename T>
bool my_greater(T a, T b) {
    return a > b;
}

template<typename T>
bool my_less(T a, T b) {
    return a < b;
}

// Compare 是 C++ 的库函数模板
template<typename T, typename Compare>
bool compare(T a, T b, Compare func) {
    // 这里通过函数指针调用函数，是没办法实现内联的（即使通过 inline 关键字将目标函数声明为内联函数），执行效率较低，因为有函数调用的开销
    return func(a, b);
}

int main() {
    cout << compare(1, 3, my_greater<int>) << endl;
    cout << compare(1, 3, my_less<int>) << endl;
    return 0;
}

程序运行输出的结果如下：

1
2
0
1

案例代码二

这里主要演示 C++ 中函数对象的使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>

using namespace std;

template<typename T>
// 函数对象
class mygreater {

public:
    bool operator()(T a, T b) {
        return a > b;
    }

};

template<typename T>
// 函数对象
class myless {

public:
    bool operator()(T a, T b) {
        return a < b;
    }

};

// Compare 是 C++ 的库函数模板
template<typename T, typename Compare>
bool compare(T a, T b, Compare func) {
    // 这里调用函数对象，会产生内联，执行效率比较高，没有函数调用的开销
    return func(a, b);
}

int main() {
    cout << compare(1, 3, mygreater<int>()) << endl;
    cout << compare(1, 3, myless<int>()) << endl;
    return 0;
}

程序运行输出的结果如下：

1
2
0
1

案例代码三

这里主要演示如何在 C++ 的 STL 中使用函数对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

void test01() {
    cout << "============ test01() ============" << endl;

    // 使用函数对象，让优先级队列里的元素从小到大排序（默认从大到小排序）
    priority_queue<int, vector<int>, greater<int>> q1;
    for (int i = 0; i < 10; i++) {
        int val = rand() % 100 + 1;
        q1.push(val);
        cout << val << " ";
    }
    cout << endl;

    while (!q1.empty()) {
        cout << q1.top() << " ";
        q1.pop();
    }
    cout << endl;
}

void test02() {
    cout << "============ test02() ============" << endl;

    // 使用函数对象，让有序集合里的元素从大到小排序（默认从小到大排序）
    set<int, greater<int>> s1;
    for (int i = 0; i < 10; i++) {
        int val = rand() % 100 + 1;
        s1.insert(val);
        cout << val << " ";
    }
    cout << endl;

    for (set<int>::iterator it = s1.begin(); it != s1.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

}

int main() {
    // 设置随机种子
    srand(time(nullptr));

    test01();
    test02();
    return 0;
}

程序运行输出的结果如下：

1
2
3
4
5
6
============ test01() ============
4 64 45 55 2 82 62 84 51 74 
2 4 45 51 55 62 64 74 82 84 
============ test02() ============
40 8 50 65 100 26 48 34 43 43 
100 65 50 48 43 40 34 26 8

泛型算法

概念介绍

  • C++ 泛型算法 = 模板（Template） + 迭代器 + 函数对象。
  • C++ 泛型算法的参数接收的都是迭代器，而且还可以接收函数对象。
  • C++ 常见的泛型算法有以下几种：
    • sort：排序算法
    • find：查找算法
    • find_if：条件查找算法
    • binary_search：二分查找算法
    • for_each：遍历算法

特别注意

二分查找算法（binary_search）并不适用于降序排序（从大到小）的容器，只适用于升序排序（从小到大）的容器，因为它默认是按照升序排序来查找元素的。

案例代码一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int arr[] = {12, 23, 7, 11, 39, 25, 45, 48, 58};
    vector<int> v1(arr, arr + sizeof(arr) / sizeof(arr[0]));

    for (int val : v1) {
        cout << val << " ";
    }
    cout << endl;

    // 排序算法（默认升序排序，即从小到大排序）
    sort(v1.begin(), v1.end());

    // 或者降序排序（从大到小）
    // sort(v1.begin(), v1.end(), greater<int>());

    for (int val : v1) {
        cout << val << " ";
    }
    cout << endl;

    // 查找算法（不要求容器按顺序存储元素）
    vector<int>::iterator it1 = find(v1.begin(), v1.end(), 48);
    if (it1 != v1.end()) {
        cout << "found number 48" << endl;
    } else {
        cout << "not found 48" << endl;
    }

    // 二分查找算法，只适用于升序排序（从小到大）的容器，如果容器的元素是按降序排序（从大到小），否则二分查找算法无法正常工作
    if (binary_search(v1.begin(), v1.end(), 25)) {
        cout << "found number 25" << endl;
    } else {
        cout << "not found 25" << endl;
    }

    return 0;
}

程序运行输出的结果如下：

1
2
3
4
12 23 7 11 39 25 45 48 58 
7 11 12 23 25 39 45 48 58 
found number 48
found number 25

案例代码二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int main() {
    int arr[] = {22, 33, 8, 21, 59, 35, 55, 63, 70};
    vector<int> v1(arr, arr + sizeof(arr) / sizeof(arr[0]));

    // 排序算法（默认升序排序，即从小到大排序）
    sort(v1.begin(), v1.end());

    for (int val : v1) {
        cout << val << " ";
    }
    cout << endl;

    // 条件查找算法，将 48 按顺序插入到 vector 容器中

    // 使用绑定器（已过时的写法）
    vector<int>::iterator it2 = find_if(v1.begin(), v1.end(), bind1st(less<int>(), 48));

    // 使用绑定器（现代 C++ 的写法）
    // vector<int>::iterator it2 = find_if(v1.begin(), v1.end(), bind(greater<int>(), placeholders::_1, 48));

    // 使用绑定器（Lambda 表达式的写法）
    // vector<int>::iterator it2 = find_if(v1.begin(), v1.end(), [](int val) -> bool { return val > 48; });

    v1.insert(it2, 48);

    for (int val : v1) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

程序运行输出的结果如下：

1
2
8 21 22 33 35 55 59 63 70 
8 21 22 33 35 48 55 59 63 70

案例代码三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 设置随机种子
    srand(time(nullptr));

    vector<int> v1;
    for (int i = 0; i < 10; i++) {
        v1.push_back(rand() % 100 + 1);
    }

    for (int val : v1) {
        cout << val << " ";
    }
    cout << endl;

    // 遍历算法
    for_each(v1.begin(), v1.end(), [](int val) -> void {
        // 打印所有偶数
        if (val % 2 == 0) {
            cout << val << " ";
        }
    });
    cout << endl;

    return 0;
}

程序运行输出的结果如下：

1
2
46 81 98 43 35 60 61 68 77 96 
46 98 60 68 96

容器原理

emplace () 函数剖析

核心概念

在 C++ 标准模板库（STL）中，大多数容器提供了类似 emplace_xxx() 的函数，比如 emplace_back()、emplace_front()、emplace() 等。这些函数是 C++ 11 引入的，用于原地构造元素，可以避免不必要的拷贝或移动操作，从而提高性能。

emplace_xxx() 函数的优点

  • 效率更高：避免多余的拷贝或移动操作。
  • 语法更直观：直接传构造参数，更贴近业务逻辑。
  • 构造时即插入：特别适合含有复杂构造函数的对象。

常见容器中的 emplace_xxx() 函数

容器类型emplace_xxx() 函数说明
vector / dequeemplace_back()在末尾就地构造元素
listemplace_back() / emplace_front()支持双端插入元素
map / set / unordered_map / unordered_setemplace()在合适位置插入新元素
stack / queue / priority_queueemplace()等价于对应容器的 emplace_back() 或 emplace_front()
forward_listemplace_front()在前端插入元素

特别注意

如果传给 emplace_xxx() 的参数本身就是一个已经构造好的对象，那它就退化成了 push_xxx() 的效果，失去了原地构造的优势。

案例代码一

这里简单介绍一下 vector 容器的 emplace_back() 函数如何使用，还有它和普通的 push_back() 函数有什么区别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <vector>

using namespace std;

class Test {

public:

    Test(int a) {
        cout << "Test(int)" << endl;
    }

    Test(int a, int b) {
        cout << "Test(int, int)" << endl;
    }

    // 析构函数
    ~Test() {
        cout << "~Test()" << endl;
    }

    // 带左值引用的拷贝构造函数
    Test(const Test &) {
        cout << "Test(const Test &)" << endl;
    }

    // 带右值引用的拷贝构造函数
    Test(Test &&) {
        cout << "Test(Test &&)" << endl;
    }

};

void test01() {
    cout << "============ test01 ===========" << endl;

    Test t1(10);
    vector<Test> v1;
    v1.reserve(100);

    // 如果直接插入普通对象，两者没有任何区别
    v1.push_back(t1);
    v1.emplace_back(t1);
}

void test02() {
    cout << "============ test02 ===========" << endl;

    vector<Test> v1;
    v1.reserve(100);

    // 如果直接插入临时对象，两者没有任何区别
    v1.push_back(Test(20));
    v1.emplace_back(Test(20));
}

void test03() {
    cout << "============ test03 ===========" << endl;

    vector<Test> v1;
    v1.reserve(100);

    // 给emplace_back()传入Test对象构造所需要的参数，会直接在容器底层调用对象的构造函数，即不会产生临时对象
    v1.emplace_back(30);
    v1.emplace_back(40, 50);
}

int main() {
    test01();
    test02();
    test03();
    return 0;
}

程序运行输出的结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
============ test01 ===========
Test(int)
Test(const Test &)
Test(const Test &)
~Test()
~Test()
~Test()
============ test02 ===========
Test(int)
Test(Test &&)
~Test()
Test(int)
Test(Test &&)
~Test()
~Test()
~Test()
============ test03 ===========
Test(int)
Test(int, int)
~Test()
~Test()

案例代码二

这里将模拟实现 vector 容器的 emplace_back() 函数。值得一提的是，由于篇幅有限，下述代码并没有实现 vector 容器的扩容功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <stdexcept>

using namespace std;

// 容器的空间配置器
template<typename T>
struct MyAllocator {

    // 申请内存
    T *allocate(size_t size) {
        return (T *) malloc(size * sizeof(T));
    }

    // 释放内存
    void deallocate(T *p) {
        free(p);
    }

    // 对象构造
    template<typename... Types>
    void construct(T *ptr, Types &&... args) {
        // 在指定的内存上构造对象（定位 new）
        new(ptr)T(forward<Types>(args)...);
    }

    // 对象析构
    void destroy(T *p) {
        // ~T() 代表了 T 类型对象的析构函数
        p->~T();
    }

};

// 自定义 Vector 容器
template<typename T, typename Alloc = MyAllocator<T>>
class MyVector {

public:
    // 构造函数
    MyVector(int size = 10) {
        _idx = 0;
        _size = size;

        // 分配内存空间
        _vec = _allocator.allocate(size);

        // 检查内存分配结果
        if (!_vec) {
            throw bad_alloc();
        }
    }

    // 析构函数
    ~MyVector() {
        // 析构容器内的有效元素
        for (int i = 0; i < _idx; i++) {
            _allocator.destroy(_vec + i);
        }

        // 释放堆上的内存
        _allocator.deallocate(_vec);
    }

    // 禁止拷贝
    MyVector(const MyVector &v) = delete;

    // 禁止赋值
    MyVector &operator=(const MyVector v) = delete;

    // 往尾部插入元素，基于引用折叠 + 类型完美转发
    template<typename Type>
    void push_back(Type &&val) {
        if (_idx >= _size) {
            throw out_of_range("Vector capacity exceeded.");
        }

        _allocator.construct(_vec + _idx, forward<Type>(val));
        _idx++;
    }

    // 往尾部插入元素，基于可变参数模板 + 引用折叠 + 类型完美转发
    template<typename... Types>
    void emplace_back(Types &&... args) {
        if (_idx >= _size) {
            throw out_of_range("Vector capacity exceeded.");
        }

        _allocator.construct(_vec + _idx, forward<Types>(args)...);
        _idx++;
    }

private:
    T *_vec;            // 指向容器的内存首地址
    size_t _size;       // 容器的大小
    size_t _idx;        // 容器最新元素的位置
    Alloc _allocator;   // 空间配置器

};
  • 测试代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Test {

public:

    Test(int a) {
        cout << "Test(int)" << endl;
    }

    Test(int a, int b) {
        cout << "Test(int, int)" << endl;
    }

    // 析构函数
    ~Test() {
        cout << "~Test()" << endl;
    }

    // 带左值引用的拷贝构造函数
    Test(const Test &) {
        cout << "Test(const Test &)" << endl;
    }

    // 带右值引用的拷贝构造函数
    Test(Test &&) {
        cout << "Test(Test &&)" << endl;
    }

};

void test01() {
    cout << "============ test01 ===========" << endl;

    Test t1(10);
    MyVector<Test> v1;

    // 如果直接插入普通对象，两者没有任何区别
    v1.push_back(t1);
    v1.emplace_back(t1);
}

void test02() {
    cout << "============ test02 ===========" << endl;

    MyVector<Test> v1;

    // 如果直接插入临时对象，两者没有任何区别
    v1.push_back(Test(20));
    v1.emplace_back(Test(20));
}

void test03() {
    cout << "============ test03 ===========" << endl;

    MyVector<Test> v1;

    // 给emplace_back()传入Test对象构造所需要的参数，会直接在容器底层调用对象的构造函数，即不会产生临时对象
    v1.emplace_back(30);
    v1.emplace_back(40, 50);
}

int main() {
    test01();
    test02();
    test03();
    return 0;
}
  • 测试结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
============ test01 ===========
Test(int)
Test(const Test &)
Test(const Test &)
~Test()
~Test()
~Test()
============ test02 ===========
Test(int)
Test(Test &&)
~Test()
Test(int)
Test(Test &&)
~Test()
~Test()
~Test()
============ test03 ===========
Test(int)
Test(int, int)
~Test()
~Test()

高频面试题

提示

  • 下述面试题都来自 "商汤科技" 的一面，难度属于是简单级别。

  • (1) 程序的内存布局

    • 从下往上分别是：.text 、.rodata、.data、.bss、堆、栈、内核空间，如图所示

  • (2) 堆和栈的区别

    • 堆内存由用户分配（new），而栈内存由系统分配（函数调用时）
    • 堆内存的数据结构通常是二叉堆、大根堆、小根堆，而栈内存的数据结构是栈

  • (3) 函数调用的参数是怎样传递的

    • 通过汇编代码的分析，可以知道底层是通过压栈的方式来传递参数

  • (4) 函数调用的参数是按什么顺序传递的

    • 函数调用是从右往左传递参数

  • (5) 为什么函数调用的参数要从右往左压栈

    • 因为 C/C++ 需要支持可变参函数（即函数的参数数量不确定）
    • C 语言的可变参数函数，缺乏类型安全
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      #include <iostream>
      #include <cstdarg>

      using namespace std;

      // 传统 C 语言风格的可变参数函数
      void printNumbers(int num, ...) {
          va_list args;
          va_start(args, num); // 初始化 args，num 是可变参数的第一个参数
          for (int i = 0; i < num; i++) {
              int n = va_arg(args, int); // 获取下一个参数
              cout << n << " ";
          }
          va_end(args); // 清理
          cout << endl;
      }

      int main() {
          printNumbers(3, 10, 20, 30);     // 输出：10 20 30
          printNumbers(5, 1, 2, 3, 4, 5);  // 输出：1 2 3 4 5
          return 0;
      }
    • C++ 可变模板参数函数，提供了类型安全，并且能更灵活地处理不同类型的参数
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      #include <iostream>

      using namespace std;

      // 可变模板参数函数
      template<typename... Args>
      void printNumbers(Args... args) {
          // 使用折叠表达式打印参数
          ((cout << args << " "), ...);
          cout << endl;
      }

      int main() {
          printNumbers(10, 20, 30);       // 输出：10 20 30
          printNumbers(1, 2, 3, 4, 5);    // 输出：1 2 3 4 5
          return 0;
      }

  • (6) 有以下一个函数 func

    • 主函数里面通过 string s = func(s1, s2); 调用该函数，说一下调用了什么构造函数和调用顺序，以及析构函数的调用顺序
      • 关键考点：如果用临时对象去拷贝构造新对象，那么临时对象就不会产生，也就是直接构造新对象就行，这是任意 C++ 编译器都会做的优化，如图所示
    • 如果在 func 函数内写成 return s1 + s2;，这与原来的写法有什么区别
      • 省略了原来字符串对象 tmp 的构造函数和析构函数的调用
        1
        2
        3
        4
        string func(string s1, string s2) {
            string tmp = s1 + s2;
            return tmp;
        }

  • (7) 在一个结构体里面定义一个 char 和 double 变量，它的内存布局是怎样的

    1
    2
    3
    4
    5
    6
    struct Data {
        char a;
        double b;
    };

    cout << sizeof(Data) << endl;  // 输出 16
    • char a 占 1 字节
    • double b 占 8 字节，并且通常需要 8 字节对齐。
    • 由于 char a 只有 1 字节，而 double b 需要 8 字节对齐，因此编译器会在 a 之后填充 7 个字节，使 b 在 8 字节边界对齐，最终 sizeof(Data) = 16。

  • (8) 空结构体占用多少个字节

    • C++ 中，空结构体占用 1 个字节
    • C 语言中，空结构体占用 0 个字节

  • (9) 如何防止指针使用带来的内存泄漏

    • 使用带引用计数的智能指针：share_ptr
    • 使用不带引用计数的智能指针：unique_ptr、scoped_ptr、auto_ptr
    • 使用特殊的智能指针：weak_ptr（不增加引用计数，但可用于观察 shared_ptr 管理的资源）
智能指针所有权带引用计数适用场景
unique_ptr独占否资源独占，生命周期明确
shared_ptr共享是资源共享，生命周期不固定
scoped_ptr独占否生命周期受限于作用域，适用于简单的场景，避免资源泄漏
weak_ptr观察 shared_ptr否避免 shared_ptr 循环引用
auto_ptr独占（拷贝时转移）否⚠ 已废弃，建议改用 unique_ptr