c++ stl vector（针对扩充空间策略）

1.vector

vector的数据安排以及操作方式，与array非常相似，两者的唯一差别在于空间的运用的灵活性。vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。因此，vector的运用对内存的合理利用与运用的灵活性有很大的帮助。vector的实现技术，关键在于对其大小的控制以及重新配置时的数据移动效率。

2.函数成员

2.1构造函数：

/// Creates an empty vector.
vector();
/// Creates a vector with n elements.
vector(size_type n);
/// Creates a vector with n copies of t.
vector(size_type n, const T& t);
/// The copy constructor.
vector(const vector&);
/// Creates a vector with a copy of a range.
template <class InputIterator> vector(InputIterator, InputIterator);

2.2析构函数：

/// The destructor.
~vector();

2.3插入元素：

/// Inserts a new element at the end.
void push_back(const T&);
/// Inserts x before pos.
iterator insert(iterator pos, const T& x);
/// Inserts the range [first, last) before pos.
template <class InputIterator> void insert(iterator pos, InputIterator f, InputIterator l);
/// Inserts n copies of x before pos.
void insert(iterator pos, size_type n, const T& x);

2.4删除元素：

/// Removes the last element.
void pop_back();
/// Erases the element at position pos.
iterator erase(iterator pos);
/// Erases the range [first, last).
iterator erase(iterator first, iterator last);
/// Erases all of the elements.
void clear();
/// Inserts or erases elements at the end such that the size becomes n.
void resize(n, t = T());

2.5返回元素指针或元素：

/// Returns an iterator pointing to the beginning of the vector.
iterator begin();
/// Returns an iterator pointing to the end of the vector.
iterator end();
/// Returns a reverse_iterator pointing to the beginning of the reversed vector.
reverse_iterator rbegin();
/// Returns a reverse_iterator pointing to the end of the reversed vector.
reverse_iterator rend();
/// Returns the n'th element.
reference operator[](size_type n);
/// Returns the first element.
reference front();	
/// Returns the last element.
reference back();

2.6其他：

/// true if the vector's size is 0.
bool empty() const;
/// Returns the size of the vector.
size_type size();
/// 返回容量大小
size_type capacity() const;
/// 设置容量大小
void reserve(size_t);

3.实例

3.1

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    typedef std::vector<int> IVEC;

    /// 1.实例对象
    IVEC first;                                  // empty
    IVEC second(3);                              // 0 0 0
    IVEC third(5,10);                            // 10 10 10 10 10
    IVEC fourth(third);                          // 10 10 10 10 10
    IVEC fifth(fourth.begin(),fourth.end());     // 10 10 10 10 10

    /// 2.插入元素
    IVEC iVector;
    /// 2.1容器尾部插入元素
    iVector.push_back(1);                        // 1
    iVector.push_back(2);                        // 1 2
    iVector.push_back(3);                        // 1 2 3
    iVector.push_back(4);                        // 1 2 3 4
    iVector.push_back(5);                        // 1 2 3 4 5
    /// 2.2查找元素，指定位置之前插入元素
    IVEC::iterator ivIte = find(iVector.begin(),iVector.end(),3);
    if(ivIte != iVector.end())
        iVector.insert(ivIte,3,9);               // 1 2 9 9 9 3 4 5

    /// 3.删除元素
    /// 3.1删除尾部元素
    iVector.pop_back();                          // 1 2 9 9 9 3 4
    iVector.pop_back();                          // 1 2 9 9 9 3
    iVector.pop_back();                          // 1 2 9 9 9
    /// 3.2删除制定元素
    ivIte = find(iVector.begin(),iVector.end(),2);
    if(ivIte != iVector.end())
        iVector.erase(ivIte);                    // 1 9 9 9
    /// 3.3清空元素
    iVector.clear();                             // empty

    /// 4.访问元素
    iVector.push_back(1);
    iVector.push_back(2);
    iVector.push_back(3);
    /// 4.1通过索引值（从0开始）访问存在的某个元素
    int nPos = iVector[1];                       // 2
    /// 4.2访问首部元素
    int nFront = iVector.front();                // 1
    /// 4.3访问尾部元素
    int nEnd = iVector.back();                   // 3

    return 0;
}

