C++：vector(2)之vector的模拟实现

@TOC

vector的模拟实现

一.vector.h

#pragma once
#include<iostream>
#include<cassert>
using namespace std;
namespace yl
{
template<typename T>
	class vector {
	private:
		iterator _start;
		iterator _finsh;
		iterator _endofstorage;

以下 C++ 代码模块说明：

1. 命名空间封装（namespace yl）

• 定义 namespace yl，将自定义 vector 类封装其中，避免与其他代码同名类冲突。

2. 模板类声明（template）

• 通过 template <class T> 声明模板类，T 为类型参数，支持灵活实例化：
  • 如 yl::vector<int> 存储 int 类型、yl::vector<double> 存储 double 类型。

3. 模板类定义（class vector）

结合模板声明，定义 class vector，实现自定义动态数组功能，核心逻辑依赖以下成员。

4. 私有成员变量（private 部分）

包含 3 个迭代器，标记容器不同边界：

• iterator _start：指向数据起始位置，是容器第一个元素的指针/迭代器。
• iterator _finish：指向已使用数据的末尾（即最后一个有效元素的下一个位置 ）。
• iterator _endofstorage：指向底层存储空间末尾，标记容器总容量边界（_finish 不能超过它 ）。

	
public:
using iterator=T*;//C++11标准
using const_iterator = const T*;

		vector()
	  :_start(nullptr)
      ,_finsh(nullptr)
	  ,_endofstorage(nullptr)
		{ }
		iterator begin()
		{
			return _start;
		}
		iterator end()
		{
			return _finsh;
		}
		const_iterator begin()const
		{
			return _start;
		}
		const_iterator end()const
		{
			return _finsh;
		}

以上代码展示的内容：

5. 类型别名定义

• using iterator=T*;
  • 在 C++11 标准下，利用 using 关键字为 T* 定义类型别名 iterator 。在自定义 vector 类中，iterator 即指向模板参数 T 类型的指针，便于在后续代码中表示可修改元素的迭代器类型，用于遍历容器元素 。
• using const_iterator = const T*;
  • 同样借助 using 定义类型别名，const_iterator 被定义为指向 const T 类型的指针，即常迭代器类型。其作用是在不修改容器元素的前提下遍历容器 。

6. 构造函数

• vector() :_start(nullptr), _finsh(nullptr), _endofstorage(nullptr)
  • 此为 vector 类的默认构造函数，采用成员初始化列表的方式，将三个私有成员变量 _start、_finsh 和 _endofstorage 初始化为 nullptr 。这表明在默认构造时，该自定义 vector 容器尚未分配实际存储空间，也没有存储任何元素 。

7. 迭代器相关成员函数

• iterator begin()
  • 属于非 const 成员函数，返回指向容器起始位置的迭代器，即私有成员变量 _start ，用于支持非 const 对象的正向遍历 。
• iterator end()
  • 也是非 const 成员函数，返回指向容器末尾（已使用元素的末尾 ）位置的迭代器，也就是 _finsh 。与 begin() 函数配合，可实现对容器内元素的遍历 。
• const_iterator begin() const
  • 是 begin() 函数的 const 版本，适用于 const 对象。由于 const 对象不能调用非 const 成员函数，通过该版本可在不修改容器内容的情况下，获取指向起始位置的常迭代器 。
• const_iterator end() const
  • 为 end() 函数的 const 版本，为 const 对象提供指向容器末尾的常迭代器 。

~vector()
{
	if (_start)
	{
		delete[] _start;
		_start = _finsh = _endofstorage = nullptr;
	}
}
vector(initializer_list li)//支持任意多个值初始化
{
	reserve(li.size());
	for (auto& e : li)
	{
		push_back(e);
	}
}
template<typename inputiterator>
vector(inputiterator begin, inputiterator end)
{
	while (begin < end)
	{
		push_back(*begin);
		++begin;
	}
}

8.vector的析构函数及拷贝构造函数：

1. 析构函数 ~vector()：

• 核心逻辑：释放容器动态分配的内存，并将指针置空，防止野指针。
• 关键点：
  • 内存释放：通过 delete[] _start 释放数组内存。
  • 安全处理：检查 _start 是否为空，避免释放空指针。
  • 指针重置：将 _start、_finish、_endofstorage 全部置为 nullptr，确保析构后对象状态安全。

2. 初始化列表构造函数 vector(initializer_list li)：

• 核心逻辑：支持使用花括号初始化器（如 vector<int> v = {1, 2, 3};）初始化容器。
• 关键点：
  • 预分配内存：通过 reserve(li.size()) 预先分配足够空间，避免多次扩容。
  • 元素添加：遍历初始化列表，通过 push_back 将元素逐个添加到容器。

3. 迭代器构造函数 vector(inputiterator begin, inputiterator end)：

• 核心逻辑：使用任意迭代器范围初始化容器，支持从其他容器或数组拷贝元素。
• 关键点：
  • 范围遍历：通过 while (begin < end) 遍历迭代器范围，逐个添加元素。
  • 适用性：适用于所有支持 < 比较和 ++ 递增的迭代器（如随机访问迭代器）。

8.1.注意事项：

• 潜在问题：迭代器构造函数假设 begin 和 end 支持 < 比较，这对输入迭代器（如 istream_iterator）不成立，可能导致编译错误。
• 优化方向：可通过迭代器分类（如 random_access_iterator_tag）区分不同迭代器类型，针对随机访问迭代器预先分配内存以提升效率。

