vector模拟实现

最坚实的数据结构，恰恰长着最简单的模样——用指针织一片连续的内存，便装下了万物的来去

1. 什么是vector

想必大家都学过顺序表这个数据结构。顺序表通过开辟一块连续的内存空间来存储数据，在C语言中，如果要自己实现一个顺序表，需要先定义一个动态数组，然后还要实现增删改查相关的操作函数。

但是C语言实现顺序表有一个很大的局限：如果程序涉及到多种数据类型的顺序表，就得为每种数据类型写一份重复的代码，导致代码冗余且难以维护。C++的vector正是为了解决这个问题而生——它是一个模板类，内部维护的是一个动态数组，增删改查等操作都封装好了，并且会自动扩容。编译器会根据创建的对象类型，实例化出对应数据类型的vector类，我们只需要放心使用即可。

2. vector的核心设计

2.1 成员变量的设计

不同于string用_str、_size、_capacity三个独立变量，vector在成员变量的设计上采用了三个迭代器（指针）来维护数组：

template<class T>
class vector
{
private:
    iterator _start = nullptr;          // 指向数组起始位置
    iterator _finish = nullptr;         // 指向有效元素末尾的下一个位置
    iterator _endofstorage = nullptr;   // 指向已分配空间的末尾
};

这种设计的好处很明显：

• _finish - _start 直接得到元素个数（size）
• _endofstorage - _start 直接得到当前容量（capacity）

用指针的差值来表示大小和容量，省去了单独维护size和capacity的烦恼，这是仿照SGI版本STL源码的设计思路。

2.2 迭代器的实现

在vector中，迭代器就是原始指针的别名：

typedef T* iterator;
typedef const T* const_iterator;

因为vector的底层是一段连续的内存空间，指针天然的"++"就能移动到下一个元素，所以在vector中迭代器的实现就这么简洁直接。

四个迭代器函数分别返回_start和_finish，并通过const版本来支持const对象的只读访问。

2.3 基本接口：size、capacity、empty、clear、operator[]

size_t size() const { return _finish - _start; }
size_t capacity() const { return _endofstorage - _start; }
bool empty() const { return _start == _finish; }
void clear() { _finish = _start; }

T& operator[](size_t n) {
    assert(n < size());
    return _start[n];
}
const T& operator[](size_t n) const {
    assert(n < size());
    return _start[n];
}

• size() 和 capacity() 利用指针差值直接计算，时间复杂度O(1)。
• empty() 判断起始和结束指针是否重合。
• clear() 只需将_finish指向_start，逻辑上清空所有元素（内存并未释放）。
• operator[] 提供下标访问，内部带断言检查越界。

3. 构造函数与析构函数

3.1 迭代器区间构造与SFINAE技巧

向量不仅可以通过无参构造和初始化列表构造，还可以通过迭代器区间构造。这里包含了一个很有意思的细节：

template<class Inputiterator, class = typename std::enable_if<!std::is_integral<Inputiterator>::value>::type>
vector(Inputiterator first, Inputiterator last)
{
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}

为什么要用enable_if加上is_integral呢？

这是因为vector还有两个构造函数的重载：

vector(size_t n, T val = T());  // 用n个val初始化
vector(int n, T val = T());     // 为了兼容int类型的n

如果不加限制，当调用vector<int> v(5, 1)时，编译器会纠结：(5, 1)到底该匹配"迭代器区间构造"（把5和1当作两个迭代器），还是匹配"n个val构造"（5是元素个数，1是元素值）？

通过enable_if检查Inputiterator是否为整型，如果是整型就排除这个重载，确保编译器能够正确选择"n个val构造"。这就是C++中SFINAE（Substitution Failure Is Not An Error）原则的应用——当一个模板重载在类型推导时失败，编译器不会报错，只是把这个重载从候选集中移除，然后尝试下一个候选函数。

⚠️ 温馨提示：enable_if必须出现在函数签名中才能参与重载解析，不能放在函数体内。而且C++20提供了concepts机制，可以用更清晰的方式来写这类约束。

3.2 拷贝构造与赋值操作

