程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 帶你深入理解STL之Vector容器

帶你深入理解STL之Vector容器

編輯:關於C++

C++內置了數組的類型,在使用數組的時候,必須指定數組的長度,一旦配置了就不能改變了,通常我們的做法是:盡量配置一個大的空間,以免不夠用,這樣做的缺點是比較浪費空間,預估空間不當會引起很多不便。

STL實現了一個Vector容器,該容器就是來改善數組的缺點。vector是一個動態空間,隨著元素的加入,它的內部機制會自行擴充以容納新元素。因此,vector的運用對於內存的合理利用與運用的靈活性有很大的幫助,再也不必因為害怕空間不足而一開始就配置一個大容量數組了,vector是用多少就分配多少。

要想實現動態分配數組,Vector內部就需要對空間控制做到有效率的掌控,這些機制要如何運作才能高效地實現動態分配呢?本篇博客就從源代碼的角度帶你領略一下Vector容器內部的構造藝術。

Vector概述

大家知道,初始化一個數組的時候,需要給數組分配一塊內存,數組中的數據都是按序存放的。vector也是如此,再初始化的時候給vector容器分配一塊內存,用來存放容器中的數據,一旦分配的內存不足以存放新加入的數據時,就需要擴充空間。STLVector的做法是:重新開辟一段新的空間,將原空間的數據遷移過去,然後新加入的數據存放在新空間之後並釋放掉原有空間。

在這個過程中,配置新空間->數據移動->釋放舊空間會帶來一定的時間成本,所以必須盡可能高效的實現,STL的Vector設計中對這一部分做了相當大的優化,使得時間成本盡可能的小。下面就一起去看看這些優秀的設計吧↓。

Vector的數據結構

我們從最簡單的開始,Vector的數據結構相當簡單,由於需要判斷內存是否夠用,所以要用到三個指針,分別指向頭,目前使用空間的尾,目前可用空間的尾。其源代碼如下:

template //alloc是STL的空間配置器
class vector
{
    // 這裡提供STL標准的allocator接口
  typedef simple_alloc data_allocator;

  iterator start;               // 內存空間起始點
  iterator finish;              // 當前使用的內存空間結束點
  iterator end_of_storage;      // 實際分配內存空間的結束點
}

每當初始化一個vector的時候,先分配一段內存,稱為目前可用空間,大小為end_of_storage - start + 1,當往vector裡面加入數據的時候,finish就往後移,代表目前已使用的空間,這樣做的好處是,不用頻繁的擴充空間和轉移數據,使得時間成本下降。

在上述代碼中,我們看到vector采用了STL標准的空間配置其接口

vector提供了如下函數來支持獲取其數據結構中的相關參數。

//獲取指向vector首元素的迭代器
iterator begin() { return start; }

//獲取指向vector尾元素的迭代器
iterator end() { return finish; }

// 返回當前對象個數,即已使用空間的大小
size_type size() const { return size_type(end() - begin()); }

// 返回重新分配內存前最多能存儲的對象個數,即目前可用空間的大小
size_type capacity() const { return size_type(end_of_storage - begin()); }

Vector的迭代器

既然是STL的容器,必須要滿足迭代器的相關要求

vector維護的是一段連續的內存空間,所以不論容器中元素的型別為何,普通指針都可以作為vector的迭代器而滿足所有必要的條件。vector支持隨機存取,所以vector提供的是Random Access Iterator。

下面來看看vector關於迭代器的源碼:

template 
class vector
{
public:
    // vector內部是連續內存空間,所以迭代器采用原生指針即可
  typedef value_type* iterator;                                 

  //以下為滿足Traits功能定義的內嵌型別
  typedef T value_type;
  typedef value_type* pointer;                  
  typedef const value_type* const_pointer;
  typedef const value_type* const_iterator;
  typedef value_type& reference;                
  typedef const value_type& const_reference;
  typedef ptrdiff_t difference_type;  

  typedef size_t size_type;         
}

vector的構造函數

