目录：#面试#

1.STL中常用的容器有哪些？

2.请你说说STL容器有哪些并且说一下时间复杂度？

3.请说说vector和list有什么区别？

4.vector和deque的区别？

5.请你说明一下STL底层数据结构实现？

6.请你说说map和set区别差异？

7.请你说说STL迭代器怎样删除元素？

内容：

1.STL中常用的容器有哪些？

顺序容器

1. vector

• 动态数组，支持随机访问。
• 元素存储在连续的内存空间中，支持高效的索引操作（O(1) 时间复杂度）。
• 在尾端增删元素。

2. deque

• 双端队列，支持在两端高效地插入和删除。
• 支持随机访问。
• 相较于 vector，不需要频繁搬移整个数组，但随机访问性能稍差。
• 需要在头尾进行频繁插入或删除操作。

3.list

• 双向链表，支持高效的插入和删除。
• 不支持随机访问。
• 插入和删除操作仅需要调整指针，时间复杂度为 O(1)。
• 频繁插入和删除操作，但对随机访问要求不高。

4 .forward_list

• 单向链表，支持单向遍历和高效的插入、删除操作。
• 相较于 list，更加轻量级。
• 使用单向链表实现，元素通过单指针链接，内存不连续。
• 需要简单链表操作，内存开销较小的场景。

5. string

• 专门用于操作字符串的容器，功能类似 vector<char>。
• 基于动态数组实现，支持动态扩容。
• 提供了大量字符串处理函数，例如拼接、查找、替换等。
• 字符串操作。

关联容器

1. map

• 存储键值对，键是唯一的，支持高效的查找、插入、删除操作（O(log n)）。
• 数据按照键值排序，支持有序遍历。
• 需要按键有序存储键值对，并支持快速查找。

2. multimap

• 和 map 类似，但允许键重复。
• 和 map 一样基于红黑树实现，区别在于支持存储重复键。
• 键值对存储，但允许键重复。

3. set

• 存储唯一的键，自动按顺序排列。
• 支持高效的插入、查找、删除操作（O(log n)）。
• 基于红黑树实现。
• 元素作为键值存储，不能重复。
• 需要存储唯一值，并支持快速查找和有序遍历。

4. multiset

• 和 set 类似，但允许重复值。
• 和 set 一样基于红黑树实现，区别在于允许重复值。
• 数据存储需支持重复值，但仍需要有序存储。

5. unordered_map

• 存储键值对，键是唯一的，查找和插入操作的平均时间复杂度为 O(1)。
• 基于哈希表实现。
• 数据无序存储。
• 快速查找键值对，但对顺序无要求。

6. unordered_multimap

• 和 unordered_map 类似，但允许键重复。
• 基于哈希表实现，支持重复键。
• 快速查找键值对，允许键重复。

7. unordered_set

• 存储唯一值，无序排列。
• 基于哈希表实现。
• 无序存储唯一值，并支持快速查找。

8. unordered_multiset

• 和 unordered_set 类似，但允许重复值。
• 基于哈希表实现。
• 无序存储值，并允许重复。

总结

2.请你说说STL容器有哪些并且说一下时间复杂度？

顺序容器

顺序容器中的元素按插入顺序存储，主要用于序列存储。

关联容器

关联容器通常按键值对存储，底层实现基于红黑树，支持有序存储和快速查找。

无序关联容器

无序关联容器底层基于哈希表实现，支持快速的查找、插入和删除操作，但不保证元素的顺序。

容器适配器

3.请说说vector和list有什么区别？

相同点

• 两者都属于顺序容器，用于按插入顺序存储元素。
• 支持动态大小调整（虽然实现方式不同）。
• 都能通过 STL 提供的标准迭代器（iterator）进行元素的访问和操作。
• 两者提供类似的容器操作接口，如插入（insert）、删除（erase）、遍历（begin/end）等。
• 支持 STL 算法（如 std::sort，但需要注意 list 需要先转为其他容器才支持随机访问相关算法）。
• 容器中的元素可以是基本数据类型，也可以是用户自定义的复杂类型。

不同点

使用场景

vector 的场景

