【C++】05.STL-容器/算法/迭代器

【嵌入式八股】一、语言篇（本专栏）https://www.nowcoder.com/creation/manager/columnDetail/mwQPeM

【嵌入式八股】二、计算机基础篇https://www.nowcoder.com/creation/manager/columnDetail/Mg5Lym

【嵌入式八股】三、硬件篇https://www.nowcoder.com/creation/manager/columnDetail/MRVDlM

【嵌入式八股】四、嵌入式Linux篇https://www.nowcoder.com/creation/manager/columnDetail/MQ2bb0

STL

基础

97.什么是STL？

STL全称是Standard Template Library（标准模板库）,是C++标准库的一部分，它是一个强大而丰富的工具集，提供了许多常用的数据结构和算法，例如容器、迭代器、算法、函数对象等，使得C++程序员能够更加高效地开发复杂的应用程序。

STL的设计思想是泛型编程，即通过模板实现通用的数据结构和算法，可以适用于不同的数据类型。它的设计理念是“container、algorithm和iterator”（容器、算法和迭代器），容器用于存储和管理数据，算法用于处理容器中的数据，迭代器用于在容器中遍历数据。

STL中提供了多种容器，例如vector、list、set、map等，每种容器都有自己的特点和适用场景；同时也提供了丰富的算法，例如排序、查找、变换等，可以直接应用于容器中的数据；另外还有迭代器，可以方便地遍历容器中的数据。

使用STL可以提高程序的开发效率和可维护性，同时还能够提高程序的性能。STL已经成为C++编程的重要组成部分，是每个C++程序员都应该掌握的技术。

98.C++中标准库是什么？

C++标准库（C++ Standard Library）是C++语言的官方库，它是由C++语言的国际标准规定的，包括大量的头文件和库函数，提供了丰富的功能，例如输入输出、字符串处理、数学计算、容器、算法、多线程等等。

C++标准库包括两部分：STL（Standard Template Library，标准模板库）和非STL部分。

STL部分提供了容器、迭代器、算法等组件，它们都是使用模板实现的，可以适应不同的数据类型和算法。STL的设计思想是泛型编程，即通过模板实现通用的数据结构和算法，可以适用于不同的数据类型。

非STL部分提供了其他的库函数和头文件，包括输入输出、字符串处理、数学计算、文件处理、时间日期等等。这些库函数和头文件提供了C++标准库的基本功能，可以满足大部分常见的编程需求。

容器

99.常见容器性质总结？

1. vector 底层数据结构为数组 ，支持快速随机访问

2. list底层数据结构为双向链表，支持快速增删

3. deque 底层数据结构为一个中央控制器和多个缓冲区，支持首尾（中间不能）快速增删，也支持随机访问

   deque是一个双端队列，也是在堆中保存内容的.

4. stack 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时

5. queue 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时（stack和queue其实是适配器,而不叫容器，因为是对容器的再封装）

6. priority_queue 的底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现

7. set 底层数据结构为红黑树，有序，不重复

8. multiset 底层数据结构为红黑树，有序，可重复

9. map 底层数据结构为红黑树，有序，不重复

10. multimap 底层数据结构为红黑树，有序，可重复

11. unordered_set 底层数据结构为hash表，无序，不重复

12. unordered_multiset 底层数据结构为hash表，无序，可重复

13. unordered_map 底层数据结构为hash表，无序，不重复

14. unordered_multimap 底层数据结构为hash表，无序，可重复

string

100.C++中新增了string，它与C语言中的 char *有什么区别吗？它是如何实现的？

string继承自basic_string,其实是对char *进行了封装，封装的string包含了char *数组，容量，长度等等属性。

C++中的string是一个字符串类，它可以动态的分配内存空间，实现了自动的内存管理，提供了方便的字符串操作方法，相对于C语言中的char*指针有以下几个区别：

1. 内存管理：char* 指针需要手动申请和释放内存，而string类使用动态内存分配， 避免了内存泄露和空间溢出等问题。
2. 长度操作：char*指针需要手动计算字符串的长度，而string类提供了方便的长度操作方法。
3. 字符串操作：char*指针需要手动实现字符串的拼接、比较、查找等操作，而string类提供了丰富的字符串操作方法。
4. 安全性：char*指针容易出现越界等安全问题，而string类可以自动检测越界错误，提高了程序的健壮性。

