https://github.com/huihut/interview?tab=readme-ov-file#problems

STL

  • STL的六大部件和联系
  • STL容器知道哪些，都解释一下，原理是什么，实现一下链表（接下来就可能考察算法题了）
  • map，multmap，set，multset的原理（接下来会考察二叉树相关的题，我后面会介绍）
  • hashtable的作用与原理
  • 操作符重载问题
  • 前置++与后置++的区别，操作符重载的角度分析源码实现
  • 函数模板（泛化和特化的问题),什么是全特化和偏特化
  • STL中常见的算法用过哪些，原理是什么（随机数，查找等）
    以上问题出现的频率最高，大厂基本必问，所以你需要必会。 答案均在侯捷老师的视频中。

STL的六大部件和联系

STL（Standard Template Library，标准模板库）由六大组件组成：

  1. 容器（Containers）
  2. 算法（Algorithms）
  3. 迭代器（Iterators）
  4. 函数对象（Functors）
  5. 适配器（Adapters）
  6. 分配器（Allocators）

STL底层实现

  • vector
    底层是一块具有连续内存的数组，vector的核心在于其长度自动可变。vector的数据结构主要由三个迭代器(指针)来完成：指向首元素的start，指向尾元素的finish和指向内存末端的end_of_storage。vector的扩容机制是：当目前可用的空间不足时，分配目前空间的两倍或者目前空间加上所需的新空间大小（取较大值），容量的扩张必须经过“重新配置、元素移动、释放原空间”等过程。

  • list
    底层是一个循环双向链表，链表结点和链表分开独立定义的，结点包含pre、next指针和data数据。

  • deque，
    双向队列，由分段连续空间构成，每段连续空间是一个缓冲区，由一个中控器来控制。它必须维护一个map指针（中控器指针），还要维护start和finish两个迭代器，指向第一个缓冲区，和最后一个缓冲区。deque可以在前端或后端进行扩容，这些指针和迭代器用来控制分段缓冲区之间的跳转。

  • stack和queue，
    栈和队列。它们都是由由deque作为底层容器实现的，他们是一种容器配接器，修改了deque的接口，具有自己独特的性质（此二者也可以用list作为底层实现）；stack是deque封住了头端的开口，先进后出，queue是deque封住了尾端的开口，先进先出。

  • priority_queue，
    优先队列。是由以vector作为底层容器，以heap作为处理规则，heap的本质是一个完全二叉树。

  • set和map。
    底层都是由红黑树实现的。红黑树是一种二叉搜索树，但是它多了一个颜色的属性。红黑树的性质如下：1）每个结点非红即黑；2）根节点是黑的；3）如果一个结点是红色的，那么它的子节点就是黑色的；4）任一结点到树尾端（NULL）的路径上含有的黑色结点个数必须相同。通过以上定义的限制，红黑树确保没有一条路径会比其他路径多出两倍以上；因此，红黑树是一种弱平衡二叉树，相对于严格要求平衡的平衡二叉树来说，它的旋转次数少，所以对于插入、删除操作较多的情况下，通常使用红黑树。

补充：平衡二叉树(AVL)和红黑树的区别：AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance（旋转操作），导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。

  • unordered_map和unordered_set

STL的六大部件和联系

容器是数据结构的实现，负责存储和管理数据。常见的STL容器包括：

  • vector：动态数组，支持随机访问和高效的尾部插入/删除。
  • list：双向链表，支持高效的任意位置插入/删除。
  • deque：双端队列，支持高效的头尾部插入/删除和随机访问。
  • set：有序集合，元素唯一。
  • multiset：有序集合，允许重复元素。
  • map：有序键值对，键唯一。
  • multimap：有序键值对，允许重复键。
  • unordered_set：无序集合，元素唯一。
  • unordered_map：无序键值对，键唯一。

vector

vector数组的底层原理

C++ vector（STL vector）底层实现机制（通俗易懂） - C语言中文网

以下是vector 的三个指针处理

分别处理内存地址和容量处理

1
2
3
4
5
6
7
8
template <class _Ty, class _Alloc = allocator<_Ty>>
class vector{
    ...
protected:
    pointer _Myfirst;
    pointer _Mylast;
    pointer _Myend;
};

img