		size_t size()const{
			return _finsh - _start;
		}
		size_t capacity() const{
			return _endofstorage - _start;
		}
		bool empty(){
			return _finsh == _start;
		}
		void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t old_size = size();
        T* tmp = new T[n];
        // 拷贝旧空间数据到新空间
        if (_start)
        {
            //memcpy(tmp, _start, sizeof(T) * old_size);
            for (size_t i = 0; i < old_size; i++)
            {
                tmp[i] = _start[i];
            }
            delete[] _start;
        }

        _start = tmp;
        _finish = _start + old_size;
        _endofstorage = _start + n;
    }
}

9.size 成员函数

• size_t size() const
  • 这是一个 const 成员函数，作用是获取当前容器中已存储元素的数量。返回值类型 size_t 是无符号整型，常用于表示大小、计数等场景。
  • 函数体为 return _finsh - _start; 。因为 _start 和 _finsh 是指向同一块连续内存区域的指针类型，二者相减得到的就是它们之间元素的个数，也就是已存储元素的数量。

10.capacity 成员函数

• size_t capacity() const
  • 作为 const 成员函数，用于获取容器当前已分配的存储空间总共能容纳元素的数量，即容器的总容量。
  • 函数体 return _endofstorage - _start;，通过表示容器底层存储空间末尾位置的迭代器 _endofstorage 减去起始位置迭代器 _start，直接计算出整个底层内存空间的总长度，该长度即为容器能够容纳的最大元素数量（总容量）。

11.empty 成员函数

• bool empty()
  • 此函数用于判断容器是否为空，返回值类型为 bool 。
  • 函数体 return _finsh == _start; ，当表示已使用数据末尾位置的迭代器 _finsh 和起始位置迭代器 _start 相等时，意味着容器中没有存储任何元素，此时返回 true ；否则返回 false 。

12.reserve 成员函数

• void reserve()

内存分配：

• 使用 new T[n] 进行类型安全的对象构造
• 相较 memcpy 或原始内存操作，确保非平凡类型正确初始化

数据迁移：

• 通过赋值操作符 tmp[i] = _start[i] 逐个迁移元素
• 支持包含资源管理的复杂对象（如 std::string、智能指针）
• 避免浅拷贝风险，保证深拷贝语义

指针更新：

• _start = tmp：指向新内存起始位置
• _finish = _start + old_size：维持原有元素数量不变
• _endofstorage = _start + n：标记新的容量上限

异常安全：

• 若元素赋值期间抛出异常：
  1. 新内存自动释放（通过作用域内临时指针 tmp）
  2. 旧内存 _start 保持完整，容器状态不变
• 提供基本异常安全保证（Basic Guarantee）

		void push_back(const T x)
		{
			if (_finsh == _endofstorage)
			{
				reserve(capacity() == 0 ? 4 : 2 * capacity());
			}
			*_finsh = x;
			_finsh++;
		}
		void pop_back()
		{
			assert(!empty());
			--_finsh;
		}
		void insert(iterator pos, const T x)
		{
			assert(pos>= _start && pos <= _finsh);
			if (_finsh == _endofstorage)
			{ 
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : 2 * capacity());
                pos = _start + len;//更新扩容之后的pos
			}
			
			iterator end = _finsh - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
		}
		void erase(iterator pos)
		{
			assert(pos >= _start && pos < _finsh&&!empty());
			iterator it = pos+1;
			while (it < _finsh)
			{
				*(it-1) = *it;
				++it;
			}
			--_finsh;
		}