string类的实现是基于动态数组的方式，它使用了一些STL中的容器和迭代器，提供了各种方便的字符串操作方法。具体实现过程中，string类在内存分配时，先分配一个足够大的内存空间，如果字符串长度超过了当前分配的空间，则重新分配更大的空间，在每次扩展的时候另外申请一块原空间大小两倍的空间（2*n），然后将原字符串拷贝到新的空间，并加上新增的内容，释放原来的空间。这样就能实现自动扩容和释放内存，同时保证字符串操作的高效性和安全性。

vector

94.STL中vector的实现

STL中的vector是一种动态数组，它的大小可以根据需要自动扩展或收缩，并且支持随机访问和快速插入/删除元素等操作。下面简单介绍一下vector的实现原理：

vector实际上是由一个连续的内存空间组成的动态数组，可以通过下标直接访问其中的元素。当需要在vector中添加一个元素时，如果当前vector中的空间不足，就需要扩展内存空间。vector的实现方式是分配一块比当前空间更大的内存空间，并将原有元素复制到新的内存空间中，然后释放原有的内存空间。这样就可以保证vector的元素是连续存储的，可以实现高效的随机访问。如果需要删除vector中的元素，则需要将后面的元素依次往前移动，覆盖被删除的元素，然后调用析构函数释放最后一个元素的内存空间。

其在扩充空间的过程中仍然需要经历：重新配置空间，移动数据，释放原空间等操作。这里需要说明一下动态扩容的规则：以原大小的两倍配置另外一块较大的空间（或者旧长度+新增元素的个数），源码：

const size_type len  = old_size + max(old_size, n); 

Vector扩容倍数与平台有关，在Win + VS 下是 1.5倍，在 Linux + GCC 下是 2 倍

除了基本的添加/删除操作，vector还提供了很多其他的操作，如查找元素、排序、遍历等。在实现这些操作时，vector使用了一些STL中的算法和迭代器，使得操作更加高效、简洁。

需要注意的是，vector的扩展是有成本的，每次扩展都需要重新分配内存并复制元素，因此如果预先知道vector需要的大小，最好在创建vector时指定初始大小，避免过多的扩展操作。此外，由于vector的内存是连续的，当需要存储大量的元素时，可能会占用过多的内存空间，导致内存不足的问题。

95.vector扩容倍数为什么是1.5或者是2倍？

在C++中，vector是一个动态数组，可以自动扩容以适应需要存储的元素数量。当vector需要扩容时，它会分配一个新的更大的内存块，并将原来的元素复制到新的内存块中。这个过程可能比较耗时，因此vector的扩容方式是一个重要的性能因素。

vector的扩容倍数通常是1.5或2倍。这是因为：

1. 扩容倍数过小可能导致过多的扩容操作，增加程序的运行时间。例如，如果扩容倍数为1，则每次插入元素时都需要重新分配内存，这会导致插入n个元素的时间复杂度为O(n^2)。
2. 扩容倍数过大可能会浪费内存。例如，如果扩容倍数为4，则可能会分配比实际需要更多的内存，导致内存浪费。

因此，通常采用1.5或2倍的扩容倍数，既能够保证性能，又能够避免内存浪费。需要注意的是，vector的扩容倍数可能因编译器和平台的不同而有所不同。

96.vector的增加删除都是怎么做的？

在C++中，vector是一个动态数组，可以在运行时改变其大小。vector有许多方便的方法可以添加、删除和修改元素。

以下是一些基本的方法：

1. 增加元素：

• 可以使用push_back()方法在vector的末尾添加一个元素。例如：

vector<int> myvector;
myvector.push_back(10); //添加元素10到vector的末尾

• 也可以使用insert()方法在指定位置插入一个元素。例如：

vector<int> myvector;
myvector.insert(myvector.begin(), 20); //将元素20插入到vector的开头

2. 删除元素：

• 可以使用pop_back()方法从vector的末尾删除一个元素。例如：

vector<int> myvector;
myvector.push_back(10);
myvector.pop_back(); //从vector的末尾删除元素

• 也可以使用erase()方法从指定位置删除一个或多个元素。例如：

vector<int> myvector;
myvector.push_back(10);
myvector.push_back(20);
myvector.push_back(30);
myvector.erase(myvector.begin() + 1); //从vector中删除第二个元素

