天天看點
傳回

面試官都在問 | 請談談vector的底層實作

名企高頻考點之-請談談vector的底層實作

0. 概述

STL版本比較多，第一個STL是在惠普實驗室完成的，簡稱HP版本，後序版本STL都是基于HP版本給出來的，大同小異，本文主要基于SGI-STL版本進行探究，linux下采用就是SGI-STL，而且該版本的命名風格以及編碼風格，可讀性非常高。

1. vector的底層結構

vector底層實際是泛型的動态類型順序表，是以其底層實際是一段連續的空間。在SGI-STL的vector中，實際在底層使用三個指針指向該段連續空間的，如下：

面試官都在問 | 請談談vector的底層實作

start指向空間的起始位置，finish指向最後一個元素的下一個位置，end_of_storage指向空間的末尾。

// SGI-STL部分源碼
template <class T, class Alloc = alloc>
class vector {
public:
  typedef T value_type;           // vector中元素的類型
  typedef value_type* iterator;   // vector的疊代器，實際就是原生态的指針的别名
  // ...
protected:
  iterator start;                 // 指向底層空空間的起始位置
  iterator finish;                // 指向最後一個有效元素的下一個位置，沒有元素時與start在同一位置
  iterator end_of_storage;        // 指向空間的末尾
  
  // ... 
  // 開辟n個元素的一段連續空間，并使用value來進行填充
  void fill_initialize(size_type n, const T& value) {
    start = allocate_and_fill(n, value);
    finish = start + n;
    end_of_storage = finish;
  }
  
  // ...
  
public:
  // n向vector中填充n個位置value的元素
  vector(int n, const T& value) { fill_initialize(n, value); }
  // ...
 
 public:
  // vector的疊代器
  iterator begin(){ return start; }
  iterator end(){ return finish; }
  
  // ...
  
};

2 vector支援随機通路

因為vector底層是連續空間，并且vector重載了[]下标運算符，使用者可以向使用數組的方式通路vector中的每一個元素，即支援随機通路，但vector不适宜做任意位置的插入和删除操作，因為要進行大量元素的搬移，比如插入：

reference operator[](size_type n) 
{ 
    return *(begin() + n); 
}

const_reference operator[](size_type n) const 
{ 
    return *(begin() + n); 
}

3 vector不适合做任意位置插入以及删除操作

vector不适宜做任意位置插入與删除操作，因為插入和删除時需要搬移大量元素：

面試官都在問 | 請談談vector的底層實作

在元素3的位置插入0時，需要将3 4 5 整體向後搬移一個位置，才可以插入資料0，最差情況下時間複雜度為O(N)；

template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
  // 檢測是否需要擴容：如果finish和end_of_storage不在同一個位置，即還有空間
  // 則不需要庫容
  if (finish != end_of_storage) {
    construct(finish, *(finish - 1));
    ++finish;
    T x_copy = x;
    
    // 将position之後的元素整體向後搬移一個位置
    copy_backward(position, finish - 2, finish - 1);
    *position = x_copy;
  }
  else {
   
    // finish與end_of_storage在同一個位置：需要進行擴容
    const size_type old_size = size();
    
    // 此處可以看到SGI-STL vector是按照2倍方式擴容的
    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 {
      // 将[start, position)區間中元素搬移到新空間，傳回拷貝完成後新空間尾即原position相同位置
      new_finish = uninitialized_copy(start, position, new_start);
      
      // 在原position位置構造新對象
      construct(new_finish, x);
      ++new_finish;
      
      // 将原position位置元素搬移到新空間
      new_finish = uninitialized_copy(position, finish, new_finish);
    }

#       ifdef
    catch(...) {
      destroy(new_start, new_finish); 
      data_allocator::deallocate(new_start, len);
      throw;
    }
#       endif/* __STL_USE_EXCEPTIONS */
    destroy(begin(), end());
    deallocate();
    start = new_start;
    finish = new_finish;
    end_of_storage = new_start + len;
  }
}

