STL vector的内部实现原理及基本用法

缺乏、安全感 2022-07-13 03:55 161阅读 0赞

【原文：[http://blog.csdn.net/u012658346/article/details/50725933][http_blog.csdn.net_u012658346_article_details_50725933]】

本文基于STL vector源代码，但是不考虑分配器allocator，迭代器iterator，异常处理try/catch等内容，同时对\_Ucopy（）、 \_Umove（）、 \_Ufill（）函数也不会过度分析。

## 一、vector的定义 ##

template<class _Ty,
        class _Ax>
        class vector
            : public _Vector_val<_Ty, _Ax>
        {   // varying size array of values
    public:
        /********/
    protected:
        pointer _Myfirst;   // pointer to beginning of array
        pointer _Mylast;    // pointer to current end of sequence
        pointer _Myend; // pointer to end of array
        };
    
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13

简单理解，就是vector是利用上述三个指针来表示的，基本示意图如下：  
![这里写图片描述][20160223191226316]  
两个关键大小：  
大小：size=\_Mylast - \_Myfirst；  
容量：capacity=\_Myend - \_Myfirst；  
分别对应于resize()、reserve()两个函数。  
size表示vector中已有元素的个数，容量表示vector最多可存储的元素的个数；为了降低二次分配时的成本，vector实际配置的大小可能比客户需求的更大一些，以备将来扩充，这就是容量的概念。即capacity>=size，当等于时，容器此时已满，若再要加入新的元素时，就要重新进行内存分配，整个vector的数据都要移动到新内存。二次分配成本较高，在实际操作时，应尽量预留一定空间，避免二次分配。

## 二、构造与析构 ##

1、构造  
vector的构造函数主要有以下几种：

vector() : _Mybase()
            {   // construct empty vector
            _Buy(0);
            }       
        explicit vector(size_type _Count) : _Mybase()
            {   // construct from _Count * _Ty()
            _Construct_n(_Count, _Ty());
            }
        vector(size_type _Count, const _Ty& _Val) : _Mybase()
            {   // construct from _Count * _Val
            _Construct_n(_Count, _Val);
            }
        vector(const _Myt& _Right) : _Mybase(_Right._Alval)
            {   // construct by copying _Right
            if (_Buy(_Right.size()))
                _Mylast = _Ucopy(_Right.begin(), _Right.end(), _Myfirst);
            }
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
         17 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
         17

vector优异性能的秘诀之一，就是配置比其所容纳的元素所需更多的内存，一般在使用vector之前，就先预留足够空间，以避免二次分配，这样可以使vector的性能达到最佳。因此元素个数\_Count是个远比元素值 \_Val重要的参数，因此当构造一个vector时，首要参数一定是元素个数。  
由上各构造函数可知，基本上所有构造函数都是基于\_Construct \_n() 的

bool _Buy(size_type _Capacity)
            {   // allocate array with _Capacity elements
            _Myfirst = 0, _Mylast = 0, _Myend = 0;
            if (_Capacity == 0)    //_Count为0时，直接返回
                return (false);
            else
                {   // nonempty array, allocate storage
                _Myfirst = this->_Alval.allocate(_Capacity);  //分配内存，并更新成员变量
                _Mylast = _Myfirst;
                _Myend = _Myfirst + _Capacity;
                }
            return (true);
            }
    
        void _Construct_n(size_type _Count, const _Ty& _Val)
            {   // 构造含有_Count个值为_Val的元素的容器
            if (_Buy(_Count))
                _Mylast = _Ufill(_Myfirst, _Count, _Val);
            }
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
         17 
         18 
         19 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
         17 
         18 
         19

这样就完成了vector容器的构造了。

2、析构  
vector的析构函数很简单，就是先销毁所有已存在的元素，然后释放所有内存

void _Tidy()
            {   // free all storage
            if (_Myfirst != 0)
                {   // something to free, destroy and deallocate it
                _Destroy(_Myfirst, _Mylast);
                this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);
                }
            _Myfirst = 0, _Mylast = 0, _Myend = 0;
            }
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9

## 三、插入和删除元素 ##

vector的插入和删除元素是通过push\_ back () 、 pop\_back()两个接口来实现的，他们的内部实现也非常简单

