【C++】手动实现C++ vector容器：深入理解动态数组的工作原理
💯个人主页: 起名字真南
💯个人专栏:【数据结构初阶】 【C语言】 【C++】 【OJ题解】
目录
- 1. 引言
- 2. 实现思路
- 3. `vector` 容器的代码实现
- 4. 代码详解
- 4.1 构造与析构函数
- 4.2 容量管理
- 4.3 迭代器与访问操作
- 4.4 增删操作
- 5.测试代码
- 6. 时间和空间复杂度分析
- 7. 总结
1. 引言
vector是 C++ 标准模板库（STL）中最常用的动态数组容器。它不仅提供了自动扩容、快速访问、灵活增删等功能，还能高效地管理内存。本篇文章将带大家实现一个简化版的vector，包含动态扩容、元素插入删除、访问等操作，以此深入理解其内部实现原理，尤其是动态数组的管理机制。
2. 实现思路
我们将实现的 vector 具有如下核心功能：
- 构造与析构：支持多种方式的构造，并在对象销毁时正确释放内存。
- 容量管理：包括扩容、调整大小等操作。
- 元素增删：支持尾部增删以及在任意位置插入删除元素。
- 迭代器与访问操作：提供迭代器和下标访问方式。
3. vector 容器的代码实现
以下是完整的代码实现，功能完备，包含了构造、析构、拷贝、赋值重载、容量管理、增删操作和元素访问等基本操作：
#pragma once
#include <iostream>
#include <assert.h>
namespace wzr
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
// 默认构造函数
vector()
: _start(nullptr)
, _finish(nullptr),
_endOfStorage(nullptr)
{}
// 构造函数：构造n个value
vector(size_t n, const T& value = T())
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
reserve(n);
while (n--)
{
push_back(value);
}
//其实我们会发现这两串代码会有一些冗余，当我们使用vector(10,1)
//编译器在编译的时候就已经将T实例化成int类型，
//并且编译器会认为10，1是int，如果两个类型一致就会选择是区间构造，会报错。
vector(int n, const T & value = T())
:_start(new T[n])
, _finish(_start + n)
, _endOfStorage(_finish)
{
reserve(n);
for (int i = 0; i < n; i++)
{
_start[i] = value;
}
}
// 拷贝构造函数
vector(const vector<T>& v)
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
reserve(v.capacity());
iterator it = begin();
const_iterator vit = v.cbegin();
while (vit != v.cend()) {
*it++ = *vit++;
}
_finish = it;
}
//如果使用iterator作为迭代器进行区间初始化构造，
//那么容器就是能是vector
//重新声明迭代器，迭代区间[first, last)可以是任意容量的迭代器
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
// 赋值操作符重载（采用拷贝交换优化）
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
// 析构函数
~vector() {
if (_start)
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
}
// 迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator cbegin() const
{
return _start;
}
const_iterator cend() const
{
return _finish;
}
// 容量管理
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endOfStorage - _start;
}
bool empty() const
{
return _start == _finish;
}
// 预留空间
void reserve(size_t n)
{
if (n > capacity()) {
size_t oldSize = size();
T* tmp = new T[n];
if (_start) {
for (size_t i = 0; i < oldSize; i++) {
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + oldSize;
_endOfStorage = _start + n;
}
}
// 改变大小
void resize(size_t n, const T& value = T())
{
if (n <= size()) {
_finish = _start + n;
} else {
if (n > capacity()) {
reserve(n);
}
iterator it = _finish;
_finish = _start + n;
while (it != _finish) {
*it = value;
it++;
}
}
}
// 元素访问
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
T& front()
{
return *_start;
}
const T& front() const
{
return *_start;
}
T& back()
{
return *(_finish - 1);
}
const T& back() const
{
return *(_finish - 1);
}
// 增删操作
void push_back(const T& value)
{
insert(end(), value);
}
void pop_back()
{
erase(end() - 1);
}
// 交换两个vector
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endOfStorage, v._endOfStorage);
}
// 插入
iterator insert(iterator pos, const T& x)
{
assert(pos <= _finish);
if (_finish == _endOfStorage) {
size_t newcapacity = (capacity() == 0 ? 1 : 2 * capacity());
reserve(newcapacity);
pos = _start + size();
}
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
// 删除
iterator erase(iterator pos)
{
iterator begin = pos + 1;
while (begin != end())
{
*(begin - 1) = *begin;
begin++;
}
--_finish;
return pos;
}
private:
iterator _start; // 数据起始指针
iterator _finish; // 有效数据的结束指针
iterator _endOfStorage; // 总容量的结束指针
};
}
4. 代码详解
4.1 构造与析构函数
vector()：默认构造函数，初始化指针为nullptr，用于构造空的vector。vector(size_t n, const T& value = T())：构造一个大小为n的vector，并用value初始化每个元素。调用reserve(n)分配空间，再通过push_back插入元素。vector(const vector<T>& v)：拷贝构造函数。分配与v相同的空间后，逐个拷贝v中的元素。vector(InputIterator first,InputIterator last):使用迭代器区间去构造函数。~vector()：析构函数。释放动态分配的内存，并将所有指针置为nullptr。
4.2 容量管理
reserve(size_t n)：扩容函数。若n大于当前容量，则分配一个大小为n的新空间，将原数据拷贝至新空间，并释放旧空间。resize(size_t n, const T& value = T())：调整vector大小。若n小于当前大小，则只需调整_finish。若n大于容量，则扩容并初始化新增元素。
4.3 迭代器与访问操作
begin()和end()：返回_start和_finish，用于迭代vector。operator[]：通过下标访问元素，并通过assert检查越界访问。front()和back()：返回首尾元素的引用，支持首尾元素的快速访问。
4.4 增删操作
push_back(const T& value)：在尾部插入元素value。若容量不足，调用reserve扩容。pop_back()：删除最后一个元素，通过调整_finish指针实现。insert(iterator pos, const T& x)：在指定位置插入元素x。若容量不足，则扩容；随后将[pos, end)的数据右移，腾出插入位置。erase(iterator pos)：删除指定位置的元素。将[pos + 1, end)的数据左移一位以覆盖删除位置，更新_finish指针。
5.测试代码
#include"Vector.h"
namespace wzr
{
void Test01()
{
vector<int> v1;
vector<int> v2(10, 6);
int array[] = { 1,2,3,4,5 };
vector<int> v3(array, array + sizeof(array) / sizeof(array[0]));
vector<int> v4(v3);
for (size_t i = 0; i < v2.size(); i++)
{
cout << v2[i] << " ";
}
cout << endl;
auto it = v3.begin();
while (it != v3.end())
{
cout << *it << " ";
it++;
}
cout << endl;
for (auto itt : v4)
{
cout << itt << " ";
}
cout << endl;
}
void Test02()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
cout << v.size() << endl;
cout << v.capacity() << endl;
cout << v.front() << endl;
cout << v.back() << endl;
cout << v[0] << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.pop_back();
v.pop_back();
v.insert(v.begin(), 0);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.erase(v.begin() + 1);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
}
int main()
{
//wzr::Test01();
wzr::Test02();
return 0;
}
6. 时间和空间复杂度分析
push_back：均摊时间复杂度为O(1)，因为扩容后插入操作是常数时间的。pop_back：O(1)。resize：O(n)。insert和erase：最坏情况时间复杂度为O(n)，因为需要移动大量数据。
7. 总结
通过对各个函数的详细解析，我们手动实现了一个简化版的 vector，展示了 C++ 标准库中 vector 的核心功能。希望通过这篇文章，大家能更好地理解 vector 容器