【C++】 vector（代码实现+坑点讲解）

作为C标准模板库STL中最基础、最常用的容器之一vector提供了动态数组的功能。今天我们将深入探讨如何从零实现一个完整的vector容器理解其内部工作原理和设计思想。代码解释C Vector模板类实现代码整体功能和主要作用C动态数组vector模板类实现其主要功能包括动态数组管理自动扩容的动态数组容器类型安全通过模板支持任意类型内存管理自动内存分配和释放迭代器支持提供随机访问迭代器STL风格接口与标准库vector类似的接口一. 主要功能模块分析1.1 核心设计思想我们的vector实现基于以下核心思想动态连续内存元素在内存中连续存储支持随机访问三指针模型通过三个指针管理内存区间指数扩容策略避免频繁内存分配RAII原则构造函数分配析构函数释放1.2 类定义框架#pragma once #includeassert.h #include initializer_list namespace wxx { templateclass T class vector { public: // 类型定义 typedef T* iterator; typedef const T* const_iterator; private: // 三指针模型 iterator _start nullptr; // 起始位置 iterator _finish nullptr; // 有效元素末尾的下一个位置 iterator _endofstorage nullptr; // 分配内存的末尾 // ... 成员函数实现 }; }二、迭代器设计与实现在C中迭代器是抽象化的指针。对于vector由于内存连续我们可以直接用原生指针作为迭代器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; }三、构造函数家族3.1 多种构造方式// 默认构造 vector() default; // 初始化列表构造C11特性 vector(std::initializer_listT il) { reserve(il.size()); for (auto e : il) { push_back(e); } } // 拷贝构造 vector(const vectorT v) { reserve(v.capacity()); // 预分配足够空间 for (auto e : v) { push_back(e); // 深拷贝每个元素 } } // 迭代器范围构造 templateclass InputIterator, typename std::enable_if!std::is_integralInputIterator::value, int::type 0 vector(InputIterator first, InputIterator last) { while (first ! last) { push_back(*first); first; } } // 指定数量和值的构造 vector(size_t n, T val T()) { resize(n, val); }3.2 SFINAE技术应用注意迭代器范围构造函数中的特殊语法templateclass InputIterator, typename std::enable_if!std::is_integralInputIterator::value, int::type 0这是SFINAE(Substitution Failure Is Not An Error)技术的应用。其作用是当InputIterator是整数类型时模板替换失败编译器会选择vector(size_t n, T val)构造函数避免了构造函数的歧义调用四、内存管理与扩容策略4.1 reserve函数实现void reserve(size_t n) { if (n capacity()) { size_t old_size size(); T* tmp new T[n]; // 1. 分配新内存 if (_start) // 2. 拷贝旧数据 { for (size_t i 0; i old_size; i) { tmp[i] _start[i]; // 调用T的拷贝赋值运算符 } delete[] _start; // 3. 释放旧内存 } // 4. 更新指针 _start tmp; _finish _start old_size; _endofstorage _start n; } }关键点先分配再拷贝最后释放保证异常安全使用循环而不是memcpy确保调用正确的拷贝赋值运算符正确处理从无到有的情况4.2 push_back与扩容策略void push_back(const T x) { if (_finish _endofstorage) // 需要扩容 { // 指数增长策略 reserve(capacity() 0 ? 4 : capacity() * 2); } *_finish x; // 在末尾构造元素 _finish; // 更新大小 }五、元素操作实现5.1 insert操作详解iterator insert(iterator pos, const T x) { // 1. 检查位置有效性 assert(pos _start); assert(pos _finish); // 2. 检查是否需要扩容 if (_finish _endofstorage) { // 记录偏移量扩容后迭代器会失效 size_t len pos - _start; reserve(capacity() 0 ? 4 : capacity() * 2); pos _start len; // 重新计算位置 } // 3. 向后移动元素 iterator end _finish - 1; while (end pos) { *(end 1) *end; // 向后移动一位 --end; } // 4. 插入新元素 *pos x; _finish; return pos; // 返回新插入元素的位置 }迭代器失效问题扩容会导致所有迭代器失效需要重新计算插入位置返回新的迭代器让调用者可以继续使用5.2 erase操作实现iterator erase(iterator pos) { assert(pos _start); assert(pos _finish); // 向前移动元素覆盖要删除的元素 iterator it pos 1; while (it ! _finish) { *(it - 1) *it; it; } --_finish; // 减少大小 return pos; // 返回被删除元素的位置 }六、拷贝控制与异常安全6.1 拷贝并交换技术// 拷贝赋值运算符 vectorT operator(vectorT v) // 注意传值参数 { swap(v); // 交换当前对象和临时对象 return *this; // v离开作用域自动调用析构函数释放原资源 }6.2 swap函数实现void swap(vectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); }特点O(1)时间复杂度不抛出异常假设std::swap不抛异常交换的是指针不是实际数据七、完整代码实现以下是完整的vector实现代码#pragma once #includeassert.h #include initializer_list #include type_traits // 需要包含这个头文件 namespace wxx { templateclass 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(std::initializer_listT il) { reserve(il.size()); for (auto e : il) { push_back(e); } } // 拷贝构造函数 vector(const vectorT v) { reserve(v.capacity()); for (auto e : v) { push_back(e); } } // 交换函数 void swap(vectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } // 赋值运算符拷贝并交换 vectorT operator(vectorT v) { swap(v); return *this; } // 迭代器范围构造函数使用SFINAE templateclass InputIterator, typename std::enable_if!std::is_integralInputIterator::value, int::type 0 vector(InputIterator first, InputIterator last) { while (first ! last) { push_back(*first); first; } } // 指定数量和值的构造函数 vector(size_t n, T val T()) { resize(n, val); } // 析构函数 ~vector() { if (_start) { delete[] _start; _start _finish _endofstorage nullptr; } } // 容量管理 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 resize(size_t n, T val T()) { if (n size()) { reserve(n); while (_finish ! _start n) { *_finish val; _finish; } } else { _finish _start n; } } // 元素访问 T operator[](size_t i) { assert(i size()); return _start[i]; } const T operator[](size_t i) const { assert(i size()); return _start[i]; } // 容量查询 void clear() { _finish _start; } size_t size() const { return _finish - _start; } size_t capacity() const { return _endofstorage - _start; } bool empty() const { return _start _finish; } // 元素操作 void push_back(const T x) { if (_finish _endofstorage) { reserve(capacity() 0 ? 4 : capacity() * 2); } *_finish x; _finish; } void pop_back() { assert(!empty()); --_finish; } iterator insert(iterator pos, const T x) { assert(pos _start); assert(pos _finish); if (_finish _endofstorage) { size_t len pos - _start; reserve(capacity() 0 ? 4 : capacity() * 2); pos _start len; } iterator end _finish - 1; while (end pos) { *(end 1) *end; --end; } *pos x; _finish; return pos; } iterator erase(iterator pos) { assert(pos _start); assert(pos _finish); iterator it pos 1; while (it ! _finish) { *(it - 1) *it; it; } --_finish; return pos; } private: iterator _start nullptr; iterator _finish nullptr; iterator _endofstorage nullptr; }; } // namespace wxx八、测试示例源码分享vector模拟实现 · 9f00357 · 加油少年/CCCCC - Gitee.comhttps://gitee.com/wxx547803_0/ccccc/commit/9f003570389e26bca34c5e62f3ba31da2005c3a1