Day 14：vector 深入、典型算法与关联容器

本节代码位置：

2-代码/day14-vector/73-vector使用示例2.cpp
2-代码/day14-vector/74-典型算法示例.cpp
2-代码/day14-vector/75-array使用示例.cpp
2-代码/day14-vector/76-list使用示例.cpp
2-代码/day14-vector/77-priority_queue示例.cpp
2-代码/day14-vector/78-map使用示例.cpp
2-代码/day14-vector/79-set使用示例.cpp
2-代码/day14-vector/80-unordered_map使用示例.cpp

1、vector 深入使用

vector 保存对象时，可以使用 push_back 放入已有对象，也可以使用 emplace_back 直接在容器尾部构造对象。

vector<Demo> a;
a.push_back(Demo(1, 1)); // 先构造临时对象
 a.emplace_back(2, 2);  // 直接构造 Demo(2, 2)

删除元素时，erase 会使被删位置及其后的迭代器失效，并返回下一个有效迭代器：

for (auto it = a.begin(); it != a.end(); )
{
    if (*it % 2 != 0)
        it = a.erase(it);
    else
        ++it;
}

2、reserve 与 resize

vector<int> a;
a.reserve(10); // size 为 0，capacity 至少为 10
// a[0] = 100; // 错误，元素尚不存在

a.resize(10);  // size 变为 10，可以使用 a[0]

reserve(n)：只预留容量，不改变元素个数。
resize(n)：改变元素个数，新元素会默认初始化。
预先知道数量时，reserve 可以减少扩容和元素搬迁。

3、典型算法

STL 算法通常操作迭代器范围 [first, last)。

auto it = find(v.begin(), v.end(), 100);

auto it2 = find_if(v.begin(), v.end(), [](int x)
{
    return x > 0;
});

for_each(v.begin(), v.end(), [](int &x)
{
    ++x;
});

find：查找等于指定值的第一个元素。
find_if：查找第一个满足条件的元素。
for_each：依次处理范围中的元素；参数是引用时可以修改原容器。

常用算法还包括：

count(v.begin(), v.end(), 3);
count_if(v.begin(), v.end(), [](int x) { return x > 0; });
reverse(v.begin(), v.end());
sort(v.begin(), v.end());
sort(v.begin(), v.end(), greater<int>());
auto maxIt = max_element(v.begin(), v.end());

sort 要求随机访问迭代器，所以 vector、array 可用，list 不能使用 std::sort。

4、remove-erase 与 unique-erase

remove 和 unique 不会真正缩短容器，只会返回新的逻辑结尾；必须再调用 erase。

vector<int> v{1, 3, 2, 3, 4, 3, 5};
auto newEnd = remove(v.begin(), v.end(), 3);
v.erase(newEnd, v.end());

sort(v.begin(), v.end());
newEnd = unique(v.begin(), v.end());
v.erase(newEnd, v.end());

remove：移走等于指定值的元素。
unique：移走连续重复元素，因此全局去重前通常先排序。

5、array 与 list

std::array<T, N> 长度固定，支持下标、迭代器和 fill，但没有插入、删除、扩容接口。

array<int, 5> a;
a[0] = 1;
a.fill(100);

std::list 是双向链表，擅长已知位置的插入、删除和节点转移，但不支持随机访问。

l1.merge(l2);                  // 合并两个有序链表
l1.splice(l1.begin(), l2);     // 转移 l2 的节点

merge 前两个链表必须已经按相同规则有序；splice 主要移动节点，不是逐个复制元素。

6、priority_queue

priority_queue 默认是大顶堆，top() 总能得到当前最大元素：

priority_queue<int> maxQueue;

priority_queue<int, vector<int>, greater<int>> minQueue;

传入 greater<int> 后变为小顶堆。优先队列不能随机访问；要按优先级依次读取元素，就循环 top() 和 pop()。

7、map、set 与 unordered_map

map 保存有序且键唯一的键值对：

map<string, string> m;
m.insert({"san", "三"});
m["si"] = "四";

auto it = m.find("san");
if (it != m.end())
{
    cout << it->first << ": " << it->second << endl;
}

it->first 是键，不能修改。
it->second 是值，可以修改。
operator[] 在键不存在时会插入默认值；只查找时优先使用 find。

set 只保存有序且唯一的元素，元素不能通过迭代器修改，否则会破坏排序规则。

unordered_map 同样键唯一，但基于哈希表，不保证遍历顺序。

map：有序，查找、插入、删除通常是 O(log n)。
unordered_map：无序，平均查找、插入、删除通常是 O(1)。

8、Day14 总结

1. emplace_back 直接构造元素；erase 返回下一个有效迭代器。
2. reserve 改容量不改元素个数；resize 会改变元素个数。
3. STL 算法通过迭代器操作范围，常见算法有 find、for_each、sort、remove、unique 等。
4. remove 和 unique 后要配合 erase，才能真正删除元素。
5. array 长度固定；list 是双向链表，不能随机访问。
6. priority_queue 默认大顶堆，使用 greater 可得到小顶堆。
7. map 有序，unordered_map 无序且平均查找更快；二者的键都唯一。
8. set 保存有序且唯一的元素，元素不能直接修改。

一句话记忆：容器决定数据如何存，迭代器定义操作范围，算法负责处理范围中的数据。