vector接口模拟实现及其原理

vector 首先支持无参构造函数，该构造函数会将对象的三个成员变量全部初始化为空指针。

//构造函数1
vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{}

2、构造函数2

        vector还支持通过迭代器区间构造对象。由于该区间可能来自任意容器，其迭代器类型无法预先确定，因此需要将此构造函数实现为函数模板。具体实现时，只需将区间内的元素逐个尾插入容器即可。

//构造函数2
template<class InputIterator> //模板函数
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{//将迭代器区间在[first,last)的数据一个个尾插到容器当中while (first != last){push_back(*first);first++;}
}

3、构造函数3

        此外，vector还支持构造包含n个值为val元素的容器。要实现这种构造，可以先调用reserve(n)预分配容量，再通过循环调用push_back(val)函数n次来填充元素。

//构造函数3
vector(size_t n, const T& val):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n); //调用reserve函数将容器容量设置为nfor (size_t i = 0; i < n; i++) //尾插n个值为val的数据到容器当中{push_back(val);}
}

注意：

• 该构造函数明确知道需要存储n个数据，因此建议使用reserve函数一次性分配足够的空间。这样可以避免后续调用push_back时多次扩容，从而提高效率。
• 该构造函数还需要实现两个重载版本，如下：

vector(long n, const T& val):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n); //调用reserve函数将容器容量设置为nfor (size_t i = 0; i < n; i++) //尾插n个值为val的数据到容器当中{push_back(val);}
}
vector(int n, const T& val):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n); //调用reserve函数将容器容量设置为nfor (int i = 0; i < n; i++) //尾插n个值为val的数据到容器当中{push_back(val);}
}

        这两个重载函数的关键区别在于参数n的类型不同，这种差异是必要的设计考量。因为如果缺少这种区分，在使用如下代码时：

vector<int> v(5, 7); // 本应调用构造函数3

        编译器会优先匹配构造函数2。由于构造函数2需要对参数first和last进行解引用操作（而int类型不支持解引用），最终会导致编译错误。

        这个问题涉及到C++的函数模板重载决议规则和模板参数推导机制。为什么编译器会优先匹配构造函数2而不是构造函数3呢？

        当你写 vector<int> v(5, 7); 时，你期望调用构造函数3 vector(size_t n, const T& val)，但编译器却尝试匹配构造函数2 vector(InputIterator first, InputIterator last)，导致编译错误。

原因分析

1、模板参数推导的优先级：

• 构造函数2是一个模板函数，可以匹配任何类型的参数

• 构造函数3是一个非模板函数（虽然有多个重载），但需要精确的类型匹配

2、整数类型的匹配：

• 当你传递 (5, 7) 时，两个参数都是 int 类型

• 构造函数3需要 size_t（通常是 unsigned long）和 T，需要进行隐式转换

• 构造函数2的模板可以精确匹配 InputIterator = int，不需要任何转换

3、重载决议规则：

• C++重载决议优先选择"最匹配"的函数，不需要类型转换的版本优先于需要类型转换的版本

• 模板函数能精确匹配时，优先于需要隐式转换的非模板函数

解决方案

1. 提供精确匹配的重载：已经提供了 int 和 long 的重载版本，这是正确的做法。

2. 使用强制类型转换：调用时可以使用 vector<int> v(5u, 7); 强制第一个参数为 unsigned

3. 使用统一初始化语法：vector<int> v{5, 7}; 这会调用 initializer_list 构造函数（原版代码是这样写的，模拟实现如果有的话）

4. 添加 SFINAE 约束（更高级的解决方案）：可以修改构造函数2，使用类型特征确保它只匹配真正的迭代器类型

为什么需要多个重载

        因为 size_t 的具体实现可能因平台而异（可能是 unsigned int 或 unsigned long），而字面量 5 默认是 int 类型。如果没有精确匹配的重载，编译器会优先选择模板版本而不是需要类型转换的非模板版本。

