C++八股7

1. 什么是STL？

STL，即标准模板库

STL从广义上讲主要包括三大部分：算法、容器和迭代器。

2. 什么是RAII？

RAII 的全称是 Resource Acquisition Is Initialization（资源获取即初始化），这是一种 C++ 中的编程范式，用于管理资源（如内存、文件句柄、网络连接等）的生命周期。

资源的分配与对象的构造绑定：在对象创建时（调用构造函数）申请或分配资源。

资源的释放与对象的析构绑定：在对象销毁时（调用析构函数）自动释放资源。

智能指针（std::shared_ptr和std::unique_ptr）即RAII最具代表的实现，使用智能指针，可以实现自动的内存管理，再也不需要担心忘记delete造成的内存泄漏。

3.++it 和 it++ 的区别以及哪个更好?

前置递增 (++it)：不需要额外创建临时对象，因此效率更高。

int& operator++() {
    *this += 1;  // 将当前对象加 1
    return *this; // 返回当前对象的引用
}

后置递增 (it++)：后置递增首先会创建一个临时对象来保存当前值，然后调用前置递增操作修改当前对象的值，最后返回临时对象。

int operator++(int) {
    int temp = *this; // 创建一个临时对象保存当前值
    ++*this;          // 调用前置递增操作，将当前对象加 1
    return temp;      // 返回临时对象
}

4. 简述哈希表的基本原理？什么是哈希冲突？有哪些解决方法？

哈希表的基本原理：通过一个哈希函数将键（Key）映射到一个固定范围的索引位置（桶，Bucket）

• 哈希函数计算：将键（Key）通过哈希函数转换为一个整数值（哈希值）。

• 映射到桶：根据哈希值确定数据在哈希表中的存储位置（桶）。

• 插入或查找：将数据存入对应的桶中，或者从桶中查找数据。

哈希冲突： 不同的键通过哈希函数映射到同一个哈希值。

解决哈希冲突的方法：

• 链地址法： 每个桶维护一个链表（或其他数据结构），当发生冲突时，将冲突的键值对存储在链表中。

• 开放地址法：

  常见的探测方法有：

  • 线性探测（Linear Probing）：依次检查当前桶的下一个桶。
  • 二次探测（Quadratic Probing）：以平方递增的方式检查桶。
  • 双重哈希（Double Hashing）：使用第二个哈希函数计算步长。

• 再哈希法

  • 使用多个哈希函数，当第一个哈希函数发生冲突时，尝试使用第二个哈希函数重新计算位置。
  • 优点：减少冲突的概率。
  • 缺点：增加了计算复杂度。

STL中的hashtable使用的是链地址法解决hash冲突问题

5.vector与list的区别与应用？怎么找某vector或者list的倒数第二个元素?STL 中vector删除其中的元素，迭代器如何变化？

vector：

• 基于动态数组实现，内存是连续的。
• 支持高效的随机访问（时间复杂度为 O(1)），因为可以通过索引直接定位到任意元素。
• 插入和删除操作效率较低（时间复杂度为 O(n)），因为在中间或头部插入/删除时需要移动大量数据。
• 动态扩容：当容量不足时，会重新分配更大的内存块，并将原有数据拷贝到新内存中。

list：

• 基于双向链表实现，内存是非连续的。
• 不支持随机访问（时间复杂度为 O(n)），需要通过遍历链表才能访问指定位置的元素。
• 插入和删除操作效率高（时间复杂度为 O(1)），只需要修改相关节点的指针即可。
• 每个节点包含三个部分：元素值、指向前一个节点的指针（prev）和指向后一个节点的指针（next）。

如何找到 vector 或 list 的倒数第二个元素：

• 由于 vector 支持随机访问，可以通过下标直接访问倒数第二个元素

• 由于 list 不支持随机访问，无法通过下标直接访问元素。但可以使用反向迭代器来访问倒数第二个元素：

  #include <iostream>
  #include <list>
  
  int main() {
      std::list<int> lst = {1, 2, 3, 4, 5};
      if (lst.size() >= 2) {
          auto it = lst.rbegin(); // 反向迭代器，指向最后一个元素
          ++it;                   // 移动到倒数第二个元素
          std::cout << "The second last element is: " << *it << std::endl;
      } else {
          std::cout << "List has fewer than 2 elements." << std::endl;
      }
      return 0;
  }

vector中的迭代器在使用后就失效了，而list的迭代器在使用之后还可以继续使用。

vector 的迭代器失效：

• vector 是基于连续内存的动态数组实现的。当发生插入或删除操作时，可能会导致内存重新分配（例如扩容），或者需要移动元素以保持连续性。这种情况下，原有的迭代器可能指向无效的内存地址。

  #include <iostream>
  #include <vector>
  int main() {
      std::vector<int> vec = {1, 2, 3, 4, 5};
      auto it = vec.begin() + 2; // 指向第三个元素（值为 3）
      std::cout << "Before insertion: " << *it << std::endl;
      vec.insert(vec.begin() + 1, 10); // 在第二个位置插入元素 10
      // 尝试访问迭代器
      std::cout << "After insertion: " << *it << std::endl; // 可能导致未定义行为
      return 0;
  }