4. 其他常用接口與底層結構關系

為了能使算法操作容器中的元素，每個容器都提供了begin()和end()的疊代器，[begin, end)區間中包含了容器中的所有元素，vector也是如此。

面試官都在問 | 請談談vector的底層實作
iterator begin() { return start; }
iterator end() { return finish; }

size()和capacity()分别表示vector中的元素個數以及底層的空間大小。

size_type size() const { 
    return size_type(end() - begin()); // finish - start
}

size_type capacity() const { 
    return size_type(end_of_storage - begin()); // end_of_storage - start
}

5. vector的擴容

在向vector中插入元素時，如果finish移動到與end_of_storage在同一個位置時，即size等于容量空間不足，則需要擴容，如下代碼實作主要探測vector的擴容機制：

// SGI-STL擴容機制
void reserve(size_type n) {
    // 當n大于目前vector的容量時才會擴容，小于等于目前容量則忽略本次操作
    if (capacity() < n) {
      const size_type old_size = size();
        
      // 使用空間配置器開辟n個新空間，并将舊空間元素拷貝到新空間
      iterator tmp = allocate_and_copy(n, start, finish);
        
      // 釋放舊空間
      // a. 先調用析構函數，将[start, finish)區間總所有的對象析構完整
      destroy(start, finish);
        
      // b. 将空間規劃給空間配置器
      deallocate();
        
      // 3. 接收新空間并更新其成員
      start = tmp;
      finish = tmp + old_size;
      end_of_storage = start + n;
    }
  }

從上述源碼中可以看到：

SGI-STL中vector是按照2倍方式擴容的，擴容需要經過以下步驟：

  1. 開辟新空間
  2. 拷貝元素
  3. 釋放舊空間
  4. 使用新空間
面試官都在問 | 請談談vector的底層實作

擴容的實際為：在插入時，當finish與start在同一個位置，或者調用reserve操作，或者resize操作等都可能引起擴容。

// vector::capacity
#include <iostream>
#include <vector>
int main ()
{
    size_t sz;
    std::vector<int> foo;
    sz = foo.capacity();
    std::cout << "making foo grow:\n";
    for (int i=0; i<100; ++i) 
    {
        foo.push_back(i);
        if (sz!=foo.capacity()) 
        {
            sz = foo.capacity();
            std::cout << "capacity changed: " << sz << '\n';
        }
    }
}

vs：運作結果：
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141
    
g++運作結果：
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128

從上述代碼可以得出：

  1. 在向vector中插入元素時，vector會自動進行擴容
  2. vs下是幾乎是按照1.5倍方式擴容的，linux下是按照2倍方式擴容的

  3. 如果确定vector中大概要存儲多少個元素時，盡量提前把空間申請好，否則邊插入邊擴容，會影響程式的效率。

    溫馨提示：随着元素不斷增多，邊擴容邊插入程式效率會非常低下，是以如果能夠預估到vector中要存儲多少個元素，可以一次性将空間給足，然後再插入。

#include <iostream>
#include <vector>
int main ()
{
    size_t sz;
    std::vector<int> foo;
    foo.reserve(100);   // 先将vector底層空間擴增到100個，然後插入
    sz = foo.capacity();
    std::cout << "making foo grow:\n";
    for (int i=0; i<100; ++i) 
    {
        foo.push_back(i);
        if (sz!=foo.capacity()) 
        {
            sz = foo.capacity();
            std::cout << "capacity changed: " << sz << '\n';
        }
    }
}

此時再運作以上代碼，幾乎就看不到擴容的過程了。

6. 總結

本文主要對vector底層進行了探究，具體包含：

c++ STL vector 資料結構 算法
上一篇: 硬碟分區的格式
下一篇: 國内yum源的安裝(163，阿裡雲，epel)

繼續閱讀