STL中vector的原理

参考链接 C++ 实现原理STL之容器用法 简介

实际上是一个动态数组，预先指向一段连续的已分配好的内存空间。

原理

通俗地讲，当在 中插入元素且 当前的容量不足以存放时， 会重新开辟一段新的内存空间，将原有的数据全部拷贝到新空间后并插入新数据后，再将原有的空间段进行释放。

内部原理

扩容过程测试：

#include 
#include using namespace std;int main()
{vector<int> myVector;for (int i = 0; i < 100; i++) {myVector.push_back(i);cout << "size: " << myVector.size() << " capacity: " << myVector.capacity() << endl;}return 0;
}

运行代码部分打印如下：

size: 1 capacity: 1
size: 2 capacity: 2
size: 3 capacity: 3
size: 4 capacity: 4
size: 5 capacity: 6
size: 6 capacity: 6
size: 7 capacity: 9
size: 8 capacity: 9
size: 9 capacity: 9
size: 10 capacity: 13
size: 11 capacity: 13
size: 12 capacity: 13
size: 13 capacity: 13
size: 14 capacity: 19
size: 15 capacity: 19
size: 16 capacity: 19
size: 17 capacity: 19
size: 18 capacity: 19
size: 19 capacity: 19
size: 20 capacity: 28
size: 21 capacity: 28
size: 22 capacity: 28
size: 23 capacity: 28
size: 24 capacity: 28
size: 25 capacity: 28
size: 26 capacity: 28
size: 27 capacity: 28
size: 28 capacity: 28
size: 29 capacity: 42

注意：每次扩容容量会增加原来内存大小的2倍或1.5倍。

() 和 ()的区别

注意：当 (_size) 中_size 数值大于 时，同样需要重新分配内存，即执行了 ()。

的实现

#include 
#include 
#include 
using namespace std;
#define MAX_CAP 10template <class T>
class Vector{
private:int size;int cap;T* ptr;
public:explicit Vector(int size=0): // 构造函数size(size), cap(size+MAX_CAP) {ptr = new T[cap]; // 分配一个这么大的内存}~Vector() { // 折构函数delete[] ptr;}Vector(const Vector& V) : // 拷贝构造函数size(0), cap(0), T(nullptr) {*this = V;}Vector& operator=(const Vector& V) { // 赋值操作符重载if (this != V) { // 放置拷贝自身delete[] ptr;size = V.size;cap = V.cap;ptr = new T[cap];ptr = V.ptr;for (int i=0; i<V.size; i++) {ptr[i] = V.ptr[i];}}return *this;}/** resize函数：改变size大小，cap不变，如果size>cap，那么重新分配内存*/void resize(int newSize) {if (newSize <= size) return;if (newSize > cap) // 超出容量，重新分配内存大小reserve(newSize);}/** reserve函数：重新分配内存大小，改变cap大小，不改变size大小*/void reserve(int newCap) {if (newCap < cap) return;T* p = ptr; // 先临时拷贝存储一下ptr = new T[newCap];for (int i=0; i<size; i++) {ptr[i] = p[i]; // 拷贝回来}delete[] p; // 释放原来空间}/** []操作符：模拟取下表功能*/const T&operator[](int index) const {return ptr[index];}/** push_back函数：尾部插入一个元素，非常重要*/void push_back(T t) {if (size == cap) {reserve(2 * cap + 1); // 扩容一倍}ptr[size++] = t;}/** pop_back函数：尾部删除一个元素*/void pop_back() {size--; // 这边有点问题????}/** 下面定义一些迭代器*/int getSize() {return size;}typedef T* iterator;typedef const T* const_iterator;iterator begin() {return &ptr[0];}iterator end() {return &ptr[size];}const_iterator cbegin() const {return &ptr[0];}const_iterator cend() const {return &ptr[size];}
};int main()
{Vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);for (auto i=v.cbegin(); i!=v.cend(); i++) {cout << *i << endl;}return 0;
}