20、基础 | C++ STL

1. 顺序容器与关联容器的比较

存储方式

• 顺序容器：顺序容器通过连续的内存位置来存储元素，元素按照它们被添加到容器中的顺序来排列（除非明确进行排序）。顺序容器存储的是单个元素。
• 关联容器：关联容器以键值对的形式存储数据，每个元素包含一个键（key）和一个值（value）。关联容器中的元素可以根据键进行排序，并且可以快速通过键来访问元素。

有序性

• 顺序容器：默认情况下，顺序容器中的元素是无序的，除非显式地对它们进行排序。
• 关联容器：关联容器保持元素的有序性，通常是按照键的顺序进行排序。

查找效率

• 顺序容器：由于顺序容器中的元素是连续存储的，大多数顺序容器的查找操作需要遍历整个容器，因此其时间复杂度通常为O(n)。
• 关联容器：关联容器内部通常使用平衡二叉搜索树（如红黑树）或其他高效的数据结构来存储元素，因此查找、插入和删除操作的时间复杂度可以达到O(log n)。

迭代器

• 顺序容器：提供从第一个元素开始的迭代器，可以按顺序访问容器中的所有元素。
• 关联容器：提供基于键的迭代器，可以直接根据键来访问和比较元素。

典型容器

• 顺序容器：包括vector（动态数组）、list（双向链表）、deque（双端队列）、array（固定大小的数组）、forward_list（单向链表，C++11引入）等。
• 关联容器：包括map（存储唯一键及其关联值的映射）、multimap（允许键重复）、set（存储唯一元素的集合）、multiset（允许元素重复）、以及无序版本的unordered_map、unordered_multimap、unordered_set、unordered_multiset等。

顺序容器与关联容器的具体类型

顺序容器

• vector：动态数组，支持随机访问，能够高效地插入和删除尾部元素，但在中间或头部插入和删除元素时效率较低。
• list：双向链表，支持快速插入和删除操作，但随机访问效率较低。
• deque：双端队列，支持在两端快速插入和删除操作，内部实现为多个连续存储的块。
• array：固定大小的数组，支持随机访问，但大小在编译时确定，不支持动态扩容。
• forward_list：单向链表，仅支持向前遍历，适用于仅需要从一端插入和删除元素的场景。

关联容器

• map：存储键值对，键唯一，根据键的顺序进行排序，支持快速查找、插入和删除操作。
• multimap：类似于map，但允许键重复。
• set：存储唯一元素的集合，根据元素的顺序进行排序。
• multiset：类似于set，但允许元素重复。
• unordered_map、unordered_multimap、unordered_set、unordered_multiset：这些是无序版本的关联容器，内部使用哈希表实现，提供平均常数时间的查找、插入和删除操作。

综上所述，顺序容器和关联容器在C++中各有特点，选择哪种容器取决于具体的应用需求，如是否需要快速查找、元素是否必须有序、以及对性能等的要求。

2. vector 底层的实现

1. std::vector底层的实现

std::vector是C++标准模板库（STL）中的一个序列容器，它能够存储具有相同类型的元素，并允许随机访问容器中的任何元素。vector的底层实现通常是一个动态分配的连续数组。这个数组的大小可以根据需要动态增长或缩小，但通常会在需要更多空间时重新分配一个更大的连续内存块，并将旧数据复制到新位置，然后释放旧的空间。

2. 迭代器类型为随机迭代器

std::vector的迭代器类型为随机访问迭代器，这意味着它们支持使用下标操作符（[]）和指针算术进行访问，允许在常数时间内访问任何元素。随机访问迭代器还允许进行元素之间的迭代比较，以及使用迭代器与整数进行加减运算来访问容器中的元素。

3. insert 具体做了哪些事？

当在std::vector的某个位置插入一个新元素时，insert成员函数会执行以下操作：

1. 检查空间：首先，vector会检查当前已分配的存储空间是否足够容纳新元素和所有现有元素。如果空间不足，vector会分配一个新的、更大的数组。

2. 移动元素：如果vector需要扩容，或者插入位置不是容器的末尾，那么vector会将插入点之后的所有元素向后移动一个位置，为新元素腾出空间。这个操作是通过复制或移动构造函数（C++11及以后）完成的，具体取决于元素的类型和是否启用了移动语义。

3. 插入新元素：在腾出的空间位置，使用给定的值或元素（如果是迭代器或范围插入）构造新元素。