以下是对新增代码部分的分析：

13.push_back 成员函数

• 功能：向容器尾部添加一个元素。
• 实现逻辑：
  1. 容量检查：若当前已使用空间（_finsh）等于总容量（_endofstorage），则调用 reserve 扩容。首次扩容为4，后续每次扩容为当前容量的2倍。
  2. 元素添加：将元素 x 赋值到 _finsh 指向的位置，并将 _finsh 指针后移一位。
• 注意点：使用 const T x 接收参数，避免修改传入值。

14.pop_back 成员函数

• 功能：删除容器尾部的元素。
• 实现逻辑：
  1. 空容器检查：使用 assert 确保容器非空。
  2. 指针调整：将 _finsh 指针前移一位，逻辑上删除最后一个元素。
• 注意点：
  • 未释放内存，仅调整指针。
  • 若容器为空时调用，assert 会触发程序终止（调试模式下）。

15.insert 成员函数

• 功能：在指定位置 pos 前插入元素 x。
• 实现逻辑：
  1. 边界检查：确保 pos 在有效范围内（_start 到 _finsh 之间）。
  2. 容量检查与扩容：若容量不足，先扩容。扩容后需重新计算 pos 位置（因内存可能已重新分配）。
  3. 元素后移：从 _finsh-1 开始，将元素依次后移一位，直至 pos。
  4. 插入元素：在 pos 位置赋值 x。
• 注意点：
  • 扩容后需更新 pos 指针，否则可能导致野指针。
  • 时间复杂度为 O(n)，适用于少量插入操作。

16.erase 成员函数

• 功能：删除指定位置 pos 的元素。
• 实现逻辑：
  1. 边界检查：确保 pos 在有效范围内（_start 到 _finsh-1）且容器非空。
  2. 元素前移：从 pos+1 开始，将后续元素依次前移一位，覆盖 pos 位置的元素。
  3. 指针调整：将 _finsh 指针前移一位。
• 注意点：
  • 未释放内存，仅覆盖元素。
  • 时间复杂度为 O(n)，适用于少量删除操作。

void swap(vector<T> v)
{
std::swap(_start, v._start);
std::swap(_finsh, v.finsh);
std::swap(_endofstorage, v._endofstorage);
}
vector<T>& operator=(vector<T> v)
{
	swap(v);
	return *this;
}
		T& operator[](size_t i)
		{
			assert(i < size());
			return _start[i];
		} 
		const T& operator[](size_t i)const
		{
			assert(i < size());
			return _start[i];
		}
	};
}

17.赋值运算符 operator=

• swap 函数：借助交换内部指针（_start、_finish、_endofstorage ） ，达成常数时间的容器内容交换，高效且直接。
• 拷贝并交换惯用法 ：
  • 赋值运算符（operator= ）采用值传递参数方式，利用类的拷贝构造函数自动创建临时对象。
  • 随后调用 swap 函数交换资源，这种方式确保了自我赋值安全（即便对象给自己赋值也不会出错），同时提供异常安全保证（若在交换过程中出现异常，原对象状态可维持不变 ）。

18.重载下标运算符 operator[]

为自定义 vector 容器实现下标访问功能，类似原生数组的 [] 操作，分为两种版本以适配不同场景：

18.1.非 const 版本

• 适用对象：非 const 修饰的 vector 对象。
• 功能：允许对容器中的元素进行读写操作。
• 参数：索引值 i（无符号整数类型），表示要访问的元素位置。
• 实现逻辑：
  1. 先检查索引 i 是否在有效范围内（即 i 小于当前容器的元素数量），若越界则在调试模式下触发错误提示。
  2. 直接返回容器中第 i 个元素的引用，通过这个引用可以直接修改元素的值。
• 用途：支持类似“容器名[索引] = 值”的赋值操作，比如 vec[2] = 10。

18.2.const 版本