另外需要指明的是，当 vector 的大小和容量相等（size==capacity）也就是满载时，如果再向其添加元素，那么 vector 就需要扩容。vector 容器扩容的过程需要经历以下 3 步：

  1. 完全弃用现有的内存空间，重新申请更大的内存空间；（一般是俩倍）
  2. 将旧内存空间中的数据，按原有顺序移动到新的内存空间中；
  3. 最后将旧的内存空间释放。

Map Set

map，multimap，set，multiset的原理

  • map：基于红黑树实现的有序键值对容器，查找、插入和删除操作的时间复杂度为O(log n)。
  • multimap：与map类似，但允许多个元素有相同的键。
  • set：基于红黑树实现的有序集合，元素唯一。
  • multiset：与set类似，但允许元素重复。

红黑树

红黑树的性质如下：

1）每个结点非红即黑；

2）根节点是黑的；

3）如果一个结点是红色的，那么它的子节点就是黑色的；

4）任一结点到树尾端（NULL）的路径上含有的黑色结点个数必须相同。

​ 通过以上定义的限制，红黑树确保没有一条路径会比其他路径多出两倍以上；

因此，红黑树是一种弱平衡二叉树，相对于严格要求平衡的平衡二叉树来说，它的旋转次数少，所以对于插入、删除操作较多的情况下，通常使用红黑树。

平衡二叉树(AVL)和红黑树的区别：AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance（旋转操作），导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。

hashtable的作用与原理

Hashtable是一种基于哈希表的数据结构，支持快速的插入、删除和查找操作。其原理是将元素的键通过哈希函数映射到一个桶数组中，处理冲突的方式有链地址法和开放地址法。

List

链表的实现

下面是一个简单的单链表实现：

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
template <typename T>
class Node {
public:
    T data;
    Node* next;

    Node(T val) : data(val), next(nullptr) {}
};

template <typename T>
class LinkedList {
private:
    Node<T>* head;
public:
    LinkedList() : head(nullptr) {}

    void insert(T val) {
        Node<T>* newNode = new Node<T>(val);
        newNode->next = head;
        head = newNode;
    }

    void display() {
        Node<T>* current = head;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

运算符

操作符重载问题

操作符重载允许自定义类型支持C++的内置运算符。例如，重载+运算符：

1
2
3
4
5
6
7
8
9
class Complex {
public:
    double real, imag;
    Complex(double r, double i) : real(r), imag(i) {}

    Complex operator+(const Complex& other) const {
        return Complex(real + other.real, imag + other.imag);
    }
};

前置++与后置++的区别，操作符重载的角度分析源码实现

前置++直接返回自增后的对象，而后置++返回自增前的对象的副本。示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Number {
public:
    int value;
    Number(int val) : value(val) {}

    // 前置++
    Number& operator++() {
        ++value;
        return *this;
    }

    // 后置++
    Number operator++(int) {
        Number temp = *this;
        ++value;
        return temp;
    }
};

函数模板（泛化和特化的问题)

  • 全特化：对模板的所有参数进行特化。
  • 偏特化：对模板的部分参数进行特化。
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
template <typename T>
class Example {
public:
    void show() {
        std::cout << "Generic template" << std::endl;
    }
};

// 全特化
template <>
class Example<int> {
public:
    void show() {
        std::cout << "Specialized template for int" << std::endl;
    }
};

// 偏特化
template <typename T>
class Example<T*> {
public:
    void show() {
        std::cout << "Partial specialization for pointers" << std::endl;
    }
};

STL中常见的算法

  • 随机数生成：std::random_shuffle（已弃用），std::shuffle。
  • 查找：std::find，std::binary_search，std::lower_bound，std::upper_bound。
  • 排序：std::sort，std::stable_sort。
  • 变换：std::transform，std::copy。

STL 常用函数

C++ STL常用函数总结_c++ std所有函数-CSDN博客

排序算法

img

img

排序
插入排序 扑克排序，插入到你何时的牌的位置
选择排序 直觉，不断选择最小的放在前面
冒泡排序 左右俩俩比较，最上面冒泡出来
归并排序 分治法，二分处理每个子块后归并成一个父块
希尔排序 h来分治处理部分排序
快速排序 选择一个piv元素 使得左边小于piv 右边大于piv
堆排序
计数排序 个位为一个桶
基数排序 十位为一个桶
桶排序 不同区间桶