第30章综合实战

课程目录第30章综合实战

第30章综合实战：构建一个迷你STL容器（如Vector）与算法库（如Sort）

终于到了最后一章。说实话，我写到这里还挺感慨的。前面29章我们聊了模板的方方面面——从最基础的函数模板，到SFINAE、变参模板、类型萃取，再到策略模式、CRTP、编译期计算……现在，是时候把这些知识串起来了。

这一章的目标很明确：手写一个迷你STL。不是玩具，而是真正能用的、有迭代器支持的、能配合算法工作的容器和算法库。我们会实现一个简化版的 Vector，以及一个泛型 Sort 算法。在这个过程中，你会看到模板元编程、类型萃取、迭代器萃取、完美转发、异常安全等知识点如何在实际项目中落地。

核心目标：构建一个包含 Vector<T> 容器和 sort() 算法的迷你STL，支持迭代器、类型萃取、异常安全、移动语义。

30.1 整体架构设计

我们先画一张图，看看这个迷你STL的模块划分。我个人习惯在动手写代码之前，先把结构理清楚。你想想看，如果连模块边界都没定好，后面很容易写出耦合严重的代码。

从图上可以看得很清楚：容器提供数据存储和迭代器，算法通过迭代器操作数据，类型萃取在编译期提供决策支持。这三层各司其职，互不侵入。嗯，这里要注意——迭代器是容器和算法之间的桥梁，这个设计理念是STL的精髓，千万别搞成容器直接暴露内部指针。

30.2 实现迷你 Vector

我们先从容器开始。实现一个 Vector，说白了就是管理一块连续内存的动态数组。我在项目中遇到过很多手写容器的场景，比如嵌入式环境下的内存池、游戏引擎中的对象池，核心逻辑都和 Vector 类似。

30.2.1 内存管理与RAII

先看骨架代码。我习惯把内存分配和对象构造分开处理——这是异常安全的关键。

template <typename T>
class Vector {
public:
    // 类型别名，供迭代器萃取使用
    using value_type      = T;
    using iterator        = T*;
    using const_iterator  = const T*;
    using reference       = T&;
    using const_reference = const T&;
    using size_type       = std::size_t;

private:
    T*      data_;      // 指向堆内存
    size_type size_;    // 已构造对象数量
    size_type cap_;     // 总容量

    // 内存分配器（简化版，直接使用 ::operator new）
    static T* allocate(size_type n) {
        return static_cast<T*>(::operator new(n * sizeof(T)));
    }

    static void deallocate(T* p) {
        ::operator delete(p);
    }

public:
    // 构造与析构
    Vector() : data_(nullptr), size_(0), cap_(0) {}

    explicit Vector(size_type n) : data_(allocate(n)), size_(n), cap_(n) {
        // 用 placement new 构造 n 个默认对象
        for (size_type i = 0; i < n; ++i) {
            new (&data_[i]) T();
        }
    }

    ~Vector() {
        clear();
        deallocate(data_);
    }

    // 禁止拷贝（简化版，实际应实现深拷贝）
    Vector(const Vector&) = delete;
    Vector& operator=(const Vector&) = delete;

    // 移动语义
    Vector(Vector&& other) noexcept
        : data_(other.data_), size_(other.size_), cap_(other.cap_) {
        other.data_ = nullptr;
        other.size_ = 0;
        other.cap_  = 0;
    }

    // 基本操作
    void push_back(const T& value) {
        if (size_ == cap_) {
            grow();
        }
        new (&data_[size_]) T(value);  // placement new
        ++size_;
    }

    void push_back(T&& value) {
        if (size_ == cap_) {
            grow();
        }
        new (&data_[size_]) T(std::move(value));
        ++size_;
    }

    void pop_back() {
        if (size_ > 0) {
            data_[--size_].~T();  // 显式调用析构
        }
    }

    void clear() {
        for (size_type i = 0; i < size_; ++i) {
            data_[i].~T();
        }
        size_ = 0;
    }

    // 迭代器
    iterator begin() { return data_; }
    iterator end()   { return data_ + size_; }
    const_iterator begin() const { return data_; }
    const_iterator end()   const { return data_ + size_; }

    // 容量与大小
    size_type size()     const { return size_; }
    size_type capacity() const { return cap_; }
    bool empty()         const { return size_ == 0; }

    // 元素访问
    reference operator[](size_type i) { return data_[i]; }
    const_reference operator[](size_type i) const { return data_[i]; }

private:
    void grow() {
        size_type new_cap = (cap_ == 0) ? 1 : cap_ * 2;
        T* new_data = allocate(new_cap);

        // 移动已有元素（异常安全：如果移动抛出异常，旧数据还在）
        for (size_type i = 0; i < size_; ++i) {
            new (&new_data[i]) T(std::move(data_[i]));
            data_[i].~T();
        }

        deallocate(data_);
        data_ = new_data;
        cap_  = new_cap;
    }
};

避坑指南：我曾经在 grow() 里直接用了 memcpy 来搬数据，结果遇到一个自定义类型，内部有 std::string 成员，直接内存拷贝导致 double free。后来我改用 placement new + move 构造，才彻底解决。记住：只有 trivially copyable 的类型才能用 memcpy。

30.2.2 迭代器萃取支持

为了让我们的 Vector 能和标准算法配合，需要提供迭代器萃取信息。其实 T* 天然就是随机访问迭代器，但标准库需要知道迭代器的类别、值类型等属性。这就是 std::iterator_traits 的作用。

// 对于原生指针，标准库已经提供了特化版本
// 但我们也可以显式提供，确保兼容性
namespace std {
    template <typename T>
    struct iterator_traits<T*> {
        using iterator_category = random_access_iterator_tag;
        using value_type        = T;
        using difference_type   = ptrdiff_t;
        using pointer           = T*;
        using reference         = T&;
    };
}