void push_back(const _Ty& _Val)
            {   // insert element at end
            if (size() < capacity())
                _Mylast = _Ufill(_Mylast, 1, _Val);
            else
                insert(end(), _Val);    //空间不足时，就会触发内存的二次分配
            }
    
        void pop_back()
            {   // erase element at end
            if (!empty())
                {   // erase last element
                _Destroy(_Mylast - 1, _Mylast);
                --_Mylast;
                }
            }
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16

## 四、其他接口 ##

1、reserve()操作

之前提到过reserve（Count） 函数主要是预留Count大小的空间，对应的是容器的容量，目的是保证（\_Myend - \_Myfirst）>=Count。只有当空间不足时，才会操作，即重新分配一块内存，将原有元素拷贝到新内存，并销毁原有内存

void reserve(size_type _Count)
            {   // determine new minimum length of allocated storage
            if (capacity() < _Count)
                {   // not enough room, reallocate
                pointer _Ptr = this->_Alval.allocate(_Count);
                _Umove(begin(), end(), _Ptr);
                size_type _Size = size();
                if (_Myfirst != 0)
                    {   // destroy and deallocate old array
                    _Destroy(_Myfirst, _Mylast);
                    this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);
                    }
                _Myend = _Ptr + _Count;
                _Mylast = _Ptr + _Size;
                _Myfirst = _Ptr;
                }
            }
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
         17 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
         17

2、resize()操作  
resize（Count） 函数主要是用于改变size的，也就是改变vector的大小，最终改变的是（\_Mylast - \_Myfirst）的值，当size < Count时,就插入元素，当size >Count时，就擦除元素。

void resize(size_type _Newsize, _Ty _Val)
            {   // determine new length, padding with _Val elements as needed
            if (size() < _Newsize)
                _Insert_n(end(), _Newsize - size(), _Val);
            else if (_Newsize < size())
                erase(begin() + _Newsize, end());
            }
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7

3、\_Insert\_n()操作

resize()操作和insert()操作都会利用到\_Insert\_n()这个函数，这个函数非常重要，也比其他函数稍微复杂一点  
虽然\_Insert\_n(\_where, \_Count, \_Val ) 函数比较长，但是操作都非常简单，主要可以分为以下几种情况：

*  1、\_Count == 0，不需要插入，直接返回
 *  2、max\_size() - size() < \_Count，超过系统设置的最大容量，会溢出，造成Xlen（）异常
 *  3、\_Capacity < size() + \_Count，vector的容量不足以插入Count个元素，需要进行二次分配，扩大vector的容量。 在VS下，vector容量会扩大50%，即 \_Capacity = \_Capacity + \_Capacity / 2;  
    若仍不足，则 \_Capacity = size() + \_Count;

else if (_Capacity < size() + _Count)
                {   // not enough room, reallocate
                _Capacity = max_size() - _Capacity / 2 < _Capacity
                    ? 0 : _Capacity + _Capacity / 2;    // try to grow by 50%
                if (_Capacity < size() + _Count)
                    _Capacity = size() + _Count;
                pointer _Newvec = this->_Alval.allocate(_Capacity);
                pointer _Ptr = _Newvec;
                _Ptr = _Umove(_Myfirst, _VEC_ITER_BASE(_Where),_Newvec);    // copy prefix
                _Ptr = _Ufill(_Ptr, _Count, _Val);  // add new stuff
                _Umove(_VEC_ITER_BASE(_Where), _Mylast, _Ptr);  // copy suffix
                //内存释放与变量更新
                }
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13

这种情况下，数据从原始容器移动到新分配内存时是从前到后移动的  
![这里写图片描述][20160223201833669]

*  4、空间足够，且被插入元素的位置比较靠近\_Mylast,即已有元素的尾部
    
    这种情况下不需要再次进行内存分配，且数据是从后往前操作的。首先是将where~last向后移动，为待插入数据预留Count大小的空间，然后从\_Mylast处开始填充，然后将从where处开始填充剩余元素