4. 更新迭代器：insert操作完成后，所有指向被移动元素的迭代器、引用和指针都会失效，因为它们的指向的内存位置可能已经被改变。返回的迭代器指向新插入的元素。

4. resize()调用的是什么？

resize()成员函数用于改变vector的大小。它接受一个参数，即新的大小n，以及一个可选的第二个参数，即如果新大小大于当前大小，则用于填充新元素的值。

• 如果新大小n小于当前大小，vector会删除超出n的元素，并释放可能不再需要的内存。
• 如果新大小n大于当前大小，vector会分配足够的空间（如果需要的话），并使用默认构造函数（如果未提供第二个参数）或给定的值来构造新元素。

在内部，resize()可能会调用内存分配函数（如operator new）来分配或重新分配内存，以及调用元素的构造函数或赋值运算符来初始化或赋值新元素。

总结来说，std::vector通过动态数组提供高效的随机访问和灵活的元素管理，但其性能可能受到重新分配和移动元素的影响。了解这些内部机制有助于更有效地使用vector并编写高效的C++代码。

3. vector 的 push_back 要注意什么

在C++中，std::vector是一个非常灵活且常用的容器，它支持动态数组的操作，如插入、删除和访问元素。然而，当在vector中大量使用push_back方法时，确实需要注意几个关键方面，特别是关于性能和资源管理的：

1. 拷贝构造与析构

拷贝构造（Copy Construction）与析构（Destruction）：每次调用push_back向vector中插入一个元素时，如果该vector的容量不足以存储新的元素，vector可能会重新分配更大的内存空间来存储所有现有的元素和新添加的元素。在这个过程中，如果元素类型不是轻量级的（比如包含大量数据或动态分配的内存），那么大量的拷贝构造和析构操作会导致性能下降。

解决方案：

• 使用移动语义：C++11引入了移动语义，允许使用std::move来传递对象，这可以避免不必要的拷贝。如果你的元素类型支持移动语义（即定义了移动构造函数和移动赋值运算符），则push_back将使用移动而不是拷贝来添加新元素，这可以显著提高性能。
• 预分配空间：使用reserve成员函数预先为vector分配足够的空间，可以避免在添加元素时重新分配内存。

2. 内存分配与释放

内存分配（Allocation）与释放（Deallocation）：如上所述，当vector的容量不足以存储更多元素时，它会分配一个新的、更大的内存块，并将旧数据拷贝（或移动）到新块中，然后释放旧块。这种内存分配和释放操作，特别是当频繁发生时，会对性能产生负面影响，并可能增加内存碎片。

解决方案：

• 预分配足够的空间：使用reserve成员函数可以预先分配足够的内存空间，从而避免不必要的内存分配和释放。
• 考虑使用其他容器：如果知道将要存储的元素数量，并且该数量在生命周期内不会改变太多，可以考虑使用std::array（固定大小数组）或std::deque（双端队列，支持在两端快速插入和删除）。

3. 迭代器失效

虽然这不是直接关于拷贝构造和析构或内存分配的问题，但值得注意的是，在vector中插入或删除元素可能会导致迭代器失效。特别是，在push_back之后，指向vector末尾的迭代器、引用和指针可能会失效，因为vector可能会重新分配内存。

解决方案：

• 尽量避免在vector的迭代过程中修改其大小，或者在修改后立即重新获取迭代器。
• 使用支持稳定迭代器的容器，如std::list或std::deque，但这可能会牺牲一些性能优势。

综上所述，当在C++中使用std::vector的push_back方法时，需要特别注意拷贝构造与析构的性能影响、内存分配与释放的效率，以及迭代器失效的问题。通过采用上述提到的解决方案，可以显著提高程序的性能和稳定性。

4. vector 的 resize() 与 reserve()

在C++中，std::vector是一个非常灵活且常用的容器，它允许存储可变数量的同类型元素。resize()和reserve()是std::vector中两个非常重要的成员函数，它们在容器的大小管理方面扮演着不同的角色。下面，我将首先解释这两个函数的作用，然后提供一个测试程序来演示它们的行为。

resize()

resize()函数用于改变容器的大小。如果新的大小大于当前大小，则会添加额外的元素（默认初始化为该类型的默认值），直到达到新的大小。如果新的大小小于当前大小，则多余的元素会被删除。

• 参数：size_type n（新的大小），可选的第二个参数const T& val（当增加大小时，用于初始化新元素的值）。
• 返回值：无返回值（但会改变容器大小）。

reserve()

