【小陈背八股-C++】Day05-为什么面试总爱问Vector、Map和List？

前言

• “Vector和List的根本区别是什么？”
• “Map的底层是如何保证高效查找的？”
• “海量数据场景下该如何选择容器？”

本文直面面试核心，系统梳理五大关键容器：从Vector的连续内存优势与扩容代价，到List的灵活插入与查找局限；从红黑树维持Map/Set有序性的平衡原理，到Deque分段结构的实现智慧。我们将穿透概念表象，直击面试官最关注的底层原理与设计取舍。

理解容器，就是理解C++性能优化的核心逻辑。让我们开始这场面向实战的深度解析。

1. list和vector有什么区别？

• 底层数据结构
  • vector : 动态数组，在内存中是连续存储的
  • list : 双向链表，每一个元素可以存储在不连续的内存块中，每一个节点包括指向前一个元素和后一个元素的指针
• 随机访问
  • vector ：支持高效率的随机访问O(log1)，因为通过索引计算地址常量时间
  • list：不支持随机访问，想要访问第n个元素，需要遍历链表
• 插入和删除操作
  • vector：在尾部插入或删除O(log1)、在中间或者头部删除/插入元素O(logN)
  • list：在任意位置删除或插入O(1)，但是找到插入/删除的位置需要的时间为O(n)
• 迭代器
  • vector：随机访问迭代器，支持所有迭代器操作（包括加减整数等）
  • list：双向迭代器，只支持前移或者后移，不支持随机访问（如It+）
• 使用场景
  • vector：当需要频繁随机访问时，或者主要在尾部添加或者删除元素时使用
  • list：当需要在容器中频繁地插入或删除元素，并且不需要随机访问时使用
• 速度
  • vector：使用连续内存分配，能够很好地利用程序空间局部性的特点，提高访问速度。程序的空间局部性原理，当程序中的某一个数据被访问后，与之相邻的数据在不久后也可能被访问。而 std::vector 连续内存分布天然的符合这一特性。那么当访问vector中的某一个元素时，会将一整个内存数据块加载到高速缓存中，后续访问到同一行中的元素时，直接命中高速缓存
  • list：内存分布不是连续的，访问下一个元素时需要跳转指针，几乎每一次的访问都会缓存未命中

2. list是如何实现元素的插入和删除的？

• list的底层是一个双链表，每一个结点都包含了指向前一个结点和指向后一个结点的指针，支持双向遍历
• 插入和删除都是通过修改指针的指向即可

3. set的底层实现与map有什么不同

• 相同点：
  • std::set 和 std::map 在C++标准库中都是基于平衡二叉树实现的（一般是红黑树）
• 不同点：
  • std::set 仅储存键值，而 std::map 储存键值对
  • std::set 存储的键就是元素本身，而 std::map 存储的键值是键，值是与键相关联的数据

4. map、set、multimap、multiset有什么区别？

C++中的map、set、multimap、multiset都是标准库中的关联容器，都是基于红黑树实现的，下面是它们的详细区别：

1. std::map
   • 存储的是键值对：<Key,T>，其中Key是键，T是与键相关联的值
   • 键的唯一性：每一个键在map中是唯一的，不允许出现重复的键
   • 排序：map中的元素根据键自动排序
   • 访问：通过键访问值，使用下标操作符operator[ ]直接访问或添加元素
2. std::set
   • 仅存储键：也就是说键就是元素本身，并不存储值
   • 元素唯一性：每一个元素在set中也是为一个，不允许出现相同的元素
   • 排序：set中的元素根据元素值自动排序
   • 访问：不支持下标访问，只支持迭代器访问
3. std::multimap
   • 键值对存储：与map类似
   • 键的重复性：允许多个元素有相同的键
   • 排序：multimap中的元素根据键自动排序，对于具有相同键的元素，它们内部也是有序的（通常是插入顺序）
   • 访问：通过键访问值，但是不能访问特定键的所有值，需要遍历
4. std::multiset
   • 只存储键：只存储键，与set类似
   • 键的重复性：允许多个元素键相同
   • 排序：multiset中的元素根据键自动排序，对于具有相同键的元素，内部也是有序的（通常是插入顺序）
   • 访问：只能通过迭代器访问，不能使用下标访问

5. 如何在set和map查找元素？

5.1. std::map

• find方法：
  • 直接使用find方法查找特定键的值
  • 如果找到了，返回一个指向该元素的迭代器；如果没有找到，返回一个指向end()的迭代器

std::map<int, std::string> myMap;
myMap[1] = "one";
myMap[2] = "two";

auto it = myMap.find(1);
if (it != myMap.end()) {
    std::cout << "Found: " << it->second << std::endl;
} else {
    std::cout << "Not found" << std::endl;
}

• count方法：
  • 用于返回具有特定键值的元素数量，如果是std::map ，键是唯一的，所以要么返回0要么是1

size_t count = myMap.count(1);
if (count > 0) {
    std::cout << "Found" << std::endl;
} else {
    std::cout << "Not found" << std::endl;
}

• lower_bound和upper_bound方法：
  • lower_bound返回不小于给定键的首个元素的迭代器
  • upper_bound返回大于给定键的首个元素的迭代器

auto lower = myMap.lower_bound(1);
auto upper = myMap.upper_bound(1);
if (lower != upper) {
    std::cout << "Found: " << lower->second << std::endl;
}

• equal_range方法： equal_range返回一个迭代器对，第一个是lower_bound，第二个是upper_bound

auto range = myMap.equal_range(1);
if (range.first != range.second) {
    std::cout << "Found: " << range.first->second << std::endl;
}

5.2. std::set

• find方法：

std::set<int> mySet;
mySet.insert(1);
mySet.insert(2);

auto it = mySet.find(1);
if (it != mySet.end()) {
    std::cout << "Found" << std::endl;
} else {
    std::cout << "Not found" << std::endl;
}

• count方法：

size_t count = mySet.count(1);
if (count > 0) {
    std::cout << "Found" << std::endl;
} else {
    std::cout << "Not found" << std::endl;
}

• lower_bound和upper_bound方法：

auto lower = myMap.lower_bound(1);
auto upper = myMap.upper_bound(1);
if (lower != upper) {
    std::cout << "Found: " << lower->second << std::endl;
}

• equal_range方法：

auto range = myMap.equal_range(1);
if (range.first != range.second) {
    std::cout << "Found: " << range.first->second << std::endl;
}

6. 容器map、deque、list的实现原理？

• std::map :
  • 基于红黑树：保证按照元素的键的顺序进行排序。每个节点存储了键值对，根据键的比较结果进行自平衡。红黑树是一种自平衡二叉树，根据颜色和节点的特定排列保持平衡
  • 有序容器：同时是按照 < 运算符定义的顺序
  • 唯一键：每一个键都是为一的，不允许有重复的键
  • 时间复杂度：查找、插入和删除的时间复杂度都是O(logN)
  • 迭代器：由于map是基于树的，所以迭代器在遍历的时候是有序的
• std::deque：
  • 是一个双端队列，允许在容器的两端进行快速的插入和删除操作
  • 允许序列操作：可以快速地在队列的前端或末端添加/删除元素
  • 时间复杂度：队列前端或后端的插入/删除操作时间复杂度为常数，中间插入/删除时间为O(N)