C++ 中的 vector 的模拟实现【代码纯享】
文章目录
- C++ 中的 vector 模拟实现
- 1. vector 的基本概念
- 2. vector 的基本操作
- 3. vector 的模拟实现
- 4.代码纯享
- 5. 总结
C++ 中的 vector 模拟实现
在 C++ 中，vector 是一个非常重要的容器，它提供了动态数组的功能。在本篇博客中，我们将尝试模拟实现一个简单的 vector 类，以便更好地理解其内部工作机制。
1. vector 的基本概念
vector 是一个封装了动态大小数组的顺序容器。与普通数组不同，vector 的大小可以根据需要动态地增加或减少，而不需要程序员手动管理内存。
2. vector 的基本操作
- 构造函数：创建一个空的
vector或者根据给定的初始值创建一个vector。 - 赋值操作：将一个
vector的内容赋值给另一个vector。 - 访问元素：通过索引访问
vector中的元素。 - 插入和删除元素：在
vector的任何位置插入或删除元素。 - 大小操作：获取
vector的大小或检查它是否为空。 - 迭代器操作：提供迭代器以遍历
vector中的元素。
3. vector 的模拟实现
首先，我们需要定义vector的基本结构。由于vector可以存储不同类型的元素，我们使用类模板来定义它：
namespace my_vector
{template<class T>class vector{public:// 定义迭代器类型typedef T* iterator;// 定义const迭代器类型typedef const T* const_iterator;// 其他成员变量和成员函数...
};
接下来，我们实现vector的一些基本成员函数，如默认构造函数，析构函数，拷贝构造函数：
iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}vector(){}//拷贝构造v2(v1)vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}//vector<int> v1 = { 1, 2, 3, 4, 5, 6, 7, 8 };//构造+拷贝构造 -> 优化 直接构造vector(initializer_list<T> il){reserve(il.size());for (auto& e : il){push_back(e);}}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);}}//深拷贝 v1=v3vector<T>& operator=(vector<T> v){swap(v);return *this;}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}
private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;
然后，我们实现vector的迭代器。迭代器是一种行为类似于指针的对象，它能够遍历容器中的元素：
bool empty(){return _start == _finish;}void insert(iterator pos, const T& val){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);//如果扩容了要更新pospos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;it--;}*pos = val;_finish++;}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的一些基本操作，如push_back、pop_back、begin、end等：
size_t size() const{return _finish - _start;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}size_t capacity() const {return _endofstorage - _start;}void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t old_size = size();//memcpy(tmp, _start, size()*sizeof(T));for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + old_size;_endofstorage = tmp + n;}}void resize(size_t n,const T& val=T()){if (n > size()){reserve(n);//插入while (_finish<_start + n){*_finish = val;_finish++;}}else{//删除_finish = _start + n;}}void push_back(const T& val){/*if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finsh = val;_finsh++;*/insert(end(), val);}void pop_back(){/*assert(empty());_finsh--;*/erase(--end());}
4.代码纯享
#pragma once
#include <assert.h>namespace my_vector
{template<class T>class vector{public:// 定义迭代器类型typedef T* iterator;// 定义const迭代器类型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(){}//拷贝构造v2(v1)vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}//vector<int> v1 = { 1, 2, 3, 4, 5, 6, 7, 8 };//构造+拷贝构造 -> 优化 直接构造vector(initializer_list<T> il){reserve(il.size());for (auto& e : il){push_back(e);}}//类模板的成员函数可以是函数模板template <class InputIerator>vector(InputIerator first, InputIerator last){while (first != last){push_back(*first);first++;}}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);}}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finsh, v._finsh);std::swap(_endofstorage, v._endofstorage);}//深拷贝 v1=v3vector<T>& operator=(vector<T> v){swap(v);return *this;}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}size_t size() const{return _finish - _start;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}size_t capacity() const {return _endofstorage - _start;}void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t old_size = size();//memcpy(tmp, _start, size()*sizeof(T));for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + old_size;_endofstorage = tmp + n;}}void resize(size_t n,const T& val=T()){if (n > size()){reserve(n);//插入while (_finish<_start + n){*_finish = val;_finish++;}}else{//删除_finish = _start + n;}}void push_back(const T& val){/*if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finsh = val;_finsh++;*/insert(end(), val);}void pop_back(){/*assert(empty());_finsh--;*/erase(--end());}bool empty(){return _start == _finish;}void insert(iterator pos, const T& val){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);//如果扩容了要更新pospos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;it--;}*pos = val;_finish++;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;it++;}--_finish;return pos;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};//函数模板//template <typename T>template <class T>void print_vector(const vector<T>& v){for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;//typename vector<int>::const_iterator it = v.begin();// auto it = v.begin();// while (it != v.end())// {// cout << *it << " ";// it++;// }// cout << endl;// for (auto e : v)// {// cout << e << " ";// }// cout << endl;}void test_vector1(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);print_vector(v1);v1.insert(v1.begin(),3);v1.insert(v1.begin() + 2, 3);v1.insert(v1.begin() + 4, 3);v1.insert(v1.begin() + 6, 3);print_vector(v1);v1.erase(v1.begin()+4);print_vector(v1);vector<double> v2;v2.push_back(0.1);v2.push_back(0.2);v2.push_back(0.3);v2.push_back(0.4);v2.push_back(0.5);v2.push_back(0.6);print_vector(v2);}void test_vector2(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);print_vector(v1);v1.resize(10);print_vector(v1);v1.resize(3);print_vector(v1);}void test_vector3(){vector<int> v3(10,1);print_vector(v3);}void test_vector4(){auto x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };cout << typeid(x).name() << endl;cout << sizeof(x) << endl;initializer_list<int> y = { 1, 2, 3, 4, 5, 6, 7 };//单参数的构造函数，隐式类型转换string str = "111111";//构造+拷贝构造->优化 直接构造const string& str1 = "111111";//构造+拷贝构造->优化 直接构造vector<string> v;v.push_back(str);v.push_back(string("22222"));v.push_back("33333");int i = 1;//不推荐 --- C++11int j = { 1 };int k{ 1 };//跟上面类似//隐式转化+优化vector<int> v1 = { 1, 2, 3, 4, 5, 6, 7, 8 };for (auto e : v1){cout << e << " ";}cout << endl;//直接构造vector<int> v2({ 1, 2, 3, 10, 20, 30 });for (auto e : v2){cout << e << " ";}cout << endl;}void test_vector5(){vector<string> v;v.push_back("11111");v.push_back("11111");v.push_back("11111");v.push_back("11111");v.push_back("11111");v.push_back("11111");for (auto& e : v){cout << e << " ";}cout << endl;}void test_vector6(){vector<int> v1;v1.push_back(1);v1.push_back(1);v1.push_back(1);v1.push_back(1);v1.push_back(1);v1.push_back(1);print_vector(v1);vector<int>::iterator it = v1.begin() + 3;v1.insert(it, 40);print_vector(v1);}
}
5. 总结
通过这个简单的 vector 模拟实现，我们不仅加深了对 vector 容器的理解，还学习了如何在 C++ 中实现一个动态数组。当然，实际的 vector 类还包含更多的功能和优化，我这个只是进行了简单的实现
