文章

c++高频总结六

发表于 更新于
作者 匆匆那年 24 分钟阅读

unique_ptr和shared_ptr区别

std::unique_ptr 和 std::shared_ptr 是 C++ 标准库中常用的智能指针，它们的主要区别在于所有权模型和引用计数。

1. std::unique_ptr

  • 所有权：独占所有权。一个对象只能由一个 std::unique_ptr 拥有，不能被多个 unique_ptr 共享。

  • 特点

    ：

    • 禁止拷贝（Copy），但支持移动（Move）。
    • 当 std::unique_ptr 超出作用域或被显式释放时，会自动销毁所管理的对象。

  • 适用场景：适合需要确保对象有唯一所有权，避免共享和复杂的生命周期管理。

  • 示例

    ：

    1
2
3
4
5
6
7
8
9
10
11
12
13

    #include <iostream>
#include <memory>
  
int main() {
    std::unique_ptr<int> ptr1 = std::make_unique<int>(42);
    // std::unique_ptr<int> ptr2 = ptr1; // 错误：拷贝构造被禁用
    std::unique_ptr<int> ptr2 = std::move(ptr1); // 转移所有权
    if (!ptr1) {
        std::cout << "ptr1 is empty\n";
    }
    std::cout << "Value: " << *ptr2 << "\n";
    return 0;
}

2. std::shared_ptr

  • 所有权：共享所有权。多个 std::shared_ptr 可以共享同一个对象的所有权。

  • 引用计数：使用引用计数来跟踪管理对象的生命周期。当最后一个 std::shared_ptr 离开作用域时，才会销毁所管理的对象。

  • 特点

    ：

    • 支持拷贝（Copy）和移动（Move）。
    • 比 std::unique_ptr 多了引用计数开销，稍慢。

  • 适用场景：适合需要多个对象共享所有权的场景，特别是当对象可能在多个地方同时被访问。

  • 示例

    ：

    1
2
3
4
5
6
7
8
9
10
11

    #include <iostream>
#include <memory>
  
int main() {
    std::shared_ptr<int> ptr1 = std::make_shared<int>(42);
    std::shared_ptr<int> ptr2 = ptr1; // 引用计数增加
    std::cout << "Use count: " << ptr1.use_count() << "\n";
    ptr2.reset(); // ptr2 放弃所有权
    std::cout << "Use count after reset: " << ptr1.use_count() << "\n";
    return 0;
}

3. 区别对比

特性std::unique_ptrstd::shared_ptr
所有权模型独占所有权共享所有权
拷贝支持不支持支持
移动支持支持支持
引用计数无有
性能较高（无额外的引用计数开销）较低（需要维护引用计数）
适用场景唯一所有权，避免重复管理共享所有权，复杂的生命周期管理

4. 选择建议

  • 使用 std::unique_ptr：
    • 当明确需要唯一所有权时，优先选择。
    • 性能优先级更高，且不需要共享对象。
  • 使用 std::shared_ptr：
    • 当对象需要在多个地方共享且生命周期复杂时使用。
    • 注意防止循环引用（需要配合 std::weak_ptr 使用）。

例如，在树结构或图结构中，需要小心 std::shared_ptr 引发的循环引用问题，这种情况下可以结合 std::weak_ptr 解决。

右值引用

右值引用（rvalue reference）是 C++11 引入的一种新特性，用于支持移动语义和完美转发。它的核心目的是通过转移资源，避免不必要的拷贝，提高程序性能。

1. 什么是右值引用

右值引用的语法是使用两个连续的 &：&&。

  • 左值：

    • 表示内存中有明确地址的对象，可以取地址。

    • 生命周期长，可多次使用。

    • 示例：变量、引用等。

      1

      int a = 10; // a 是左值

  • 右值：

    • 没有明确地址的临时对象，通常是表达式的结果。

    • 生命周期短，不能取地址。

    • 示例：字面量、函数返回的非引用值、临时对象。

      1

      int b = a + 10; // (a + 10) 是右值

  • 右值引用：

    • 用于绑定到右值的引用。

    • 允许通过右值引用操作和复用右值，主要用于实现移动语义。

    • 示例：

      1

      int&& r = 10; // 右值引用绑定到字面量 10

2. 右值引用的用途

(1) 移动语义

右值引用的核心作用是实现移动语义，即在对象拷贝时，通过“转移”资源避免昂贵的深拷贝操作。

  • 普通拷贝（深拷贝）：

    1
2

    std::string s1 = "Hello";
std::string s2 = s1; // 拷贝了 s1 的内容，耗时

  • 移动语义（浅拷贝 + 资源转移）：

    1
2

    std::string s1 = "Hello";
std::string s2 = std::move(s1); // 转移 s1 的内容到 s2，s1 变为空

  • 示例：用户自定义类实现移动构造函数

    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

    #include <iostream>
#include <utility> // for std::move
  
class MyClass {
    int* data;
public:
    MyClass(int value) : data(new int(value)) {}
    ~MyClass() { delete data; }
  
    // 移动构造函数
    MyClass(MyClass&& other) noexcept : data(other.data) {
        other.data = nullptr; // 转移资源
    }
  
    void print() const {
        if (data) std::cout << "Value: " << *data << "\n";
        else std::cout << "Empty\n";
    }
};
  
int main() {
    MyClass obj1(10);
    MyClass obj2 = std::move(obj1); // 触发移动构造
    obj1.print(); // 输出 Empty
    obj2.print(); // 输出 Value: 10
    return 0;
}

(2) 完美转发

右值引用结合模板，支持完美转发（Perfect Forwarding），即将函数的参数保持原样传递给其他函数（左值或右值）。

  • 示例：

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

    #include <iostream>
#include <utility>
  
void process(int& lval) { std::cout << "Lvalue\n"; }
void process(int&& rval) { std::cout << "Rvalue\n"; }
  
template <typename T>
void forwarder(T&& arg) {
    process(std::forward<T>(arg)); // 保持参数原有的左值或右值性质
}
  
int main() {
    int x = 10;
    forwarder(x);        // 输出 Lvalue
    forwarder(20);       // 输出 Rvalue
    forwarder(std::move(x)); // 输出 Rvalue
    return 0;
}

  • 原理：

    • std::forward<T>能够根据 T的类型判断是左值还是右值：
      • 如果 T 是 int&，传递左值。
      • 如果 T 是 int&&，传递右值。

3. 右值引用与左值引用的对比

特性左值引用（T&）右值引用（T&&）
绑定对象左值右值
典型用途传递和修改已有对象移动语义、完美转发
是否支持取地址可以不可以
主要目标保持对象生命周期临时性对象的资源复用

4. 注意事项

  • 右值引用不能绑定到左值，但可以通过 std::move 将左值强制转换为右值：

    1
2

    int a = 10;
int&& r = std::move(a); // std::move(a) 将 a 转换为右值

  • 避免使用转移后的对象：

    1
2
3

    std::string s = "Hello";
std::string s2 = std::move(s); // s 的资源被转移
std::cout << s; // 未定义行为，s 的状态不可预测

  • 右值引用优先用于性能优化：

    • 对于小对象，使用移动语义可能没有明显的性能提升。
    • 适合需要管理动态内存或其他昂贵资源的场景。

右值引用的出现大大提升了 C++ 的性能和灵活性，但需要合理设计和使用，避免潜在问题。

函数参数可不可以传右值

在 C++ 中，函数参数可以传递右值，而且右值传递有多种方式，具体取决于参数类型的定义：

1. 直接传递右值

函数的参数可以是按值传递、右值引用传递，甚至可以通过模板参数完美转发右值。

(1) 按值传递

  • 特点：右值通过按值传递会产生一次拷贝。

  • 示例：

    1
2
3
4
5
6
7
8
9
10
11
12

    #include <iostream>
  
void foo(int x) {
    std::cout << "Value: " << x << std::endl;
}
  
int main() {
    foo(10); // 右值 10 被按值传递
    int a = 20;
    foo(a);  // 左值 a 被拷贝
    return 0;
}
    • 优点：简单直接，适合小对象。
    • 缺点：大对象时性能较低，因为涉及拷贝。

(2) 右值引用传递

  • 特点：右值引用专门绑定到右值，可以避免拷贝，直接操作右值。

  • 示例：

    1
2
3
4
5
6
7
8
9
10
11
12

    #include <iostream>
  
void foo(int&& x) {
    std::cout << "Rvalue: " << x << std::endl;
}
  
int main() {
    foo(10); // 右值 10 传递给右值引用
    // int a = 20;
    // foo(a); // 错误：左值不能绑定到右值引用
    return 0;
}
    • 优点：高效，适合移动语义场景。
    • 注意：左值无法直接传递给右值引用。

(3) 结合 std::move 将左值转为右值

  • 左值可以通过 std::move 转换为右值，以绑定到右值引用参数。

  • 示例：

    1
2
3
4
5
6
7
8
9
10
11

    #include <iostream>
  
void foo(int&& x) {
    std::cout << "Rvalue: " << x << std::endl;
}
  
int main() {
    int a = 20;
    foo(std::move(a)); // 将左值 a 转为右值传递
    return 0;
}

(4) 通过模板实现完美转发

  • 使用模板和 std::forward 保持参数的左值或右值特性，右值可以直接完美传递。

  • 示例：

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

    #include <iostream>
#include <utility>
  