4、拷贝构造函数

关于vector的深拷贝构造函数，这里提供两种实现方式：

写法一：传统实现方法

        传统实现思路直观明了：首先开辟与原容器大小相同的内存空间，接着逐个拷贝原容器中的元素数据，最后更新_finish和_endofstorage指针的值即可。

//传统写法
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来{_start[i] = v[i];}_finish = _start + v.size(); //容器有效数据的尾_endofstorage = _start + v.capacity(); //整个容器的尾
}

注意事项：

        在逐个拷贝容器数据时，应避免使用memcpy函数。当vector存储的是内置类型或无需深拷贝的自定义类型时，memcpy函数尚可适用；然而，当vector存储需要深拷贝的自定义类型（如string类）时，memcpy函数的局限性就会显现。

并且vector当中存储的每一个string都指向自己所存储的字符串。

        若使用memcpy函数进行拷贝构造，新构造的vector中每个string对象的成员变量值将与原vector中的string对象完全相同。这意味着两个vector中对应的string成员会指向相同的字符串存储空间。

显然，这与我们预期的结果不符。那么，这段代码具体是如何解决问题的呢？

for (size_t i = 0; i < v.size(); i++) 
{start[i] = v[i];
}

这段代码的作用是：

1. 遍历源容器 v 的所有元素（v.size() 表示 v 的元素数量）。

2. 将 v[i] 的值逐个赋值给目标容器的 start[i]（start 可能是目标容器的底层数组指针）。

        代码中看似通过普通的"="运算符逐个复制容器元素，实则调用了元素类型的赋值运算符重载函数。由于string类的赋值运算符实现了深拷贝，因此最终复制的数据会保持独立性。

总结：

        当vector存储内置类型（如int）或浅拷贝的自定义类型（如Date）时，使用memcpy进行拷贝构造是可行的。然而，若vector存储深拷贝的自定义类型（如string），memcpy就无法实现预期效果。

理清思路：

1. string 对象本身的地址（容器内存储的地址）

• 是连续的
  当 string 对象存储在 vector（或数组）中时，string 对象本身的内存地址是连续的。
  例如：

  std::vector<std::string> v = {"hello", "world", "cpp"};

  内存布局大致如下：

  [string对象1] [string对象2] [string对象3] ... （地址连续）

  每个 string 对象的大小固定（通常为几个指针的大小，如 24 或 32 字节，取决于实现），它们在 vector 的内存中是紧密排列的。

2. string 内部字符串数据的地址（实际存储的字符数据）

• 通常是离散的（不连续）
  每个 string 对象内部管理一个独立的堆内存块，用于存储实际的字符串数据（如 "hello"、"world"）。
  这些字符串数据的地址是动态分配的，彼此之间没有连续性。例如：

  string对象1.data() -> 堆内存地址 0x1234 (存储 "hello")
  string对象2.data() -> 堆内存地址 0x5678 (存储 "world")
  string对象3.data() -> 堆内存地址 0x9abc (存储 "cpp")

  这些地址可能相差很远，取决于堆内存的分配情况。

3. 深拷贝时的行为

当执行 start[i] = v[i]（即 string 的拷贝赋值）时：

1. string 对象本身（位于 vector 的连续内存中）会被逐字节复制（包括其内部指针、大小等信息）。

2. 字符串数据（如 "hello"）会重新在堆上分配新内存，并拷贝内容，实现深拷贝。
   因此，拷贝后的 string 对象：

   • 新对象的地址仍在 vector 的连续空间中。

   • 但新对象的字符串数据会指向另一块独立的堆内存。

写法二：现代写法

        拷贝构造函数的现代写法也比较简单，使用范围for（或是其他遍历方式）对容器v进行遍历，在遍历过程中将容器v中存储的数据一个个尾插过来即可。

