【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化

时间：2024-09-29 19:41:16

文章目录

  • 从零实现 C++ Vector
    • 前言
    • 1. 基本结构与初始化细分
      • 1.1 空构造函数的实现与测试
        • 实现代码：
        • 测试用例：
        • 输出：
      • 1.2 带大小和默认值的构造函数
        • 实现代码：
        • 测试用例：
        • 输出：
      • 1.3 拷贝构造函数
        • 实现代码：
        • 测试用例：
        • 输出：
      • 1.4 赋值操作符的实现
        • 实现代码：
        • 测试用例：
        • 输出：
    • 2. 容量管理的实现与测试
      • 2.1 `reserve`函数：动态扩容
        • 实现代码：
        • 测试用例：
        • 输出：
      • 2.2 `resize`函数：改变大小
        • 实现代码：
        • 测试用例：
        • 输出：
    • 3. 元素插入与删除
      • 3.1 `push_back`函数：向`vector`末尾插入元素
        • 3.1.1 需求分析
        • 实现思路
        • 实现代码：
        • 测试用例：
        • 输出：
      • 3.2 `pop_back`函数：删除末尾元素
        • 3.2.1 需求分析
        • 实现思路
        • 实现代码：
        • 测试用例：
        • 输出：
      • 3.3 `insert`函数：在指定位置插入元素
        • 3.3.1 需求分析
        • 实现思路
        • 实现代码：
        • 测试用例：
        • 输出：
      • 3.4 `erase`函数：删除指定位置的元素
        • 3.4.1 需求分析
        • 实现思路
        • 实现代码：
        • 测试用例：
        • 输出：
    • 4. `front`和`back`函数
      • 4.1 `front`函数：获取第一个元素
        • 4.1.1 需求分析
        • 实现代码：
        • 测试用例：
        • 输出：
      • 4.2 `back`函数：获取最后一个元素
        • 4.2.1 需求分析
        • 实现代码：
        • 测试用例：
        • 输出：
      • 5.1 `begin` 与 `end` 函数：迭代器的基本操作
        • 5.1.1 需求分析
        • 实现代码：
        • 测试用例：
        • 输出：
      • 5.2 `swap` 函数：交换两个 `vector`
        • 5.2.1 需求分析
        • 实现代码：
        • 测试用例：
        • 输出：
      • 5.3 赋值运算符重载：深拷贝 `vector`（现代写法）
        • 5.3.1 需求分析
        • 实现代码：
        • 现代写法说明
        • 测试用例：
        • 输出：
      • 5.4 优点总结
    • 写在最后

从零实现 C++ Vector

???? 欢迎讨论：学习过程中有问题吗？随时在评论区与我交流。你们的互动是我创作的动力！

???? 支持我：如果你觉得这篇文章对你有帮助，请点赞、收藏并分享给更多朋友吧！
???? 一起成长：欢迎分享给更多对计算机视觉和图像处理感兴趣的小伙伴，让我们共同进步！

前言

接上篇【C++篇】解密 STL 动态之魂：全面掌握 C++ vector 的高效与优雅
在现代 C++ 编程中，容器类 vector 是不可或缺的数据结构。作为一个动态数组，它提供了高效的随机访问和动态内存管理。为了加深对 vector 的理解，本文将从零开始模拟实现一个 vector，详细解析其核心机制。我们不仅会展示基础的构造、拷贝、扩展和元素插入操作，还将采用现代 C++ 的最佳实践来优化代码，尤其是在异常安全和性能上。

通过从浅入深的分步骤实现与测试，希望让读者能够全面掌握 vector 的核心逻辑与细节。本教程不仅适合初学者，也适合想深入理解 C++ STL 背后实现的开发者。

1. 基本结构与初始化细分

