C++ 巩固基础之六

发表于 阅读次数： 评论数： 本文字数： 1.9k 阅读时长 ≈ 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

常见面试题

提示

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

  • (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
    • 使用不带引用计数的智能指针：auto_ptr、unique_ptr
    • 使用特殊的智能指针：weak_ptr（不增加引用计数，但可用于观察 shared_ptr 管理的资源）
    智能指针所有权引用计数适用场景
    unique_ptr独占❌资源独占，生命周期明确
    shared_ptr共享✅资源共享，生命周期不固定
    weak_ptr观察 shared_ptr❌避免 shared_ptr 循环引用
    auto_ptr独占（拷贝时转移）❌⚠ 已废弃，建议改用 unique_ptr