目录
在C++标准库中， vector 是一个非常常用的动态数组容器，它能够自动管理内存，并且提供了丰富的操作接口。本文将通过分析一段手写 vector 的核心代码，深入理解 vector 的底层实现原理。
整体结构概述
我们实现的 vector 类模板主要包含以下几个关键部分：
1. 数据成员：用于管理动态数组的内存和元素范围。
2. 赋值运算符重载：实现对象之间的赋值操作。
3. 下标运算符重载：支持通过 [] 访问元素。
4. 内存管理函数： reserve 和 resize 用于控制动态数组的容量和大小。
5. 元素访问函数： front 和 back 用于获取容器的首元素和尾元素。
6. 插入和删除操作： push_back 、 pop_back 、 insert 和 erase 用于元素的增删。
cpp
template <typename T>
class vector {
private:
iterator _start; // 指向动态数组起始位置
iterator _finish; // 指向最后一个有效元素的下一个位置
iterator _end_of_storage; // 指向动态数组容量的末尾位置
public:
typesdef T* iterator;
typesdef const T* const_iterator;
// 以下是具体成员函数的实现
};
赋值运算符重载
cpp
vector<T>& operator=(vector<T>& v) {
swap(v);
return *this;
}现代化写法
该函数实现了 vector 对象之间的赋值操作。通过调用 swap 函数交换当前对象和传入对象的内部数据（ _start 、 _finish 和 _end_of_storage ），从而高效地完成赋值。 swap 函数的具体实现通常会交换两个对象的资源，而不是逐个复制元素，这样可以提高效率。
下标运算符重载
cpp
T& operator[](size_t pos) {
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const {
assert(pos < size());
return _start[pos];
}这两个函数实现了通过 [] 操作符访问 vector 中的元素。第一个函数是非 const 版本，用于修改元素；第二个函数是 const 版本，用于在 const vector 对象上读取元素。通过 assert 确保访问的下标在有效范围内，防止越界访问。
内存管理函数
reserve 函数
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
t* tmp = new t[n];
if (_start)
{
//memcpy(_tmp,_start,sizeof(T)*sz);
for (size_t i = 0;i < sz;i++)
{
tmp[i] = _start[i];
}
delete[]_start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
reserve 函数用于确保 vector 的容量至少为 n 。如果 n 大于当前容量，会分配一块新的更大的内存，将原有的元素逐个复制到新内存中，然后释放旧内存，并更新 _start 、 _finish 和 _end_of_storage 指针。
resize 函数
cpp
void resize(size_t n, const T& val = T()) {
if (n < size()) {
_finish = _start + n;
} else {
reserve(n);
while (_finish != _start + n) {
*_finish = val;
++_finish;
}
}
}
resize 函数用于改变 vector 的大小。如果 n 小于当前大小，会截断 vector ；如果 n 大于当前大小，会先调用 reserve 确保有足够的容量，然后将新增位置初始化为 val 。
元素访问函数
front 函数
cpp
T& front() {
return *_start;
}
const T& front() const {
return *_start;
}
front 函数用于获取 vector 的首元素。非 const 版本允许修改首元素， const 版本则用于在 const vector 对象上获取首元素。
back 函数
cpp
T& back() {
return *(_finish - 1);
}
const T& back() const {
return *(_finish - 1);
}back 函数用于获取 vector 的尾元素。同样分为非 const 和 const 版本，分别用于修改和读取尾元素。
插入和删除操作
push_back 函数
cpp
void push_back(const T& x) {
insert(end(), x);
}push_back 函数在 vector 的末尾插入一个元素，它通过调用 insert 函数实现。
pop_back 函数
cpp
void pop_back() {
erase(end() - 1);
}pop_back 函数删除 vector 的尾元素，通过调用 erase 函数实现。
erase 函数
cpp
iterator erase(iterator pos) {
iterator begin = pos + 1;
while (begin != _finish) {
*(begin - 1) = *begin;
++begin;
}
_finish--;
return pos;
}
erase 函数删除指定位置的元素。通过将该位置之后的元素逐个向前移动，覆盖要删除的元素，然后更新 _finish 指针。
insert 函数
cpp
iterator insert(iterator pos, const T& x) {
assert(pos <= _finish);
if (_finish == _end_of_storage) {
size_t len = pos - _start;
size_t new_cap = (capacity() == 0) ? 4 : capacity() * 2;
reserve(new_cap);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
end--;
}
*pos = x;
_finish++;
return pos;
}
insert 函数在指定位置插入一个元素。如果当前容量已满，会先调用 reserve 扩大容量，然后将插入位置之后的元素逐个向后移动，腾出空间插入新元素，并更新 _finish 指针。
通过以上代码的实现，我们可以对 vector 的核心功能有一个更深入的理解，掌握动态数组的内存管理和元素操作的底层原理。在实际开发中，合理使用 vector 可以提高代码的效率和可读性。
完整代码
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include<assert.h>
namespace ldg
{
template<class T>
class vecctor
{
public:
//原生指针
typedef T* iterator;
typedef const T* const_iterator;
size_t size() {
return _finish - _start;
}
size_t capacity()
{
return _end_of_storage - _start;
}
bool empty()const
{
return _start == _finish;
}
iterator begin()
{
return _start;
}
iterator cend()
{
return _finish;
}
const_iterator cbegin()const
{
return _start;
}
const_iterator cend()const
{
return _finish;
}
//构造和销毁
vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
vector(size_t n,const T& val=T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
while (n--) push_back(val);
}
vector(int n, const T& val = T())
:_start(new T[n])
, _finish(_start+n)
, _end_of_storage(_finish)
{
for (int i = 0;i < n;i++)_start[i] = val;
}
template <class Inititerator>
vector(Inititerator first, Inititerator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}
//vector(const vector<T>& v)
// :_start(nullptr)
// , _finish(nullptr)
// , _end_of_storage(nullptr)
//{
// _start = new T[v.capacity()];
// //memccpy(_start,v._start,sizeof(T)*v.size());
// for (size_t i = 0;i < size();i++)
// {
// _start[i] = v._start[i];
// }
// _finish = _start + v.size();
// _ens_of_storage = _start + v.capacity();
//}
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(v.capacity());
for (auto e : v)push_back(e);
}
~vector()
{
if (_start) {
delete[]_start;
_start = _finish = _end_of_storage = nullptr;
}
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_ens_of_storage, v._ens_of_storage);
}
vector<T>& operator=(vector<T>& v)
{
swap(v);
return *this;
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos)const
{
assert(pos < size());
return _start[pos];
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
t* tmp = new t[n];
if (_start)
{
//memcpy(_tmp,_start,sizeof(T)*sz);
for (size_t i = 0;i < sz;i++)
{
tmp[i] = _start[i];
}
delete[]_start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
void resize(size_t n, const T& val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish != _start + n)
{
*finish = val;
++_finish;
}
}
}
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& x)
{
insert(end(), x);
}
void pop_back()
{
ease(end() - 1);
}
//pos位置插入x
//删除pos位置，返回pos+1
iterator erase(iterator pos)
{
iterator begin = pos + 1;
while (begin = _finish)
{
*(begin - 1) = *begin;
++begin;
}
_finish--;
return pos;
}
iterator insert(iterator pos, const T& x)
{
assert(pos <= finish);
if (_finish == _end_of_storage)
{
size_t len = pos-start;
size_t newst = (capacity() == 0) ? 4 : capacity() * 2;
reserve(newst);
pos = _start + len;//防止迭代器失效
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
finish--;
return pos;//防止迭代器失效
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};