Day 13：类模板与 vector

本节代码位置：

2-代码/day13-类模板/71-类模板使用示例.cpp
2-代码/day13-类模板/72-vector使用示例.cpp
2-代码/day13-类模板/list.hpp
2-代码/day13-类模板/stack.hpp
2-代码/day13-类模板/myalgo.hpp

1、类模板

类模板让一个类可以处理不同的数据类型。课程中的链表和栈不再只能保存某一种元素，而是通过类型参数决定元素类型。

template <typename Type>
class List
{
    // 节点数据、push_back、迭代器等都使用 Type
};

List<int> l1;
List<string> l2;

List<int> 和 List<string> 是同一个模板生成的两个具体类型，它们的操作逻辑相同，保存的数据类型不同。

2、模板栈与别名模板

MyStack 在内部复用了 List<Type>：

template <typename Type>
class MyStack
{
public:
    void push(Type x);
    void pop();
    Type top() const;

private:
    List<Type> _list;
    int _capacity;
};

栈的容量已满时会抛出 std::overflow_error。别名模板可以给类型换一个更贴近用途的名字：

template <typename Type>
using LinkStack = MyStack<Type>;

3、模板实现为什么通常放在头文件

普通函数先编译成固定目标代码；模板则要等到使用 List<int>、List<string> 时，编译器才根据实际类型生成代码。

模板的声明和实现通常都放在 .hpp 头文件中。
如果把模板实现单独放进 .cpp，其他源文件实例化模板时看不到实现，通常会产生链接错误。

4、迭代器与通用算法

myfind 不绑定 List、vector 或 string。它只要求传入的迭代器支持比较、递增和解引用。

template <typename Iterator, typename T>
Iterator myfind(Iterator first, Iterator last, T x)
{
    for (; first != last; ++first)
    {
        if (*first == x)
            return first;
    }
    return last;
}

auto it = myfind(l1.begin(), l1.end(), 300);
if (it != l1.end())
{
    *it = 999;
}

begin() 指向第一个元素。
end() 指向尾后位置，不是最后一个元素。
查找成功返回目标元素的位置；失败返回 end()。
迭代器解引用得到元素本身，因此可以读取或修改元素。

5、vector 动态数组

std::vector 是标准库的动态数组，元素连续存储，支持下标访问。

vector<int> a;                       // 空 vector
vector<int> a2 = {1, 2, 3, 4, 5};     // 列表初始化
vector<int> a3(a2.begin(), a2.end()); // 迭代器区间构造

int arr[5] = {1, 2, 3, 4, 5};
vector<int> a4(arr, arr + 3);         // 原始数组区间构造

6、圆括号与大括号

vector<int> a6(10); // 创建 10 个默认初始化元素
vector<int> a7{10}; // 创建 1 个元素，值为 10

() 常用于“数量”或构造参数。
{} 优先表示列表初始化。
vector<int> v(10) 与 vector<int> v{10} 的含义完全不同。

7、vector 常用操作

a.push_back(1); // 尾部添加
 a.pop_back();  // 删除最后一个元素
a[0] = 100;     // 下标修改

auto it = find(a.begin(), a.end(), 6);
auto it2 = find_if(a.begin(), a.end(),
                   [](int x) { return x < 100; });

find 按值查找；find_if 根据谓词查找，示例中的 lambda 表达式表示“查找小于 100 的元素”。

8、size 与 capacity

size()：当前实际元素个数。
capacity()：已经分配、最多可容纳的元素数量。

push_back() 发现容量不足时，vector 会重新分配一段更大的连续空间，再迁移旧元素。因此扩容后，之前保存的迭代器、指针和引用可能失效。

9、Day13 总结

1. 类模板让容器和数据结构支持多种元素类型。
2. 使用时写成 类名<实际类型>，例如 List<int>。
3. 模板实现通常放在头文件。
4. 迭代器把容器和算法连接起来。
5. vector 是连续存储的动态数组，支持随机访问。
6. vector 的 () 与 {} 初始化含义不同。
7. vector 扩容可能使旧迭代器、指针和引用失效。

一句话记忆：模板让类和算法按类型复用；迭代器让算法不绑定具体容器；vector 是可自动扩容的连续动态数组。