//现代写法
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(v.capacity()); //调用reserve函数将容器容量设置为与v相同for (auto e : v) //将容器v当中的数据一个个尾插过来{push_back(e);}
}

注意：

        在使用范围for循环遍历容器v时，变量e会获取每个元素的拷贝值，随后将e插入到新构建的容器的末尾。即使容器v中存储的是string类对象，在拷贝e时也会自动调用string的拷贝构造函数（执行深拷贝），因此同样可以避免类似使用memcpy时可能出现的问题。

5、赋值运算符重载函数

vector的赋值运算符重载当然也涉及深拷贝问题，我们这里也提供两种深拷贝的写法：

写法一：传统写法

        首先判断是否是给自己赋值，若是给自己赋值则无需进行操作。若不是给自己赋值，则先开辟一块和容器v大小相同的空间，然后将容器v当中的数据一个个拷贝过来，最后更新_finish和_endofstorage的值即可。

//传统写法
vector<T>& operator=(const vector<T>& v)
{if (this != &v) //防止自己给自己赋值{delete[] _start; //释放原来的空间_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来{_start[i] = v[i];}_finish = _start + v.size(); //容器有效数据的尾_endofstorage = _start + v.capacity(); //整个容器的尾}return *this; //支持连续赋值
}

注意：此处与传统拷贝构造函数的写法类似，也不建议使用 memcpy 进行拷贝。

写法二：现代写法

        赋值运算符重载的现代写法较为巧妙，其右值传参未采用引用方式，而是通过直接传值间接调用 vector 的拷贝构造函数。随后将拷贝构造出的临时容器 v 与左值进行交换，从而完成赋值操作。临时容器 v 会在函数结束时自动析构。

//现代写法
vector<T>& operator=(vector<T> v) //编译器接收右值的时候自动调用其拷贝构造函数
{swap(v); //交换这两个对象return *this; //支持连续赋值
}

        在 C++ 中，swap 通常是一个成员函数，因此它只需要一个显式参数，因为另一个参数是隐式的 this 指针（即调用 swap 的对象本身）。后面会实现！！！

注意： 赋值运算符重载的现代写法也是进行的深拷贝，只不过是调用的vector的拷贝构造函数进行的深拷贝，在赋值运算符重载函数当中仅仅是将深拷贝出来的对象与左值进行了交换而已。

6、析构函数

        对容器进行析构时，首先判断该容器是否为空容器，若为空容器，则无需进行析构操作，若不为空，则先释放容器存储数据的空间，然后将容器的各个成员变量设置为空指针即可。

//析构函数
~vector()
{if (_start) //避免对空指针进行释放{delete[] _start; //释放容器存储数据的空间_start = nullptr; //_start置空_finish = nullptr; //_finish置空_endofstorage = nullptr; //_endofstorage置空}
}

7、动态二维数组理解

// 以杨辉三角的前n行为例：假设n为5
void test2vector(size_t n)
{// 使用vector定义二维数组vv，vv中的每个元素都是vector<int>bit::vector<bit::vector<int>> vv(n);// 初始化二维数组：将每一行的vector<int>设置为对应长度并填充1for (size_t i = 0; i < n; ++i)vv[i].resize(i + 1, 1);// 计算杨辉三角的内部元素：每个元素等于上方两个元素之和for (int i = 2; i < n; ++i) {for (int j = 1; j < i; ++j) {vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];}}
}

代码解析：

1. bit::vector<bit::vector<int>> vv(n);

   • 构造一个动态二维数组vv，包含n个元素

   • 每个元素都是一个vector<int>对象

   • 初始化时每行都是空的vector（尚未分配空间）

   当n=5时，初始结构如下：

   

2. 初始化循环：

   • 为每一行分配空间并填充初始值1

   • 第i行有i+1个元素（杨辉三角性质）

   • 使用resize(i + 1, 1)同时设置大小和初始值

   填充完成后结构如下（n=5时）：

   

3. 计算杨辉三角：

   • 从第3行(i=2)开始计算内部元素

   • 每个元素等于其正上方和左上方元素之和

   • 保留每行的首尾元素为1（不进入内层循环）

   最终生成的杨辉三角：

   [1]
   [1, 1]
   [1, 2, 1]
   [1, 3, 3, 1]
   [1, 4, 6, 4, 1]

补充说明：

• 该实现展示了如何使用vector嵌套创建动态二维数组

• 杨辉三角的性质被充分利用来初始化数组结构

• 时间复杂度为O(n²)，空间复杂度为O(n²)

• 边界条件处理完善（n=0或1时也能正确运行）

四、迭代器相关函数

vector当中的迭代器实际上就是容器当中所存储数据类型的指针。

typedef T* iterator;
typedef const T* const_iterator;

或者使用using：

using iterator = T*;
using const_iterator = const T*;

begin和end

        vector当中的begin函数返回容器的首地址，end函数返回容器当中有效数据的下一个数据的地址。

iterator begin()
{return _start; //返回容器的首地址
}
iterator end()
{return _finish; //返回容器当中有效数据的下一个数据的地址
}

        我们还需要重载一对适用于const对象的begin和end函数，使得const对象调用begin和end函数时所得到的迭代器只能对数据进行读操作，而不能进行修改。

const_iterator begin()const
{return _start; //返回容器的首地址
}
const_iterator end()const
{return _finish; //返回容器当中有效数据的下一个数据的地址
}

此时再让我们来看看vector使用迭代器的代码也就一目了然了，实际上就是使用指针遍历容器。

vector<int> v(5, 3);
vector<int>::iterator it = v.begin();
while (it != v.end())
{cout << *it << " ";it++;
}
cout << endl;

        现在我们实现了迭代器，实际上也就可以使用范围for遍历容器了，因为编译器在编译时会自动将范围for替换为迭代器的形式。

vector<int> v(5, 3);
//范围for进行遍历
for (auto e : v)
{cout << e << " ";
}
cout << endl;

五、容量与大小相关函数

1、size与capacity

        通过对比vector中三个成员指针的指向关系，我们可以直观地获取当前容器的有效元素数量和最大容量。

由于指针相减的结果表示两者之间该类型元素的数量，因此：

• size可通过_finish - _start计算
• capacity可通过_endofstorage - _start计算

size_t size()const
{return _finish - _start; //返回容器当中有效数据的个数
}
size_t capacity()const
{return _endofstorage - _start; //返回当前容器的最大容量
}

2、reserve

reserve规则：

• 当n大于对象当前的capacity时，将capacity扩大到n或大于n。
• 当n小于对象当前的capacity时，什么也不做。

    reserve 函数的实现原理如下：首先检查给定的容量 n 是否超过当前容器的最大容量（若未超过则无需处理）。若需要扩容，则执行以下步骤：

1. 申请可容纳 n 个元素的新内存空间
2. 将现有有效数据拷贝至新空间
3. 释放原内存空间
4. 将新空间交由容器管理
5. 更新容器相关成员变量

void reserve(size_t n)
{if (n > capacity()) //判断是否需要进行操作{size_t sz = size(); //记录当前容器当中有效数据的个数T* tmp = new T[n]; //开辟一块可以容纳n个数据的空间if (_start) //判断是否为空容器{for (size_t i = 0; i < sz; i++) //将容器当中的数据一个个拷贝到tmp当中{tmp[i] = _start[i];}delete[] _start; //将容器本身存储数据的空间释放}_start = tmp; //将tmp所维护的数据交给_start进行维护_finish = _start + sz; //容器有效数据的尾_endofstorage = _start + n; //整个容器的尾}
}

在实现reserve函数时，有两个关键点需要注意：