拷贝构造的实现思路很简单：根据被拷贝对象的容量先开辟好足够大的空间，然后逐个元素进行赋值。需要注意的细节是reserve的参数应该传被拷贝对象的capacity()而不是size()。如果传的是size()，虽然也能运行，但下一次push_back会立即触发扩容，效率会打折扣。提前预留足够的容量可以避免多次扩容带来的性能损耗。

vector(const vector<T>& v)
{
    reserve(v.capacity());
    for (auto& e : v)
    {
        push_back(e);
    }
}

赋值操作则巧妙地利用了拷贝交换（copy-and-swap）惯用法：

void swap(vector<T> tmp)
{
    std::swap(_start, tmp._start);
    std::swap(_finish, tmp._finish);
    std::swap(_endofstorage, tmp._endofstorage);
}

vector<T>& operator=(vector<T> v)  // 传值调用自动生成了副本
{
    swap(v);  // 交换副本与当前对象的内容
    return *this;
}

先通过传值调用生成一份副本，再通过交换成员变量完成赋值，最后副本在函数结束时自动析构——简洁且异常安全。

3.3 析构函数

~vector()
{
    if (_start)
    {
        delete[] _start;
        _start = _finish = _endofstorage = nullptr;
    }
}

析构函数负责释放动态分配的内存，并将三个指针置空，防止悬空指针。

4. 容量管理与动态扩容

4.1 reserve：预留空间

reserve是vector扩容的核心函数，它保证容器能够容纳n个元素而不需要重新分配内存：

void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t old_size = size();
        T* tmp = new T[n];
        if(_start)
        {
            for (size_t i = 0; i < old_size; i++)
            {
                tmp[i] = _start[i];
            }
            delete[] _start;
        }
        _start = tmp;
        _finish = _start + old_size;
        _endofstorage = _start + n;
    }
}

有几个关键点值得注意：

关键点一：为什么要提前记录old_size？ _finish和_start都是指针，size() = _finish - _start在扩容过程中。如果先更新_start再计算_finish，等式右边会算错。所以必须在_start被覆盖之前把size()保存下来。

关键点二：为什么不直接用memcpy拷贝？ 如果T是string等自定义类型，memcpy只是按字节复制浅拷贝，会导致两个对象指向同一块资源，析构时会double free。用赋值运算符逐个赋值，才能调用自定义类型的拷贝逻辑，实现深拷贝。

4.2 push_back与pop_back

有了reserve，尾插操作变得简洁：

void push_back(const T& val)
{
    if (_finish == _endofstorage)
    {
        reserve(capacity() == 0 ? 4 : 2 * capacity());
    }
    *_finish = val;
    ++_finish;
}

当空间满了就用reserve扩容，扩容因子是2倍（g++下是2倍扩容，VS下是1.5倍）。然后直接在_finish指向的位置放入新元素即可。

尾删的逻辑更直接：

void pop_back()
{
    assert(!empty());
    --_finish;
}

只需要确保容器非空，然后让_finish指针前移一位即可——这就是顺序表删除操作的简洁之处。

5. 插入与删除

5.1 insert：在指定位置插入

insert操作的实现思路分为三步：判断是否需要扩容、将pos及之后的元素后移、在pos位置放入新元素。

iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start && pos <= _finish);
    if (_finish == _endofstorage)
    {
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : 2 * capacity());
        pos = _start + len;   // 关键：重新定位pos
    }
    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }
    *pos = x;
    ++_finish;
    return pos;
}

这里有一个非常隐蔽的问题：如果在扩容前保存了pos，扩容后新空间来了，pos指向的还是旧空间的地址——此时旧空间已被释放，pos变成了野指针！解决方法是在扩容前记录pos相对于_start的偏移量len，扩容后让pos重新指向新空间中对应的位置。

5.2 erase：删除指定位置

erase的实现思路是：将pos位置之后的元素逐个向前覆盖一位，然后将_finish指针前移。

iterator erase(iterator pos)
{
    assert(pos >= _start && pos < _finish);
    iterator it = pos + 1;
    while (it != _finish)
    {
        *(it - 1) = *it;
        ++it;
    }
    --_finish;
    return pos;
}

5.3 迭代器失效问题剖析

迭代器本质上就是指针，迭代器失效意味着这个指针指向的内存已经被释放了，如果继续使用就会产生未定义行为，程序可能会崩溃。

在vector中有以下几种情况会导致迭代器失效：