默認構造函數

在使用vector的時候,我們通常會有如下定義:

#include 

vector vec;

在上述定義中,調用了vector的默認構造函數,其默認不分配內存空間,如下:

// vector的默認構造函數默認不分配內存空間
vector() : start(0), finish(0), end_of_storage(0) {}

帶參構造函數

通常,vector的初始化可以指定元素個數和初始化類型。如下:

vector vec(10,1); // 將vec初始化為10個1

vector提供下面的構造函數以支持上述初始化操作:

 

帶參構造函數

 <喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwcmUgY2xhc3M9"brush:java;"> // 構造函數,允許指定vector的元素個數和初值 vector(size_type n, const T& value) { fill_initialize(n, value); } vector(int n, const T& value) { fill_initialize(n, value); } vector(long n, const T& value) { fill_initialize(n, value); } // 需要對象提供默認構造函數 explicit vector(size_type n) { fill_initialize(n, T()); } /** * 填充並予以初始化 */ void fill_initialize(size_type n, const T& value) { start = allocate_and_fill(n, value); finish = start + n; // 設置當前使用內存空間的結束點 //這裡不過多的分配內存 end_of_storage = finish; } /** * 配置一塊大小為n的內存空間,並予以填充 */ iterator allocate_and_fill(size_type n, const T& x) { // 調用STL的空間配置器配置一塊大小為n的內存空間 iterator result = data_allocator::allocate(n); // 調用底層函數uninitialized_fill_n予以填充 uninitialized_fill_n(result, n, x); return result; }

這裡面調用了uninitialized_fill_n函數,這個函數是STL的內存基本處理函數,存放在stl_uninitialized.h中,下面來看看它的源碼:

// 如果copy construction和operator =等效, 並且destructor is trivial
// 那麼就可以使用本函數
template 
inline ForwardIterator
__uninitialized_fill_n_aux(ForwardIterator first, Size n,
                           const T& x, __true_type)
{
  return fill_n(first, n, x);
}
// 不是POD類型使用以下函數
template 
ForwardIterator
__uninitialized_fill_n_aux(ForwardIterator first, Size n,
                           const T& x, __false_type)
{
  ForwardIterator cur = first;
  for ( ; n > 0; --n, ++cur)
    construct(&*cur, x);
  return cur;
}
// 利用type_traits來判斷是否是POD類型
template 
inline ForwardIterator __uninitialized_fill_n(ForwardIterator first, Size n,
    const T& x, T1*)
{
  typedef typename __type_traits::is_POD_type is_POD;
  return __uninitialized_fill_n_aux(first, n, x, is_POD());

}
// 利用Iterator_traits來萃取出其值類型
template 
inline ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n,
    const T& x)
{
  return __uninitialized_fill_n(first, n, x, value_type(first));
}

vector的元素操作函數

push_back()

push_back()函數將新元素插入於vector的尾部,該函數再完成這一操作的時候,先檢查是否還有備用空間,如果有直接再備用空間上構造函數;如果沒有就擴充空間,通過重新配置一塊大空間,移動數據,釋放原空間的操作來完成push_back操作。其源代碼如下:

////////////////////////////////////////////////////////////////////////////////
// 向容器尾追加一個元素, 可能導致內存重新分配
////////////////////////////////////////////////////////////////////////////////
//                          push_back(const T& x)
//                                   |
//                                   |---------------- 容量已滿?
//                                   |
//               ----------------------------
//           No  |                          |  Yes
//               |                          |
//               ↓                          ↓
//      construct(finish, x);       insert_aux(end(), x);
//      ++finish;                           |
//                                          |------ 內存不足, 重新分配
//                                          |       大小為原來的2倍
//      new_finish = data_allocator::allocate(len);       
//      uninitialized_copy(start, position, new_start);   
//      construct(new_finish, x);                         
//      ++new_finish;
//      uninitialized_copy(position, finish, new_finish); 
////////////////////////////////////////////////////////////////////////////////
void push_back(const T& x)
{
  // 內存滿足條件則直接追加元素, 否則需要重新分配內存空間
  if (finish != end_of_storage) {
    construct(finish, x);
    ++finish;
  }
  else
    insert_aux(end(), x);
}