else if ((size_type)(_Mylast - _VEC_ITER_BASE(_Where)) < _Count)
                {   // new stuff spills off end
                _Umove(_VEC_ITER_BASE(_Where), _Mylast,
                    _VEC_ITER_BASE(_Where) + _Count);   // copy suffix
                _Ufill(_Mylast, _Count - (_Mylast - _VEC_ITER_BASE(_Where)),
                    _Val);  // insert new stuff off end
                _Mylast += _Count;
                std::fill(_VEC_ITER_BASE(_Where), _Mylast - _Count,
                    _Val);  // insert up to old end
                }
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10

*  5、空间足够，但插入的位置比较靠前

{   // new stuff can all be assigned
                _Ty _Tmp = _Val;    // in case _Val is in sequence
    
                pointer _Oldend = _Mylast;
                _Mylast = _Umove(_Oldend - _Count, _Oldend,
                    _Mylast);   // copy suffix
                _STDEXT _Unchecked_move_backward(_VEC_ITER_BASE(_Where), _Oldend - _Count,
                    _Oldend);   // copy hole
                std::fill(_VEC_ITER_BASE(_Where), _VEC_ITER_BASE(_Where) + _Count,
                    _Tmp);  // insert into hole
                }
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11

4、erase()操作

iterator erase(const_iterator _First_arg,
            const_iterator _Last_arg)
            {   // erase [_First, _Last)
            iterator _First = _Make_iter(_First_arg);
            iterator _Last = _Make_iter(_Last_arg);
    
            if (_First != _Last)
                {   // worth doing, copy down over hole
                pointer _Ptr = _STDEXT unchecked_copy(_VEC_ITER_BASE(_Last), _Mylast,
                    _VEC_ITER_BASE(_First));
    
                _Destroy(_Ptr, _Mylast);
                _Mylast = _Ptr;
                }
            return (_First);
            }
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16

主要操作就是将后半部分的有效元素向前拷贝，并将后面空间的无效元素析构，并更新\_Mylast变量  
![这里写图片描述][20160223203457456]

5、assign()操作

assign()操作最终都会调用到下面的函数，主要操作是首先擦除容器中已有的全部元素，在从头开始插入Count个Val元素

void _Assign_n(size_type _Count, const _Ty& _Val)
            {   // assign _Count * _Val
            _Ty _Tmp = _Val;    // in case _Val is in sequence
            erase(begin(), end());
            insert(begin(), _Count, _Tmp);
            }
       
        
         1 
         2 
         3 
         4 
         5 
         6 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6

五、基本使用  
在经过上述对vector内部实现的分析后，再来理解相应接口就变得简单得多。  
vector对外接口主要可以分为：

*  构造、析构：

ector<Elem> c
    vector <Elem> c1(c2)
    vector <Elem> c(n)
    vector <Elem> c(n, elem)
    vector <Elem> c(beg,end)
    c.~ vector <Elem>()
       
        
         1 
         2 
         3 
         4 
         5 
         6 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6

*  插入、删除、赋值

c.push_back(elem)
    c.pop_back()
    c.insert(pos,elem)
    c.insert(pos,n,elem)
    c.insert(pos,beg,end)
    c.erase(pos)
    c.erase(beg,end)
    c.clear()
    c.assign(beg,end)
    c.assign(n,elem)
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10

*  大小相关

c.capacity()
    c.max_size()
    c.resize(num)
    c.reserve()
    c.size()
       
        
         1 
         2 
         3 
         4 
         5 
        
       
        
         1 
         2 
         3 
         4 
         5

*  获取迭代器

c.begin()
    c.end()
    c.rbegin()
    c.rend()
       
        
         1 
         2 
         3 
         4 
        
       
        
         1 
         2 
         3 
         4

*  获取数据

operator[]
    c.at(idx)
    c.front()
    c.back()
       
        
         1 
         2 
         3 
         4 
        
       
        
         1 
         2 
         3 
         4

[http_blog.csdn.net_u012658346_article_details_50725933]: http://blog.csdn.net/u012658346/article/details/50725933
[20160223191226316]: /images/20220713/89c40f7303e94ababc30f810eaad7fa2.png
[20160223201833669]: /images/20220713/c4148f9ed4b548ec82352a43c51510f9.png
[20160223203457456]: /images/20220713/df42a9b5101545f9ab5efe717b8a3546.png