STL重点

1.容器：vector,list,map,set的底层实现（数组、链 表、红黑树）及时间复杂度

1. 容器分类概览

序列式容器 vs 关联式容器

// 序列式容器：元素顺序由插入顺序决定
std::vector<int> vec;     // 动态数组
std::list<int> lst;       // 双向链表
std::deque<int> deq;      // 双端队列

// 关联式容器：元素按特定顺序存储
std::set<int> s;          // 有序集合（红黑树）
std::map<int, std::string> m; // 有序映射（红黑树）
std::unordered_set<int> us;   // 哈希集合
std::unordered_map<int, std::string> um; // 哈希映射

2. std::vector - 动态数组

底层实现

// vector的简化内存布局
template<typename T>
class vector {
private:
    T* start;          // 指向首元素
    T* finish;         // 指向最后一个元素的下一个位置
    T* end_of_storage; // 指向分配内存的末尾
};

内存增长策略：当容量不足时，通常按2倍或1.5倍扩容，分配新内存，拷贝元素，释放旧内存。

时间复杂度分析

代码示例

#include <vector>
#include <iostream>

void vector_example() {
    std::vector<int> vec;
    
    // 插入 - 分摊O(1)
    for (int i = 0; i < 10; ++i) {
        vec.push_back(i); // 可能触发扩容
    }
    
    // 随机访问 - O(1)
    std::cout << "Element at index 5: " << vec[5] << std::endl;
    
    // 中间插入 - O(n)
    vec.insert(vec.begin() + 3, 100); // 需要移动后面所有元素
    
    // 删除中间元素 - O(n)
    vec.erase(vec.begin() + 3); // 需要移动后面所有元素
}

3. std::list - 双向链表

底层实现

// list节点的简化结构
template<typename T>
struct list_node {
    T data;
    list_node* prev;
    list_node* next;
};

// list的简化结构
template<typename T>
class list {
private:
    list_node<T>* head; // 头节点（通常包含双向循环）
    size_t size;
};

时间复杂度分析

代码示例

#include <list>
#include <iostream>

void list_example() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    
    // 头尾插入 - O(1)
    lst.push_front(0);
    lst.push_back(6);
    
    // 中间插入 - O(1)（已知迭代器位置）
    auto it = lst.begin();
    std::advance(it, 3); // 移动到第4个元素 - O(n)
    lst.insert(it, 100); // 插入 - O(1)
    
    // 删除 - O(1)（已知迭代器位置）
    it = lst.begin();
    std::advance(it, 2); // O(n)
    lst.erase(it);       // O(1)
    
    // 查找 - O(n)
    auto found = std::find(lst.begin(), lst.end(), 4);
    if (found != lst.end()) {
        std::cout << "Found: " << *found << std::endl;
    }
}

4. std::map - 有序映射（红黑树）

底层实现：红黑树

红黑树是一种自平衡的二叉搜索树，满足：

1. 每个节点是红色或黑色

2. 根节点是黑色

3. 所有叶子节点（NIL）是黑色

4. 红色节点的子节点必须是黑色

5. 从任一节点到其每个叶子的所有路径包含相同数目的黑色节点

时间复杂度分析

代码示例

#include <map>
#include <iostream>

void map_example() {
    std::map<int, std::string> student_map;
    
    // 插入 - O(log n)
    student_map.insert({1, "Alice"});
    student_map[2] = "Bob";        // O(log n)
    student_map.emplace(3, "Charlie"); // O(log n)
    
    // 查找 - O(log n)
    auto it = student_map.find(2);
    if (it != student_map.end()) {
        std::cout << "Found: " << it->second << std::endl;
    }
    
    // 访问 - O(log n)
    std::cout << "Student 1: " << student_map.at(1) << std::endl;
    
    // 删除 - O(log n)
    student_map.erase(3);
    
    // 有序遍历 - O(n)
    for (const auto& [id, name] : student_map) {
        std::cout << id << ": " << name << std::endl;
    }
}

5. std::set - 有序集合（红黑树）

底层实现

std::set 的底层实现也是红黑树，但只存储键（没有值）。

时间复杂度分析

#include <set>
#include <iostream>