////////////////////////////////////////////////////////////////////////////////
// 提供插入操作
////////////////////////////////////////////////////////////////////////////////
//                 insert_aux(iterator position, const T& x)
//                                   |
//                                   |---------------- 容量是否足夠?
//                                   ↓
//              -----------------------------------------
//        Yes   |                                       | No
//              |                                       |
//              ↓                                       |
// 從opsition開始, 整體向後移動一個位置                     |
// construct(finish, *(finish - 1));                    |
// ++finish;                                            |
// T x_copy = x;                                        |
// copy_backward(position, finish - 2, finish - 1);     |
// *position = x_copy;                                  |
//                                                      ↓
//                            data_allocator::allocate(len);
//                            uninitialized_copy(start, position, new_start);
//                            construct(new_finish, x);
//                            ++new_finish;
//                            uninitialized_copy(position, finish, new_finish);
//                            destroy(begin(), end());
//                            deallocate();
////////////////////////////////////////////////////////////////////////////////
template 
void vector::insert_aux(iterator position, const T& x)
{
  if (finish != end_of_storage) {       // 還有剩余內存
    construct(finish, *(finish - 1));
    ++finish;
    T x_copy = x;
    copy_backward(position, finish - 2, finish - 1);
    *position = x_copy;
  }
  else {        
    // 內存不足, 需要重新分配
    const size_type old_size = size();
    //配置原則:如果原大小為0,就配置1個元素大小
    //        如果原大小不為0,就配置原大小的兩倍
    //              前半段用來放置原數據,後半段用來放置新數據
    const size_type len = old_size != 0 ? 2 * old_size : 1;
    iterator new_start = data_allocator::allocate(len);
    iterator new_finish = new_start;
    // 將內存重新配置
    __STL_TRY {
        // 將原vector的內容拷貝到新vector
      new_finish = uninitialized_copy(start, position, new_start);
      // 構造新元素並賦值為x
      construct(new_finish, x);
      // 調整finish的位置
      ++new_finish;
      // 將安插點的原內容也拷貝過來
      new_finish = uninitialized_copy(position, finish, new_finish);
    }
        // 分配失敗則拋出異常
    catch (...) {
      destroy(new_start, new_finish);
      data_allocator::deallocate(new_start, len);
      throw;
    }
    // 析構原容器中的對象
    destroy(begin(), end());
    // 釋放原容器分配的內存
    deallocate();
    // 調整內存指針狀態
    start = new_start;
    finish = new_finish;
    end_of_storage = new_start + len;
  }
}

pop_back()函數

pop_back函數彈出當前尾端元素。其源代碼比較簡單,如下:

void pop_back()
{
    //調整finish
  --finish;
  //釋放調彈出的元素
  destroy(finish);
}

erase()函數

erase函數支持兩個版本:

清除某個位置上的元素
iterator erase(iterator position)
{
  if (position + 1 != end())
    copy(position + 1, finish, position); //將[position+1,finish]移到[position,finish]
  --finish;
  destroy(finish);
  return position;//返回刪除點的迭代器
}
清除某個區間上的所有函數
iterator erase(iterator first, iterator last)
{
  iterator i = copy(last, finish, first);//關於copy函數的源碼分析在以後的博文中會提到
  // 析構掉需要析構的元素
  destroy(i, finish);
  finish = finish - (last - first);
  return first;
}

這裡放上兩張《STL源碼剖析》中的圖,便於理解這一過程:

 

erase函數

 

有上述erase函數,可以衍生出一個函數,用來清除迭代器中所有的元素

void clear() { erase(begin(), end()); }

insert()函數

insert函數實現的功能是:從position開始,插入n個元素,元素的初值均為x。其源碼如下:

