C++STL的vector扩容原理及实现
C++的STL中vector的扩容思想及实现原理C++的STL库中的vector,是一种使用很频繁的容器,因为它是一个自动扩容的容器,使用起来比较灵活,可以一直往容器的末尾添加数据。那么它是怎么实现自动扩容的呢?其实关键点就是对于容器里的元素数量进行判断,当容器的存储数量已经达到容量时,那么就需要进行一个倍增扩容了。整体的一个扩容流程为:申请新的内存空间(空间大小为原空间的两倍或一点五倍)—>
·
C++的STL中vector的扩容思想及实现
原理
C++的STL库中的vector,是一种使用很频繁的容器,因为它是一个自动扩容的容器,使用起来比较灵活,可以一直往容器的末尾添加数据。
那么它是怎么实现自动扩容的呢?其实关键点就是对于容器里的元素数量进行判断,当容器的存储数量已经达到容量时,那么就需要进行一个倍增扩容了。整体的一个扩容流程为:申请新的内存空间(空间大小为原空间的两倍或一点五倍)—> 把原空间的元素拷贝到新的空间里 —> 释放原空间 —> 数组指针指向新空间。
实现
vec_inc.hpp
#ifndef _VECTOR_H_
#define _VECTOR_H_
#include <iostream>
using namespace std;
// 创建模板类
#define VECTOR_BASE_SIZE 5 // 默认基础容量
#define INC_BASE 2 // 默认扩容倍数
template <class T>
class Vector {
public:
// 常见的vector构造函数
Vector()
: _cap(VECTOR_BASE_SIZE), _size(0)
{
_arr = new T[VECTOR_BASE_SIZE];
}
Vector(int cap)
: _cap(cap), _size(0)
{
_arr = new T[cap];
}
Vector(int cap, T e)
: _cap(cap), _size(0)
{
_arr = new T[cap];
for (int i = 0; i < cap; i++)
_arr[i] = e;
}
~Vector()
{
if (_arr) {
delete[] _arr;
_arr = nullptr;
}
_cap = 0;
_size = 0;
}
// 向尾部插入元素
void push_back(T e)
{
// 先要判断当前的存储数量是不是已经到达容器容量
if (_cap == _size) // 已经到达最大容量了,需要进行扩容
{
// 开辟一块新的内存,原来的元素拷贝过去
T *new_arr = new T[_cap * 2];
for (int i = 0; i < _cap; i++)
new_arr[i] = _arr[i];
// 释放原来那块内存,重新指向
delete[] _arr;
_arr = new_arr;
_cap *= 2;
}
// 插入最后
_arr[_size++] = e;
}
// 删除尾部元素
void pop_back()
{
if (_size) // 有元素,让下标减1
_size--;
}
// 获取尾部元素
T back()
{
if (_size)
return _arr[_size - 1];
}
// 获取头部元素
T front()
{
if (_size)
return _arr[0];
}
// 重载下标运算符
T operator [](int idx)
{
if (idx >= _size || idx < 0) // 非法下标,不允许访问,返回相关出错信息
{
cout << "This index invalid.Return arguement idx." << endl;
return idx;
}
return _arr[idx];
}
// 获取容量和已存储数量
int size() const
{
return _size;
}
int capacity() const
{
return _cap;
}
private:
T* _arr;
int _cap;
int _size;
};
#endif // !_VECTOR_H_
main.cpp
#include <iostream>
#include "vec_inc.hpp"
using namespace std;
int main()
{
Vector<int> vec;
for (int i = 0; i < 10; i++) {
vec.push_back(i+1);
cout << "capacity: " << vec.capacity() << " size: " << vec.size() << endl;
}
cout << "idx: 5 element: " << vec[5] << endl;
return 0;
}
capacity: 5size: 1
capacity: 5size: 2
capacity: 5size: 3
capacity: 5size: 4
capacity: 5size: 5
capacity: 10size: 6
capacity: 10size: 7
capacity: 10size: 8
capacity: 10size: 9
capacity: 10size: 10
idx: 5 element: 6
总结
上面的程序只是对于vector的扩容原理进行简单的实现,大家可以参考,然后去实现一下,重在理解原理,倍增思想。
以上有什么错误的话,请大家积极指出,欢迎留言!
(码文不易,希望得到大家的点赞和关注)
更多推荐
已为社区贡献1条内容
所有评论(0)