• 适用对象：被 const 修饰的 vector 对象（即不能修改的容器）。
• 功能：仅允许对容器中的元素进行读取操作，不允许修改。
• 参数：与非 const 版本相同，即索引值 i。
• 实现逻辑：
  1. 同样先检查索引 i 的有效性，确保不越界。
  2. 返回容器中第 i 个元素的常量引用，通过这个引用只能读取元素值，无法修改。
• 用途：支持类似“变量 = 容器名[索引]”的只读访问，比如 int x = const_vec[1]。

18.3.设计特点

1. 版本区分：两个版本通过是否带 const 修饰符区分，编译器会根据容器对象是否为 const 自动选择对应的版本。
2. 直接访问：通过元素在内存中的起始位置和索引计算偏移量，直接定位到目标元素，访问效率极高（和原生数组一样快）。
3. 安全性：通过检查索引是否在有效范围内（调试模式下）避免越界访问，但这种检查仅在调试时生效，正式环境中需额外处理。
4. 灵活性：非 const 版本支持修改元素，const 版本仅允许读取，既满足了修改需求，又保证了 const 对象的不可变性。

二.test.cpp

#include "vector.h" 

// 不展开yl命名空间，避免与其他命名空间冲突

// 辅助函数：打印vector状态
template<typename T>
void print_vector(const yl::vector<T>& v, const std::string& name) {
    std::cout << "[" << name << "] size:" << v.size() 
              << " capacity:" << v.capacity() << " elements: ";
    for (size_t i = 0; i < v.size(); ++i) {
        std::cout << v[i] << " ";
    }
    std::cout << std::endl;
}

// 1. 测试各类构造函数
void test01() {
    std::cout << "=== 测试构造函数 ===" << std::endl;
    // 1.1 默认构造
    yl::vector<int> v1;
    assert(v1.size() == 0 && v1.capacity() == 0 && v1.empty());
    
    // 1.2 初始化列表构造
    yl::vector<int> v2 = {1, 2, 3, 4};
    assert(v2.size() == 4 && v2[2] == 3);
    
    // 1.3 n个值构造（size_t版本）
    yl::vector<int> v3(5, 10);
    assert(v3.size() == 5 && v3[3] == 10);
    
    // 1.4 迭代器范围构造
    yl::vector<int> v4(v2.begin(), v2.end());
    assert(v4.size() == 4 && v4[0] == 1);
    
    print_vector(v4, "v4(迭代器构造)");
    std::cout << "test01 测试通过！\n" << std::endl;
}

// 2. 测试push_back/pop_back
void test02() {
    std::cout << "=== 测试push_back/pop_back ===" << std::endl;
    yl::vector<int> v;
    v.push_back(10);
    v.push_back(20);
    assert(v.size() == 2 && v[1] == 20);
    
    v.pop_back();
    assert(v.size() == 1 && v[0] == 10);
    
    print_vector(v, "v(push_back后)");
    std::cout << "test02 测试通过！\n" << std::endl;
}

// 3. 测试reserve/resize
void test03() {
    std::cout << "=== 测试reserve/resize ===" << std::endl;
    yl::vector<int> v;
    v.push_back(1);
    
    // 测试reserve（只改容量，不改大小）
    v.reserve(10);
    assert(v.capacity() >= 10 && v.size() == 1);
    
    // 测试resize（扩大并填充）
    v.resize(5, 30);
    assert(v.size() == 5 && v[4] == 30);
    
    // 测试resize（缩小截断）
    v.resize(3);
    assert(v.size() == 3);
    
    print_vector(v, "v(resize后)");
    std::cout << "test03 测试通过！\n" << std::endl;
}

// 4. 测试insert/erase
void test04() {
    std::cout << "=== 测试insert/erase ===" << std::endl;
    yl::vector<int> v = {1, 2, 3, 4};
    
    // 测试insert
    v.insert(v.begin() + 1, 99);
    assert(v.size() == 5 && v[1] == 99);
    
    // 测试erase
    v.erase(v.begin() + 3);
    assert(v.size() == 4 && v[3] == 4);
    
    print_vector(v, "v(insert/erase后)");
    std::cout << "test04 测试通过！\n" << std::endl;
}