reserve()函数用于请求改变容器的容量（即分配的内存大小）。这不会改变容器的大小（即已存储元素的数量），但会预留足够的空间以存储更多的元素，从而减少未来添加元素时重新分配内存的需要。

• 参数：size_type n（请求的新容量）。
• 返回值：无返回值（但会改变容器的容量）。

测试程序

以下是一个简单的C++程序，展示了resize()和reserve()的用法及其效果：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;

    // 初始状态
    std::cout << "初始容量: " << vec.capacity() << ", 大小: " << vec.size() << std::endl;

    // 使用reserve()增加容量
    vec.reserve(10);
    std::cout << "增加容量后: 容量: " << vec.capacity() << ", 大小: " << vec.size() << std::endl;

    // 使用resize()改变大小
    vec.resize(5, 100); // 将大小改为5，并用100初始化新增的元素
    std::cout << "改变大小后: 容量: " << vec.capacity() << ", 大小: " << vec.size() << std::endl;
    for (int val : vec) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // 再次使用resize()减小大小
    vec.resize(3);
    std::cout << "再次改变大小后: 容量: " << vec.capacity() << ", 大小: " << vec.size() << std::endl;
    for (int val : vec) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出

程序的输出将取决于std::vector的具体实现（特别是其内存管理策略），但通常会类似于以下形式：

初始容量: 0, 大小: 0
增加容量后: 容量: 10, 大小: 0
改变大小后: 容量: 10, 大小: 5
100 100 100 100 100 
再次改变大小后: 容量: 10, 大小: 3
100 100 100 

注意，reserve()调用后，容量增加了，但大小（即元素数量）保持不变。resize()调用则改变了大小，并且如果需要，还会改变容量。在第二次resize()调用中，大小减小了，但容量保持不变（除非实现决定减小容量以节省内存）。

5. 如何释放 vector 的空间？

在C++中，std::vector是一个序列容器，它能够存储具有相同类型的元素。关于如何释放vector占用的空间，有几种不同的策略和方法，每种方法适用于不同的场景和需求。

1. 使用swap技巧释放vector空间

当你想重置vector的大小并尽可能释放其已分配的内存时，可以使用swap技巧。具体做法是，先将vector与一个空的临时vector进行swap操作，然后让临时vector离开作用域自动销毁，从而释放原vector占用的内存。

std::vector<int> vec;
// 假设vec已经被填充了数据，占用了大量内存

// 使用swap技巧释放vec的内存
std::vector<int>().swap(vec);

// 现在vec是空的，并且其容量被缩减到最小（或者实现定义的某个最小值）

2. 容器的元素类型为指针

如果vector的元素是指针，那么释放vector的内存本身并不会释放指针所指向的内存。这意呀着，你需要手动管理这些指针所指向的内存，以避免内存泄露。

• 直接管理：确保在删除vector元素之前，手动释放每个指针所指向的内存。
• 使用智能指针：为了避免手动管理内存的复杂性，可以使用智能指针（如std::unique_ptr或std::shared_ptr）来自动管理内存。这样，当智能指针离开作用域或被删除时，它们会自动释放所管理的内存。

3. 指针是trivial_destructor

如果指针的析构函数是trivial（即默认析构函数，不执行任何操作），那么当vector被销毁时，其元素（即指针）的析构函数也不会执行任何操作。这意呀着，即使vector被销毁，指针所指向的内存也不会被自动释放。因此，你需要确保在vector销毁之前，手动释放或转移这些指针所指向的内存的所有权。

4. 使用智能指针管理内存

为了避免内存泄露和简化内存管理，推荐使用智能指针来管理vector中的元素（如果元素是指针的话）。智能指针能够自动管理内存，减少手动释放内存的需要，从而降低出错的风险。

#include <vector>
#include <memory>

std::vector<std::unique_ptr<int>> vec;

// 添加元素
vec.emplace_back(std::make_unique<int>(10));
vec.emplace_back(std::make_unique<int>(20));

// 当vec被销毁时，所有unique_ptr也会自动销毁，进而释放它们所指向的内存

总结来说，释放vector占用的空间可以通过swap技巧实现，而管理vector中指针所指向的内存则需要额外的注意，包括手动管理或使用智能指针来自动管理。

6. vector 的 clear 与 deque 的 clear

在C++中，std::vector和std::deque是两种常用的序列容器，它们各自在处理元素时有着不同的内存管理策略。关于clear方法和erase方法在这两个容器中的行为，以及它们与内存管理的关系，我们可以从以下几个方面来详细解释。

std::vector 的 clear 和 erase