void set_example() {
    std::set<int> unique_numbers;
    
    // 插入 - O(log n)
    unique_numbers.insert(5);
    unique_numbers.insert(2);
    unique_numbers.insert(8);
    unique_numbers.insert(2); // 重复，不会插入
    
    // 查找 - O(log n)
    if (unique_numbers.find(5) != unique_numbers.end()) {
        std::cout << "5 exists" << std::endl;
    }
    
    // 删除 - O(log n)
    unique_numbers.erase(2);
    
    // 有序遍历 - O(n)
    for (int num : unique_numbers) {
        std::cout << num << " "; // 输出: 5 8
    }
    std::cout << std::endl;
}

6. 综合对比表

*注：vector的push_back()是分摊O(1)，最坏情况O(n)

7. 常见问题

Q1: vector的扩容策略是什么？

答：通常按2倍或1.5倍扩容。当容量不足时，分配新内存（通常是原来的2倍），拷贝所有元素到新内存，释放旧内存。扩容操作的时间复杂度是O(n)。

Q2: 为什么vector的push_back()是分摊O(1)？

答：虽然单次扩容是O(n)，但经过数学证明，n次push_back()操作的总时间复杂度是O(n)，因此单次操作的分摊时间复杂度是O(1)。

Q3: list和vector如何选择？

答：

• 需要随机访问：选择vector (O(1))

• 需要频繁在中间插入删除：选择list (O(1))

• 内存连续性重要：选择vector

• 需要大量头尾操作：都可以，但list的push_front也是O(1)

Q4: 红黑树相比AVL树有什么优势？

答：红黑树的平衡要求比AVL树宽松，插入删除时需要更少的旋转操作，因此在实际应用中性能更好，特别是写入操作频繁的场景。

Q5: map和unordered_map如何选择？

答：

• 需要元素有序：选择map (红黑树)

• 需要最快查找速度：选择unordered_map (哈希表，平均O(1))

• 需要内存紧凑：选择map (红黑树更节省内存)

• 需要频繁插入删除：两者都是O(log n) / O(1)，但unordered_map常数因子更小

总结

理解STL容器的底层实现至关重要：

• ✅ vector：动态数组，随机访问快，中间操作慢

• ✅ list：双向链表，插入删除快，随机访问慢

• ✅ map/set：红黑树，有序，查找插入删除都是O(log n)

• ✅ 选择策略：根据具体需求选择最合适的容器

• ✅ 性能特征：不同操作的时间复杂度差异很大

2.迭代器：种类及失效问题

1. 迭代器基本概念

什么是迭代器？

迭代器是STL中用于遍历容器元素的对象，它提供了统一的访问接口，使得算法可以独立于容器类型工作。

#include <vector>
#include <list>
#include <iostream>

void iterator_basics() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::list<int> lst = {1, 2, 3, 4, 5};
    
    // 使用迭代器遍历vector
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 使用迭代器遍历list（接口相同！）
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 这就是STL的设计哲学：算法与容器分离
}

2. 迭代器的五种类型

1. 输入迭代器（Input Iterator）

特性：只读，单向，只能递增

// 典型应用：从输入流读取数据
#include <iterator>
#include <iostream>

void input_iterator_example() {
    std::istream_iterator<int> input_it(std::cin);
    std::istream_iterator<int> end;
    
    while (input_it != end) {
        std::cout << "Read: " << *input_it << std::endl;
        ++input_it; // 只能向前，不能回头
    }
}

2. 输出迭代器（Output Iterator）

特性：只写，单向，只能递增

// 典型应用：向输出流写入数据
#include <iterator>
#include <vector>

void output_iterator_example() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::ostream_iterator<int> output_it(std::cout, " ");
    
    for (int num : vec) {
        *output_it = num; // 只能写入，不能读取
        ++output_it;
    }
}

3. 前向迭代器（Forward Iterator）

特性：可读写，单向，可多次遍历

// 典型应用：单链表（std::forward_list）
#include <forward_list>

void forward_iterator_example() {
    std::forward_list<int> flist = {1, 2, 3, 4, 5};
    
    auto it = flist.begin();
    std::cout << *it << std::endl; // 读取
    *it = 100;                     // 写入
    ++it;                          // 只能向前
    
    // 可以多次遍历
    for (auto it = flist.begin(); it != flist.end(); ++it) {
        std::cout << *it << " ";
    }
}