有了这个，我们的 Vector::iterator 就能被标准算法正确识别。你想想看，如果没有这层萃取，算法怎么知道迭代器是随机访问的还是单向的？

30.3 实现泛型 Sort 算法

接下来实现排序算法。我选择快速排序作为基础，并加入小规模数据时切换到插入排序的优化。这个策略在工业界很常见——std::sort 内部就是这么干的。

30.3.1 算法骨架

namespace mystl {

// 插入排序：小规模数据时使用
template <typename RandomIt>
void insertion_sort(RandomIt first, RandomIt last) {
    using value_type = typename std::iterator_traits<RandomIt>::value_type;

    for (auto it = first + 1; it != last; ++it) {
        value_type key = std::move(*it);
        auto j = it - 1;

        while (j >= first && *j > key) {
            *(j + 1) = std::move(*j);
            --j;
        }
        *(j + 1) = std::move(key);
    }
}

// 快速排序的分区函数
template <typename RandomIt>
RandomIt partition(RandomIt first, RandomIt last) {
    using value_type = typename std::iterator_traits<RandomIt>::value_type;

    // 选择最后一个元素作为 pivot
    auto pivot = *(last - 1);
    auto i = first - 1;

    for (auto j = first; j != last - 1; ++j) {
        if (*j <= pivot) {
            ++i;
            std::iter_swap(i, j);
        }
    }
    std::iter_swap(i + 1, last - 1);
    return i + 1;
}

// 主排序函数
template <typename RandomIt>
void sort(RandomIt first, RandomIt last) {
    constexpr size_t threshold = 16;  // 小规模阈值

    while (last - first > 1) {
        if (last - first <= threshold) {
            insertion_sort(first, last);
            return;
        }

        auto pivot = partition(first, last);

        // 递归处理较短的区间，尾递归优化较长的区间
        if (pivot - first < last - pivot) {
            sort(first, pivot);
            first = pivot + 1;
        } else {
            sort(pivot + 1, last);
            last = pivot;
        }
    }
}

// 带比较器的版本
template <typename RandomIt, typename Compare>
void sort(RandomIt first, RandomIt last, Compare comp) {
    // 实现类似，只是比较时用 comp(*j, pivot) 代替 *j <= pivot
    // 篇幅原因，这里省略
}

} // namespace mystl

关键设计点：

迭代器萃取：通过 std::iterator_traits 获取值类型，不依赖具体容器
移动语义：插入排序中使用 std::move 避免不必要的拷贝
尾递归优化：手动将递归转换为循环，避免栈溢出
阈值切换：小规模数据用插入排序，常数更小

30.4 整合测试

好了，现在把容器和算法拼起来跑一下。我建议你亲手敲一遍这段代码，感受一下模板元编程在实际项目中的威力。

#include <iostream>
#include <string>

// 假设上面的 Vector 和 mystl::sort 已经定义

struct Person {
    std::string name;
    int age;

    // 为了测试移动语义
    Person(const std::string& n, int a) : name(n), age(a) {
        std::cout << "构造: " << name << "\n";
    }
    Person(const Person& other) : name(other.name), age(other.age) {
        std::cout << "拷贝: " << name << "\n";
    }
    Person(Person&& other) noexcept
        : name(std::move(other.name)), age(other.age) {
        std::cout << "移动: " << name << "\n";
    }
    ~Person() {
        std::cout << "析构: " << name << "\n";
    }

    bool operator<(const Person& rhs) const {
        return age < rhs.age;
    }
};

int main() {
    mystl::Vector<Person> people;
    people.push_back(Person("Alice", 30));
    people.push_back(Person("Bob",   25));
    people.push_back(Person("Charlie", 35));

    std::cout << "\n排序前:\n";
    for (const auto& p : people) {
        std::cout << p.name << " (" << p.age << ")\n";
    }

    mystl::sort(people.begin(), people.end());

    std::cout << "\n排序后:\n";
    for (const auto& p : people) {
        std::cout << p.name << " (" << p.age << ")\n";
    }

    return 0;
}

运行结果应该按年龄从小到大排序。注意观察构造、拷贝、移动、析构的调用顺序——你会看到移动语义大大减少了不必要的拷贝。这就是模板元编程 + 移动语义带来的性能提升。

警告：上面的 Vector 为了演示做了大量简化。实际生产环境中，你还需要考虑：

异常安全（强保证 vs 基本保证）
分配器支持（可替换的内存分配策略）
emplace_back 完美转发
shrink_to_fit 缩容
const 迭代器与反向迭代器

不过作为教学示例，它已经足够展示模板泛型编程的核心思想了。

30.5 总结与思考

这一章我们亲手构建了一个迷你STL。从 Vector 的内存管理、迭代器设计，到 sort 算法的泛型实现，再到类型萃取的配合使用——你会发现，前面29章学到的每一个知识点，都在这里找到了落脚点。

我个人觉得，模板元编程最迷人的地方就在这里：你在编译期做的每一分努力，都会在运行期得到回报。类型萃取让算法自动选择最优路径，移动语义消除了不必要的拷贝，迭代器解耦了容器和算法……这些设计思想，放到今天任何一个C++项目里都不过时。

如果你有兴趣，可以继续扩展这个迷你STL：加入 List 容器、find 算法、for_each 算法，甚至实现一个简单的 tuple。每一次扩展，都会让你对模板的理解更深一层。

好了，课程到这里就结束了。感谢你一路跟下来。希望这些内容能帮你在C++模板的世界里走得更远。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录