1、执行扩容操作前需要先保存当前容器中的有效元素数量。 因为最终需要更新_finish指针的位置，而_finish的正确位置等于_start指针加上原始元素数量。如果在_start指针改变后再通过_finish - _start计算size，得到的结果将是无效的随机值。

2、拷贝容器数据时，禁止使用memcpy函数。

        你可能会认为：当vector存储string类型时，虽然用memcpy复制后新容器中的每个string与原容器指向同一块字符串内存，但原容器的存储空间已被释放，现在只有新容器维护这些字符串，似乎没有影响。

        然而需要注意：当原容器释放空间时，其中的每个string都会调用析构函数，从而释放其指向的字符串内存。因此，memcpy复制出的新容器中的string实际上指向的是已释放的内存空间，访问该容器将导致非法内存访问。

        所以说我们还是得用for循环将容器当中的string一个个赋值过来，因为这样能够间接调用string的赋值运算符重载，实现string的深拷贝。

3、resize

resize规则：

1. 当n大于当前size时，将size扩展到n。新增元素初始化为val，若未提供val，则使用该类型的默认构造函数生成默认值。
2. 当n小于当前size时，将size缩减到n。

实现逻辑：

        首先比较n与当前size的大小。若n较小，则直接调整_finish指针位置完成缩减；若n较大，则先检查是否需要扩容，再对新元素进行val赋值操作。

void resize(size_t n, const T& val = T())
{if (n < size()) //当n小于当前的size时{_finish = _start + n; //将size缩小到n}else //当n大于当前的size时{if (n > capacity()) //判断是否需要增容{reserve(n);}while (_finish < _start + n) //将size扩大到n{*_finish = val;_finish++;}}
}

注意：

        在C++当中内置类型也可以看作是一个类，它们也有自己的默认构造函数，所以在给resize函数的参数val设置缺省值时，设置为T( )即可。

4、empty

        empty函数可以直接通过比较容器当中的_start和_finish指针的指向来判断容器是否为空，若所指位置相同，则该容器为空。

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

六、修改容器内容相关函数

        要尾插数据首先得判断容器是否已满，若已满则需要先进行增容，然后将数据尾插到_finish指向的位置，再将_finish++即可。

//尾插数据
void push_back(const T& x)
{if (_finish == _endofstorage) //判断是否需要增容{size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); //将容量扩大为原来的两倍reserve(newcapacity); //增容}*_finish = x; //尾插数据_finish++; //_finish指针后移
}

2、pop_back

尾删数据之前也得先判断容器是否为空，若为空则做断言处理，若不为空则将_finish减减即可。

//尾删数据
void pop_back()
{assert(!empty()); //容器为空则断言_finish--; //_finish指针前移
}

3、insert

        insert函数可以在所给迭代器pos位置插入数据，在插入数据前先判断是否需要增容，然后将pos位置及其之后的数据统一向后挪动一位，以留出pos位置进行插入，最后将数据插入到pos位置即可。

//在pos位置插入数据
void insert(iterator pos, const T& x)
{if (_finish == _endofstorage) //判断是否需要增容{size_t len = pos - _start; //记录pos与_start之间的间隔size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); //将容量扩大为原来的两倍reserve(newcapacity); //增容pos = _start + len; //通过len找到pos在增容后的容器当中的位置}//将pos位置及其之后的数据统一向后挪动一位，以留出pos位置进行插入iterator end = _finish;while (end >= pos + 1){*end = *(end - 1);end--;}*pos = x; //将数据插入到pos位置_finish++; //数据个数增加一个，_finish后移
}

注意： 若需要增容，则需要在增容前记录pos与_start之间的间隔，然后通过该间隔确定在增容后的容器当中pos的指向，否则pos还指向原来被释放的空间。

4、erase

        erase函数可以删除所给迭代器pos位置的数据，在删除数据前需要判断容器是否为空，若为空则需做断言处理，删除数据时直接将pos位置之后的数据统一向前挪动一位，将pos位置的数据覆盖即可。

