一、vector是什么？
vector是表示可变大小数组的序列容器，它也采用连续存储空间来存储元素，因此可以采用下标对vector的元素进行访问，它的大小是动态改变的，vector使用动态分配数组来存储它的元素；
二、容器特性
1.顺序序列
顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素;
2.动态数组
支持对序列中的任意元素进行快速直接访问，甚至可以通过指针进行该操作。操供了在序列末尾相对快速地添加/删除元素的操作;
3.能够感知内存分配器的
容器使用一个内存分配器对象来动态地处理它的存储需求;
三、vector的模拟实现
定义一个类：
|
1
2
3
4
5
6
7
8
9
|
template<class T>
class Vector
{
T* _start; //首元素地址
T* _finish; //最后一个元素地址的下一个地址
T* _endOfStorage; //空间的尾地址
public：
//成员函数
};
|
构造函数
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
Vector()
:_start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{}
Vector(size_t n, const T& value = T())
:_start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
reserve(n);
while (n--)
{
push_back(value);
}
}
Vector(InputInterator first, InputInterator last)
:_start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
while (first != last)
{
pushBack(*first);
++first;
}
}
|
数据大小、空间大小
|
1
2
3
4
5
6
7
8
9
|
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endOfStorage - _start;
}
|
尾插
|
1
2
3
4
5
6
7
8
9
10
|
void pushBack(const T& value)
{
if (_finish == _endOfStorage)
{
size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity();
reverse(value);
}
*_finish = value;
++_finish;
}
|
扩容
有资源进行拷贝时，使用深拷贝；类型为自定义类型时，发生浅拷贝，调用自定义类型析构函数，释放资源，导致资源二次释放，所以自定义类型的拷贝有资源时进行深拷贝；
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* arr = new T[n];
if (_start)
{
memcpy(arr, _start, sizeof(T) * sz);
delete[] _start;
}
//update
_start = arr;
_finish = _start + sz;
_endOfStorage = _start + n;
}
}
|
改变数据大小
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
void resize(size_t n, const T& val = T())
{
if (n > capacity())
{
reserve(n);
}
else if (n > size())
{
while (_finish != _start + n)
{
*_finish = val;
_finish++;
}
}
_finish = _start + n;
}
|
位置插入值
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
void insert(iterator pos, const T& val)
{
size_t sz = pos - _start;
//检查位置
if (pos >= _start && pos <= _finish)
{
//检查容量
if (_finish == _endOfStoage)
{
size_t n = _endOfStorage == nullptr ? 1 : 2 * capacity();
reserve(n);
//更新迭代器
pos = _start + sz;
}
//移动元素
iterator end_u = _finish;
while (end_u != pos)
{
*end = *(end_u - 1);
--end_u();
}
//插入元素
*pos = val;
//更新位置
++_finish;
}
}
|
删除数据
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
iterator erase(iterator pos)
{
//检查位置
if (pos < _finish && pos >= _start)
{
//移动元素
iterator start = pos + 1;
while (start!=_finish)
{
*(start - 1) = *start;
start++;
}
//更新
--_finish;
}
return pos;
}
//返回删除数据的下一个元素的位置
|
operator[] 重载
|
1
2
3
4
5
|
T& operator[](size_t pos)
{
if (pos >= 0 && pos < size())
return _start[pos];
}
|
operator= 重载
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
Vector<T>& operator=(const Vector<T>& v)
{
if (this != &v)
{
delete[]_start;
size_t n = v.capacity();
_start = new T[n];
for (size_t i = 0; i < v.capacity(); ++i)
{
_start[i] = v._start[i];
}
_finish = _start + v.size();
_finish = _start + n;
}
return *this;
}
|
迭代器
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
//vector迭代器：T*
typedef T* iterator;
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;
}
|
析构函数
|
1
2
3
4
5
6
7
8
|
~Vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
}
|
总结
到此这篇关于c++ vector模拟实现的文章就介绍到这了,更多相关c++ vector模拟实现内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.51cto.com/u_14982125/2699511