4. 双向迭代器（Bidirectional Iterator）

特性：可读写，可向前向后移动

// 典型应用：双向链表（std::list）
#include <list>

void bidirectional_iterator_example() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    
    auto it = lst.begin();
    ++it; // 向前
    --it; // 向后
    
    // 反向遍历
    for (auto rit = lst.rbegin(); rit != lst.rend(); ++rit) {
        std::cout << *rit << " ";
    }
}

5. 随机访问迭代器（Random Access Iterator）

特性：可读写，支持随机访问，算术运算

// 典型应用：数组、vector、deque
#include <vector>

void random_access_iterator_example() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    auto it = vec.begin();
    it += 3;                    // 随机访问
    std::cout << it[1] << endl; // 支持下标操作
    std::cout << it - vec.begin() << endl; // 计算距离
    
    // 支持比较操作
    if (it > vec.begin()) {
        std::cout << "it is after begin" << std::endl;
    }
}

迭代器类别总结表

3. 迭代器失效问题

什么是迭代器失效？

当容器结构发生变化（插入、删除元素）时，指向容器元素的迭代器可能变得无效，继续使用会导致未定义行为。

1. vector的迭代器失效

void vector_iterator_invalidation() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = vec.begin() + 2; // 指向3
    
    // 情况1：插入元素可能导致重新分配
    for (int i = 0; i < 100; ++i) {
        vec.push_back(i); // 可能触发扩容
        // 此时it可能失效！
    }
    // std::cout << *it << std::endl; // 危险！未定义行为
    
    // 情况2：删除元素
    it = vec.begin() + 2; // 重新获取
    vec.erase(vec.begin() + 1); // 删除第2个元素
    // it现在指向什么？可能失效！
    
    // 正确做法：使用erase的返回值
    it = vec.erase(it); // it现在指向被删除元素的下一个元素
    std::cout << *it << std::endl; // 安全
}

1. vector的迭代器失效

void vector_iterator_invalidation() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = vec.begin() + 2; // 指向3
    
    // 情况1：插入元素可能导致重新分配
    for (int i = 0; i < 100; ++i) {
        vec.push_back(i); // 可能触发扩容
        // 此时it可能失效！
    }
    // std::cout << *it << std::endl; // 危险！未定义行为
    
    // 情况2：删除元素
    it = vec.begin() + 2; // 重新获取
    vec.erase(vec.begin() + 1); // 删除第2个元素
    // it现在指向什么？可能失效！
    
    // 正确做法：使用erase的返回值
    it = vec.erase(it); // it现在指向被删除元素的下一个元素
    std::cout << *it << std::endl; // 安全
}

2. list的迭代器失效

void list_iterator_invalidation() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    auto it = ++lst.begin(); // 指向2
    
    // list的插入不会使其他迭代器失效
    lst.insert(lst.begin(), 0); // 插入开头
    std::cout << *it << std::endl; // 安全：仍然指向2
    
    // 但删除会使被删除元素的迭代器失效
    auto to_erase = it;
    ++it; // 先移动下一个迭代器
    lst.erase(to_erase); // 删除元素2
    std::cout << *it << std::endl; // 安全：指向3
}

3. map/set的迭代器失效

void map_iterator_invalidation() {
    std::map<int, std::string> map = {{1, "a"}, {2, "b"}, {3, "c"}};
    auto it = map.find(2);
    
    // 插入不会使迭代器失效
    map.insert({4, "d"});
    std::cout << it->second << std::endl; // 安全：仍然指向"b"
    
    // 删除会使被删除元素的迭代器失效
    auto to_erase = it;
    ++it; // 先移动到下一个元素
    map.erase(to_erase); // 删除键为2的元素
    std::cout << it->second << std::endl; // 安全：指向"c"
}

4. deque的迭代器失效

void deque_iterator_invalidation() {
    std::deque<int> deq = {1, 2, 3, 4, 5};
    auto it = deq.begin() + 2; // 指向3
    
    // 在头尾插入通常不会使迭代器失效
    deq.push_front(0);
    deq.push_back(6);
    std::cout << *it << std::endl; // 通常安全：仍然指向3
    
    // 在中间插入可能使所有迭代器失效
    deq.insert(deq.begin() + 2, 100);
    // std::cout << *it << std::endl; // 危险！可能失效
}

