c++中vector的使用和模拟实现

Natalia ·

更新时间:2024-09-20

· 953 次阅读

一、接口介绍

1、插入数据

void push_back(const T& x)

在当前vector尾部插入x,如果容量不够扩大二倍。

iterator insert(iterator pos, const T& x)

在POS位置插入元素x

2、容量相关

size_t capacity()

返回当前vector的容量（size+剩余容量）

size_t size()

返回当前vector的元素个数

void resize(size_t n, const T& val = T())

改变当前vector的size,如果n>size则大于部分初始值为val。（capacity的大小始终保持不变）

void reserve(size_t n)

改变当前vector的capacity，如果n<capacity则不改变。

3、删除数据

void pop_back()

如果vector不为空，删除当前vector的最后一个元素

iterator erase(iterator pos)

删除POS位置的元素

4、运算符重载

T& operator[](size_t pos)

[]运算符重载，支持使用下标访问vector

二、实现


#include<iostream>
#include<string.h>
#include<assert.h>
using namespace std;
namespace myvector
{
template<class T>
class vector
{
public:
typedef T* iterator;
iterator begin()
{
return start;
}
iterator end()
{
return finish;
}
//默认构造函数
vector()
:start(nullptr)
, finish(nullptr)
, end_of_storage(nullptr)
{}
//容量
size_t capacity()
{
return end_of_storage - start;
}
size_t size()
{
return finish - start;
}
void reserve(size_t n)
{
if (n > capacity())
{
//开新空间
T* tmp = new T[n];
//拷贝旧空间的内容
memcpy(tmp, start, sizeof(T)*size());
//改变容量
finish = tmp + size();
end_of_storage = tmp + n;
//释放旧空间
T* tmp1 = start;
start = tmp;
tmp = nullptr;
}
}
void resize(size_t n, const T& val = T())
{
//判断容量
if (n > capacity())
reserve(n);
//如果n<size
if (n < size())
{
finish = start + n;
}
else
{
while (finish != start + n)
{
*finish = val;
finish++;
}
}
}
//检查空间
void check_capacity()
{
if (finish == end_of_storage)
{
//如果当前不为空，就扩2倍，为空就开4个吧
size_t newcapacity = finish == nullptr ? 4 : capacity()*2;
reserve(newcapacity);
}
}
T& operator[](size_t pos)
{
assert(pos < size());
return start[pos];
}
//插入
void push_back(const T& x)
{
insert(finish,x);
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= start && pos <= finish);
size_t pos1 = pos - start;
check_capacity();
//解决迭代器失效
pos = start + pos1;
//移动数据
iterator end = finish;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
//插入数据
*pos = x;
finish++;
return pos;
}
//删除数据
void pop_back()
{
assert(finish > start);
finish--;
}
iterator erase(iterator pos)
{
assert(pos >= start && pos < finish);
iterator it = pos + 1;
while (it != finish)
{
*(it - 1) = *it;
++it;
}
--finish;
return pos;
}
//析构函数
~vector()
{
delete[] start;
start = finish = end_of_storage = nullptr;
}
private:
iterator start;
iterator finish;
iterator end_of_storage;
};
}

三、测试用例


void test1()
{
//测试默认构造和析构函数
myvector::vector<int> v1;
}
void test2()
{
//测试push_back()、reserve、check_capacity、size、capacity
myvector::vector<int> v2;
//插入至少五个数据，进行一次扩容，扩容间接对size和capacity以及check_capacity进行了测试
v2.push_back(1);
v2.push_back(2);
v2.push_back(3);
v2.push_back(4);
//v2.push_back(5);
for (size_t i = 0; i < v2.size(); i++)
cout << v2[i] << " ";
cout << endl;
//测试resize,变小变大
v2.resize(8,6);
for (size_t i = 0; i < v2.size(); i++)
cout << v2[i] << " ";
cout << endl;
v2.resize(4);
//测试[]
//正常访问
for (size_t i = 0; i < v2.size(); i++)
cout << v2[i] << " ";
cout << endl;
//越界访问
//cout << v2[v2.size()] << endl;
//cout << v2[-1] << endl;
//测试insert---将push_back使用insert插入也可以进行检查
myvector::vector<int>::iterator it = v2.begin();
it = v2.insert(it,0);
it = v2.insert(it + 2, 10);
for (size_t i = 0; i < v2.size(); i++)
cout << v2[i] << " ";
cout << endl;
//测试删除
v2.pop_back();
v2.pop_back();
for (size_t i = 0; i < v2.size(); i++)
cout << v2[i] << " ";
cout << endl;
v2.erase(v2.begin());
for (size_t i = 0; i < v2.size(); i++)
cout << v2[i] << " ";
cout << endl;
}

四、迭代器失效

1、在vector的接口中，使用insert插入数据时可能导致迭代器失效，具体如下