1.模拟实现vector

vector使用文章

1.1构造函数

析构函数

  在C++中，vector是一个动态数组容器，可以根据需要自动调整大小。vector类提供了几个不同的构造函数来创建和初始化vector对象。

  （1）默认构造函数： vector<类型> v; 创建一个空的vector对象v，其中类型是vector中元素的数据类型。这个构造函数将创建一个初始大小为0的vector。

  （2）带有初始大小的构造函数： vector<类型> v(n); 创建一个大小为n的vector对象v，并将所有元素初始化为默认值。例如，如果类型是int，则所有元素将初始化为0。

  （3）带有初始值的构造函数： vector<类型> v(n, 初始值); 创建一个大小为n的vector对象v，并将所有元素初始化为给定的初始值。例如，如果类型是int且初始值为5，则所有元素将初始化为5。

  （4）复制构造函数： vector<类型> v(v2); 创建一个新的vector对象v，其中包含与另一个vector对象v2相同的元素。这个构造函数将复制v2中的所有元素。

  （5）使用迭代器的构造函数： vector<类型> v(begin, end); 创建一个新的vector对象v，其中包含从迭代器begin到迭代器end之间的所有元素。这个构造函数将复制这些元素。

namespace vec
{//类模板template<class T>class vector{public://带有初始值的构造函数vector(size_t n, const T& val = T()){resize(n, val);}//带有初始值的构造函数vector(int n, const T& val = T()){resize(n, val);}//使用迭代器的构造函数template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}//空构造函数vector(){ }构造函数//vector()//	:_start(nullptr)//	,_finish(nullptr)//	,_end_of_storage(nullptr)//{}//深拷贝实现拷贝构造vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){_start = new T[v.capacity()];//memcpy(_start, v._start, sizeof(T) * v.size());for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}//析构函数~vector(){if (_start != nullptr){delete[] _start;_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;}}private://成员变量给缺省值iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};
}

 

1.2迭代器

  和string的迭代器使用类似，begin 函数返回指向字符串的起始位置的迭代器，end 函数返回指向字符串的结束位置的迭代器。这样，就可以使用标准的迭代器操作来遍历字符串，如使用循环来遍历每个字符。

  对于普通的vector类型，编译器调用上面两个类型iterator的迭代器，表示可以对该类型容器可读可写；而对于const类型的vector，编译器就会调用下面两个类型const_iterator的迭代器，表示对该类型容器只有可写权限。

  这样，通过调用begin()和end()函数，可以获取vector容器的起始位置和结束位置的迭代器，然后通过迭代器进行遍历和操作容器中的元素。

//T类指针来实现迭代器
typedef T* iterator;
typedef const T* const_iterator;//迭代器
iterator begin()
{return _start;
}iterator end()
{return _finish;
}//const修饰的迭代器
const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}

 

1.3运算符重载

 
赋值运算符重载

  赋值运算符operator=被重载为接受一个vector对象作为参数，并返回一个指向当前对象的引用。在重载实现中，首先创建一个临时的vector对象v，并将传入的vector对象拷贝给v。接着，调用swap函数，将当前对象和临时对象的成员变量进行交换。最后，返回指向当前对象的引用，以支持连续赋值的操作。

  通过这种方式，可以实现高效的赋值操作，避免了逐个元素的拷贝，提高了性能。同时，使用swap函数进行交换，可以确保在异常发生时，不会导致资源泄漏。

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}//赋值运算符重载，现代写法
vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}

 

重载operator[]

  对于普通的版本，我们重载了operator[]运算符，返回一个可读可写的引用。它接受一个参数pos，表示要访问的元素的位置。 在函数内部，通过assert函数进行断言，确保pos在有效的范围内，即小于vector的大小。然后，返回一个对_start[pos]的引用，以实现对指定位置元素的读写操作。

  对于const类型的vector，我们在上一个operator[]运算符的版本添加const进行修饰，返回一个只读的引用。 它也接受一个参数pos，并通过assert函数进行断言，确保pos在有效的范围内。然后，返回一个对_start[pos]的常量引用，以实现对指定位置元素的只读访问。

  通过重载operator[]运算符，可以像使用数组一样，通过下标访问vector容器中的元素。而且，通过重载常量版本的operator[]，可以在常量对象上也能进行只读访问。

//重载operator[] 可读可写
T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}//重载operator[] 只读不可写
const T& operator[](size_t pos) const
{ assert(pos < size());return _start[pos];
}

 

1.4扩容函数

reserve和resize

  reserve函数用于将vector对象的容量调整为至少为n。 如果n大于当前容量，则需要进行扩容操作。在函数内部，首先获取当前vector的大小，然后创建一个临时的指针tmp，指向一个大小为n的新数组。如果当前vector不为空，就将原有元素逐个拷贝到新数组中。

  注意，如果元素类型是自定义类型，可能会出现浅拷贝问题，不能使用memcpy函数进行内存拷贝。

  resize函数用于调整vector对象的大小为n，并在需要时填充指定的元素值val。 如果n小于当前大小，则将_finish指针移动到新的位置，即截断vector。如果n大于当前大小，则调用reserve函数进行扩容操作。然后，通过循环将新元素值拷贝到vector中，直到_finish指针指向新的位置。这样就实现了将vector的大小调整为n，并在需要时填充指定元素值的功能。

  通过这两个函数，可以实现对vector容器的容量和大小的调整，以及在扩容和调整大小时进行元素的拷贝和填充。这样可以灵活地管理vector容器的内存空间和元素数量。