////////////////////////////////////////////////////////////////////////////////
// 在指定位置插入n個元素
////////////////////////////////////////////////////////////////////////////////
//             insert(iterator position, size_type n, const T& x)
//                                   |
//                                   |---------------- 插入元素個數是否為0?
//                                   ↓
//              -----------------------------------------
//        No    |                                       | Yes
//              |                                       |
//              |                                       ↓
//              |                                    return;
//              |----------- 內存是否足夠?
//              |
//      -------------------------------------------------
//  Yes |                                               | No
//      |                                               |
//      |------ (finish - position) > n?                |
//      |       分別調整指針                              |
//      ↓                                               |
//    ----------------------------                      |
// No |                          | Yes                  |
//    |                          |                      |
//    ↓                          ↓                      |
// 插入操作, 調整指針           插入操作, 調整指針           |
//                                                      ↓
//            data_allocator::allocate(len);
//            new_finish = uninitialized_copy(start, position, new_start);
//            new_finish = uninitialized_fill_n(new_finish, n, x);
//            new_finish = uninitialized_copy(position, finish, new_finish);
//            destroy(start, finish);
//            deallocate();
////////////////////////////////////////////////////////////////////////////////
template 
void vector::insert(iterator position, size_type n, const T& x)
{
  // 如果n為0則不進行任何操作
  if (n != 0) {
    if (size_type(end_of_storage - finish) >= n) {      // 剩下的內存夠分配
      T x_copy = x;
      const size_type elems_after = finish - position; // 計算插入點之後的現有元素個數
      iterator old_finish = finish;
      if (elems_after > n) {  // 插入點之後的現有元素個數大於新增元素個數,見下圖1
        // 先復制尾部n個元素到尾部
        uninitialized_copy(finish - n, finish, finish);
        finish += n; // 調整新的finish
        // 從後往前復制剩余的舊元素
        copy_backward(position, old_finish - n, old_finish);
        // 從position開始填充新元素
        fill(position, position + n, x_copy);
      }
      else {
        // 插入點之後的現有元素個數小於新增元素個數,見下圖2
        // 先在尾部填充n - elems_after個新增元素
        uninitialized_fill_n(finish, n - elems_after, x_copy);
        // 調整新的finish
        finish += n - elems_after;
        // 復制[position,old_finish]區間的數到新的finish之後
        uninitialized_copy(position, old_finish, finish);
        // 調整finish
        finish += elems_after;
        // 從position開始填充新增元素
        fill(position, old_finish, x_copy);
      }
    }
    else {      // 剩下的內存不夠分配, 需要重新分配
      const size_type old_size = size();
      const size_type len = old_size + max(old_size, n);
      iterator new_start = data_allocator::allocate(len);
      iterator new_finish = new_start;
      __STL_TRY {
        // 將舊的vector中插入點之前的元素復制到新空間,見下圖3
        new_finish = uninitialized_copy(start, position, new_start);
        // 將新增元素復制到新空間
        new_finish = uninitialized_fill_n(new_finish, n, x);
        // 將插入點之後的元素復制到新空間
        new_finish = uninitialized_copy(position, finish, new_finish);
      }
      catch (...) {
        destroy(new_start, new_finish);
        data_allocator::deallocate(new_start, len);
        throw;
      }
      // 清除並釋放原有vector
      destroy(start, finish);
      deallocate();
      // 調整新的start和finish
      start = new_start;
      finish = new_finish;
      end_of_storage = new_start + len;
    }
  }
}

上述操作可以使插入操作達到最高的效率。配合以下圖解更容易理解:

插入點之後的現有元素個數大於新增元素個數的情況

第一種情況

 

插入點之後的現有元素個數小於新增元素個數的情況

第二種情況

 

剩下的內存不夠分配,重新配置的情況

第三種情況

 

後記

STL的Vector容器到此就介紹完畢了。其中對改善效率作了不少優化,很多設計點都值得學習!若有疑惑可以在博文下方留言,我看到會及時幫大家解答!

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved