C++ vector容器底层深度剖析与模拟实现代码示例
<div id="navCategory"><h5 class="catalogue">目录</h5><ul class="first_class_ul"><li>1 模板的使用说明</li><li>2 vector深度剖析及模拟实现</li><ul class="second_class_ul"><li>2.1 vector的成员变量</li><li>2.2 构造函数</li><ul class="third_class_ul"><li>2.2.1 指定大小和初始值的构造函数</li><li>2.2.2 迭代器范围构造函数</li><li>2.2.3 拷贝构造函数（现代写法）</li></ul><li>2.3 赋值运算符重载</li><ul class="third_class_ul"></ul><li>2.4 容量相关操作</li><ul class="third_class_ul"><li>2.4.1 reserve 开空间</li><li>2.4.2 用resize 调整大小</li><li>2.4.3 size和capacity</li></ul><li>2.5 元素访问操作</li><ul class="third_class_ul"><li>2.5.1 下标运算符</li></ul><li>2.6 修改操作</li><ul class="third_class_ul"><li>2.6.1 push_back 尾部添加元素</li><li>2.6.2 pop_back 尾部删除元素</li><li>2.6.3 insert 在指定位置插入元素</li><li>2.6.4 erase 删除指定位置元素</li></ul></ul><li>3 vector迭代器失效问题</li><ul class="second_class_ul"><li>3.1 insert失效问题</li><ul class="third_class_ul"></ul><li>3.2 erase失效问题</li><ul class="third_class_ul"></ul><li>3.3 删除所有的偶数</li><ul class="third_class_ul"></ul><li>3.4 不同编译器对迭代器失效的检查</li><ul class="third_class_ul"></ul><li>3.5 扩容之后，迭代器已经失效了</li><ul class="third_class_ul"></ul><li>3.6 erase删除的迭代器如果是最后一个元素</li><ul class="third_class_ul"></ul><li>3.7 string的迭代器失效</li><ul class="third_class_ul"></ul></ul><li>4 本文代码完整展示</li><ul class="second_class_ul"><li>（一）vector.h</li><ul class="third_class_ul"></ul><li>（二）Test.c</li><ul class="third_class_ul"></ul></ul><li>总结</li><ul class="second_class_ul"></ul></ul></div><p class="maodian"></p><h2>1 模板的使用说明</h2><p>在C++中，模板是实现<strong>泛型编程</strong>的重要工具，它允许我们编写与数据类型无关的代码。vector容器正是通过模板技术实现的，可以存储任意类型的数据：</p>
<div class="jb51code"><pre class="brush:cpp;">template<class T>
class vector
{
// ... 实现细节
};</pre></div>
<p>这里的<code>T</code>是类型参数，当我们创建vector对象时，需要指定具体的类型</p>
<div class="jb51code"><pre class="brush:cpp;">vector<int> intVector; // 存储int类型的vector
vector<string> strVector; // 存储string类型的vector
vector<double> dblVector; // 存储double类型的vector</pre></div>
<p>模板的使用让vector具有了极强的<strong>通用性</strong>，可以容纳各种数据类型，从基本类型到自定义类类型。</p>
<p class="maodian"></p><h2>2 vector深度剖析及模拟实现</h2>
<p class="maodian"></p><h3>2.1 vector的成员变量</h3>
<p>vector底层使用动态数组实现，通过<strong>三个指针</strong>来管理内存：</p>
<div class="jb51code"><pre class="brush:cpp;">private:
iterator _start = nullptr; // 指向数组的开始位置
iterator _finish = nullptr; // 指向最后一个元素的下一个位置
iterator _end_of_storage = nullptr; // 指向分配内存的末尾</pre></div>
<p>在这里，给了三个指针缺省值nullptr初始化。</p>
<p class="maodian"></p><h3>2.2 构造函数</h3>
<p>vector提供了多种构造函数来满足不同的初始化需求：、</p>
<p class="maodian"></p><h4>2.2.1 指定大小和初始值的构造函数</h4>
<div class="jb51code"><pre class="brush:cpp;">vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}</pre></div>
<p>使用示例：</p>
<div class="jb51code"><pre class="brush:cpp;">vector<int> v1(5); // 包含5个0的vector
vector<int> v2(3, 10); // 包含3个10的vector
vector<string> v3(2, "hello"); // 包含2个"hello"的vector</pre></div>
<p class="maodian"></p><h4>2.2.2 迭代器范围构造函数</h4>
<div class="jb51code"><pre class="brush:cpp;">template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}</pre></div>
<p>这个构造函数是函数模板，可以接受任意类型的迭代器：</p>
<div class="jb51code"><pre class="brush:cpp;">int arr[] = {1, 2, 3, 4, 5};
vector<int> v1(arr, arr + 5); // 从数组构造
vector<int> v2(v1.begin(), v1.end()); // 从另一个vector构造</pre></div>
<p class="maodian"></p><h4>2.2.3 拷贝构造函数（现代写法）</h4>
<div class="jb51code"><pre class="brush:cpp;">vector(const vector<T>& v)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}</pre></div>
<p>现代写法通过创建临时对象并交换资源，代码简洁且异常安全~</p>
<p class="maodian"></p><h3>2.3 赋值运算符重载</h3>
<div class="jb51code"><pre class="brush:cpp;">vector<T>& operator=(vector<T> tmp)
{
swap(tmp);
return *this;
}</pre></div>
<p class="maodian"></p><h3>2.4 容量相关操作</h3>
<p class="maodian"></p><h4>2.4.1 reserve 开空间</h4>
<div class="jb51code"><pre class="brush:cpp;">void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T;
if (_start)
{
for (size_t i = 0; i < sz; i++)
{
std::swap(tmp, _start);
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}</pre></div>
<ul><li><p>使用<code>std::swap</code>而不是直接赋值，这样可以高效地交换资源（）</p></li><li><p>如果直接使用<code>memcpy</code>，对于管理资源的类（如string）会导<strong>致浅拷贝</strong>问题！</p></li><li><p>重新计算<code>_finish</code>和<code>_end_of_storage</code>指针</p></li></ul>
<p class="maodian"></p><h4>2.4.2 用resize 调整大小</h4>
<div class="jb51code"><pre class="brush:cpp;">void resize(size_t n, T val = T())
{
if (n < size())
{
// 缩小size，只是移动_finish指针
_finish = _start + n;
}
else
{
reserve(n);// 可能需要扩容
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}</pre></div>
<p>这里使用<strong>匿名对象</strong>做缺省参数。</p>
<p>使用示例：</p>
<div class="jb51code"><pre class="brush:cpp;">vector<int> v = {1, 2, 3};
v.resize(5); // 变为 {1, 2, 3, 0, 0}
v.resize(2); // 变为 {1, 2}</pre></div>
<p class="maodian"></p><h4>2.4.3 size和capacity</h4>
<div class="jb51code"><pre class="brush:cpp;">size_t capacity() const
{
return _end_of_storage - _start;
}
size_t size() const
{
return _finish - _start;
}</pre></div>
<p class="maodian"></p><h3>2.5 元素访问操作</h3>
<p class="maodian"></p><h4>2.5.1 下标运算符</h4>
<div class="jb51code"><pre class="brush:cpp;">T& operator[](size_t i)
{
assert(i < size());
return _start;
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start;
}</pre></div>
<p>提供const和非const版本，支持<strong>读写访问</strong>和<strong>只读访问</strong>。</p>
<p class="maodian"></p><h3>2.6 修改操作</h3>
<p class="maodian"></p><h4>2.6.1 push_back 尾部添加元素</h4>
<div class="jb51code"><pre class="brush:cpp;">void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}</pre></div>
<p>扩容策略：初始为0时分配4个元素空间，否则每次扩容为原来的2倍。</p>
<p class="maodian"></p><h4>2.6.2 pop_back 尾部删除元素</h4>
<div class="jb51code"><pre class="brush:cpp;">void pop_back()
{
assert(!empty());
--_finish;
}</pre></div>
<p class="maodian"></p><h4>2.6.3 insert 在指定位置插入元素</h4>
<div class="jb51code"><pre class="brush:cpp;">iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
// 扩容
if (_finish == _end_of_storage)
{
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;
}</pre></div>
<p>扩容后需要<strong>重新计算</strong>pos的位置，因为_start可能改变了。</p>
<p class="maodian"></p><h4>2.6.4 erase 删除指定位置元素</h4>
<div class="jb51code"><pre class="brush:cpp;">iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}</pre></div>
<p class="maodian"></p><h2>3 vector迭代器失效问题</h2>
<p>迭代器失效是使用vector时需要特别注意的问题，不当使用会导致未定义行为。</p>
<p class="maodian"></p><h3>3.1 insert失效问题</h3>
<p>当在vector中插入元素时，如果引起扩容，所有迭代器都会失效。</p>
<div class="jb51code"><pre class="brush:cpp;">void test_vector2()
{
bit::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
auto it = v.begin() + 3;
v.insert(v.begin(), 0);// 可能引起扩容
// insert以后，it失效了，不能再使用
// *it = 10;// 错误！未定义行为
}</pre></div>
<p class="maodian"></p><h3>3.2 erase失效问题</h3>
<p>erase操作会使被删除元素及其后面所有元素的迭代器失效。</p>
<div class="jb51code"><pre class="brush:cpp;">void test_vector3()
{
bit::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
auto it = v.begin() + 2;
v.erase(v.begin());// 删除第一个元素
// it失效了，不能访问，访问结果未定义
// cout << *it << endl;// 错误！
}</pre></div>
<p class="maodian"></p><h3>3.3 删除所有的偶数</h3>
<p>正确使用erase删除元素的模式：</p>
<div class="jb51code"><pre class="brush:cpp;">void test_vector4()
{
bit::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
// 正确做法：接收erase的返回值
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);// erase返回下一个有效迭代器
}
else
{
++it;
}
}
// 错误做法：直接递增迭代器
// auto it = v.begin();
// while (it != v.end())
// {
// if (*it % 2 == 0)
// {
// v.erase(it);// erase后it失效
// }
// ++it;// 错误：对失效迭代器递增
// }
}</pre></div>
<p class="maodian"></p><h3>3.4 不同编译器对迭代器失效的检查</h3>
<p>不同编译器对迭代器失效的检查严格程度不同：</p>
<ul><li><p>Debug模式下通常会进行严格的迭代器检查</p></li><li><p>Release模式下可能没有检查，导致难以发现的bug</p></li><li><p>Linux的gcc编译器检查就会比较宽松</p></li></ul>
<p class="maodian"></p><h3>3.5 扩容之后，迭代器已经失效了</h3>
<div class="jb51code"><pre class="brush:cpp;">vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4);// 可能引起扩容
// it已经失效，不能再使用</pre></div>
<p class="maodian"></p><h3>3.6 erase删除的迭代器如果是最后一个元素</h3>
<div class="jb51code"><pre class="brush:cpp;">vector<int> v = {1, 2, 3};
auto it = v.begin() + 2;// 指向3
it = v.erase(it); // 删除最后一个元素
// 此时it == v.end()，不能解引用</pre></div>
<p class="maodian"></p><h3>3.7 string的迭代器失效</h3>
<p>与vector类似，string在插入、扩容操作、erase之后，迭代器也会失效。</p>
<p class="maodian"></p><h2>4 本文代码完整展示</h2>
<p class="maodian"></p><h3>（一）vector.h</h3>
<div class="jb51code"><pre class="brush:cpp;">#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace bit
{
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(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
vector(int n, const T& val = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
// 迭代器范围构造函数
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
// 默认构造函数
vector() = default;
// 拷贝构造函数（现代写法）
vector(const vector<T>& v)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
// 赋值运算符（现代写法）
vector<T>& operator=(vector<T> tmp)
{
swap(tmp);
return *this;
}
// 交换两个vector
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
// 清空元素
void clear()
{
_finish = _start;
}
// 判断是否为空
bool empty() const
{
return _start == _finish;
}
// 预留空间
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T;
if (_start)
{
for (size_t i = 0; i < sz; i++)
{
std::swap(tmp, _start);
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
// 调整大小
void resize(size_t n, T val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}
// 获取容量
size_t capacity() const
{
return _end_of_storage - _start;
}
// 获取元素个数
size_t size() const
{
return _finish - _start;
}
// 下标运算符
T& operator[](size_t i)
{
assert(i < size());
return _start;
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start;
}
// 尾部添加元素
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
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 == _end_of_storage)
{
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;
}
// 析构函数
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}</pre></div>
<p class="maodian"></p><h3>（二）Test.c</h3>
<div class="jb51code"><pre class="brush:cpp;">#include "vector.h"
#include <iostream>
using namespace std;
namespace bit
{
// 打印vector内容
void Print(const vector<int>& v)
{
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
// 测试基本操作
void test_vector1()
{
cout << "测试基本操作:" << endl;
bit::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v++;// 修改第一个元素
Print(v);
// 范围for遍历
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
// 测试insert操作
void test_vector2()
{
cout << "\n测试insert操作:" << endl;
bit::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
Print(v);
v.insert(v.begin(), 0);// 头部插入
Print(v);
// 注意：insert后迭代器可能失效
auto it = v.begin() + 3;
v.insert(it, 30);// 指定位置插入
Print(v);
}
// 测试erase操作
void test_vector3()
{
cout << "\n测试erase操作:" << endl;
bit::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
Print(v);
v.erase(v.begin());// 删除第一个元素
Print(v);
auto it = v.begin() + 2;
v.erase(it);// 删除指定位置元素
Print(v);
}
// 测试删除特定元素（删除所有偶数）
void test_vector4()
{
cout << "\n测试删除所有偶数:" << endl;
bit::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
cout << "删除前: ";
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
// 正确删除方法
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);// 接收erase返回值
}
else
{
++it;
}
}
cout << "删除后: ";
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
// 测试resize操作
void test_vector5()
{
cout << "\n测试resize操作:" << endl;
bit::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
cout << "原始vector: ";
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.resize(3);// 缩小
cout << "resize(3): ";
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.resize(20, 5);// 扩大并填充
cout << "resize(20, 5): ";
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
// 测试拷贝构造和赋值
void test_vector6()
{
cout << "\n测试拷贝构造和赋值:" << endl;
bit::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.push_back(6);
cout << "v1: ";
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
// 拷贝构造
bit::vector<int> v2(v1);
cout << "v2(拷贝v1): ";
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
// 赋值操作
bit::vector<int> v3 = {10, 20, 30, 40};
v1 = v3;
cout << "v1(赋值后): ";
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
// 指定大小构造
bit::vector<int> v4(10, 1);
cout << "v4(10个1): ";
for (auto e : v4)
{
cout << e << " ";
}
cout << endl;
bit::vector<char> v5(10, 'x');
cout << "v5(10个x): ";
for (auto e : v5)
{
cout << e << " ";
}
cout << endl;
}
// 测试string类型vector
void test_vector7()
{
cout << "\n测试string类型vector:" << endl;
bit::vector<string> v1;
v1.push_back("111111111111111111111111");
v1.push_back("222222222222222222222222");
v1.push_back("333333333333333333333333");
v1.push_back("444444444444444444444444");
v1.push_back("555555555555555555555555");
for (auto& e : v1)
{
cout << e << " ";
}
cout << endl;
}
}
int main()
{
bit::test_vector1();
bit::test_vector2();
bit::test_vector3();
bit::test_vector4();
bit::test_vector5();
bit::test_vector6();
bit::test_vector7();
return 0;
}</pre></div>
<p>C++ vector基于动态数组实现，通过三个指针管理内存。核心风险是迭代器失效：insert可能扩容使所有迭代器失效；erase使被删位置后迭代器失效，必须通过it=erase(it)接收返回值。采用2倍扩容策略，现代写法通过swap实现安全拷贝。连续存储支持高效随机访问，但需警惕迭代器失效这一主要陷阱。</p>
<p class="maodian"></p><h2>总结</h2>
<p>到此这篇关于C++ vector容器底层深度剖析与模拟实现的文章就介绍到这了,更多相关C++ vector容器底层内容请搜索琼殿技术社区以前的文章或继续浏览下面的相关文章希望大家以后多多支持琼殿技术社区！</p>
<div class="art_xg">
<b>您可能感兴趣的文章:</b><ul><li>C++入门之vector的底层实现详解</li><li>C++学习笔记std::vector底层原理及扩容</li><li>C++中的vector使用详解及重要部分底层实现</li></ul>
</div>
</div>
<!--endmain-->
頁:
[1]