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=v3
vector<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);
//如果扩容了要更新pos
pos = _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=v3
vector<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);
//如果扩容了要更新pos
pos = _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++11
int 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 类还包含更多的功能和优化，我这个只是进行了简单的实现