template <typename T>
void foo(T&& x) {
    std::cout << (std::is_rvalue_reference<T&&>::value ? "Rvalue" : "Lvalue") << std::endl;
}
  
int main() {
    int a = 20;
    foo(a);        // 输出 Lvalue
    foo(10);       // 输出 Rvalue
    foo(std::move(a)); // 输出 Rvalue
    return 0;
}
    • 优点：支持同时处理左值和右值，灵活且通用。
    • 注意：必须小心避免意外的拷贝或移动。

2. 小结

  • 函数参数当然可以传递右值。
  • 右值可以按值传递（拷贝），也可以通过右值引用（避免拷贝），甚至使用模板完美转发保持右值特性。
  • 选择方法时应根据场景考虑性能和灵活性：
    • 小对象：按值传递即可。
    • 大对象：使用右值引用或完美转发以提高效率。
    • 不确定参数是否是左值或右值：优先使用模板和 std::forward 实现通用方案。

参考c/c++堆栈实现自己的堆栈。要求：不能使用stl容器

以下是一个使用原生 C++ 语言实现的堆栈（Stack）。我们会使用动态分配的数组来存储数据，同时提供基本的堆栈操作，包括 push、pop 和 top，并管理栈的容量动态增长。

实现思路

  1. 数据结构：
    • 使用动态数组存储堆栈元素。
    • 使用一个指针变量或索引表示栈顶位置。
    • 使用一个变量记录当前容量，用于动态扩展存储空间。
  2. 操作实现：
    • push: 添加元素到栈顶，如果空间不足，动态扩展栈的容量。
    • pop: 移除栈顶元素。
    • top: 返回栈顶元素，但不删除。
    • isEmpty: 检查栈是否为空。
    • size: 返回栈中元素个数。
  3. 动态扩容：
    • 当栈满时，分配一个容量更大的新数组，将原数组数据拷贝到新数组，释放旧数组内存。

完整代码

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

#include <iostream>
#include <stdexcept> // 用于抛出异常

class Stack {
private:
    int* data;       // 动态数组指针
    int capacity;    // 栈的容量
    int topIndex;    // 栈顶索引

    // 动态扩展容量
    void resize() {
        int newCapacity = capacity * 2; // 扩容为原来的两倍
        int* newData = new int[newCapacity];
        for (int i = 0; i < capacity; ++i) {
            newData[i] = data[i]; // 复制数据到新数组
        }
        delete[] data; // 释放旧数组内存
        data = newData;
        capacity = newCapacity;
    }

public:
    // 构造函数
    Stack(int initialCapacity = 10) 
        : capacity(initialCapacity), topIndex(-1) {
        if (initialCapacity <= 0) {
            throw std::invalid_argument("Capacity must be greater than 0");
        }
        data = new int[capacity];
    }

    // 析构函数
    ~Stack() {
        delete[] data;
    }

    // 压栈操作
    void push(int value) {
        if (topIndex + 1 == capacity) { // 栈满时扩容
            resize();
        }
        data[++topIndex] = value;
    }

    // 出栈操作
    void pop() {
        if (isEmpty()) {
            throw std::out_of_range("Stack is empty");
        }
        --topIndex;
    }

    // 获取栈顶元素
    int top() const {
        if (isEmpty()) {
            throw std::out_of_range("Stack is empty");
        }
        return data[topIndex];
    }

    // 检查栈是否为空
    bool isEmpty() const {
        return topIndex == -1;
    }

    // 返回栈中元素个数
    int size() const {
        return topIndex + 1;
    }
};

int main() {
    try {
        Stack stack;

        stack.push(10);
        stack.push(20);
        stack.push(30);

        std::cout << "Stack top: " << stack.top() << std::endl;
        std::cout << "Stack size: " << stack.size() << std::endl;

        stack.pop();
        std::cout << "After pop, stack top: " << stack.top() << std::endl;

        stack.pop();
        stack.pop();

        // Uncommenting this will throw an exception
        // stack.pop(); 

    } catch (const std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }

    return 0;
}

代码说明

  1. 构造函数:
    • 初始化栈的容量和动态数组。
    • topIndex 用于表示栈顶索引，初始化为 -1 表示栈为空。
  2. 动态扩容:
    • 当 push 操作导致栈满时，通过 resize 方法分配新数组。
    • 扩容时将容量翻倍（2 倍），并将旧数据拷贝到新数组中。
  3. 异常处理:
    • 栈为空时调用 pop 或 top，会抛出 std::out_of_range 异常。
    • 初始化时非法容量会抛出 std::invalid_argument 异常。
  4. 功能验证:
    • 在 main 函数中测试了栈的基本操作。

扩展功能建议

  1. 模板支持:

    • 可以改为模板类，使栈支持任意类型的数据。
    1