//删除pos位置的数据
iterator erase(iterator pos)
{assert(!empty()); //容器为空则断言//将pos位置之后的数据统一向前挪动一位，以覆盖pos位置的数据iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;it++;}_finish--; //数据个数减少一个，_finish前移return pos;
}

5、swap

        swap函数用于交换两个容器的数据，我们可以直接调用库当中的swap函数将两个容器当中的各个成员变量进行交换即可。

//交换两个容器的数据
void swap(vector<T>& v)
{//交换容器当中的各个成员变量::swap(_start, v._start);::swap(_finish, v._finish);::swap(_endofstorage, v._endofstorage);
}

注意： 

        在此处调用库当中的swap需要在swap之前加上“::”（作用域限定符），告诉编译器这里优先在全局范围寻找swap函数，否则编译器会认为你调用的就是你正在实现的swap函数（就近原则）。

七、访问容器相关函数

        vector也支持我们使用“下标+[ ]”的方式对容器当中的数据进行访问，实现时直接返回对应位置的数据即可。

T& operator[](size_t i)
{assert(i < size()); //检测下标的合法性return _start[i]; //返回对应数据
}
const T& operator[](size_t i)const
{assert(i < size()); //检测下标的合法性return _start[i]; //返回对应数据
}

注意： 

        重载运算符[ ]时需要重载一个适用于const容器的，因为const容器通过“下标+[ ]”获取到的数据只允许进行读操作，不能对数据进行修改。

八、使用 hmz::vector 的示例代码

#include <iostream>
#include <string>int main() {// 1. 创建空的 vector 并添加元素hmz::vector<int> v1;std::cout << "Empty vector created. Size: " << v1.size() << ", Capacity: " << v1.capacity() << std::endl;for (int i = 1; i <= 5; ++i) {v1.push_back(i * 10);}std::cout << "After push_back: ";for (auto num : v1) {std::cout << num << " ";}std::cout << std::endl;// 2. 使用迭代器范围构造int arr[] = {5, 10, 15, 20};hmz::vector<int> v2(arr, arr + sizeof(arr)/sizeof(arr[0]));std::cout << "Vector from array: ";for (auto num : v2) {std::cout << num << " ";}std::cout << std::endl;// 3. 使用 n 个相同元素构造hmz::vector<std::string> v3(3, "Hello");std::cout << "Vector with 3 \"Hello\": ";for (const auto& str : v3) {std::cout << str << " ";}std::cout << std::endl;// 4. 测试拷贝构造和赋值hmz::vector<int> v4(v1);std::cout << "Copied vector: ";for (auto num : v4) {std::cout << num << " ";}std::cout << std::endl;hmz::vector<int> v5;v5 = v2;std::cout << "Assigned vector: ";for (auto num : v5) {std::cout << num << " ";}std::cout << std::endl;// 5. 测试插入和删除v5.insert(v5.begin() + 2, 99);std::cout << "After insert 99 at pos 2: ";for (auto num : v5) {std::cout << num << " ";}std::cout << std::endl;v5.erase(v5.begin() + 1);std::cout << "After erase pos 1: ";for (auto num : v5) {std::cout << num << " ";}std::cout << std::endl;// 6. 测试 resize 和 reservestd::cout << "Before resize - Size: " << v5.size() << ", Capacity: " << v5.capacity() << std::endl;v5.resize(10, 77);std::cout << "After resize to 10: ";for (auto num : v5) {std::cout << num << " ";}std::cout << std::endl;v5.reserve(20);std::cout << "After reserve(20) - Size: " << v5.size() << ", Capacity: " << v5.capacity() << std::endl;// 7. 测试 operator[] 和 pop_backv5[0] = 100;std::cout << "After v5[0] = 100: " << v5[0] << std::endl;while (!v5.empty()) {v5.pop_back();}std::cout << "After pop all elements - Size: " << v5.size() << std::endl;return 0;
}