// 5. 测试operator[]访问
void test05() {
    std::cout << "=== 测试operator[] ===" << std::endl;
    yl::vector<int> v = {10, 20, 30};
    
    // 测试修改
    v[1] = 999;
    assert(v[1] == 999);
    
    // 测试常量对象访问
    const yl::vector<int> cv = {100, 200};
    assert(cv[0] == 100);
    
    std::cout << "test05 测试通过！\n" << std::endl;
}

// 6. 测试clear/swap
void test06() {
    std::cout << "=== 测试clear/swap ===" << std::endl;
    yl::vector<int> v = {1, 2, 3};
    
    // 测试clear（清空元素，保留容量）
    v.clear();
    assert(v.size() == 0 && v.capacity() != 0);
    
    // 测试swap
    yl::vector<int> v2 = {100, 200};
    v.swap(v2);  // 调用yl::vector的swap成员函数
    assert(v.size() == 2 && v[0] == 100);
    
    print_vector(v, "v(swap后)");
    std::cout << "test06 测试通过！\n" << std::endl;
}

// 7. 测试拷贝构造和赋值运算符
void test07() {
    std::cout << "=== 测试拷贝构造和赋值 ===" << std::endl;
    yl::vector<int> v = {10, 20, 30};
    
    // 测试拷贝构造
    yl::vector<int> v_copy(v);
    assert(v_copy.size() == 3 && v_copy[1] == 20);
    
    // 测试赋值运算符
    yl::vector<int> v_assign;
    v_assign = v;
    assert(v_assign.size() == 3 && v_assign[2] == 30);
    
    std::cout << "test07 测试通过！\n" << std::endl;
}

// 8. 测试析构函数（间接验证）
void test08() {
    std::cout << "=== 测试析构函数 ===" << std::endl;
    // 动态创建对象，手动析构（验证无崩溃）
    yl::vector<int>* v = new yl::vector<int>{1, 2, 3};
    delete v;  // 若析构函数有误，此处会崩溃
    std::cout << "test08 测试通过！\n" << std::endl;
}

int main() {
    // 依次执行所有测试
    test01();
    test02();
    test03();
    test04();
    test05();
    test06();
    test07();
    test08();
    
    std::cout << "所有测试执行完毕！" << std::endl;
    return 0;
}

1.代码优点：

1. 功能完整性：覆盖了自定义vector的核心功能，包括构造函数、元素操作、容量管理、迭代器、拷贝/赋值等，测试全面。
2. 模块化设计：采用test01()至test08()的封装方式，每个函数专注测试一类功能，逻辑清晰，便于维护和定位问题。
3. 边界条件验证：针对常见边界情况（如空容器、容量扩展、自赋值等）进行了测试，增强代码健壮性。
4. 命名空间管理：通过显式使用yl::vector而非展开命名空间，保持命名空间隔离，避免潜在冲突。
5. 异常安全测试：通过动态内存分配（如new/delete）验证析构函数的正确性，确保无内存泄漏。

2.潜在问题：

1. 原代码依赖问题：测试代码依赖原自定义vector实现，但原代码存在以下问题：
   • 拼写错误：_finsh应为_finish，v.finsh应为v._finish。
   • swap参数问题：swap(vector<T> v)采用值传递，会触发拷贝构造，建议改为引用传递swap(vector<T>& v)。
2. 测试覆盖不足：
   • 未测试移动构造函数和移动赋值运算符（若原代码实现了这些功能）。
   • 对迭代器失效场景（如插入/删除后迭代器是否失效）验证不足。
3. 断言局限性：依赖assert进行验证，在发布版本中可能被忽略，建议结合更完善的测试框架（如Google Test）。

3.优化建议：

1. 修正原代码问题：
   • 修复拼写错误和容量计算逻辑。
   • 将swap参数改为引用传递，避免不必要的拷贝。
2. 增强测试覆盖：
   • 添加移动语义测试（如std::move）。
   • 验证迭代器失效规则（如插入后原迭代器是否仍有效）。
3. 引入测试框架：使用专业测试框架替代简单的assert，提供更详细的测试报告和错误信息。
4. 性能测试：对关键操作（如扩容策略、批量插入）进行性能测试，确保符合预期。

4.总结：

该测试代码为自定义vector提供了全面的功能验证框架，结构清晰且模块化，但需注意原代码存在的拼写和逻辑错误。通过修正原代码问题并扩展测试覆盖，可以进一步提升代码质量和可靠性。