• 需要随机访问，如果需要频繁按索引访问元素，vector 是更好的选择。
• 数据量变化不频繁，数据量相对固定或变化不频繁，避免频繁的动态扩容带来的性能开销。
• 需要排序或二分查找，vector 支持快速排序和二分查找等操作，效率比 list 高。
• 空间效率高，内存连续分配，不需要额外的指针存储。

list 的场景

• 需要频繁的插入/删除操作，特别是在容器中间进行大量插入或删除操作时，list 的性能比 vector 好。
• 数据较大或变化频繁，数据量较大时，可以避免因 vector 扩容带来的大量内存分配和拷贝。
• 不需要随机访问，如果只需顺序访问，链表的性能足够且更灵活。

例子：

vector

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3};
    v.push_back(4); // 在尾部插入
    v[2] = 5;       // 通过索引修改
    for (int i : v) {
        cout << i << " "; // 输出：1 2 5 4
    }
    return 0;
}

list

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l = {1, 2, 3};
    auto it = l.begin();
    advance(it, 1); // 移动迭代器到第二个元素
    l.insert(it, 5); // 在第二个位置插入 5
    for (int i : l) {
        cout << i << " "; // 输出：1 5 2 3
    }
    return 0;
}

4.vector和deque的区别？

区别

vector：

• 底层使用动态连续数组实现。
• 所有元素存储在一块连续的内存空间中。
• 扩容时需要重新分配更大的连续内存空间，并将原数据拷贝到新内存。
• 所有元素在一块连续的内存中，内存使用效率较高。
• 扩容时会分配更大的连续内存块，并将数据拷贝到新内存中。

deque：

• 底层使用分段数组实现。
• 内存不是连续的，由多个固定大小的内存块（缓冲区）组成，通过中间的指针数组（映射表）管理。
• 不需要重新分配整个内存，添加元素时，只需分配新的内存块。
• 内存是分段分配的，不需要分配连续内存，适合频繁的插入和删除操作。
• 因为有额外的指针数组（映射表）管理多个内存块，内存开销略高。
• 动态扩容时，只需分配新块并更新指针数组，无需整体移动元素。

例子

vector

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3};
    v.push_back(4); // 在尾部插入元素
    v[1] = 10;      // 通过索引访问
    for (int i : v) {
        cout << i << " "; // 输出：1 10 3 4
    }
    return 0;
}

deque

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> d = {1, 2, 3};
    d.push_front(0); // 在头部插入元素
    d.push_back(4);  // 在尾部插入元素
    for (int i : d) {
        cout << i << " "; // 输出：0 1 2 3 4
    }
    return 0;
}

5.请你说明一下STL底层数据结构实现？

6.请你说说map和set区别差异？

差异

1. map

• 存储键值对的数据。
• 键（key）是唯一的，每个键对应一个值（value）。
• 可以通过键快速查找对应的值。
• 通过键直接访问值：O(log n)。
• 插入时，需要同时插入键和值。

常用操作：

• 插入：map[key] = value 或 emplace(key, value)。
• 查找：map.find(key)。
• 访问：通过 map[key] 获取对应的值。

2. set

• 存储唯一的键，不存储值。
• 每个元素是唯一的，且只包含键（key）。
• 只存储键，操作相对更简单，内存占用也更少。

常用操作：

• 插入：set.insert(key)。
• 查找：set.find(key)。
• 删除：set.erase(key)。

底层结构：

• 二者底层均基于红黑树实现。
• 红黑树是一种平衡二叉搜索树，保证插入、删除、查找操作的时间复杂度为 O(log n)。
• 数据在红黑树中是按键值大小自动排序的（中序遍历为升序）。

时间复杂度：两者的插入、删除、查找操作的时间复杂度都是 O(log n)

使用场景

1. 使用 map 的场景

• 需要通过键快速找到对应值的场景，例如： 记录学生学号与成绩的对应关系。存储配置项（键值对）。
• 例子：

std::map<std::string, int> studentScores;
studentScores["Alice"] = 90; // 插入
studentScores["Bob"] = 85;  // 插入
std::cout << studentScores["Alice"]; // 输出 90

2. 使用 set 的场景

• 需要快速查找某个值是否存在，或者对一组数据去重的场景，例如： 检查一组单词是否唯一。判断一个元素是否在集合中。
• 例子：