2

    template <typename T>
class Stack { /* 实现类似 */ };

  2. 添加容量缩减功能:

    • 当栈中元素较少时，可以考虑释放部分空间以节省内存。

  3. 优化拷贝:

    • 添加拷贝构造函数和移动构造函数，支持栈的复制和转移。

  4. 多线程安全:

    • 使用互斥锁（std::mutex）保护栈操作，以实现线程安全。

通过以上实现，您可以自定义和扩展堆栈功能以满足更复杂的需求。

stl容器了解吗？底层如何实现：vector数组，map红黑树，红黑树的实现

STL 容器是 C++ 标准模板库中的重要组成部分，包含多种数据结构如 vector、map、set 等。它们的底层实现基于不同的数据结构，提供高效的操作性能。

以下是 STL 容器 vector 和 map 的底层实现，以及红黑树的详细说明。

1. std::vector 的底层实现

特点

  • vector是动态数组：
    • 支持随机访问（时间复杂度 O(1)O(1)）。
    • 元素连续存储，类似 C 风格数组。
    • 动态扩展容量，插入新元素时若容量不足，会重新分配更大的内存。

底层实现

  • 使用动态分配的连续内存存储元素。
  • 主要成员变量：
    • data：指向动态分配的内存的指针。
    • size：当前元素的个数。
    • capacity：分配的内存容量。

关键点

  1. 扩容机制：
    • 当容量不足时，新容量通常是当前容量的 2 倍（避免频繁分配内存）。
    • 重新分配时，会将旧数据拷贝到新内存中。
  2. 空间管理：
    • std::allocator 用于管理内存分配和释放。
  3. 时间复杂度：
    • 插入和删除：
      • 末尾操作 O(1)（均摊）。
      • 中间插入/删除 O(n)（涉及元素移动）。
    • 访问：随机访问 O(1)。

示例

1
2
3

std::vector<int> v;
v.push_back(1);
v.push_back(2);
  • 初始容量可能为 0，push_back(1) 分配内存，容量扩展到 1。
  • 再次 push_back(2)，容量扩展到 2，并复制已有数据。

2. std::map 的底层实现

特点

  • std::map是基于红黑树实现的有序关联容器：
    • 键值对（key-value）存储。
    • 键（key）唯一，按升序排列。
    • 插入、删除、查找的时间复杂度 O(log⁡n)。

底层实现

  • 底层使用红黑树。
  • 红黑树是一种自平衡二叉搜索树（BST），通过颜色规则保持树的平衡，从而保证操作复杂度为 O(log⁡n)。

时间复杂度

  • 插入、删除：O(log⁡n)。
  • 查找：O(log⁡n)。
  • 遍历：按键值顺序，时间复杂度 O(n)。

3. 红黑树的实现

特点

红黑树是一种自平衡二叉搜索树，满足以下特性：

  1. 每个节点是红色或黑色。
  2. 根节点是黑色。
  3. 每个叶子节点（nullptr 或 NIL）是黑色。
  4. 如果一个节点是红色，则其子节点必须是黑色（即不能有连续的红色节点）。
  5. 从任意节点到其每个叶子节点的路径都包含相同数量的黑色节点（黑高相等）。

插入操作

  1. 插入节点作为红色节点。
  2. 检查树是否违反红黑树性质：
    • 如果违反规则，通过旋转和重新着色修正。
  3. 可能需要执行以下修复操作：
    • 左旋：右孩子变为父节点。
    • 右旋：左孩子变为父节点。
    • 颜色调整。

删除操作

  1. 删除节点，可能需要调整树平衡。
  2. 通过颜色调整和旋转恢复红黑树性质。

旋转示例

  • 左旋

    ：

    1
2
3
4
5
6
7
8
9
10
11
12

    Node* rotateLeft(Node* root, Node* x) {
    Node* y = x->right;
    x->right = y->left;
    if (y->left) y->left->parent = x;
    y->parent = x->parent;
    if (!x->parent) root = y;
    else if (x == x->parent->left) x->parent->left = y;
    else x->parent->right = y;
    y->left = x;
    x->parent = y;
    return root;
}

时间复杂度

  • 插入、删除、查找操作：O(log⁡n)。

总结对比

容器类型底层数据结构时间复杂度（插入/删除/查找）特点
std::vector动态数组插入末尾 O(1)，其他 O(n)支持随机访问，动态扩容，连续存储
std::map红黑树O(log⁡n)有序存储，支持按键值顺序遍历
红黑树红黑树O(log⁡n)自平衡二叉搜索树，确保高效操作

通过这些实现，STL 容器实现了高效、通用和灵活的功能，同时为用户屏蔽了底层复杂性。

C++, C++面经
C++ 面经
本文由作者按照 CC BY 4.0 进行授权