1.1 空构造函数的实现与测试

  • 实现一个空的vector，不分配任何内存。
  • 测试是否创建了容量为0的vector。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        typedef T* iterator;

        vector() : _start(nullptr), _finish(nullptr), _endOfStorage(nullptr) {}

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

    private:
        iterator _start;
        iterator _finish;
        iterator _endOfStorage;
    };
}
测试用例：
void TestEmptyVector() {
    W::vector<int> v;
    assert(v.size() == 0);  // 验证大小
    assert(v.capacity() == 0);  // 验证容量
    assert(v.empty());  // 验证是否为空
    std::cout << "TestEmptyVector passed" << std::endl;
}
输出：
TestEmptyVector passed

1.2 带大小和默认值的构造函数

  • 初始化一个给定大小的vector，并使用默认值填充。
  • 测试构造后大小、容量是否符合要求。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        typedef T* iterator;

        vector(size_t n, const T& value = T()) {
            _start = new T[n];
            _finish = _start + n;
            _endOfStorage = _finish;
            for (size_t i = 0; i < n; ++i) {
                _start[i] = value;  // 填充默认值
            }
        }

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

        T& operator[](size_t pos) { return _start[pos]; }

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

    private:
        iterator _start;
        iterator _finish;
        iterator _endOfStorage;
    };
}
测试用例：
void TestInitVector() {
    W::vector<int> v(5, 10);
    assert(v.size() == 5);  // 验证大小
    assert(v.capacity() == 5);  // 验证容量
    assert(!v.empty());  // 验证非空
    for (size_t i = 0; i < 5; ++i) {
        assert(v[i] == 10);  // 验证默认值
    }
    std::cout << "TestInitVector passed" << std::endl;
}
输出：
TestInitVector passed

1.3 拷贝构造函数

  • 实现vector的拷贝构造函数。
  • 测试拷贝后的vector是否完全复制原来的内容和容量。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        typedef T* iterator;

        vector(const vector<T>& v) {
            size_t n = v.size();
            _start = new T[n];
            _finish = _start + n;
            _endOfStorage = _finish;
            for (size_t i = 0; i < n; ++i) {
                _start[i] = v._start[i];  // 复制数据
            }
        }

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

        T& operator[](size_t pos) { return _start[pos]; }

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

    private:
        iterator _start;
        iterator _finish;
        iterator _endOfStorage;
    };
}
测试用例：
void TestCopyVector() {
    W::vector<int> v1(5, 10);
    W::vector<int> v2(v1);
    assert(v2.size() == 5);  // 验证大小
    assert(v2.capacity() == 5);  // 验证容量
    for (size_t i = 0; i < 5; ++i) {
        assert(v2[i] == 10);  // 验证数据拷贝
    }
    std::cout << "TestCopyVector passed" << std::endl;
}
输出：
TestCopyVector passed

1.4 赋值操作符的实现

  • 实现赋值操作符重载。
  • 测试两个vector赋值后，是否正确拷贝了内容和容量。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        typedef T* iterator;

        vector<T>& operator=(const vector<T>& v) {
            if (this != &v) {
                delete[] _start;  // 释放旧的空间
                size_t n = v.size();
                _start = new T[n];
                _finish = _start + n;
                _endOfStorage = _finish;
                for (size_t i = 0; i < n; ++i) {
                    _start[i] = v._start[i];  // 复制数据
                }
            }
            return *this;
        }

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

        T& operator[](size_t pos) { return _start[pos]; }

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

    private:
        iterator _start;
        iterator _finish;
        iterator _endOfStorage;
    };
}
测试用例：
void TestAssignVector() {
    W::vector<int> v1(5, 10);
    W::vector<int> v2 = v1;  // 赋值操作
    assert(v2.size() == 5);  // 验证大小
    assert(v2.capacity() == 5);  // 验证容量
    for (size_t i = 0; i < 5; ++i) {
        assert(v2[i] == 10);  // 验证数据拷贝
    }
    std::cout << "TestAssignVector passed" << std::endl;
}
输出：
TestAssignVector passed

