vector底层原理和扩容机制以及简单实现

vector迭代器源码非常长，但底层原理（这篇博客非常清晰）

转载：C++ vector 底层实现_chengjian168的博客-CSDN博客_c++vector底层

重点：

1.三个指针表示一切操作

2.外加一个迭代器和重载操作符

迭代器扩容机制：线性扩容和倍数扩容的数学论证非常清晰。

c++ stl vector为什么两倍扩容？如何释放内存？_不想讀研的研究僧的博客-CSDN博客_vector为什么2倍扩容

重点：

假设：m：初始个数大小，x：扩容倍数，n是要存储的个数

m^x=n;; 为常数级

假设：m：初始个数大小，x：扩容固定次数，n是要存储的个数

mx=n;  ;  为指数级别

1.windows下扩容机制为1.5倍，linux为2倍。

2.个人不太认同1.5和2倍是更好的用以前开辟的内存空间，因为扩容后将原先的数据复制到新的内存上面，新内存地址一般都不会和原先内存地址连续，那怎么可能复用原先开辟的内存，除非记录了原先内存的位置，这样就矛盾了，vector是一个指针指向一片连续的内存空间，这样就导致指向的内存空间不连续，所以复用原先内存是不存在的。

vector代码的简单实现：这一篇的实现相对好很多

转载：vector容器的迭代器实现_知报的博客-CSDN博客_vector迭代器实现

这一篇代码非常详细，非常perfect,但是没涉及迭代器的实现

C++ 简单实现vector_吃米饭的博客-CSDN博客

 重点：

1.vector自身需要实现的函数包括：

(1)构造、虚构、复制、拷贝、初始化列表

(2)迭代器的开始和结束、emplace_back、pop_back、size、empty、重载[]操作符

右值移动折叠表达式实现有难度(后期有精力再补充)

2.迭代器需要实现的函数包括：

(1)重载操作符： !=,==,++,--,*

using namespace std;

template<typename T>
class MyVector
{
private:
    T* _first;//指针数组起始地址
    T* _last;//指针数组有效元素起始地址
    T* _end;//指针数组空间的最后地址
    void expand() //扩容机制
    {
        int size = _end - _first;
        T* _temp = new T[size * 2];
        for (int i=0;i<size;++i)
        {
            _temp[i]= _first[i];
        }
        delete[] _first;
        _first = nullptr;
        _first = _temp;
        _last = _first + size;
        _end = _first + 2 * size;
    }
public:
    //迭代器嵌套:需要重载操作符： !=,==,++,--,*
    class iterator
    {
    private:
        T* _ptr;
    public:
        iterator() :_ptr(nullptr) {};
        ~iterator() 
        {
            if (_ptr)
            {
                delete _ptr;
                _ptr = nullptr;
            }   
        };
        iterator(T* p = nullptr) :_ptr(p) {};
        iterator& operator=(const iterator& it)
        {
            if (this!=&it)
            {
                _ptr = it._ptr;
            }
            return *this;
        }
    public:
        bool operator!=(const iterator& it) const
        {
            return _ptr != it._ptr;
        }
        bool operator==(const iterator& it) const
        {
            return _ptr == it._ptr;
        }
        void operator++()
        {
            ++_ptr;
        }
        void operator--()
        {
            --_ptr;
        }
        T& operator*()
        {
            return *_ptr;
        }
    };

public:
    //需要的函数：构造、虚构、复制、拷贝、初始化列表
    MyVector() :_first(nullptr), _last(nullptr), _end(nullptr) {};
    virtual ~MyVector()
    {
        if (_first)
        {
            delete[] _first;
            _first = _last = _end = nullptr;
        }
    }
public:  
    MyVector(int num = 10)
    {
        _first = new T[num];
        _last = _first;
        _end = _first + num;
    }
    MyVector(const MyVector<T>& vec)
    {
        int size = vec._end - vec._first;
        int num = vec._last - vec._first;
        _first = new T[size];
        for (int i = 0; i < size; ++i)
        {
            _first[i] = vec._first[i];
        }
        _last = _first+ num;
        _end = _first + size;
    }
    MyVector<T>& operator=(const MyVector<T>& vec)
    {
        if (_first)
        {
            delete[] _first;
            _first = _last = _end = nullptr;
        }
        if (this!=&vec)
        {
            int size = vec._end - vec._first;
            int num = vec._last - vec._first;
            _first = new T[size];
            for (int i = 0; i < size; ++i)
            {
                _first[i] = vec._first[i];
            }
            _last = _first + num;
            _end = _first + size;
        }
        return *this;
    }
    MyVector(const initializer_list<T>& il)
    {
        int size = il.size();
        _first = new T[size];
        for (const T& var:il)
        {
            *_first= var;
            _first++;
        }
        _last= _first;
        _end = _first;
        _first -= size;
    }
public://需要实现其他函数：迭代器的开始和结束、emplace_back、pop_back、size、empty、重载[]操作符
    iterator begin()
    {
        return iterator(_first);
    }
    iterator end()
    {
        return iterator(_last);
    }
    int size() const
    {
        return _last - _first;
    }
    bool empty() const
    {
        return  _first==_last;
    }
    void emplace_back(const T& val)
    {
        if (_last == _end)
        {
            expand();
        }
        *_last++ = val;
    }
    void emplace_back(T&& val)
    {
        if (_last == _end)
        {
            expand();
        }
        *_last++ = val;
    }
    void pop_back()
    {
        if (empty())
        {
            return;
        }
        --_last;     
    }
    T& operator[](int index)
    {
        if (index < 0 || index >= size())
        {
            throw "OutRange";
        }
        return _first[index];
    }
};
int main()
{
    MyVector<int> data1{1,2,3,4};
    data1.emplace_back(5);
    MyVector<int> data(data1);
    for (int i=0;i<data.size();++i)
    {
        cout << data[i] << endl;
    }
    return 0;
}