MyTinySTL源码探秘：从vector和list看STL容器的生命轨迹

记得第一次翻开STL源码时，那些密密麻麻的模板参数和指针操作就像一堵高墙。直到有一天，我把vector想象成一个不断扩容的智能数组，把list看作一群手拉手的小人，一切突然变得生动起来。今天，我们就用这种"人性化"的视角，走进MyTinySTL中两个最经典的容器实现。

1. 容器的诞生：构造函数里的设计哲学

所有STL容器的故事都从构造函数开始。在MyTinySTL中，vector和list的"出生方式"就暗示了它们截然不同的性格。

vector的默认构造 就像规划一块空地：

explicit vector(size_type n) {
    begin_ = alloc_.allocate(n);
    end_ = begin_ + n;
    cap_ = end_;
}

这里 allocate 相当于申请一块连续内存，三个指针 begin_ 、 end_ 和 cap_ 分别标记了当前元素的起止位置和容量边界。这种"一步到位"的内存策略，体现了vector追求高效随机访问的特点。

相比之下， list的构造 则显得更加"佛系"：

list() { 
    node_ = get_node();
    node_->next = node_;
    node_->prev = node_;
}

它只创建一个孤零零的哨兵节点（node_），这个节点前后都指向自己，形成一个闭环。这种"按需生长"的特性，正是链表结构的精髓所在。

设计启示：vector像精心规划的现代城市，list则像自然生长的有机体

2. 成长的故事：插入操作背后的内存博弈

当容器开始"成长"，vector和list展现出完全不同的行为模式，这直接反映了它们的内存管理策略。

2.1 vector的扩容机制

vector的 push_back 就像在拥挤的地铁里安排新乘客：

void push_back(const T& value) {
    if (end_ != cap_) {
        // 还有空间，直接安置
        alloc_.construct(end_, value);
        ++end_;
    } else {
        // 需要扩容
        reallocate_insert(end_, value);
    }
}

关键的 reallocate_insert 过程可以拆解为：

1. 计算新容量（通常是当前2倍）
2. 申请新内存
3. 搬运旧数据（"搬家"成本很高！）
4. 释放原内存

用表格对比不同场景下的时间复杂度：

操作场景	时间复杂度	内存影响
尾部插入(有空间)	O(1)	无变化
尾部插入(需扩容)	O(n)	可能翻倍
中间插入	O(n)	可能触发扩容

2.2 list的优雅连接

list的插入则像在朋友聚会中介绍新朋友：

iterator insert(iterator pos, const T& value) {
    Node* new_node = create_node(value);
    new_node->next = pos.node;
    new_node->prev = pos.node->prev;
    pos.node->prev->next = new_node;
    pos.node->prev = new_node;
    return iterator(new_node);
}

四个指针调整看似复杂，实则只是让新节点与前后邻居"握手"的过程。无论插入位置在哪里，时间复杂度都是稳定的O(1)。

3. 危机处理：删除元素时的内存考量

容器也需要"减肥"，但vector和list的"减肥方式"大相径庭。

vector的erase操作 就像早高峰地铁有人下车：

iterator erase(iterator pos) {
    if (pos + 1 != end_) {
        // 需要移动后方元素填补空缺
        mystl::move(pos + 1, end_, pos);
    }
    --end_;
    alloc_.destroy(end_);
    return pos;
}

这个 move 操作意味着每次删除非尾部元素都会引发数据搬迁，性能消耗不容忽视。

list的remove操作 则像从聊天群组中退出：

void remove(const T& value) {
    for (auto it = begin(); it != end(); ) {
        if (*it == value) {
            it = erase(it);  // 只需调整相邻节点的指针
        } else {
            ++it;
        }
    }
}

链表节点的删除只需断开原有连接，不会波及其他节点。这种特性使list特别适合频繁增删的场景。

4. 社交网络：迭代器如何连接容器与算法

STL的精妙之处在于容器与算法的解耦，而实现这一点的关键就是迭代器。vector和list的迭代器虽然用法相似，但内部实现却天差地别。

vector迭代器 本质就是指针：

typedef T* iterator;  // 随机访问迭代器

它支持 + 、 - 等算术运算，因为底层内存是连续的。

list迭代器 则是一个智能代理：

struct iterator {
    Node* node;
    
    iterator& operator++() { 
        node = node->next;
        return *this;
    }
    // 其他操作符重载...
};

每次 ++ 操作都相当于沿着链表"走一步"，这种单向移动的特性决定了它是双向迭代器。

来看一个经典算法 find 在不同容器上的表现：

auto find_v = std::find(vec.begin(), vec.end(), target);  // 对vector是内存扫描
auto find_l = std::find(lst.begin(), lst.end(), target);  // 对list是链表遍历

虽然调用方式完全相同，但底层的内存访问模式却完全不同。这种抽象的一致性，正是STL设计的精妙之处。

5. 性能对决：何时选择vector或list

经过前面的探索，我们可以总结出这两个容器的典型应用场景：

vector更擅长：

• 需要频繁随机访问（O(1)时间复杂度）
• 数据总量可预估，避免频繁扩容
• 内存使用效率要求高（无额外指针开销）

list更擅长：

• 频繁在任意位置插入删除（O(1)时间复杂度）
• 不需要随机访问（只需顺序遍历）
• 内存碎片化不是主要问题

实际项目中，vector通常是默认选择，除非有明确的频繁中间插入需求。现代CPU的缓存机制也让连续内存的vector在遍历时比list快得多——这可能是初学者的常见认知误区。

在MyTinySTL的测试案例中，可以明显看到两者的差异：

// 测试10000次插入
void test_vector() {
    mystl::vector<int> v;
    for (int i = 0; i < 10000; ++i) {
        v.insert(v.begin(), i);  // 每次都在头部插入
    }
}

void test_list() {
    mystl::list<int> l;
    for (int i = 0; i < 10000; ++i) {
        l.insert(l.begin(), i);  // 链表头部插入效率稳定
    }
}

这个例子中，list版本会比vector快几个数量级，因为vector每次插入都要移动所有现有元素。