list 的迭代器失效：

• list 是基于双向链表实现的，每个节点独立存储，并通过指针连接。插入和删除操作只会影响相邻节点的指针，而不会影响其他节点的地址。因此，list 的迭代器在插入或删除后通常仍然有效。

  #include <iostream>
  #include <list>
  
  int main() {
      std::list<int> lst = {1, 2, 3, 4, 5};
      auto it = std::next(lst.begin(), 2); // 指向第三个元素（值为 3）
      std::cout << "Before insertion: " << *it << std::endl;
      lst.insert(std::next(lst.begin(), 1), 10); // 在第二个位置插入元素 10
      // 继续访问迭代器
      std::cout << "After insertion: " << *it << std::endl; // 安全且正确
      return 0;
  }

  注：std::next: 基于给定的迭代器，向前或向后移动指定的步数，返回一个新的迭代器。

6. reserve 和 resize 的区别

reserve(n)： 只分配内存，不影响元素数量。

• 只改变 capacity()，即预分配的总空间大小。
• 不会改变 size()，也不会初始化新分配的内存。

std::vector<int> vec;
vec.reserve(10); // 预分配 10 个元素的空间
std::cout << vec.size() << " " << vec.capacity(); // 输出：0 10

resize: 改变元素数量，并可能分配更多内存。

• 改变 size()，即实际存储的元素数量
• 如果 n > size()，会初始化新增的元素（对于基本类型，默认初始化为 0）。

std::vector<int> vec;
vec.resize(10); // 调整大小为 10
std::cout << vec.size() << " " << vec.capacity(); // 输出：10 10

7. 容器内部删除一个元素

顺序容器(vector、deque):

• erase(it) 不仅会使被删除元素的迭代器失效，还会使被删除元素之后的所有迭代器失效。

• 不能使用 erase(it++)

• 正确的删除方式：erase 的返回值是下一个有效的迭代器，可以直接赋值给当前迭代器。

  for (auto it = c.begin(); it != c.end(); ) {
      if (需要删除(*it)) {
          it = c.erase(it); // erase 返回下一个有效迭代器
      } else {
          ++it; // 如果不删除，则正常递增迭代器
      }
  }

关联容器（map、set、multimap、multiset）

• 可以安全地使用 erase(it++)

8.map、set是怎么实现的，红黑树是怎么能够同时实现这两种容器？ 为什么使用红黑树？

map 和 set 的底层实现:

• map 和 set 是 C++ STL 中的关联容器，它们的底层实现通常基于红黑树。红黑树是一种自平衡二叉搜索树，它能够在插入、删除和查找操作中保持对数时间复杂度 $O(log⁡n)$。

红黑树的核心特性：

• 每个节点要么是红色，要么是黑色。
• 根节点是黑色。
• 每个叶子节点（NIL 节点）是黑色。
• 如果一个节点是红色，那么它的两个子节点必须是黑色（即没有连续的红色节点）。
• 从任意节点到其每个叶子的所有路径都包含相同数量的黑色节点。

map 和 set 的区别：

• set：

  • 底层红黑树的节点数据类型为 key（即存储的值本身）。
  • 插入和查找时，直接根据 key 进行操作。

• map：

  • 底层红黑树的节点数据类型为 key + value（即键值对）。
  • 插入和查找时，根据 key 进行操作，但节点中还存储了与 key 对应的 value。

为什么使用红黑树？

• 自动排序：红黑树作为一种二叉搜索树，能够自然地按照 key 的顺序组织数据。

• 时间复杂度低：红黑树的操作（如插入、删除、查找）的时间复杂度为 $O(log⁡n)$，这比线性时间复杂度 $O(n)$​高效得多。

  注：相比于 AVL 树，在插入和删除时的调整开销较小。

9.关于this指针你知道什么？

• this 是一个常量指针（const pointer），指向当前对象的首地址。

• 它是一个隐含参数，编译器会自动将其作为非静态成员函数的第一个参数传递给函数。

  this 指针的作用：

• 访问类的成员

• 返回当前对象： 可以直接使用 return *this;

this 指针是什么时候创建的？

• this 指针在调用成员函数时由编译器生成，并在成员函数执行结束后销毁。

10.a=10,b=30,如何不使用新的变量交换两个数

使用异或：

#include <iostream>
using namespace std;
int main() {
    int a = 10, b = 30;
    // 交换逻辑
    a = a ^ b; // a = 10 ^ 30
    b = a ^ b; // b = (10 ^ 30) ^ 30 = 10
    a = a ^ b; // a = (10 ^ 30) ^ 10 = 30
    cout << "a = " << a << ", b = " << b << endl;
    return 0;
}

11.双端队列（deque)是否支持随机访问？