3.2

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    typedef std::vector<int> IVEC;

    IVEC iVec(2,4);
    std::cout<<"size : "<<iVec.size()<<std::endl;
    std::cout<<"capacity : "<<iVec.capacity()<<std::endl;
    // size     : 2
    // capacity : 2
    iVec.push_back(1);
    std::cout<<"size : "<<iVec.size()<<std::endl;
    std::cout<<"capacity : "<<iVec.capacity()<<std::endl;
    // 没有备用空间，扩充空间大小为2 * 2
    // size     : 3
    // capacity : 4
    iVec.push_back(2);
    std::cout<<"size : "<<iVec.size()<<std::endl;
    std::cout<<"capacity : "<<iVec.capacity()<<std::endl;
    // size     : 4
    // capacity : 4
    iVec.push_back(3);
    std::cout<<"size : "<<iVec.size()<<std::endl;
    std::cout<<"capacity : "<<iVec.capacity()<<std::endl;
    // 没有备用空间，扩充空间大小为4 * 2
    // size     : 5
    // capacity : 8
    iVec.push_back(4);
    std::cout<<"size : "<<iVec.size()<<std::endl;
    std::cout<<"capacity : "<<iVec.capacity()<<std::endl;
    // size     : 6
    // capacity : 8
    iVec.push_back(5);
    std::cout<<"size : "<<iVec.size()<<std::endl;
    std::cout<<"capacity : "<<iVec.capacity()<<std::endl;
    // size     : 7
    // capacity : 8
    iVec.push_back(6);
    std::cout<<"size : "<<iVec.size()<<std::endl;
    std::cout<<"capacity : "<<iVec.capacity()<<std::endl;
    // size     : 8
    // capacity : 8
//    IVEC::iterator ivIte = iVec.begin();
    iVec.push_back(7);
    std::cout<<"size : "<<iVec.size()<<std::endl;
    std::cout<<"capacity : "<<iVec.capacity()<<std::endl;
    // 没有备用空间，扩充空间大小为8 * 2
    // size     : 9
    // capacity : 16
//    iVec.erase(ivIte);

    IVEC GoodIVec;
    GoodIVec.reserve(16);
    for(int i = 0;i < 16;i++)
    {
        GoodIVec.push_back(i);
        std::cout<<"size : "<<GoodIVec.size()<<std::endl;
        std::cout<<"capacity : "<<GoodIVec.capacity()<<std::endl;
    }
    // 存在备用空间，没有发生过扩充空间
    // size     : i
    // capacity : 16

    return 0;
}

4.解析

push_back()函数，如果无备用空间调用_M_insert_aux()重新分配空间。

void push_back(const _Tp& __x) {  
  /// 存在备用空间
  if (_M_finish != _M_end_of_storage) {  
    /// placement new
    construct(_M_finish, __x);  
    /// 向后移动使用空间的尾迭代器
    ++_M_finish;  
  }
  /// 没有备用空间
  else  
    _M_insert_aux(end(), __x);  
}  

template <class _Tp, class _Alloc>  
void   
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)  
{  
  if (_M_finish != _M_end_of_storage) {  
    construct(_M_finish, *(_M_finish - 1));  
    ++_M_finish;  
    _Tp __x_copy = __x;  
    copy_backward(__position, _M_finish - 2, _M_finish - 1);  
    *__position = __x_copy;  
  }  
  /// 已无备用空间
  else {  
    const size_type __old_size = size();  
    /// 原空间大小不为0，则配置原大小的两倍
    const size_type __len = __old_size != 0 ? 2 * __old_size : 1; 
    /// 申请新vector的空间，大小__len
    iterator __new_start = _M_allocate(__len);  
    iterator __new_finish = __new_start;  
    __STL_TRY {  
      /// 从新vector首部开始，将原vector的内容拷贝到新vector
      __new_finish = uninitialized_copy(_M_start, __position, __new_start);  
      /// 在新vector的__new_finish位置上，为新元素设定初始值__x
      construct(__new_finish, __x);  
      /// 向后移动使用空间的尾迭代器
      ++__new_finish;  
      /// __position = _M_finish拷贝空集？
      __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);  
    }  
    __STL_UNWIND((destroy(__new_start,__new_finish),   
                  _M_deallocate(__new_start,__len))); 
    /// 析构原vector的元素
    destroy(begin(), end());  
    /// 释放原vector的空间
    _M_deallocate(_M_start, _M_end_of_storage - _M_start);  
    _M_start = __new_start;  
    _M_finish = __new_finish;  
    _M_end_of_storage = __new_start + __len;  
  }  
}  

1）扩充空间不是在原空间之后接续新空间，而是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对vector的任何操作，

一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。

例：46行 IVEC::iterator ivIte = iVec.begin();定义迭代器ivIte，53行 iVec.erase(ivIte);此时vector已经发生空间重新配置，再去调用ivIte就会引发错误。

2）预估vector容器空间大小，

使用reserve()提前设定空间大小（capacity）可以避免不必要的空间重新分配。

5.参考文献

本文内容摘录于《STL源码剖析》