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
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& 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& operator=(const MyVector& 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& 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 data1{1,2,3,4};
    data1.emplace_back(5);
    MyVector data(data1);
    for (int i=0;i

 

 

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/579464.html