• 扩容类操作（reserve、resize、push_back、insert等）。当触发扩容时，容器会重新分配一块新内存，将旧空间的元素逐个拷贝过去，然后释放旧空间。此时任何指向旧空间的迭代器都会失效，变成野指针。
• erase删除操作。当删除pos位置的元素时，pos位置之后的元素会向前覆盖。虽然底层空间没有变化，但VS等编译器认为该位置的迭代器已经失效，尤其是删除最后一个元素时，pos会变成end位置，而end位置没有元素，因此pos失效。

5.4 resize：调整容器大小

resize函数根据n的不同取值分两种情况处理：

void resize(size_t n, T val = T())
{
    if (n > size())
    {
        reserve(n);
        while (_finish != _start + n)
        {
            *_finish = val;
            ++_finish;
        }
    }
    else 
    {
        _finish = _start + n;
    }
}

• 当n大于当前size时，扩容后用val填充多出的位置。
• 当n小于当前size时，只需将_finish指针调整到_start + n位置即可，相当于截断处理。

6. 总结

从成员变量的设计（三个迭代器）、迭代器的简单实现（原生指针），到自动扩容机制（2倍扩容因子），再到插入删除时对迭代器失效的处理（记录偏移量重新定位），每一个细节都体现了C++顺序表这一核心数据结构的设计精髓。正如我们在本文开头所说的那样——最坚实的数据结构，恰恰长着最简单的模样。希望这次模拟实现的讲解，能帮助大家更深入地理解vector的底层原理，在实际开发中写出更健壮的代码。

7. vector.h完整代码

#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
#include<type_traits>
using namespace std;

namespace ray 
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		iterator begin() { return _start; }
		iterator end() { return _finish; }
		const_iterator begin() const { return _start; }
		const_iterator end() const { return _finish; }

		vector() = default;

		vector(initializer_list<T> il)
		{
			reserve(il.size());
			for (auto& e : il) push_back(e);
		}

		vector(const vector<T>& v)
		{
			reserve(v.capacity());
			for (auto& e : v) push_back(e);
		}

		void swap(vector<T> tmp)
		{
			std::swap(_start, tmp._start);
			std::swap(_finish, tmp._finish);
			std::swap(_endofstorage, tmp._endofstorage);
		}

		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

		template<class Inputiterator, class = typename std::enable_if<!std::is_integral<Inputiterator>::value>::type>
		vector(Inputiterator first, Inputiterator last)
		{
			while (first != last) push_back(*first++);
		}

		vector(size_t n, T val = T()) { resize(n, val); }
		vector(int n, T val = T()) { resize(n, val); }

		~vector()
		{
			if (_start) delete[] _start;
			_start = _finish = _endofstorage = nullptr;
		}

		void resize(size_t n, T val = T())
		{
			if (n > size())
			{
				reserve(n);
				while (_finish != _start + n) *_finish++ = val;
			}
			else _finish = _start + n;
		}

		size_t size() const { return _finish - _start; }
		size_t capacity() const { return _endofstorage - _start; }

		T& operator[](size_t n)
		{
			assert(n < size());
			return _start[n];
		}
		const T& operator[](size_t n) const
		{
			assert(n < size());
			return _start[n];
		}

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t old_size = size();
				T* tmp = new T[n];
				if (_start)
				{
					for (size_t i = 0; i < old_size; ++i) tmp[i] = _start[i];
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + old_size;
				_endofstorage = _start + n;
			}
		}

		void push_back(const T& val)
		{
			if (_finish == _endofstorage)
				reserve(capacity() == 0 ? 4 : 2 * capacity());
			*_finish++ = val;
		}

		void clear() { _finish = _start; }
		bool empty() const { return _start == _finish; }

		void pop_back()
		{
			assert(!empty());
			--_finish;
		}

		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start && pos <= _finish);
			if (_finish == _endofstorage)
			{
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : 2 * capacity());
				pos = _start + len;
			}
			iterator end = _finish - 1;
			while (end >= pos) *(end + 1) = *end--;
			*pos = x;
			++_finish;
			return pos;
		}

		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator it = pos + 1;
			while (it != _finish) *(it - 1) = *it++;
			--_finish;
			return pos;
		}

	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _endofstorage = nullptr;
	};
}