vector底层所采用的数据结构非常简单，就只是一段连续的线性内存空间
vector维护了三个迭代器first last end，分别指向起始字节位置，当前最后一个元素的位置，整个容器所占用内存空间的末尾字节
当 vector 的大小和容量相等（size==capacity）也就是满载时，如果再向其添加元素， vector 就需要扩容。vector 容器扩容的过程需要经历以下 3 步：完全弃用现有的内存空间，重新申请更大的内存空间；将旧内存空间中的数据，按原有顺序移动到新的内存空间中；最后将旧的内存空间释放。
底层实现：https://www.cnblogs.com/-citywall123/p/12846941.html
```
#ifndef _MY_VECTOR_HPP_
#define _MY_VECTOR_HPP_
```

template class MyVector {

public: // 构造函数 MyVector() { //这里默认数组大小为10 //但是vector文件中默认构造的方式是0，之后插入按照1 2 4 8 16 二倍扩容。注（GCC是二倍扩容，VS13是1.5倍扩容 data = new T[10]; _capacity = 10; _size = 0; } ~MyVector() { delete[] data; } //reserve只是保证vector的空间大小(_capacity)最少达到它的参数所指定的大小n。在区间[0, n)范围内,预留了内存但是并未初始化 void reserve(size_t n) { if(n>_capacity) { data = new T[n]; _capacity = n; } } //向数组中插入元素 void push_back(T e) { //如果当前容量已经不够了，重新分配内存，均摊复杂度O(1) if (_size == _capacity) { resize(2 _capacity); } data[_size++] = e; } //删除数组尾部的数据，同时动态调整数组大小，节约内存空间 T pop_back() { T temp = data[_size]; _size--; //如果容量有多余的，释放掉 if (_size == _capacity / 4) { resize(_capacity / 2); } return temp; } //获取当前数组中元素的个数 size_t size() { return _size; } //判断数组是否为空 bool empty() { return _size==0?1:0; } //重载[]操作 int &operator[](int i) { return data[i]; } //获取数组的容量大小 size_t capacity() { return _capacity; } //清空数组,只会清空数组内的元素，不会改变数组的容量大小 void clear() { _size=0; } private: T data; //实际存储数据的数组 size_t _capacity; //容量 size_t _size; //实际元素个数 //扩容 void resize(int st) { //重新分配空间，在栈区新开辟内存，然后将以前数组的值赋给他，删除以前的数组 T *newData = new T[st]; for (int i = 0; i < _size; i++) { newData[i] = data[i]; } //实际使用时是清除数据，但不会释放内存 delete[] data; data = newData; _capacity = st; }

};

endif //_MY_VECTORHPP

测试代码：

include

include "MyVector.hpp"

using namespace std; int main() { int size=11; MyVector p; p.reserve(5); cout<<"size="<<p.size()<<"capacity="<<p.capacity()<<endl; for (int i = 0; i < size; i++) { p.push_back(i); }

for(int i=0;i<size;i++)
{
    cout<<p[i]<<' ';
}
cout<<endl;
printf("size=%d     capcity=%d\n",p.size(),p.capacity());

// MyVector<string>pp;

// for(int i=0;i<5;i++)
// {
//     pp.push_back("str");
// }
// cout<<pp.size()<<"        "<<pp.capacity()<<endl;
cout<<endl;
return 0;

}

zhangyuanes / cpp-interviews-questions

【2021-腾讯实习一面】3.vector底层实现 #20

endif //_MY_VECTORHPP

include

include

include "MyVector.hpp"