C++八股之STL（四）
一、讲一下C++的STL
C++的STL（Standard Template Library，标准模板库）是C++语言的一个核心组成部分，它提供了一系列预先定义的类和函数模板，用于实现通用的、类型安全的数据结构和算法。STL极大地增强了C++的功能性和表现力，允许开发者编写高效且可重用的代码。
STL的主要组件：
- 容器（Containers）：提供了多种数据结构，如向量（std::vector）、列表（std::list）、双端队列（std::deque）、集合（std::set）、多重集合（std::multiset）、映射（std::map）和多重映射（std::multimap）等。
- 迭代器（Iterators）：迭代器是STL中用于遍历容器中元素的对象。迭代器可以视为一种泛化的指针，支持对容器元素的访问和操作。
- 算法（Algorithms）：STL提供了大量通用算法，如排序（std::sort）、搜索（std::find）、复制（std::copy）、变换（std::transform）、算术运算等。
- 配器（Adaptors）：配器是特殊的迭代器，它们改变迭代器的行为以适应不同的需求，如流迭代器（std::istream_iterator）、反向迭代器（std::reverse_iterator）等。
- 分配器（Allocators）：分配器负责管理内存分配和回收，STL容器使用分配器来分配和释放内存。默认情况下，STL使用std::allocator作为分配器。
- 函数对象（Functional）：函数对象是一类可以像函数一样使用的模板类，例如谓词（std::less）、二元操作（std::plus）等。
- 容器适配器（Container Adaptors）：容器适配器是特殊的容器，它们提供了额外的功能或不同的接口，如栈（std::stack）、队列（std::queue）、优先队列（std::priority_queue）等。
- 数值操作（Numeric Operations）：STL提供了一些用于数值计算的算法，如std::accumulate、std::inner_product等。
- 分布式算法（Distributed Algorithms）：C++并行STL（Parallel STL）是STL的一个扩展，它提供了并行版本的算法，可以在多核处理器上利用并行计算提高性能。
使用STL的好处：
- 类型安全：STL提供了类型安全的数据操作方式，减少了类型错误的风险。
- 代码重用：STL的组件是通用的，可以在不同的项目中重复使用。
- 效率：STL的算法和数据结构经过优化，能够提供良好的性能。
- 简化编程：STL简化了复杂的数据结构操作，使编程更加直观和简洁。
示例：
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
// 使用STL算法对向量进行排序
std::sort(vec.begin(), vec.end());
// 遍历向量并打印元素
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
在这个示例中，我们使用了std::vector容器、std::sort算法和基于范围的for循环来操作和打印容器中的元素。STL的使用使得代码更加简洁和易于理解。
二、vector list异同⭐⭐
std::vector 和 std::list 是C++ STL中的两种不同的顺序容器，它们各有特点和适用场景。以下是它们的异同点：
相同点：
- STL容器：std::vector 和 std::list 都是C++ STL中提供的容器。
- 模板类：两者都是模板类，可以存储任何类型的数据。
- 迭代器：它们都提供迭代器，允许按顺序访问容器中的元素。
- 元素访问：都允许通过迭代器访问元素，支持常见的元素访问操作，如遍历、搜索等。
不同点：
- 内存分配：std::vector 通常使用连续的内存块来存储元素，类似于数组。std::list 使用非连续的内存块，每个元素（节点）包含数据和指向前一个和后一个节点的指针，形成链表结构。
- 性能特点：std::vector 在随机访问和通过索引访问元素时非常高效，时间复杂度为 O(1)。std::list 在随机访问上效率较低，因为它需要从头开始遍历到特定位置，时间复杂度为 O(n)。
- 插入和删除操作：std::vector 在中间或开始插入或删除元素时效率较低，因为这可能需要移动大量元素以维持连续性。std::list 在任何位置插入或删除元素都很快，只需要改变相邻节点的指针，时间复杂度为 O(1)。
- 空间效率：std::vector 通常具有较高的空间效率，因为它没有额外的内存开销。std::list 由于每个元素都需要额外存储指针，因此空间效率较低。
- 容量和调整大小：std::vector 可以调整大小，当超过当前容量时会进行扩容操作，这可能涉及复制或移动大量元素。std::list 没有容量的概念，通常不需要调整大小。
- 用途：std::vector适用于需要快速随机访问和在末尾添加元素的场景。std::list适用于需要频繁插入和删除元素的场景，尤其是在容器的中间部分。
- 标准库实现：std::vector 是基于数组实现的，而 std::list 是基于双向链表实现的。
示例：
#include <vector>
#include <list>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::list<int> lst = {1, 2, 3, 4, 5};
// 访问元素
std::cout << "Vector at index 2: " << vec[2] << std::endl;
// std::cout << "List at index 2: " << lst[2] << std::endl; // 错误：list不支持随机访问
// 插入元素
vec.push_back(6); // 在末尾插入
lst.insert(lst.begin(), 0); // 在开始插入
// 删除元素
vec.pop_back(); // 删除末尾元素
lst.erase(--lst.end()); // 删除最后一个元素
return 0;
}
在这个示例中，std::vector 允许随机访问和使用索引，而 std::list 不支持。此外，std::vector 的插入和删除操作在末尾是高效的，而 std::list 可以在任何位置高效地插入和删除。
选择 std::vector 还是 std::list 取决于具体的应用场景和性能要求。
list：
vector：
- 综上所述，list适用于需要频繁插入和删除元素的场景，对内存占用要求较高；
- vector适用于需要高效的随机访问和尾部插入操作的场景，对内存占用要求较低。
选择合适的容器类型取决于具体的需求和对性能的要求。
三、vector的底层实现⭐⭐
std::vector 在C++中的底层实现是基于动态数组的。以下是一些关键点，描述了 std::vector 的底层实现细节：
- 连续内存分配：std::vector 存储其元素在堆上一段连续的内存区域内，这使得它可以提供快速的随机访问能力。
- 容量和大小：区分了“容量”（capacity）和“大小”（size）两个概念。大小是容器中元素的数量，而容量是容器当前分配的内存能够容纳的元素数量。
- 自动扩容：当添加元素使得 std::vector 的大小超过当前容量时，std::vector 会自动进行扩容。这通常涉及分配更大的内存区域，复制现有元素到新内存，并释放旧内存。
- 扩容策略：扩容时，新的容量通常是当前容量的两倍，这是一种常见的策略，旨在平衡扩容操作的频率和每次扩容的复制成本。
- 内存分配：std::vector 使用分配器（allocator）来分配和释放内存。默认情况下，使用的是 std::allocator，但可以自定义分配器以适应特定的内存管理需求。
- 元素构造和析构：当在 std::vector 中添加元素时，会调用元素的构造函数来初始化新元素。当从 std::vector 中移除元素时，会调用元素的析构函数。
- 内存复制和移动：在扩容或重新分配内存时，std::vector 会使用复制或移动构造函数来复制或移动元素。C++11引入的移动语义可以减少不必要的复制，提高性能。
- 迭代器失效：当 std::vector 调整其大小或重新分配内存时，可能会导致迭代器失效。例如，push_back、pop_back、resize 和赋值操作都可能使迭代器失效。
- 性能特点：由于内存连续性，std::vector 提供了对元素的快速访问。然而，中间插入和删除操作可能较慢，因为可能需要移动大量元素以维持连续性。
- 非线程安全：std::vector 并不是线程安全的。如果需要在多线程环境中使用，需要额外的同步机制。
示例：
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec;
// 扩容前添加元素
for (int i = 0; i < 10; ++i) {
vec.push_back(i);
}
// 扩容时添加元素
vec.push_back(10); // 可能触发扩容
// 访问元素
for (const auto& elem : vec) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
在这个示例中，std::vector 被用来存储整数。随着元素的添加，如果超出当前容量，std::vector 会自动扩容。通过迭代器遍历 std::vector 并打印元素展示了其连续内存分配的特点。
四、vector和deque的区别 ⭐⭐
std::vector 和 std::deque（double-ended queue，双端队列）都是C++ STL中的顺序容器，但它们在设计和性能特点上有所不同。以下是 std::vector 和 std::deque 的主要区别：
内存分配：
- std::vector 使用一块连续的内存空间存储其元素，类似于传统的C语言数组。
- std::deque 使用多个固定大小的内存块存储元素，这些块可以分布在内存中的不同位置，并通过内部指针连接起来。
性能特点：
- std::vector 在随机访问（通过索引访问元素）、扩展（在尾部添加或删除元素）方面非常高效，但在中间插入或删除元素时可能较慢，因为这可能需要移动大量元素以维持元素的连续性。
- std::deque 提供了在头部和尾部快速插入和删除元素的能力，不需要移动除了新插入或删除的元素之外的其他元素。但在随机访问方面，std::deque 通常比 std::vector 慢，因为它可能需要遍历多个内存块。
用途：
- std::vector 更适合于需要频繁随机访问元素、在尾部添加或删除元素的场景。
- std::deque 更适合于需要在头部或中间快速插入或删除元素的场景。
迭代器失效：
- 在 std::vector 中，中间的插入或删除操作可能导致所有指向容器的迭代器失效。
- 在 std::deque 中，只有插入或删除操作影响的元素的迭代器会失效。
示例：
#include <vector>
#include <deque>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::deque<int> deq = {1, 2, 3, 4, 5};
// 在尾部添加元素
vec.push_back(6);
deq.push_back(6);
// 在头部添加元素
vec.insert(vec.begin(), 0); // 可能慢，因为需要移动元素
deq.push_front(0); // 快，不需要移动元素
// 访问元素
std::cout << "Vector at index 2: " << vec[2] << std::endl;
std::cout << "Deque at index 2: " << deq[2] << std::endl; // 慢，因为deque不支持快速随机访问
return 0;
}
在这个示例中，std::vector 和 std::deque 都被用来存储整数并执行一些基本操作。示例展示了 std::vector 在随机访问上的便利性，以及 std::deque 在头部插入上的效率。
Deque和vector和LIST使用场景：⭐⭐
- 如果需要高效的随即存取，而不需要在乎插入和删除的效率，使用 vector；
- 如果需要大量的插入和删除，而不需要关心随即存取，则应使用 list；
- 如果需要随即存取，而且需要关心两端数据的插入和删除，则应使用 deque。
五、deque和queue的区别⭐⭐
std::deque 和 std::queue 都是C++ STL中的容器或容器适配器，但它们在功能和用途上有所不同：
std::deque（双端队列）:
- std::deque 是一个基于动态数组的双端队列容器，可以高效地从两端添加或删除元素。
- 它提供了快速的随机访问能力，允许在两端快速插入和删除元素，而不需要移动其他元素。
- std::deque 没有大小限制，只受系统内存大小的限制。
- 它是一个底层容器，提供了广泛的操作，包括访问任何位置的元素。
std::queue（队列）:
- std::queue 是一个容器适配器，它使用 std::deque（默认情况下，但也可以与 std::list 一起使用）作为其底层容器。
- 它实现了标准的先进先出（FIFO）队列操作，只允许在队列的末尾添加元素（push），并在队列的开头移除元素（pop）。
- std::queue 不提供随机访问元素的能力，访问仅限于队列的前端和后端。
- 它是一个高层适配器，只提供了队列操作所需的接口。
主要区别：
- 访问能力：std::deque 允许随机访问，可以快速访问任何位置的元素。std::queue 不允许随机访问，只能访问队列的前端和后端元素。
- 操作限制：std::deque 提供了广泛的操作，包括在两端插入和删除元素。std::queue 只提供了队列操作，限制了在队列末尾添加元素和在队列开头移除元素。
- 底层实现：std::deque 是一个实际的容器类，有自己的内存管理机制。std::queue 是一个容器适配器，依赖于一个底层容器来存储元素。
- 用途：std::deque适用于需要从两端高效操作的场景。std::queue 适用于需要实现标准队列行为的场景。
- 性能特点：std::deque 在随机访问和两端操作方面表现良好。std::queue 在队列操作方面表现良好，但受限于其适配器的性质，可能在某些操作（如 pop 和 push）上不如 std::deque 高效。
示例：
#include <deque>
#include <queue>
#include <iostream>
int main() {
// 使用 std::deque
std::deque<int> deq = {1, 2, 3};
deq.push_back(4); // 在尾部添加
deq.push_front(0); // 在头部添加
std::cout << "Deque front: " << deq.front() << ", back: " << deq.back() << std::endl;
// 使用 std::queue
std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.pop(); // 移除队列前端元素
std::cout << "Queue front after pop: " << q.front() << std::endl;
return 0;
}
在这个示例中，std::deque 被用来展示其两端操作的能力，而 std::queue 被用来展示其标准的队列操作。选择使用哪一个取决于具体的应用需求。
六、为什么list里面还要再定义一个sort函数⭐
- 1.整个STL设计的指导思想是GP，即模板编程。在此思想的指导下，少了面向象编程的类继承、虚函数、多态等的设计，取而代之的是数据与方法的分离，表现在STL中将容器与算法分离，两者分别闭门造车，中间依靠迭代器联系。
- 2.故sort算法被单独剥离出来，与所有的容器分开。虽然想的挺好但是总有例外，list容器就是那个例外。从源码可以看出，sort函数用到的迭代器的操作链表是不可能做到的，故list需要设计自己的sort函数。
在C++中，list 是一种顺序容器，它提供了双向迭代器，允许在序列的任何位置快速插入和删除元素。尽管C++标准库提供了一个通用的 sort 函数，位于 <algorithm> 头文件中，但是 list 容器本身也提供了一个成员函数 sort。以下是为什么 list 容器可能需要自己的 sort 成员函数的几个原因：
- 容器特定优化：list 的 sort 成员函数可以利用 list 的特性进行优化。例如，它可以在原地进行排序，不需要额外的内存，因为它不需要像数组那样复制元素。
- 稳定性：list 的 sort 函数可以保证排序的稳定性，即相等的元素在排序后仍然保持它们原始的顺序。这对于某些应用是非常重要的。
- 自定义比较函数：list 的 sort 成员函数允许用户传递自定义的比较函数，这与标准库中的 sort 函数提供的灵活性类似。
- 直接操作容器元素：list 的 sort 成员函数直接作用于容器的元素，不需要用户手动指定范围，这简化了使用。
- 避免不必要的复制：由于 list 是一个链表结构，使用标准库的 sort 函数可能需要将元素复制到数组中，然后再复制回去，这在某些情况下可能是不必要的开销。
- 保持容器的完整性：使用 list 的 sort 成员函数可以确保排序操作不会破坏 list 的内部结构，因为 list 的迭代器在排序过程中仍然有效。
- 符合容器的接口规范：C++ 标准库容器通常提供了一组一致的操作，包括 sort，这使得用户在使用不同容器时可以有一个统一的体验。
总的来说，list 容器的 sort 成员函数提供了一种适合链表结构的排序方式，同时保持了与标准库其他容器操作的一致性。
七、STL底层数据结构实现⭐
STL（Standard Template Library，标准模板库）是C++中一个功能强大的库，它提供了一系列通用的模板类和函数，用于处理各种数据结构和算法。STL的底层数据结构主要包括以下几种：
- 向量（Vector）：底层实现：动态数组。特点：连续内存分配，提供快速随机访问。
- 列表（List）：底层实现：双向链表。特点：允许在任何位置快速插入和删除，但不支持随机访问。
- 双端队列（Deque）：底层实现：通常是一个固定大小的数组或多个固定大小的数组块，每个块之间通过指针连接。特点：支持在两端快速插入和删除元素。
- 集合（Set）：底层实现：红黑树。特点：自动排序，提供对数时间复杂度的查找、插入和删除操作。
- 多重集合（Multiset）：底层实现：与 set 相同，使用红黑树。特点：允许存储重复元素。
- 映射（Map）：底层实现：红黑树。特点：键值对存储，自动排序。
- 多重映射（Multimap）：底层实现：与 map 相同，使用红黑树。特点：允许键的重复，每个键可以有多个关联的值。
- 栈（Stack）：底层实现：可以是 deque、list 或 vector。特点：后进先出（LIFO）的数据结构。
- 队列（Queue）：底层实现：通常使用双向队列 deque。特点：先进先出（FIFO）的数据结构。
- 优先队列（Priority Queue）：底层实现：通常使用堆（通常是二叉堆）。特点：总是能够快速访问最高或最低优先级的元素。
八、利用迭代器删除元素会发生什么？⭐⭐⭐⭐
在C++中，迭代器是标准模板库（STL）中用来遍历容器的元素的一种机制。利用迭代器删除元素是STL容器操作中常见的一种行为。以下是使用迭代器删除元素时可能发生的几种情况：
- 元素被删除：通过迭代器删除元素时，迭代器指向的元素会被从容器中移除。
- 迭代器失效：删除元素后，指向被删除元素的迭代器会失效，不能用于后续操作。这是因为元素的物理位置已经被释放。
- 后续迭代器移动：删除元素后，所有指向被删除元素之后位置的迭代器都会向前移动一个位置。也就是说，它们现在指向之前紧随被删除元素的元素。
- 容器大小变化：删除元素会导致容器的大小减少。
- 内存重新分配：对于某些容器，如 vector，在删除元素后可能需要重新分配内存，特别是当删除操作导致容器大小显著减少时。
- 异常安全：STL容器的删除操作通常保证基本的异常安全性。如果删除操作过程中抛出异常，容器的状态将保持不变，或者至少处于有效但可能未定义的状态。
- 迭代器范围调整：如果使用范围迭代器（如 erase(first, last)）删除多个元素，那么所有 first 和 last 之间的元素都会被删除，last 之后的迭代器都会向前移动到 first 的位置。
- 引用和指针失效：如果存在指向被删除元素的引用或指针，这些引用或指针也会失效。
- 算法影响：如果容器中存在指向当前元素的算法（如排序或搜索算法），删除元素可能会影响这些算法的执行。
- 稳定性：对于某些容器（如 list），删除元素是稳定的，即相同元素的相对顺序在删除操作后保持不变。
正确地使用迭代器进行元素删除是STL编程中的一个重要技能，需要对迭代器的失效规则有清晰的理解，以避免程序中出现未定义行为。
vector容器
在删除元素时需要确保迭代器的有效性。可以使用erase函数来删除元素，并且要注意将erase函数返回的下一个元素的迭代器保存起来，以便正确遍历容器。
map和set容器
由于其底层数据结构为红黑树，删除当前元素不会影响到下一个元素的迭代器，因此在调用erase函数之前，记录下一个元素的迭代器是一种常见的处理方式。
list容器
由于其底层数据结构是链表，使用了不连续分配的内存，且erase函数会返回下一个有效的迭代器，所以无论是记录下一个元素的迭代器还是使用erase返回的迭代器，两种方式都是可行的。
当然可以。以下是一些C++代码示例，展示了如何使用迭代器删除元素的不同场景：
1. 使用 vector 删除单个元素：
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin() + 2; // 指向第三个元素
vec.erase(it); // 删除第三个元素
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
2. 使用 list 删除指定范围内的元素：
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {1, 2, 3, 4, 5, 6};
auto it1 = lst.begin();
std::advance(it1, 2); // 移动到第三个元素
auto it2 = it1;
std::advance(it2, 2); // 移动到第五个元素
lst.erase(it1, it2); // 删除从第三个到第五个元素
for (int num : lst) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
3. 使用 set 删除特定的元素：
#include <iostream>
#include <set>
int main() {
std::set<int> s = {1, 2, 3, 4, 5};
auto it = s.find(3); // 查找元素3
if (it != s.end()) {
s.erase(it); // 删除找到的元素
}
for (int num : s) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
4. 使用 map 删除键值对：
#include <iostream>
#include <map>
int main() {
std::map<int, std::string> m = {{1, "one"}, {2, "two"}, {3, "three"}};
auto it = m.find(2); // 查找键为2的元素
if (it != m.end()) {
m.erase(it); // 删除找到的键值对
}
for (const auto &pair : m) {
std::cout << pair.first << ": " << pair.second << " ";
}
std::cout << std::endl;
return 0;
}
5. 删除 vector 中满足特定条件的元素：
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5, 6};
// 删除所有大于3的元素
vec.erase(
std::remove_if(vec.begin(), vec.end(), [](int x) { return x > 3; }),
vec.end()
);
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
九、map是如何实现的，查找效率是多少⭐⭐⭐
C++中的 std::map 是一种关联容器，其底层实现通常是基于红黑树。红黑树是一种自平衡的二叉搜索树，它保证了树的高度大致为 log(n)，其中 n 是树中元素的数量。以下是 std::map 的一些关键特性和实现细节：
红黑树特性：
- 每个节点都有一个颜色属性，可以是红色或黑色。
- 树的根节点和叶子节点（NIL节点，空节点）都是黑色。
- 任何从根到叶子的路径上，黑色节点的数量都是相同的。
- 每个红色节点的两个子节点都是黑色的（没有两个连续的红色节点）。
- 从任一节点到其每个叶子的所有简单路径，都包含相同数目的黑色节点。
查找效率：
由于红黑树保持了大致的平衡，std::map 中的查找操作具有对数时间复杂度，即O(log n)。这意味着即使在最坏的情况下，查找操作的效率也不会随着元素数量的增加而显著下降。
插入和删除操作：
- 插入：当新元素插入红黑树时，为了保证红黑树的性质，可能需要进行一系列的颜色变换和旋转操作。
- 删除：删除操作也可能导致树的不平衡，需要通过颜色变换和旋转来重新平衡树。
性能考虑：
- 由于 std::map 需要维护红黑树的平衡，插入和删除操作相对于无序容器（如 std::vector）来说通常要慢一些。
- 但是，std::map 提供了快速的查找、插入和删除操作，这对于需要频繁进行这些操作的应用来说是非常重要的。
其他特性：
- std::map 保持元素的有序性，元素按照键的顺序进行排序。
- 它提供了键值对（key-value pairs）的存储方式，其中键是唯一的。
示例代码：
#include <iostream>
#include <map>
int main() {
std::map<int, std::string> myMap;
// 插入元素
myMap.insert({1, "one"});
myMap.insert({2, "two"});
myMap.insert({3, "three"});
// 查找元素
auto it = myMap.find(2);
if (it != myMap.end()) {
std::cout << "Found: " << it->second << std::endl;
}
// 删除元素
myMap.erase(it);
// 再次查找已删除的元素
it = myMap.find(2);
if (it == myMap.end()) {
std::cout << "Not found" << std::endl;
}
return 0;
}
这个示例展示了如何在 std::map 中插入、查找和删除元素。由于 std::map 的底层实现是红黑树，这些操作都能以 O(log n)的时间复杂度完成。
十、map和unordered_map有什么区别？⭐⭐⭐
C++中的 std::map 和 std::unordered_map 是两种不同的关联容器，它们在内部实现、性能特点以及使用场景上有所区别。以下是它们的主要差异：
1. 内部实现：
- std::map：基于红黑树实现，保证元素按照键值的顺序存储。
- std::unordered_map：基于哈希表实现，元素的存储顺序不保证有序。
2. 元素排序：
- std::map：元素自动按照键值排序，便于进行有序遍历。
- std::unordered_map：元素存储无序，不便于有序遍历。
3. 查找效率：
- std::map：平均情况下，查找操作的时间复杂度为 O(log n)，但在最坏情况下，如树的平衡性被破坏，查找效率可能降低。
- std::unordered_map：理想情况下，查找操作的平均时间复杂度接近 O(1)，但最坏情况下可能退化为 O(n)，这取决于哈希函数的质量和冲突解决机制。
4. 插入和删除操作：
- std::map：插入和删除操作可能需要树的旋转和颜色变换来保持红黑树的平衡。
- std::unordered_map：插入和删除操作通常只需要在哈希表中找到对应的位置，然后进行替换或删除。
5. 内存使用：
- std::map：由于需要存储额外的平衡信息（红黑树的节点颜色），可能会使用更多的内存。
- std::unordered_map：通常使用较少的内存，因为它不需要存储额外的平衡信息。
6. 性能波动：
- std::map：性能相对稳定，不受哈希函数质量的影响。
- std::unordered_map：性能可能受到哈希函数和冲突解决机制的影响，如果哈希分布不均匀，可能导致性能下降。
7. 使用场景：
- std::map：适用于需要有序遍历元素、对元素进行范围查询或需要元素有序的场景。
- std::unordered_map：适用于对元素进行快速查找、插入和删除操作，且不关心元素的存储顺序的场景。
示例代码：
- 使用 std::map：
- 使用 std::unordered_map：
- 选择使用 std::map 还是 std::unordered_map 取决于具体的应用需求和性能考虑。
- 如果需要有序的元素存储和遍历，std::map 是更好的选择；
- 如果需要快速的查找操作且不关心元素的顺序，std::unordered_map 可能更合适。
十一、for (const auto &pair : myMap) 这里的const和& 的作用是什么？⭐⭐
在C++11及之后的版本中，使用 for 循环遍历 std::map 或 std::unordered_map 时，const auto &pair 的声明有几个重要的作用：
- const：const 关键字表示引用的元素是不可修改的。在这个上下文中，它防止了循环内部对元素的修改。这是一个很好的实践，因为它避免了意外修改容器中的元素，并且可以提高编译器优化代码的能力。
- auto：auto 关键字用于自动推断变量 pair 的类型。std::map 和 std::unordered_map 中的元素是 pair<const Key, T> 类型，其中 Key 是键的类型，T 是值的类型。使用 auto 可以简化代码，避免需要显式写出复杂的类型名称。
- &（引用）：& 表示我们正在获取容器中元素的引用，而不是它们的副本。这使得循环更加高效，因为我们不需要为每个元素创建副本，尤其是在元素类型较大或复杂时。同时，由于使用了 const，这些引用是不可修改的。
将这些结合起来，for (const auto &pair : myMap) 的作用是：
- 遍历 myMap 容器中的每个元素。
- 每个元素被声明为 const，所以不能在循环中修改这些元素。
- 每个元素是通过引用访问的，避免了不必要的复制，提高了效率。
- auto 用于自动推断元素的类型，使得代码更加简洁。
这种循环语法是C++11引入的范围基于（range-based）for循环的一部分，它提供了一种简洁、安全且易于阅读的方式来遍历容器中的元素。
十二、几种模板插入的时间复杂度 ⭐⭐⭐⭐
在C++中，几种模板容器（如 std::vector、std::list、std::deque、std::map、std::set 和 std::unordered_map）的插入操作的时间复杂度各有不同，取决于容器的内部实现和插入位置。以下是一些常见容器的插入操作的时间复杂度概览：
- std::vector尾部插入：通常为 O(1)，因为 std::vector 在尾部预留了额外空间。中间或开始插入：为 O(n)，因为可能需要移动插入点后的所有元素。
- std::list任何位置插入：通常为 O(1)，因为 std::list 是链表结构，插入操作只需要修改相邻节点的指针。
- std::deque（双端队列）尾部或头部插入：通常为 O(1)，如果尾部或头部有足够的空间。中间插入：为 O(n)，因为可能需要移动插入点后的所有元素。
- std::map 和 std::set任何位置插入：平均为 O(log n)，因为这些容器基于红黑树实现，插入操作需要维护树的平衡。
- std::unordered_map 和 std::unordered_set任何位置插入：平均为 O(1)，因为这些容器基于哈希表实现，理想情况下插入操作不需要重新排列元素。最坏情况下：可能退化为 O(n)，这通常发生在哈希冲突较多，且链表或子数组较长时。
- std::forward_list任何位置插入：为 O(1)，因为 std::forward_list 是单向链表，插入操作只需要修改相邻节点的指针。
- std::stack 和 std::queue这些容器通常只提供对顶部或尾部的插入和删除操作，时间复杂度通常为 O(1)。
- std::priority_queue插入：为 O(log n)，因为需要维护堆的性质。
请注意，上述时间复杂度是理想情况下的平均情况，实际的时间复杂度可能会受到特定实现、元素的哈希函数质量、内存分配策略等因素的影响。在设计算法时，了解不同容器的插入操作时间复杂度对于选择最合适的数据结构非常重要。
十三、容器和适配器有什么区别？⭐⭐
在C++中，容器（如 std::vector、std::list）和适配器（如 std::queue、std::stack）是标准模板库（STL）中两种不同类型的组件，它们在功能和使用方式上有所区别：
容器（Container）：
- 存储：容器直接存储数据元素。
- 类型：容器可以存储任意类型的数据。
- 大小：容器有固定的大小，尽管某些容器（如 std::vector）可以动态调整大小。
- 访问：容器提供了多种访问元素的方式，例如随机访问（ std::vector）、顺序访问（ std::list）等。
- 操作：容器提供了丰富的成员函数来操作元素，如插入、删除、查找等。
- 迭代器：容器使用迭代器来遍历元素。
适配器（Adapter）：
- 抽象：适配器是一种抽象层，它定义了一组特定的操作来使用容器。
- 依赖：适配器依赖于容器来存储数据，但隐藏了容器的具体实现。
- 接口：适配器提供了一种特定的接口来访问数据，通常只暴露几种基本操作。
- 限制：适配器限制了对容器的访问方式，只允许通过适配器定义的方式进行操作。
- 用途：适配器用于实现特定的数据结构，如队列、栈等，它们具有特定的操作规则。
具体区别：
- std::vector 是一个动态数组，可以随机访问元素，支持在尾部快速插入和删除，但在其他位置进行这些操作可能较慢。
- std::list 是一个双向链表，支持在任何位置快速插入和删除，但不支持随机访问。
- std::queue 是一个队列适配器，通常使用 std::deque 作为底层容器，只允许在尾部插入元素和在头部删除元素。
- std::stack 是一个栈适配器，通常使用 std::deque 或 std::vector 作为底层容器，只允许在栈顶进行插入和删除操作。
示例代码：
- 使用容器 std::vector：
- 使用适配器 std::queue：
选择使用容器还是适配器取决于你的具体需求。如果你需要一个具有特定操作规则的数据结构，适配器可能是更好的选择。如果你需要更多的灵活性和控制，直接使用容器可能更合适。
十四、 讲一下vector动态扩展的原理？⭐
在vector中，为了实现自动的容量拓展，需要进行以下几个步骤：
- 检查空间是否足够：在插入新元素之前，需要检查当前的元素数量是否已经达到了当前容量（capacity）。如果元素数量等于容量，表示容量不足。
- 分配新的内存空间：当容量不足时，需要对vector进行容量的拓展。此时，会通过一定的策略来计算新的容量大小，并在内存中分配一块新的连续空间，用于存储更多的元素。通常的策略可以是将容量翻倍或者增加一个固定的增量。
- 复制元素：接下来，需要将当前的元素从旧的内存空间复制到新的内存空间中。这一步是为了保持原有元素的顺序和正确性。
- 释放旧内存空间：完成元素的复制后，旧的内存空间将不再使用，需要将其释放，避免内存泄漏。
为什么要以这样的方式实现自动拓展呢？
这是因为vector要求元素在内存中是连续存储的，这样可以实现高效的随机访问和迭代。
而为了避免频繁的内存重分配和复制，采取动态拓展的方式可以减少内存重分配的次数，提高效率。在容量拓展时，翻倍或固定增量的方式可以充分利用已分配内存空间，避免过多的内存浪费。这样设计的vector可以在大多数情况下保持较好的性能，同时能够适应不断变化的元素数量需求。
十五、Vector动态扩展时，编译器为什么不先判断一下原有空间后面的内存是否空闲，如果空闲，直接在后面的内存空间继续分配空间？⭐
- 内存池的设计目标与vector的扩展策略存在冲突。
- 内存池通常以预先分配和划分的固定大小内存块为基础，不涉及连续内存空间的动态扩展。
- Vector需要动态扩展来容纳更多元素，通常会请求更大的连续内存空间，并将原有元素复制到新的内存中。
- 编译器追求数据连续性和性能平衡，因此不会利用内存池来判断和利用原有空间后面的内存。
- 基于内存池进行动态扩展的实现通常并不会比常规的动态分配方式更加麻烦。占用更多的资源。
十六、Unordered_map和map，unordered_set和set，分别有什么区别，它们的底层数据结构是什么？⭐⭐
std::map、std::set 和它们对应的无序版本 std::unordered_map、std::unordered_set 在C++中是四种不同的关联容器，它们在底层数据结构、性能特点以及使用场景上有所区别：
std::map 与 std::unordered_map
std::map:
- 底层数据结构：红黑树，一种自平衡的二叉搜索树。
- 元素排序：自动按照键的顺序进行排序。
- 查找效率：平均时间复杂度为 O(log n)。
- 插入/删除操作：可能需要树的旋转和颜色变换来保持平衡。
std::unordered_map:
- 底层数据结构：哈希表，通过哈希函数将键映射到存储位置。
- 元素排序：元素存储无序，不保证有序遍历。
- 查找效率：平均时间复杂度接近 O(1)，但最坏情况下可能退化为 O(n)。
- 插入/删除操作：通常只需要在哈希表中找到对应的位置，然后进行替换或删除。
std::set 与 std::unordered_set
std::set:
- 底层数据结构：与 std::map 相同，使用红黑树。
- 元素排序：自动按照元素的顺序进行排序。
- 查找效率：平均时间复杂度为 O(log n)。
- 插入/删除操作：与 std::map 类似，需要保持树的平衡。
std::unordered_set:
- 底层数据结构：与 std::unordered_map 相同，使用哈希表。
- 元素排序：元素存储无序。
- 查找效率：平均时间复杂度接近 O(1)，但可能在最坏情况下退化。
- 插入/删除操作：与 std::unordered_map 类似，操作简单。
选择使用哪个？
- 有序性：如果你需要有序的元素存储和有序遍历，使用 std::map 或 std::set。
- 性能：如果元素的顺序不重要，且需要快速的查找、插入和删除操作，使用 std::unordered_map 或 std::unordered_set。
- 内存使用：std::map 和 std::set 可能使用更多的内存，因为它们需要存储额外的平衡信息。
- 稳定性：std::map 和 std::set 提供稳定的排序，而 std::unordered_map 和 std::unordered_set 的元素顺序可能会在每次插入或删除后改变。
示例代码：
- 使用 std::map：
- 使用 std::unordered_map：
选择使用哪种容器取决于你的具体需求和性能考虑。如果你需要有序的元素存储和遍历，std::map 和 std::set 是更好的选择；如果你需要快速的查找操作且不关心元素的顺序，std::unordered_map 和 std::unordered_set 可能更合适。
十七、map和set有什么区别？⭐⭐
std::map 和 std::set 都是C++标准模板库（STL）中的关联容器，它们用于存储元素并提供高效的查找功能。尽管它们在某些方面相似，但它们之间存在一些关键区别：
- 存储内容：std::map 存储的是键值对（key-value pairs），每个元素包含一个键（key）和一个与之关联的值（value）。std::set 只存储唯一的键，没有与之关联的值。
- 元素类型：std::map 的元素类型是 std::pair<const Key, T>，其中 Key 是键的类型，T 是值的类型。std::set 的元素类型就是键的类型。
- 迭代器返回类型：当遍历 std::map 时，迭代器返回的是 std::pair<const Key, T>。当遍历 std::set 时，迭代器返回的是键类型。
- 默认构造函数：std::map 的默认构造函数创建一个空的映射，不包含任何键值对。std::set 的默认构造函数创建一个空的集合，不包含任何元素。
- 用途：std::map 适用于需要将数据项映射或关联到其他数据项的场景。std::set 适用于需要存储唯一元素集合的场景，例如，去重或确保元素的唯一性。
- 操作：std::map 提供了插入键值对、通过键查找值、更新值等操作。std::set 提供了插入元素、查找元素、删除元素等操作。
- 底层数据结构：尽管两者都基于红黑树实现，但 std::map 使用红黑树存储键值对，而 std::set 使用红黑树仅存储键。
- 性能：std::map 和 std::set 在大多数操作上都有相似的性能特征，例如，查找、插入和删除操作的平均时间复杂度都是 O(log n)。
示例代码：
- 使用 std::map：
- 使用 std::set：
选择 std::map 还是 std::set 取决于你的具体需求。如果你需要存储键值对，使用 std::map；如果你只需要存储唯一的键，使用 std::set。
十八、讲一下map和set的定义 ， 以及相对应的无序集合unordered_map 和 unordered_set⭐⭐
在C++中，std::map、std::set、std::unordered_map 和 std::unordered_set 是四种不同的关联容器，它们各自有独特的定义和用途：
std::map
std::map 是一个关联容器，它存储了键值对（key-value pairs），其中每个键都是唯一的。std::map 中的元素按照键的顺序自动排序，通常是基于键的比较函数实现的。
定义:
template <
class Key,
class T,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, T>>
>
class map {
public:
// ...
};
std::set
std::set 是一个关联容器，它存储了唯一元素的集合。std::set 中的元素也是自动按照元素的顺序排序的。
定义:
template <
class Key,
class Compare = std::less<Key>,
class Allocator = std::allocator<Key>
>
class set {
public:
// ...
};
std::unordered_map
std::unordered_map 是一个关联容器，它存储了键值对，但与 std::map 不同的是，它不保证元素的顺序。std::unordered_map 基于哈希表实现，提供了平均时间复杂度为 O(1) 的查找效率。
定义:
template <
class Key,
class T,
class Hash = std::hash<Key>,
class Pred = std::equal_to<Key>,
class Allocator = std::allocator<std::pair<const Key, T>>
>
class unordered_map {
public:
// ...
};
std::unordered_set
std::unordered_set 是一个关联容器，它存储了唯一元素的集合，同样不保证元素的顺序。它也基于哈希表实现，提供了高效的查找性能。
定义:
template <
class Key,
class Hash = std::hash<Key>,
class Pred = std::equal_to<Key>,
class Allocator = std::allocator<Key>
>
class unordered_set {
public:
// ...
};
区别和选择
- std::map 和 std::set 基于红黑树实现，保证元素有序，适用于需要有序数据的场景。
- std::unordered_map 和 std::unordered_set 基于哈希表实现，提供更快的查找速度，适用于不需要有序数据且对查找速度有较高要求的场景。
- std::map 和 std::unordered_map 存储键值对，适合于需要通过键快速访问值的场景。
- std::set 和 std::unordered_set 只存储键，适合于需要快速查找元素是否存在的场景。
在选择使用哪种容器时，需要根据具体的应用需求来决定，考虑数据的有序性、查找效率、内存使用等因素。
十九、prioriry_queue优先级队列的底层数据结构是什么？操作的时间复杂度是什么？⭐⭐⭐
std::priority_queue 是C++标准模板库中的一个容器适配器，它提供了一种方式来访问一个元素集合中具有最高（或最低，取决于优先级规则）优先级的元素。std::priority_queue 本身并不存储元素，而是通常使用 std::vector 作为底层数据结构来存储元素。
底层数据结构：
- 尽管 std::priority_queue 没有直接指定其底层数据结构，但它通常使用一个二叉堆（binary heap）来维护元素的顺序。二叉堆可以是最大堆或最小堆，这取决于优先级队列的实现和配置。
操作的时间复杂度：
- 插入元素 (push): 平均时间复杂度为 O(log n)，因为新元素需要被添加到堆的末尾，并向上调整以维持堆的性质。
- 删除最高优先级元素 (pop): 也是 O(log n)，因为需要将堆顶元素移除，并将最后一个元素移动到顶部，然后重新调整堆。
- 访问最高优先级元素 (top): 通常为 O(1)，因为最高优先级的元素始终位于堆顶。
示例代码：
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
// 插入元素
pq.push(10);
pq.push(5);
pq.push(20);
// 访问并移除最高优先级的元素
while (!pq.empty()) {
std::cout << pq.top() << " "; // 输出最高优先级的元素
pq.pop(); // 移除最高优先级的元素
}
// 输出: 20 10 5
return 0;
}
在这个示例中，std::priority_queue 按照最大堆的方式工作，所以最大的元素首先被输出。
注意事项：
- std::priority_queue只提供了对最高优先级元素的访问和移除操作，不支持随机访问或修改除了最高优先级以外的其他元素。
- 优先级队列的元素需要定义严格的弱排序规则，即元素之间可以相互比较。
- 默认情况下，std::priority_queue 使用 std::less 作为比较操作，这使得队列成为一个最大堆；如果需要最小堆，可以使用 std::greater 作为比较操作。
priority_queue 使用最小堆：
#include <iostream>
#include <queue>
#include <functional> // 包含 std::greater
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
// 插入元素
minHeap.push(30);
minHeap.push(10);
minHeap.push(20);
// 弹出元素，此时会按照最小堆的顺序
while (!minHeap.empty()) {
std::cout << minHeap.top() << " "; // 输出最小元素
minHeap.pop(); // 移除最小元素
}
// 输出: 10 20 30
return 0;
}#include <iostream>
#include <queue>
#include <functional> // 包含 std::greater
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
// 插入元素
minHeap.push(30);
minHeap.push(10);
minHeap.push(20);
// 弹出元素，此时会按照最小堆的顺序
while (!minHeap.empty()) {
std::cout << minHeap.top() << " "; // 输出最小元素
minHeap.pop(); // 移除最小元素
}
// 输出: 10 20 30
return 0;
}
#自动驾驶##机器人##C++##八股#自动驾驶/机器人C++八股精选 文章被收录于专栏
在自动驾驶和机器人领域，C++因其高性能、内存管理高效和跨平台兼容性等特性，被广泛应用。本专栏整理了C++面试中常遇到的八股问题，可私信作者要飞书文档，不论是嵌入式软开、算法、软件开发都可以阅读，包括了C++的虚函数、C++11新特性、C++的STL库、Linux常见命令......
大疆公司氛围 167人发布