4. 迭代器失效规则总结

各容器迭代器失效规则

安全使用准则

void safe_iterator_usage() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // 错误示范：在遍历时修改容器
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        if (*it == 3) {
            vec.erase(it); // 错误！it失效后继续使用
            // 应该：it = vec.erase(it); 然后 continue;
        }
    }
    
    // 正确做法1：使用返回值更新迭代器
    for (auto it = vec.begin(); it != vec.end(); ) {
        if (*it == 3) {
            it = vec.erase(it); // erase返回下一个有效迭代器
        } else {
            ++it;
        }
    }
    
    // 正确做法2：使用算法remove-erase惯用法
    vec.erase(std::remove(vec.begin(), vec.end(), 3), vec.end());
}

5. 特殊迭代器

反向迭代器（Reverse Iterator）

void reverse_iterator_example() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // 反向遍历
    for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        std::cout << *rit << " "; // 输出: 5 4 3 2 1
    }
    
    // 反向迭代器与普通迭代器的转换
    auto rit = vec.rbegin();
    auto it = rit.base(); // 获取对应的正向迭代器
    std::cout << *it << std::endl; // 输出rend位置的元素
}

插入迭代器（Insert Iterator）

void insert_iterator_example() {
    std::vector<int> vec = {1, 2, 3};
    std::list<int> lst = {4, 5, 6};
    
    // 使用插入迭代器拷贝元素
    std::back_insert_iterator<std::vector<int>> back_inserter(vec);
    std::copy(lst.begin(), lst.end(), back_inserter);
    // vec现在: {1, 2, 3, 4, 5, 6}
    
    // 简便写法
    std::copy(lst.begin(), lst.end(), std::back_inserter(vec));
}

6. 常见问题

Q1: 什么是迭代器失效？举例说明

答：迭代器失效是指当容器结构发生变化时，之前获取的迭代器不再指向有效的元素。例如在vector中插入元素可能导致扩容，所有迭代器都失效。

Q2: 如何安全地在遍历时删除元素？

答：

• vector/deque：使用 it = vec.erase(it) 并检查返回值

• list/map/set：先保存下一个迭代器 next = it++; 再删除

• 或者使用 remove-erase惯用法

Q3: 不同容器的迭代器类别是什么？

答：

• vector, deque, array：随机访问迭代器

• list, map, set：双向迭代器

• forward_list：前向迭代器

• unordered容器：前向迭代器

Q4: 什么是迭代器 trait？

答：迭代器trait是用于在编译期获取迭代器特性的模板类，可以获取迭代器的类别、值类型、差异类型等信息。

Q5: 如何实现自定义迭代器？

答：需要定义相应的iterator_category、value_type、difference_type、pointer、reference类型，并实现相应的操作符重载。

7. 最佳实践

使用算法避免手动迭代

void use_algorithms() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 3, 2, 1};
    
    // 而不是手动遍历删除
    vec.erase(std::remove(vec.begin(), vec.end(), 3), vec.end());
    
    // 使用算法处理
    std::sort(vec.begin(), vec.end());
    auto last = std::unique(vec.begin(), vec.end());
    vec.erase(last, vec.end());
}

谨慎保存迭代器

void be_careful_with_iterators() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // 危险：保存迭代器
    auto saved_it = vec.begin() + 2;
    
    // 中间操作可能使迭代器失效
    for (int i = 0; i < 100; ++i) {
        vec.push_back(i);
    }
    
    // std::cout << *saved_it << std::endl; // 未定义行为！
    
    // 解决方案：保存索引而不是迭代器
    size_t index = 2;
    // ... 各种操作
    std::cout << vec[index] << std::endl; // 安全
}

总结

理解迭代器及其失效机制至关重要：

• ✅ 迭代器类别：了解不同迭代器的能力和限制

• ✅ 失效规则：掌握各容器在修改操作后的迭代器状态

• ✅ 安全实践：使用正确的方法在遍历时修改容器

• ✅ 算法优先：尽量使用STL算法而不是手动迭代

3.算法：find,sort,copy等

//TODO