目录
目录
一、接口介绍
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插入数据时可能导致迭代器失效，具体如下
2、删除操作导致迭代器失效
3、迭代器失效的解决办法
1）在vector中，解决迭代器失效的办法是在插入、删除等可能会导致迭代器失效的地方，返回新的迭代器来解决迭代器失效。
转载：https://blog.csdn.net/qq_47406941/article/details/115418977
查看评论