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

STL

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

STL的六大部件和联系

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

容器（Containers）
算法（Algorithms）
迭代器（Iterators）
函数对象（Functors）
适配器（Adapters）
分配器（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 常用函数

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

排序算法

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

快排：

STL的六大部件和联系

1. 容器

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

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

链表的实现

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

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;
    }
};

map，multimap，set，multiset的原理

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

hashtable的作用与原理

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

操作符重载问题

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

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);
    }
};

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

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

class Number {
public:
    int value;
    Number(int val) : value(val) {}

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

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

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

全特化：对模板的所有参数进行特化。
偏特化：对模板的部分参数进行特化。

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各个方面的介绍。如果有特定部分需要更详细的解答或者示例代码，请告知。