对于std::vector来说，clear和erase方法确实会析构容器中的元素，但是它们本身并不直接释放分配给容器的全部内存。std::vector内部维护一个连续的内存块来存储元素，这个内存块的大小（即容量，capacity）可能会比当前存储的元素数量（即大小，size）大。当你调用clear或erase移除所有元素时，这些操作会遍历并析构所有元素，将容器的大小设置为0，但并不会立即减小其容量。

• clear：将容器的大小设置为0，但容量保持不变。如果需要减少容量，需要显式调用shrink_to_fit（C++11及以后）来请求容器释放不需要的内存。但请注意，shrink_to_fit是一个请求，并非保证会释放内存。
• erase：从容器中移除一个或多个元素，但同样不改变容量。被移除的元素会被析构，剩余的元素会被向前移动以填补空白。

std::deque 的 clear 和 erase

与std::vector不同，std::deque是一个双端队列，它允许在容器的前端和后端快速插入和删除元素。std::deque的内部实现通常是由多个小的连续内存块（或称为缓冲区）组成的，这些内存块之间通过指针链接起来。这种设计使得std::deque在两端操作时可以避免整体数据的移动。

• clear：对于std::deque，clear方法会析构容器中的所有元素，并且根据实现的不同，它可能会释放内部使用的某些或全部缓冲区。然而，与std::vector类似，C++标准并没有强制要求std::deque在调用clear后必须释放所有内存。
• erase：与clear类似，erase方法会析构被移除的元素，并且根据删除操作的位置和范围，它可能会调整内部缓冲区的链接和大小。在某些情况下，这可能会导致释放一些不再需要的缓冲区。

总结

• std::vector的clear和erase只会析构元素，不会释放内存（除非显式调用shrink_to_fit）。
• std::deque的clear和erase同样会析构元素，并且可能会根据内部实现和删除操作的具体情况释放一些或全部缓冲区。然而，C++标准并不保证std::deque在调用clear后必须释放所有内存。

在面试中，解释这些概念时，可以强调标准库实现的具体行为可能因编译器和库的不同而有所差异，但总体上遵循上述原则。同时，也可以讨论在特定情况下，如内存使用非常紧张时，如何通过手动管理内存（如使用std::unique_ptr管理动态分配的std::vector）或使用其他容器（如std::list，虽然它在随机访问上不如vector和deque高效）来优化内存使用。

7. list 的底层实现

在C++标准库中，std::list 是一种双向链表（doubly linked list）的实现。这种数据结构允许高效的插入和删除操作，而不需要像数组或向量（std::vector）那样进行大量的元素移动。下面，我将详细解释 std::list 的底层实现，特别是它如何支持双向迭代器。

双向链表的结构

双向链表中的每个节点（node）都包含三个部分：

1. 数据域：存储元素的值。
2. 前驱指针（prev pointer）：指向链表中前一个节点的指针。对于链表的头节点，这个指针通常被设置为 nullptr 或指向一个特殊的哨兵节点（sentinel node，具体取决于实现）。
3. 后继指针（next pointer）：指向链表中后一个节点的指针。对于链表的尾节点，这个指针通常被设置为 nullptr。

std::list 的实现

std::list 的实现围绕上述双向链表结构进行。它提供了丰富的成员函数来管理链表，如插入、删除、遍历等。

双向迭代器

由于 std::list 是一个双向链表，它自然支持双向迭代器。双向迭代器允许你向前或向后遍历链表，但不能直接进行随机访问（如 std::vector 的迭代器那样）。

双向迭代器通常至少包含以下两个操作：

• operator++()：将迭代器向前移动到下一个元素。
• operator--()：将迭代器向后移动到前一个元素。

此外，为了支持双向遍历，双向迭代器还可能包含比较运算符（如 == 和 !=）来比较两个迭代器是否指向相同的元素。

std::list 的迭代器实现

在 std::list 的实现中，迭代器通常是一个轻量级的封装，它内部持有一个指向链表节点的指针（或引用）。这个指针允许迭代器访问节点的数据，以及通过前驱和后继指针在链表中移动。

示例

尽管我们不能直接看到标准库的内部实现，但我们可以想象一个简化的迭代器类可能看起来像这样：

template<typename T>
class ListNode {
public:
    T data;
    ListNode* prev;
    ListNode* next;

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

template<typename T>
class ListIterator {
private:
    ListNode<T>* node;

public:
    ListIterator(ListNode<T>* n = nullptr) : node(n) {}

    T& opera