//扩容函数capacity
void reserve(size_t n)
{if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//如果是自定义类型，假如string，则会出现浅拷贝//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;}
}//扩容size
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;}}
}

 

capacity和size

  capacity的大小范围是：_end_of_storage - _start

  size的大小范围是：_finish - _start

  需要注意的是，vector的大小不一定等于容量，而且大小可以小于或等于容量。 当向vector中添加元素时，size大小会增加；当从vector中删除元素时，size大小会减少。当大小超过容量capacity时，vector会自动进行内存的重新分配，通常会分配更大的内存空间，将原有的元素拷贝到新的内存空间中，并释放原有的内存空间。

//返回capacity
size_t capacity() const
{return _end_of_storage - _start;
}//返回size
size_t size() const
{return _finish - _start;
}

 

1.5增删查改

push_back

  push_back函数的实现，用于在vector的末尾添加一个元素。

//尾插
void push_back(const T& v)
{if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = v;++_finish;//insert(end(),x)
}

 

insert

  insert函数的实现，用于在vector中的pos处插入一个元素。

//插入
iterator insert(iterator pos, const T& x)
{assert(pos >= _start && pos <= _finish);//判断是否扩容if (_finish == _end_of_storage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);//解决pos迭代器失效问题pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = x;_finish++;return pos;
}

 

erase

  erase函数的实现，用于在vector的pos位置删除指定元素。

//删除
iterator erase(iterator pos)
{assert(pos >= _start && pos <= _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;++it;}--_finish;return pos;
}

 

完整实现

#pragma once#include<assert.h>namespace vec
{//类模板template<class T>class vector{public://T类指针来实现迭代器typedef T* iterator;typedef const T* const_iterator;//迭代器iterator begin(){return _start;}iterator end(){return _finish;}//const修饰的迭代器const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//构造函数，将空间填充为val对象vector(size_t n, const T& val = T()){resize(n, val);}vector(int n, const T& val = T()){resize(n, val);}//构造函数，迭代区间进行构造template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}//空构造函数vector(){ }构造函数//vector()//	:_start(nullptr)//	,_finish(nullptr)//	,_end_of_storage(nullptr)//{}//深拷贝实现拷贝构造vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){_start = new T[v.capacity()];//memcpy(_start, v._start, sizeof(T) * v.size());for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}//赋值运算符重载，现代写法vector<T>& operator=(vector<T> v){swap(v);return *this;}//析构函数~vector(){if (_start != nullptr){delete[] _start;_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;}}//扩容函数capacityvoid reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//如果是自定义类型，如果是string，则会出现浅拷贝//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;}}//扩容sizevoid resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}//尾插void push_back(const T& v){if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = v;++_finish;//insert(end(),x)}//返回capacitysize_t capacity() const{return _end_of_storage - _start;}//返回sizesize_t size() const{return _finish - _start;}//重载operator[] 可读可写T& operator[](size_t pos){assert(pos < size());return _start[pos];}//重载operator[] 只读不可写const T& operator[](size_t pos) const{ assert(pos < size());return _start[pos];}//插入iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);//判断是否扩容if (_finish == _end_of_storage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);//解决pos迭代器失效问题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 && pos <= _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;++it;}--_finish;return pos;}private://成员变量给缺省值iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};//打印template<class T>void print(const T& v){for (auto e : v){cout << e << " ";}cout << endl;}
}

 
测试代码

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
#include<vector>
#include<string>
using namespace std;#include"vector.h"void test_vector1()
{vec::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;for (size_t i = 0; i < v1.size(); i++){v1[i]++;}for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;vec::print(v1);
}void test_vector2()
{vec::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";} cout << endl;v1.insert(v1.begin(), 10);for (auto e : v1){cout << e << " ";}cout << endl;vec::vector<int>::iterator p = v1.begin() + 3;//insert迭代器可能会失效//insert建议不要使用这个形参迭代器v1.insert(p, 100);*p += 10;vec::print(v1);
}void test_vector3()
{vec::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (auto e : v1){cout << e << " ";}cout << endl;//v1.erase(v1.begin());auto it = v1.begin()+4;v1.erase(it);//erase以后，迭代器失效了，不能访问it指向的空间//因为vs会对其进行强制检查，访问会报错cout << *it << endl;++it;cout << *it << endl;for (auto e : v1){cout << e << " ";}cout << endl;
}void test_vector4()
{vec::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;vec::vector<int> v2(v1);for (auto e : v1){cout << e << " ";}cout << endl;vec::vector<int> v3;v3 = v1;vec::print(v3);
}void test_vector5()
{vector<string> v1;v1.push_back("11111");v1.push_back("22222");v1.push_back("33333");v1.push_back("44444");v1.push_back("55555");for (auto& e : v1){cout << e << " ";}cout << endl;vector<string> v2(v1);for (auto& e : v2){cout << e << " ";}cout << endl;
}int main()
{//test_vector1();//test_vector2();//test_vector3();//test_vector4();test_vector5();return 0;
}