std::deque（双端队列）是 C++ STL 中的一个容器，支持在两端高效地插入和删除元素。它的底层实现基于分段连续存储结构，每个段是一个固定大小的连续内存块，这些段通过指针链接起来。这种设计使得 std::deque 能够在两端进行高效的插入操作。

std::deque支持随机访问，可以通过下标直接访问任意位置的元素。

12.举三个智能指针的应用场景

• std::shared_ptr 在多线程编程中保证线程安全的引用计数

  在多线程环境中，多个线程可能需要共享同一个对象（例如数据库连接池、配置文件对象等），并且需要确保对象在所有线程都使用完毕后才被释放。std::shared_ptr 的引用计数是线程安全的，因此可以用来实现这种共享。

  #include <iostream>
  #include <memory>
  #include <thread>
  class DatabaseConnection {
  public:
      void query(const std::string& sql) {
          std::cout << "Executing query: " << sql << std::endl;
      }
  };
  void threadTask(std::shared_ptr<DatabaseConnection> conn, const std::string& queryStr) {
      conn->query(queryStr); // 使用共享的数据库连接
  }
  int main() {
      auto dbConn = std::make_shared<DatabaseConnection>(); // 创建一个共享的数据库连接
      std::thread t1(threadTask, dbConn, "SELECT * FROM users");
      std::thread t2(threadTask, dbConn, "SELECT * FROM products");
      t1.join(); // 等待线程1完成
      t2.join(); // 等待线程2完成
      // 当所有线程都完成后，dbConn 自动释放
  }

• std::unique_ptr 在工厂模式中返回独占所有权的对象

  std::unique_ptr 明确表示对象的所有权不可共享。

• std::weak_ptr：检测对象是否已被销毁

  使用 std::weak_ptr 来检测对象是否仍然有效（即是否已经被销毁）。

  #include <iostream>
  #include <memory>
  
  class EventListener {
  public:
      void onEvent() {
          std::cout << "Event triggered!" << std::endl;
      }
  };
  
  int main() {
      std::shared_ptr<EventListener> listener = std::make_shared<EventListener>();
      std::weak_ptr<EventListener> weakListener = listener; // 创建弱引用
      // 模拟事件触发
      if (auto strongListener = weakListener.lock()) { // 尝试提升为 shared_ptr
          strongListener->onEvent();
      } else {
          std::cout << "Listener has been destroyed." << std::endl;
      }
      // 销毁 listener
      listener.reset();
      // 再次尝试触发事件
      if (auto strongListener = weakListener.lock()) {
          strongListener->onEvent();
      } else {
          std::cout << "Listener has been destroyed." << std::endl;
      }
  }

  注：weakListener.lock() 是 C++ 中 std::weak_ptr 提供的一个成员函数，用于尝试将弱引用（std::weak_ptr）提升为强引用（std::shared_ptr）。它的主要作用是检查底层对象是否仍然存在，并在对象有效时返回一个 std::shared_ptr。对象不存在返回空指针。

12.举例说明万能引用和完美转发的作用

万能引用： 指的是那些可以绑定到左值引用或右值引用的引用类型

当一个模板函数的参数类型为 T&& 并且 T 是通过模板参数推导出来的，则该参数是一个万能引用。

#include <iostream>
#include <utility>
template<typename T>
void displayType(T&& val) { // 这里 T&& 是一个万能引用
    std::cout << "Value: " << val << std::endl;
}
int main() {
    int x = 10;
    displayType(x);        // 左值传递给万能引用
    displayType(20);       // 右值传递给万能引用
    return 0;
}

完美转发:

完美转发: 允许函数模板将参数按其原始形式（包括值类别：左值或右值）转发给另一个函数。这意味着如果传入的是一个右值，那么它将以右值的形式被转发；如果是左值，则以左值的形式被转发。

• 完美转发借助于万能引用和 std::forward，能够让函数模板准确地将参数按照它们的原始类型和值类别转发给其他函数，保持了参数的特性和优化机会

• #include <iostream>
  #include <utility> // std::forward 所在头文件
  // 一个简单的函数，用于接收左值或右值
  void process(int& x) {
      std::cout << "Lvalue reference: " << x << std::endl;
  }
  void process(int&& x) {
      std::cout << "Rvalue reference: " << x << std::endl;
  }
  // 模板函数，使用 std::forward 实现完美转发
  template<typename T>
  void wrapper(T&& arg) {
      process(std::forward<T>(arg)); // 使用 std::forward 转发参数
  }
  int main() {
      int x = 42;
      wrapper(x);       // 传入左值
      wrapper(42);      // 传入右值
      return 0;
  }
  

13.extern “C”的作用

extern “C”： 用于告诉编译器按照C语言的方式编译和链接函数或变量，来解决兼容性的问题。

为什么需要extern “C”？

C++: 支持函数重载，在编译时会修改函数名，加入参数类型信息。

C: 不支持重载，编译后函数名不会改变。