【十三】【C++】vector简单实现

代码实现

/*vector类简单实现*/
#if 1
#define _CRT_SECURE_NO_WARNINGS#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <crtdbg.h>
#include <assert.h>
#include <string.h>namespace MyVector {template<class T>class vector {public:typedef T* itertor;public:vector(): _start(nullptr), _finish(nullptr), _endofstorage(nullptr){}vector(int n, const T& val = T()): _start(new T[n]) {//memset(_start, val, sizeof(T)*n);for (int i = 0; i < n; ++i) {_start[i] = val;}_finish = _start + n;_endofstorage = _finish;}template<class Iterator>vector(Iterator first, Iterator last) {// size_t n = last - first;  //注意：一定不能减Iterator it = first;size_t n = 0;while (it != last) {n++;++it;}_start = new T[n];_finish = _start;while (first != last) {*_finish++ = *first++;// _finish++;// first++;}_endofstorage = _finish;}vector(const vector<T>& v): _start(new T[v.size()]) {size_t n = v.size();for (size_t i = 0; i < n; ++i) {_start[i] = v[i];}_finish = _start + n;_endofstorage = _finish;}vector<T>& operator=(vector<T> v) {swap(v);return *this;}~vector() {if (_start) {delete[] _start;_start = _finish = _endofstorage = nullptr;}}/// 迭代器itertor begin() {return _start;}itertor end() {return _finish;}itertor rbegin() {return end();}itertor rend() {return begin();}// 容量size_t size()const {return _finish - _start;}size_t capacity()const {return _endofstorage - _start;}bool empty()const {return _start == _finish;}void resize(size_t newsize, const T& val = T()) {size_t oldsize = size();if (newsize > oldsize) {size_t oldcap = capacity();if (newsize > oldcap)reserve(newsize);for (size_t i = oldsize; i < newsize; ++i) {_start[i] = val;}}_finish = _start + newsize;}void reserve(size_t newcap) {size_t oldcap = capacity();size_t count = size();if (newcap > oldcap) {// 1. 申请新空间T* temp = new T[newcap];if (_start) {// 2. 拷贝元素// 浅拷贝// memcpy(temp, _start, sizeof(T)*count);for (size_t i = 0; i < count; ++i) {temp[i] = _start[i];}// 3. 释放旧空间delete[] _start;}_start = temp;_finish = _start + count;_endofstorage = _start + newcap;}}// 元素访问T& front() {// return *begin();return _start[0];}const T& front()const {return _start[0];}T& back() {return *(_finish - 1);}const T& back()const {return *(_finish - 1);}T& operator[](size_t index) {assert(index < size());return _start[index];}const T& operator[](size_t index)const {assert(index < size());return _start[index];}//// 修改void push_back(const T& value) {if (_finish == _endofstorage) {reserve(size() * 2 + 3);}*_finish = value;++_finish;}void pop_back() {if (empty())return;--_finish;}itertor insert(itertor pos, const T& value) {if (pos < _start || pos > _finish)return end();if (_finish == _endofstorage)reserve(2 * size());// 将pos及其后续所有的元素整体往后搬移itertor it = _finish;while (it != pos) {*it = *(it - 1);--it;}*pos = value;++_finish;return pos;}itertor erase(itertor pos) {if (pos < _start || pos >= _finish)return end();itertor it = pos + 1;while (it != _finish) {*(it - 1) = *it;++it;}--_finish;return pos;}void clear() {_finish = _start;}void swap(vector<T>& v) {std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}//vector成员变量private:itertor _start;itertor _finish;itertor _endofstorage;};}void TestVector1() {MyVector::vector<int> v1;// int  intMyVector::vector<int> v2(10, 5);for (size_t i = 0; i < v2.size(); ++i)cout << v2[i] << " ";cout << endl;int array[] = { 1, 2, 3, 4, 5 };MyVector::vector<int> v3(array, array + 3);for (auto e : v3)cout << e << " ";cout << endl;MyVector::vector<int> v4(v3);auto it = v4.begin();while (it != v4.end()) {cout << *it << " ";++it;}cout << endl;}void TestVector4() {MyVector::vector<int> v(10, 5);for (auto e : v)cout << e << " ";cout << endl;cout << "size=" << v.size() << endl;cout << "capacity=" << v.capacity() << endl;v.resize(20, 8);for (auto e : v)cout << e << " ";cout << endl;cout << "size=" << v.size() << endl;cout << "capacity=" << v.capacity() << endl;v.resize(30, 6);for (auto e : v)cout << e << " ";cout << endl;cout << "size=" << v.size() << endl;cout << "capacity=" << v.capacity() << endl;v.resize(10);for (auto e : v)cout << e << " ";cout << endl;cout << "size=" << v.size() << endl;cout << "capacity=" << v.capacity() << endl;v.resize(15, 0);for (auto e : v)cout << e << " ";cout << endl;cout << "size=" << v.size() << endl;cout << "capacity=" << v.capacity() << endl;}void TestVector2() {MyVector::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);cout << v.size() << endl;cout << v.capacity() << endl;for (auto e : v)cout << e << " ";cout << endl;v.push_back(4);cout << v.size() << endl;cout << v.capacity() << endl;for (auto e : v)cout << e << " ";cout << endl;cout << v.front() << endl;cout << v.back() << endl;v.pop_back();cout << v.front() << endl;cout << v.back() << endl;}void TestVector3() {MyVector::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (auto e : v)cout << e << " ";cout << endl;v.insert(v.begin(), 0);for (auto e : v)cout << e << " ";cout << endl;v.insert(v.begin() + 2, 22);for (auto e : v)cout << e << " ";cout << endl;auto it = v.begin();while (it != v.end()) {it = v.erase(it);++it;}}#include <list>class String {
public:String(const char* str = "") {if (nullptr == str)str = "";_str = new char[strlen(str) + 1];strcpy(_str, str);}String(const String& s): _str(new char[strlen(s._str) + 1]) {strcpy(_str, s._str);}String& operator=(const String& s) {if (this != &s) {char* temp = new char[strlen(s._str) + 1];strcpy(temp, s._str);delete[] _str;_str = temp;}return *this;}~String() {if (_str) {delete[] _str;_str = nullptr;}}
private:char* _str;};void Teststdvector() {vector<String> v;v.push_back("1111");v.push_back("1111");v.push_back("2222");v.push_back("3333");}void TestMyvector() {MyVector::vector<String> v;v.push_back("1111");v.push_back("2222");v.push_back("3333");v.push_back("4444");}int main() {//int array[10];//memset(array, 5, sizeof(array));/*int array[] = { 1, 2, 3, 4 };vector<int> v1(array, array + sizeof(array) / sizeof(array[0]));list<int> L{ 1, 2, 3 };vector<int> v2(L.begin(), L.end());*/// TestVector1();// TestVector2();// TestVector3();// TestVector4();// Teststdvector();Testvector();_CrtDumpMemoryLeaks();return 0;}
#endif

这段代码是一个简化版的 vector 类的实现，模拟了 C++ 标准库中 std::vector 的核心功能。vector 是一个模板类，用于存储元素的动态数组，可以根据需要动态地增加或减少其大小。下面是对代码中每个部分的简要解释：

类模板声明

template<class T>
class vector {

这里定义了一个模板类 vector，T 是元素类型的占位符，允许 vector 存储任意类型的元素。

成员变量

typedef T* itertor;
itertor _start; // 指向数组首元素的指针
itertor _finish; // 指向数组最后一个元素的下一个位置的指针
itertor _endofstorage; // 指向数组分配的存储空间尾部的下一个位置的指针

vector内的迭代器底层是T类型的指针类型。

_start相当于string类的字符指针。

_finish相当于string类的size。

_endofstorage相当于string类的capacity。

构造函数

默认构造函数、带参数的构造函数、范围构造函数、拷贝构造函数和析构函数用于初始化 vector 实例和清理资源。

范围构造函数特别注意不直接使用迭代器相减来确定元素数量，以支持不支持随机访问的迭代器。

默认构造函数

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

所有的指针都指向空。

带参数的构造函数

 vector(int n, const T& val = T())
: _start(new T[n]) {for (int i = 0; i < n; ++i) {_start[i] = val;}_finish = _start + n;_endofstorage = _finish;
}

使用默认的构造器给_start开辟空间，再依次赋值为val，接着修正_finish和_endofstorage。

可以理解为，_start相当于string类的字符指针。

_finish相当于string类的size。

_endofstorage相当于string类的capacity。

范围构造函数

 template<class Iterator>
vector(Iterator first, Iterator last) {// size_t n = last - first;  //注意：一定不能减Iterator it = first;size_t n = 0;while (it != last) {n++;++it;}_start = new T[n];_finish = _start;while (first != last) {*_finish++ = *first++;// _finish++;// first++;}_endofstorage = _finish;
}

注意，对于 vector 的构造函数，使用了模板来允许接受任意类型的迭代器 Iterator 作为参数。这里不支持迭代器相加计算距离，原因是并不是所有的迭代器类型都支持相减计算距离。

随机访问迭代器（Random Access Iterator）：支持直接相减操作，因为它们可以在常数时间内访问序列中的任何元素。vector 和 deque 容器提供的迭代器就是随机访问迭代器。

双向迭代器（Bidirectional Iterator）、前向迭代器（Forward Iterator）、输入迭代器（Input Iterator） 和 输出迭代器（Output Iterator）：不支持相减操作，因为它们只能单向移动（或者在双向迭代器的情况下，前后移动），无法直接计算两个迭代器之间的距离。

根据迭代器范围来构造对象，首先计算迭代器范围内有多少个元素，计算的方法是迭代器依次++。计算好元素个数之后先开辟对应的空间大小。接着通过迭代器依次赋值。修正_finish和_endofstorage。

拷贝构造函数

 vector(const vector<T>& v)
: _start(new T[v.size()]) {size_t n = v.size();for (size_t i = 0; i < n; ++i) {_start[i] = v[i];}_finish = _start + n;_endofstorage = _finish;
}

std::vector<int> vec6(vec4)括号里面传入的是vector类型，属于拷贝构造函数。如上述代码所示，利用vec4构造vec6对象。此时vec6对象元素的数据类型是int类型，这个int类型就是上面代码的T类型，当然，和vec4里面的数据类型是相同的。

析构函数

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

赋值操作符

vector<T>& operator=(vector<T> v) {swap(v);return *this;
}

通过拷贝-交换技巧实现赋值操作符，确保异常安全和自赋值安全。swap函数是vector类内部定义的函数。

迭代器相关方法

提供 begin() 和 end() 方法返回指向首元素和尾后位置的迭代器。

rbegin() 和 rend() 方法在此实现中不是反向迭代器的正确实现，它们只是简单地返回了 end() 和 begin()。

// 迭代器
itertor begin() {return _start;
}itertor end() {return _finish;
}itertor rbegin() {return end();
}itertor rend() {return begin();
}

end()函数返回的是_finish迭代器，_finish迭代器指向最后一个元素的下一个位置。

容量相关方法

size(), capacity(), empty(), resize(), reserve() 方法用于查询和修改 vector 的大小和容量。

// 容量
size_t size()const {return _finish - _start;
}size_t capacity()const {return _endofstorage - _start;
}bool empty()const {return _start == _finish;
}

随机访问迭代器（Random Access Iterator）：支持直接相减操作，因为它们可以在常数时间内访问序列中的任何元素。vector 和 deque 容器提供的迭代器就是随机访问迭代器。

因此在vector内部可以直接对指针进行相减操作，计算出来的就是指针之间的元素个数。

 void resize(size_t newsize, const T& val = T()) {size_t oldsize = size();if (newsize > oldsize) {size_t oldcap = capacity();if (newsize > oldcap)reserve(newsize);for (size_t i = oldsize; i < newsize; ++i) {_start[i] = val;}}_finish = _start + newsize;
}

计算当前大小：首先通过 size() 方法获取当前容器中元素的数量。

比较新旧大小：

如果 newsize 大于 oldsize（当前容器的大小），则需要扩展容器。

如果 newsize 小于或等于 oldsize，代码当前版本中没有显式处理这种情况，实际上通过设置 _finish = _start + newsize; 来减少容器的大小，多余的元素虽在逻辑上被“丢弃”，但它们并没有被销毁。

扩展容器（如果需要）：

首先检查是否需要扩展底层存储空间，即 newsize 是否大于当前容器的容量（oldcap）。如果是，调用 reserve(newsize) 来分配更大的存储空间。

然后，使用循环从 oldsize 开始，直到 newsize 结束，为新添加的位置赋予 val 值。这确保了扩展部分的元素被初始化。

更新 _finish：最后，无论容器是被扩展还是缩小，都通过设置 _finish = _start + newsize; 来更新指向容器中最后一个有效元素之后位置的指针。这样，容器的大小被改变为 newsize。

void reserve(size_t newcap) {size_t oldcap = capacity();size_t count = size();if (newcap > oldcap) {// 1. 申请新空间T* temp = new T[newcap];if (_start) {// 2. 拷贝元素// 浅拷贝// memcpy(temp, _start, sizeof(T)*count);for (size_t i = 0; i < count; ++i) {temp[i] = _start[i];}// 3. 释放旧空间delete[] _start;}_start = temp;_finish = _start + count;_endofstorage = _start + newcap;}
}

这段代码是 vector 类中 reserve 方法的实现，它的主要目的是确保 vector 拥有至少 newcap 个元素的容量。如果当前容量小于请求的新容量，则会分配更大的存储空间并移动现有元素到新空间。

获取当前容量和元素数量：

oldcap 存储当前容量，通过 capacity() 方法获取。

count 存储当前元素的数量，通过 size() 方法获取。

检查是否需要扩容：

如果 newcap 大于 oldcap，则需要进行扩容。如果不是，什么都不做，即函数直接返回，保持现状。

申请新空间：

使用 new T[newcap] 申请一个新的元素数组，大小为请求的新容量 newcap。

拷贝现有元素到新空间：

如果 _start 不是 nullptr（即当前容器非空），则需要将现有元素从旧空间复制到新空间。

使用循环遍历当前所有元素，对每个元素使用拷贝赋值操作进行复制。这里的复制保证了如果类型 T 有特殊的拷贝语义（例如深拷贝需要的操作），那么这些语义会被正确处理。

注释中提到的“浅拷贝”和 memcpy 是不正确的选择。对于类类型 T，应使用循环拷贝来确保正确的语义。

释放旧空间：

使用 delete[] _start 释放原有的存储空间。

更新内部指针以反映新状态：

_start 更新为指向新分配的存储空间的开始。

_finish 更新为新空间中最后一个元素之后的位置，即 _start + count。

_endofstorage 更新为新空间的末尾，即 _start + newcap。

元素访问方法

front(), back(), operator[] 提供对 vector 元素的访问。

// 元素访问
T& front() {// return *begin();return _start[0];
}const T& front()const {return _start[0];
}T& back() {return *(_finish - 1);
}const T& back()const {return *(_finish - 1);
}T& operator[](size_t index) {assert(index < size());return _start[index];
}const T& operator[](size_t index)const {assert(index < size());return _start[index];
}

修改方法

包括 push_back(), pop_back(), insert(), erase(), clear() 等方法，用于修改 vector 的内容。

swap() 方法用于交换两个 vector 实例的内容。

// 修改
void push_back(const T& value) {if (_finish == _endofstorage) {reserve(size() * 2 + 3);}*_finish = value;++_finish;
}void pop_back() {if (empty())return;--_finish;
}itertor insert(itertor pos, const T& value) {if (pos < _start || pos > _finish)return end();if (_finish == _endofstorage)reserve(2 * size());// 将pos及其后续所有的元素整体往后搬移itertor it = _finish;while (it != pos) {*it = *(it - 1);--it;}*pos = value;++_finish;return pos;
}itertor erase(itertor pos) {if (pos < _start || pos >= _finish)return end();itertor it = pos + 1;while (it != _finish) {*(it - 1) = *it;++it;}--_finish;return pos;
}void clear() {_finish = _start;
}void swap(vector<T>& v) {std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}

push_back：

向 vector 的末尾添加一个新元素。如果当前没有足够的存储空间（即 _finish == _endofstorage），则通过调用 reserve 来扩展容量，保证有足够的空间存储新元素。新元素被复制到 _finish 指向的位置，然后 _finish 自增以指向新的末尾。

pop_back：

从 vector 的末尾移除一个元素。这是通过简单地将 _finish 指针递减实现的。如果 vector 为空（即 _start == _finish），则不执行任何操作。

insert：

在指定位置 pos 前面插入一个新元素。首先检查 pos 是否在合法范围内。如果容量不足以插入新元素，则通过调用 reserve 扩展容量。然后，从 vector 的末尾开始，将元素向后移动一位，直到达到插入位置，最后在 pos 位置放入新元素并更新 _finish。

erase：

从 vector 中移除位于 pos 的元素。该操作通过将从 pos + 1 开始的所有元素向前移动一位来实现，并递减 _finish 指针。如果 pos 不在合法范围内，函数返回 end()，即 _finish。

clear：

清空 vector 中的所有元素，实现上通过将 _finish 设置为 _start 实现，逻辑上移除所有元素。这不会释放已分配的内存。

swap：

交换当前 vector 与另一个 vector 的内容。这是通过对 _start、_finish 和 _endofstorage 使用 std::swap 函数实现的。这个操作是非常高效的，因为它只涉及指针的交换，而不需要元素的逐个复制或移动。

反向迭代器探究

/*vector反向迭代器探究*/
#if 1
#define _CRT_SECURE_NO_WARNINGS#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <crtdbg.h>void TestVector14() {vector<int> v={1,2,3,4,5};auto it=v.rbegin();while(it!=v.rend()){cout<<*it<<endl;it++;}}
int main() {TestVector14();return 0;}#endif

反向迭代器中rbegin指向的是最后一个元素后一个位置，但是解引用的时候，它能够输出最后一个元素的位置，我认为这是编译器做出的自动优化，在反向迭代器中，解引用相当于调用迭代器++后的解引用。

针对于自定义类型的解引用

class Date{
private:int _year;int _month;int _day;
public:Date():_year(2024),_month(1),_day(1){}void Show(){cout<<_year<<"-"<<_month<<"-"<<_day<<endl;}};
int main() {MyVector::vector<Date>v;v.push_back(Date());v.push_back(Date());v.push_back(Date());v.push_back(Date());auto it=v.begin();while(it!=v.end()){it->Show();it++;}return 0;}
#endif