• 还可以采用通用算法remove()来删除vector容器中的元素.这个算法实际上不是真正地删除元素，而是将待删除的元素移到vector的末尾，并返回指向这个新的“逻辑末尾”的迭代器。且采用remove一般情况下不会改变容器的大小，而pop_back()与erase()等成员函数会改变容器的大小。

3. 修改元素： 可以使用下标运算符[]或at()方法修改vector中的元素。例如：

vector<int> myvector;
myvector.push_back(10);
myvector.push_back(20);
myvector[1] = 30; //将第二个元素修改为30

注意，使用at()方法可以检查越界错误，因为它会抛出一个异常，而下标运算符不会。

以上是vector中的一些基本操作，还有其他更高级的操作，比如排序、查找等等。

97.vector容器避免push_back时扩展容器开销的办法。

在使用 vector 容器时，避免频繁扩容可以提高程序的效率。以下是几种避免 push_back 时扩展容器开销的办法：

1. 初始化容器大小：在创建 vector 容器时，可以通过传递初始大小来预留足够的空间，避免频繁扩容。例如：

   std::vector<int> vec(100);  // 初始化大小为 100
   

2. 预留空间：如果无法确定容器的初始大小，可以使用 reserve 函数预留一定的空间，避免频繁扩容。例如：

   std::vector<int> vec;
   vec.reserve(100);  // 预留空间，大小为 100
   

3. 使用 emplace_back 函数：emplace_back 函数可以直接在容器的末尾构造元素，避免拷贝构造函数的调用。例如：

   std::vector<std::string> vec;
   vec.emplace_back("hello");  // 直接在容器末尾构造元素
   

4. 使用移动语义：使用移动语义避免不必要的拷贝构造函数调用，提高程序效率。例如：

   std::vector<std::string> vec;
   std::string str = "hello";
   vec.push_back(std::move(str));  // 使用 std::move 移动 str
   

98.STL 中vector删除其中的元素，迭代器如何变化？

在STL中，vector删除元素时，迭代器的指向会发生变化。具体来说，删除元素后，指向被删除元素的迭代器和指向被删除元素之后元素的迭代器都会失效。

为了避免这种情况，可以在删除元素后使用返回值更新迭代器，或者使用迭代器的算术运算来保证指向正确的元素。具体方法如下：

1. 使用erase()方法删除元素并返回指向下一个元素的迭代器。因为删除元素后，迭代器指向的位置已经发生了变化，所以必须使用返回值更新迭代器。

std::vector<int> vec{1, 2, 3, 4, 5};
auto it = vec.begin() + 2;
it = vec.erase(it);  // 删除3并返回指向4的迭代器

2. 使用算术运算符更新迭代器的指向。可以使用前置递增运算符++或后置递增运算符++来移动迭代器。

std::vector<int> vec{1, 2, 3, 4, 5};
auto it = vec.begin() + 2;
vec.erase(it);
it = vec.begin() + 2;  // 更新迭代器指向正确的位置

需要注意的是，在循环中使用迭代器遍历vector时，如果需要删除元素，必须使用erase()方法来删除元素并返回新的迭代器。如果使用迭代器的算术运算符或索引来删除元素，可能会导致迭代器失效，导致程序崩溃或产生未定义行为。

99.Vector如何释放空间,删除元素时会不会释放空间?

在C++中使用标准库中的vector，可以使用以下两种方式释放vector占用的内存空间：

1. clear()函数

使用vector的clear()函数可以清空vector中的元素，同时也会释放vector占用的内存空间。但是，这种方法只会释放vector中元素占用的内存空间，而不会释放vector对象本身占用的内存空间。

示例代码：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};

    // 使用clear()函数释放vector占用的内存空间
    v.clear();

    return 0;
}

2. swap()函数

使用vector的swap()函数可以将一个空的vector对象与要释放内存的vector对象进行交换，这样可以释放vector对象占用的内存空间。在交换之后，空的vector对象会占用原先vector对象的内存空间，而原先的vector对象则变为空。

示例代码：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};

    // 使用swap()函数释放vector占用的内存空间
    std::vector<int>().swap(v);

    return 0;
}

需要注意的是，使用swap()函数释放内存空间的方式并不是立即生效的，需要等到程序退出当前作用域时才会真正释放内存空间。