std::set<int> uniqueNumbers;
uniqueNumbers.insert(10); // 插入
uniqueNumbers.insert(20); // 插入
if (uniqueNumbers.find(10) != uniqueNumbers.end()) {
    std::cout << "10 exists in the set." << std::endl;
}

map 和 set 的比较

map 例子

#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> scores;
    scores["Alice"] = 90;
    scores["Bob"] = 85;

    // 查找键值对
    if (scores.find("Alice") != scores.end()) {
        std::cout << "Alice's score: " << scores["Alice"] << std::endl;
    }

    // 遍历
    for (const auto& pair : scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

set 例子

#include <iostream>
#include <set>

int main() {
    std::set<int> uniqueNumbers;
    uniqueNumbers.insert(10);
    uniqueNumbers.insert(20);
    uniqueNumbers.insert(10); // 重复插入，不会生效

    // 查找
    if (uniqueNumbers.find(10) != uniqueNumbers.end()) {
        std::cout << "10 exists in the set." << std::endl;
    }

    // 遍历
    for (int num : uniqueNumbers) {
        std::cout << num << " ";
    }

    return 0;
}

7.请你说说STL迭代器怎样删除元素？

基本规则

删除容器中的元素时，删除操作会使迭代器失效，但容器通常会返回指向下一个有效元素的迭代器。常见的操作方式如下：

it = container.erase(it);

这里，erase() 函数会删除迭代器 it 指向的元素，并返回一个新的迭代器，指向被删除元素的下一个位置。

各容器中使用迭代器删除元素的方法

（1）std::vector 和 std::deque

• 删除单个元素或范围元素时，需要移动后续元素，效率为 O(n)。
• 使用 erase() 函数可以避免迭代器失效。

例子：为 3 的元素

#include <vector>
#include <iostream>

std::vector<int> vec = {1, 3, 2, 3, 4};
for (auto it = vec.begin(); it != vec.end(); ) {
    if (*it == 3) {
        it = vec.erase(it); // 删除当前元素，并更新迭代器指向下一个元素
    } else {
        ++it; // 否则移动到下一个元素
    }
}

// 输出结果：1 2 4
for (int v : vec) {
    std::cout << v << " ";
}

注意：直接 ++it 后调用 erase(it) 会导致迭代器失效。

（2）std::list

• std::list 是双向链表，删除元素时不需要移动后续元素，因此删除效率较高，复杂度为 O(1)。
• erase() 函数可以删除单个元素或范围。

例子：删除所有偶数

#include <list>
#include <iostream>

std::list<int> lst = {1, 2, 3, 4, 5};
for (auto it = lst.begin(); it != lst.end(); ) {
    if (*it % 2 == 0) {
        it = lst.erase(it); // 删除当前元素，并更新迭代器指向下一个元素
    } else {
        ++it; // 否则移动到下一个元素
    }
}

// 输出结果：1 3 5
for (int v : lst) {
    std::cout << v << " ";
}

（3）std::set 和 std::map

• std::set 和 std::map 基于红黑树，删除元素的复杂度为 O(log n)。
• 迭代器删除时需要使用 erase() 方法。

例子：从 std::set 中删除所有偶数

#include <set>
#include <iostream>

std::set<int> s = {1, 2, 3, 4, 5};
for (auto it = s.begin(); it != s.end(); ) {
    if (*it % 2 == 0) {
        it = s.erase(it); // 删除当前元素，更新迭代器
    } else {
        ++it; // 否则移动到下一个元素
    }
}

// 输出结果：1 3 5
for (int v : s) {
    std::cout << v << " ";
}

注意：对于 std::map，删除时基于键值对，迭代器指向 std::pair。

（4）std::unordered_set 和 std::unordered_map

• 这类容器基于哈希表，删除操作的复杂度为 O(1)。
• 使用迭代器删除与 std::set 和 std::map 类似。

例子：删除所有偶数

#include <unordered_set>
#include <iostream>

std::unordered_set<int> us = {1, 2, 3, 4, 5};
for (auto it = us.begin(); it != us.end(); ) {
    if (*it % 2 == 0) {
        it = us.erase(it); // 删除当前元素，更新迭代器
    } else {
        ++it;
    }
}

// 输出结果：1 3 5
for (int v : us) {
    std::cout << v << " ";
}

#秋招##春招##嵌入式##牛客激励计划##面经#