介绍

• 主要使用数组实现了Vector中push_back和pop_back的操作
• 若一直push_back造成越界，自动设置一个更大的的数组来存放当前数据
• 若一直pop_back造被浪费的内存过多，自动设置一个更小的数组来存放当前数据
• 利用均摊复杂度防止在越界边缘连续pop和push频繁resize产生复杂度的震荡

代码实现

MyVector.h

#ifndef MYVECTOR_H
#define MYVECTOR_H
#include <assert.h>

template <typename T>
class MyVector
{
private:
    T* data;        //存放数据的数组
    int capacity;   //容量
    int size;       //储存数组中的元素个数
  
    //重新设置新的数组
    //使用均摊复杂度来降低平均的复杂度
    void resize(int newCapactiry)
    {
        assert(newCapactiry >= size);
        T* newData = new T[newCapactiry];
        //将老的数据存到新开的数组中
        for(int i = 0; i < size; i++)
        {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
        capacity = newCapactiry;
    }
public:
    MyVector()
    {
        data = new T[10];
        capacity = 10;
        size = 0;
    }
    ~MyVector()
    {
        delete[] data;
    }
  
    //平均复杂度为O(1)
    void push_back(T e)
    {
        if(size == capacity)
        {
            resize(2*capacity);
        }
        assert(size < capacity);
        data[size++] = e;
    }
  
    //平均复杂度为O(1)
    T pop_back()
    {
        assert(size > 0);
        T ret = data[size];
        size --;
        //防止连续pop和push产生复杂度的震荡
        if(size == capacity/4)
        {
            resize(capacity/2);
        }
        return ret;
    }

};

#endif

MyVector.cpp（测试）

#include <iostream>
#include <cmath>
#include "MyVector.h"
using namespace std;
int main()
{
    for(int i = 10; i <= 26; i++)
    {
        int n = pow(2,i);
        clock_t startTime = clock();
        MyVector<int> vec;
        for(int i = 0; i < n; i++)
        {
            vec.push_back(i);
        }
        for(int i = 0; i < n; i++)
        {
            vec.pop_back();
        }
        clock_t endTime = clock();
  
        cout<<2*n<<" operations:\t";
        cout<<double(endTime - startTime)/CLOCKS_PER_SEC<<"s"<<endl;
    }
    return 0;
}

更多C++知识

https://github.com/lengyueling/AlgorithmStudy