C++中的STL

STL

vector

特点：

• 底层结构：由动态数组实现，特点是存储空间连续
• 访问遍历：支持随机访问，可使用下标访问，访问时间复杂度为O(1)
• 插入/删除：尾部插入/删除效率较高；中间和头部插入/删除效率较低，因为存储空间是连续的，插入后需要改变元素顺序
• 空间效率：底层实现时，会事先预留一些额外空间， 以减少重新分配的次数
• 使用场景：需要随机访问且频繁在尾部进行操作的场景；如果频繁增删元素则不适用该容器

实现原理：

std::vector内部维护一个动态数组，当容量不足以容纳新元素时，std::vector会分配更大的内存空间，并将现有元素复制到新的存储空间。新容量通常是旧容量的两倍，以减少频繁的内存分配和拷贝操作

deque

特点：

• 底层结构：由双向队列实现，特点是存储空间连续
• 访问遍历：支持随机访问，其性能比vector要低
• 插入/删除：尾部和头部插入/删除效率较高；中间插入/删除时间效率较低，但比vector高效一些
• 空间效率：底层实现时比vector的结构更复杂，也会事先预留一些额外空间， 以减少重新分配的次数
• 使用场景：需要随机访问且频繁在头部和尾部进行操作的场景；如果频繁在中部增删元素则不适用该容器

实现原理：

std::queue是一个双端队列，支持在两端快速插入和删除。内部使用分段存储结构，，而不是一个连续的大块内存。这使得在两端的插入和删除更加高效。使用一个指针管理这些块，并在需要时动态调整指针数组的大小

list

特点：

• 底层结构：由双向链表实现，特点是存储空间不连续
• 访问遍历：不支持随机访问，只能通过迭代器进行访问
• 插入/删除：任意位置插入/删除效率都很高
• 空间效率：每个元素都需要分配额外的空间
• 使用场景：需要在任意位置频繁插入/删除操作的场景

实现原理：

std::list是一个双向链表，包含节点，每个节点包含一个数据元素和两个指针，分别指向前一个和后一个节点。每次插入或删除节点时，都会进行动态内存分配和释放

set

特点：

• 底层结构：由红黑树实现，是一种平衡二叉搜索树，存储空间不连续
• 访问遍历：不支持随机访问，只能通过迭代器进行访问
• 插入/删除：查询/插入/删除效率为O(log N)复杂度
• 排序方式：默认使用less仿函数，即<运算符进行排序；也可以自定义排序规则仿函数
• 使用场景：需要有序集合且元素不重复的场景

multiset

特点：

• 底层结构：由红黑树实现，是一种平衡二叉搜索树，存储空间不连续
• 访问遍历：不支持随机访问，只能通过迭代器访问
• 插入/删除：查询/插入/删除效率为O(log N)复杂度
• 排序方式：默认使用less仿函数，即<运算符进行排序；也可以自定义排序规则仿函数
• 使用场景：需要有序集合且元素重复的场景

map

特点：

• 底层结构：由红黑树实现，是一种平衡二叉搜索树，存储空间不连续
• 访问遍历：不支持随机访问，只能通过迭代器进行访问
• 插入/删除：查询/插入/删除效率为O(log N)复杂度
• 排序方式：默认使用less仿函数，即<运算符进行排序‘；也可以自定义排序规则的仿函数
• 使用场景：需要有序键值对且键值不重复的场景

multimap

特点：

• 底层结构：由红黑树实现，是一种平衡二叉搜索树，存储空间不连续
• 访问遍历：不支持随机访问，只能通过迭代器进行访问
• 插入/删除：查询/插入/删除效率为O(log N)复杂度
• 排序方式：默认使用less仿函数，即<运算符进行排序‘；也可以自定义排序规则的仿函数
• 使用场景：需要有序键值对且键值重复的场景

emplace_back和push_back

概述： 二者的功能都是向容器尾部添加新元素

区别：

• push_back：先创建临时对象，然后再拷贝复制到对应的内存，再删除临时对象，效率较低
• emplace_back：直接在内存处创建对象，效率较高

在代码中能用emplace_back就用emplace_back

unordered_map vs. map

底层数据结构：

• unordered_map：基于哈希表实现，元素没有排序，键值对的顺序是随机的。在内部，哈希表将键值分配到不同的bucket中，元素的顺序取决于它们的哈希值
• map：基于红黑树（一种近似平衡的二叉查找树）实现，元素按键排序，支持有序的遍历。

插入和查找时间复杂度：

• unordered_map：平均时间复杂度是O(1)，在大量哈希冲突的情况下，复杂度会退化到O(n)
• map：时间复杂度为O(log n)，因为每次操作都涉及红黑树的自平衡

内存开销：

• unordered_map：哈希表的实现需要更多内存来存储bucket和哈希表。哈希表大小是动态调整的，以减少哈希冲突的影响，可能因为内存重新分配导致一定的内存浪费
• map：基于红黑树实现，每个元素存储的开销相对较大，因为每个节点需要存储指向左右子节点、父节点的指针，但是总体内存开销可能比unordered_map低

键的比较方式：

• unordered_map：键的比较通过哈希函数进行，默认情况下标准库为常见类型提供了哈希函数
• map：键的比较通过operator<（或自定义的比较器）来进行，要求键类型必须是可比较的

std::unordered_map示例：

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    unordered_map<int, string> um;
    um[1] = "one";
    um[2] = "two";
    um[3] = "three";

    // 元素的顺序是随机的
    for (const auto& pair : um) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

std::map示例：

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<int, string> m;
    m[1] = "one";
    m[2] = "two";
    m[3] = "three";

    // 元素会按照键升序排序
    for (const auto& pair : m) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

使用场景：

• unordered_map：适用于快速查找和快速插入操作的场景，顺序无关紧要，只关心查找效率
• map：适用于需要按键排序的场景，例如查找范围、按顺序遍历等情况。需要保证有序的插入和删除。