关于vector删除元素时是否会释放空间，答案是：不一定。当调用vector的erase()函数或者resize()函数时，vector会释放掉被删除或调整大小的元素占用的内存空间，但是vector对象占用的内存空间并不会减少。如果需要释放vector对象占用的内存空间，可以使用上面提到的clear()函数或swap()函数。

如果要想在删除内容的同时释放内存，那么你可以选择deque容器。

100.vector和list的区别是什么？

1. vector底层实现是数组；list是双向链表。
2. vector支持随机访问，list不支持。
3. vector是顺序内存，list不是。
4. vector在中间节点进行插入删除会导致内存拷贝，list不会。
5. vector一次性分配好内存，不够时才进行2倍扩容；list每次插入新节点都会进行内存申请。
6. vector随机访问性能好，插入删除性能差，时间复杂度为O(n)；list随机访问性能差，插入删除性能好，时间复杂度为O(1)。

101.怎么找vector或者list的倒数第二个元素

找vector的倒数第二个元素

std::vector<int> vec = {1, 2, 3, 4, 5};
if (vec.size() >= 2) {
    int second_last = vec.at(vec.size() - 2); // 获取倒数第二个元素的值
}

找list的倒数第二个元素

list不提供随机访问，所以不能用下标直接访问到某个位置的元素，要访问list里的元素只能遍历，不过你要是只需要访问list的最后N个元素的话，可以用反向迭代器来遍历：

std::list<int> lst = {1, 2, 3, 4, 5};
if (lst.size() >= 2) {
    auto it = lst.rbegin();
    ++it; // 获取倒数第二个元素的迭代器
    int second_last = *it; // 获取倒数第二个元素的值
}

102.vector越界访问下标，map越界访问下标？

在C++中，如果访问vector或map中不存在的下标，会导致越界访问错误。不过，vector和map越界访问的表现形式不同。

当访问vector中不存在的下标时，会触发运行时错误，并且程序可能会崩溃。例如，以下代码访问了vector中不存在的下标5：

std::vector<int> vec = {1, 2, 3};
int x = vec[5]; // 访问不存在的下标，会触发越界访问错误

当程序运行到上述代码时，会抛出std::out_of_range异常，如果没有被捕获，程序会异常终止。因此，在使用vector时，应该始终确保访问的下标不越界。

当访问map中不存在的下标时，不会抛出异常或导致程序崩溃，而是返回默认值。map的下标访问操作会返回一个引用，如果map中不存在该下标，则会自动插入一个具有该下标的默认值，并返回一个对该默认值的引用。例如，以下代码访问了map中不存在的下标5：

std::map<int, int> m = {{1, 10}, {2, 20}, {3, 30}};
int x = m[5]; // 访问不存在的下标，返回默认值0

在上述代码中，访问不存在的下标5会自动插入一个具有下标5和默认值0的键值对，x的值为默认值0。因此，在使用map时，需要注意如果需要区分不存在的下标和默认值时的情况，可以使用map的count函数来检查下标是否存在。

deque

103.STL中的deque的实现

STL中的deque（双端队列）是一种支持随机访问和在两端插入和删除操作的序列容器。deque的实现通常是基于一个或多个连续的动态数组，每个数组被称为一个缓冲区（buffer），缓冲区之间通过指针进行链接。

deque的主要实现原理是使用一个双向链表维护各个缓冲区之间的链接关系，并将每个缓冲区看作一个固定大小的数组，用来存储具体的元素。这样，deque就可以支持在两端进行快速的插入和删除操作，同时也可以支持随机访问。

为了实现随机访问，deque内部还维护了一个索引表（index table），用来保存缓冲区的起始地址和尺寸信息。索引表本质上也是一个数组，每个元素对应一个缓冲区。索引表的大小通常比实际元素数量大一些，以便能够在需要时动态地扩展和收缩缓冲区。

stack

104.STL中stack的实现和常用方法

在STL中，stack通常是基于deque（双端队列）实现的。

可以使用以下代码来创建一个stack对象：

#include <stack>
std::stack<int> myStack;

默认情况下，这将创建一个空的int类型的stack对象。下面是一些常用的stack方法：

• push(elem)：将元素elem推入栈顶。
• pop()：弹出栈顶元素。
• top()：返回栈顶元素，但不弹出它。
• empty()：如果栈为空则返回true，否则返回false。
• size()：返回栈中元素的数量。

queue

105.STL中queue的实现和常用方法

在STL中，queue通常是基于deque（双端队列）实现的

可以使用