2. 容量管理的实现与测试

2.1 reserve函数：动态扩容

  • 实现reserve函数，测试在容量不足时是否能正确扩展。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        void reserve(size_t n) {
            if (n > capacity()) {
                size_t oldSize = size();
                T* tmp = new T[n];
                for (size_t i = 0; i < oldSize; ++i) {
                    tmp[i] = _start[i];
                }
                delete[] _start;
                _start = tmp;
                _finish = _start + oldSize;
                _endOfStorage = _start + n;
            }
        }
    };
}
测试用例：
void TestReserveVector() {
    W::vector<int> v(5, 10);
    v.reserve(10);  // 预留容量
    assert(v.capacity() == 10);  // 验证容量扩展
    for (size_t i = 0; i < 5; ++i) {
        assert(v[i] == 10);  // 验证数据保持不变
    }
    std::cout << "TestReserveVector passed" << std::endl;
}
输出：
TestReserveVector passed

2.2 resize函数：改变大小

  • 实现resize函数，测试增加或减少vector大小。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        void resize(size_t n, const T& value = T()) {
            if (n < size()) {
                _finish = _start + n;  // 缩小大小
            } else {
                reserve(n);
                for (iterator it = _finish; it != _start + n; ++it)
			    {
                    *it = value;  // 填充新值
                }
                _finish = _start + n;
            }
        }
    };
}
测试用例：
void TestResizeVector() {
    W::vector<int> v(5, 10);
    v.resize(8, 20);  // 扩展大小并填充新值
    assert(v.size() == 8);  // 验证扩展后大小
    for (size_t i = 0; i < 5; ++i) {
        assert(v[i] == 10);  // 验证原值不变
    }
    for (size_t i = 5; i < 8; ++i) {
        assert(v[i] == 20);  // 验证新值
    }
    std::cout << "TestResizeVector passed" << std::endl;
}
输出：
TestResizeVector passed

3. 元素插入与删除

3.1 push_back函数：向vector末尾插入元素

3.1.1 需求分析
  • push_back是vector中最常用的操作之一。需要确保：
    • 当空间不足时，进行自动扩容。
    • 插入的元素位于现有元素的末尾。
实现思路
  1. 检查容量是否足够，若不足则扩容（通常容量加倍）。
  2. 将新元素插入到当前末尾。
  3. 更新_finish指针，指向新的末尾。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        void push_back(const T& x) {
            // 如果空间不足，扩展容量为当前容量的两倍
            if (_finish == _endOfStorage) {
                size_t newCapacity = capacity() == 0 ? 1 : capacity() * 2;
                reserve(newCapacity);
            }

            // 在末尾插入新元素
            *_finish = x;
            ++_finish;
        }

    private:
        T* _start;
        T* _finish;
        T* _endOfStorage;
    };
}
测试用例：
void TestPushBackVector() {
    W::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);

    assert(v.size() == 3);  // 验证插入后的大小
    assert(v.capacity() >= 3);  // 验证容量是否自动扩展
    assert(v[0] == 1 && v[1] == 2 && v[2] == 3);  // 验证插入的元素是否正确

    std::cout << "TestPushBackVector passed" << std::endl;
}
输出：
TestPushBackVector passed

3.2 pop_back函数：删除末尾元素

3.2.1 需求分析
  • pop_back用于删除vector中的最后一个元素。需要确保：
    • 删除后更新_finish指针。
    • 元素已经从逻辑上被移除，但空间不回收。
实现思路
  1. 将_finish指针向前移动一位，即删除最后一个元素。
  2. 不释放空间。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        void pop_back() {
            assert(_finish != _start);  // 确保vector非空
            --_finish;  // 逻辑删除最后一个元素
        }

    private:
        T* _start;
        T* _finish;
        T* _endOfStorage;
    };
}
测试用例：
void TestPopBackVector() {
    W::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3)

相关文章