C++ STL容器空間配置器詳解

文章目錄

一、一個簡單的vector容器
二、不使用空間配置器存在的問題
三、使用空間配置器

一、一個簡單的vector容器

模拟實作一個簡單的vector容器

#include <iostream>

using namespace std;

const int INIT_SIZE = 10;

template<typename T>
class vector {
public:
  vector(int size = INIT_SIZE) {
    first_ = new T[size];
    last_ = first_;
    end_ = first_ + size;
  }

  ~vector() {
    delete[] first_;
    last_ = first_ = end_ = nullptr;
  }

  vector(const vector<T>& src) {
    // 深拷貝
    // 開辟空間
    int size = src.end_ - src.first_;  
    first_ = new T[size];
    // 拷貝有效元素
    int len = src.last_ - src.first_;
    for (int i = 0; i < len; i++) {
      first_[i] = src.first_[i];
    }
    last_ = first_ + len;
    end_ = first_ + size;
  }

  vector<T>& operator=(const vector<T> &src){
    if (this == &src) {
      return *this;
    }
    // 釋放目前對象原來的資源
    delete[] first_;
    // 開辟空間
    int size = src.end_ - src.first_;
    first_ = new T[size];
    // 拷貝有效元素
    int len = src.last_ - src.first_;
    for (int i = 0; i < len; i++) {
      first_[i] = src.first_[i];
    }
    last_ = first_ + len;
    end_ = first_ + size;
    // 支援連續指派
    return *this;
  }

  bool inline full() const{
    return last_ == end_;
  }

  bool inline empty() const {
    return first_ == last_;
  }

  bool inline size() const {
    return last_ - first_;
  }

  void push_back(const T& val) {
    if (full()) {
      expand();
    }
    *last_ = val;
    last_++;
  }

  // 從末尾删除元素
  void pop_back() {
    if (empty()) {
      return;
    }
    last_--;
  }

  T back() const {
    return *(last_ - 1);
  }

private:
  void expand() {
    int size = end_ - first_;
    T* tmp = new T [2 * size];
    for (int i = 0; i < size; i++) {
      tmp[i] = first_[i];
    }
    delete[] first_;
    first_ = tmp;
    last_ = first_ + size;
    end_ = first_ + 2 * size;
  }

  T* first_;   // 指向數組起始位置
  T* last_;    // 指向數組中有效元素的後繼位置
  T* end_;     // 指向數組空間的後繼位置
};

int main() {
  vector<int> vec;
  
  for (int i = 0; i < 20; i++) {
    vec.push_back(rand() % 100);
  }

  while (!vec.empty()) {
    cout << vec.back() << " ";
    vec.pop_back();
  }
  
  return 0;
}

看起來沒有任何問題

二、不使用空間配置器存在的問題

我們用容器存儲類對象試試

class Test {
public:
  Test() {
    cout << "Test()" << endl;
  }

  ~Test() {
    cout << "~Test()" << endl;
  }
};

int main() {
  vector<Test> vec;
  return 0;
}

這就不對了，我隻是聲明了一個空容器，并沒有放入元素，竟然構造了10個Test對象，出作用域析構的時候，析構了10個Test對象由于我們在vector的構造函數中使用了new，這個new操作符不僅僅開辟了空間，還在每個記憶體空間上構造了對象，也就是new操作符不僅執行了malloc函數，還執行了類的構造函數

而這時我們并沒有想在容器中存放對象，我們希望的是當我們放入元素的時候，再構造對象，而不是開辟容器空間的同時就構造對象

new執行了malloc和類的構造函數，我們需要把記憶體開辟（malloc）和對象構造（構造函數）這倆過程分開，這就需要使用空間配置器

我們再來看析構函數

我們使用delete，就是根據容器的空間（end_ - first_）執行析構函數，而不是按照容器的有效元素的個數（last_ - first_）執行析構函數。如果我們聲明一個可以存放1000個元素的空容器，卻隻是放入1個元素，這種寫法會導緻執行1000次析構函數，效率極其低下

此外還有一種場景：

我們pop_back删除容器末尾元素時，我們想要的就是析構容器内對象（對象可能占用了外部資源，需要釋放）的同時還不釋放容器某個位置的空間。如果我們還是使用delete做這件事，析構對象和釋放空間又一起做了，這不是我們想要的。是以我們也需要使用空間配置器将析構對象和釋放空間兩個操作分開

delete做了兩件事：執行對象的析構函數、free釋放空間

如果按照我們寫的簡單vector裡的pop_back函數，就隻是對last_指針進行了偏移，假如容器中存放的對象占用了外部資源，我們這時就沒有釋放，就會導緻記憶體洩漏

不使用空間配置器存在的問題：

聲明空容器時，由于直接使用了new，開辟空間的同時還構造了對象
需要删除容器元素時，由于直接使用了delete，析構對象的同時還釋放了容器空間
最終釋放整合容器空間時，由于直接使用了delete，釋放空間的同時還執行了析構函數，這在隻存放少量元素的大容器場景是很不合理的

三、使用空間配置器

空間配置器的作用：将記憶體開辟和對象構造過程分開，将記憶體釋放和對象析構過程分開

template<typename T>
class Allocator {
public:
  // 開辟size位元組
  T* allocate(size_t size) {
    return (T*)malloc(size);
  }

  void deallocate(void* p) {
    free(p);
  }

  void construct(T* p, const T& val) {
    new (p) T(val);  // 定位new，指定位址構造值為val的對象，調用拷貝構造函數
  }

  void destroy(T* p) {
    p->~T();
  }
};

修改vector類所有的開辟/釋放空間，構造/析構對象代碼

template<typename T, typename Alloc = Allocator<T>>
class vector {
public:
  vector(int size = INIT_SIZE, const Alloc& alloc = Allocator<T>()) 
    : allocator_(alloc)
  {
    // first_ = new T[size];
    first_ = allocator_.allocate(size * sizeof(T));
    last_ = first_;
    end_ = first_ + size;
  }

  ~vector() {
    // delete[] first_;
    
    // 析構時，隻析構容器中有效元素[first_, last - 1]
    for (T* p = first_; p != last_; p++) {
      allocator_.destroy(p);
    }
    // 釋放整個容器空間
    allocator_.deallocate(first_);
    last_ = first_ = end_ = nullptr;
  }

  vector(const vector<T>& src) {
    // 深拷貝
    // 開辟空間
    int size = src.end_ - src.first_;  
    // first_ = new T[size];
    first_ = allocator_.allocate(sizeof(T) * size);

    // 拷貝有效元素
    int len = src.last_ - src.first_;
    for (int i = 0; i < len; i++) {
      // first_[i] = src.first_[i];
      allocator_.construct(first_ + i, src.first_[i]);
    }
    last_ = first_ + len;
    end_ = first_ + size;
  }

  vector<T>& operator=(const vector<T> &src){
    if (this == &src) {
      return *this;
    }
    // 釋放目前對象原來的資源
    // delete[] first_;
    for (T* p = first_; p != last_; p++) {
      allocator_.destroy(p);
    }
    allocator_.deallocate(first_);
    last_ = first_ = end_ = nullptr;
    
    // 開辟空間
    int size = src.end_ - src.first_;
    // first_ = new T[size];
    first_ = allocator_.allocate(sizeof(T) * size);
    
    // 拷貝有效元素
    int len = src.last_ - src.first_;
    for (int i = 0; i < len; i++) {
      allocator_.construct(first_ + i, src.first_[i]);
    }
    last_ = first_ + len;
    end_ = first_ + size;
    // 支援連續指派
    return *this;
  }

  bool inline full() const{
    return last_ == end_;
  }

  bool inline empty() const {
    return first_ == last_;
  }

  bool inline size() const {
    return last_ - first_;
  }

  // 在容器末尾構造一個值為val的對象
  void push_back(const T& val) {
    if (full()) {
      expand();
    }
    allocator_.construct(last_, val);
    last_++;
  }

  // 從末尾删除元素
  void pop_back() {
    if (empty()) {
      return;
    }
    last_--; 
    allocator_.destroy(last_);
  }

  T back() const {
    return *(last_ - 1);
  }

private:
  void expand() {
    int size = end_ - first_;
    // T* tmp = new T [2 * size];
    T* tmp = allocator_.allocate(2 * sizeof(T) * size);
    for (int i = 0; i < size; i++) {
      allocator_.construct(tmp + i, first_[i]);
    }

    // delete[] first_;
    for (T* p = first_; p != last_; p++) {
      allocator_.destroy(p);
    }
    allocator_.deallocate(first_);

    first_ = tmp;
    last_ = first_ + size;
    end_ = first_ + 2 * size;
  }

  T* first_;   // 指向數組起始位置
  T* last_;    // 指向數組中有效元素的後繼位置
  T* end_;     // 指向數組空間的後繼位置
  Alloc allocator_;
};

class Test {
public:
  Test() {
    cout << "Test()" << endl;
  }
  
  Test(const Test& src) {
    cout << "Test(const Test& src)" << endl;
  }
  
  ~Test() {
    cout << "~Test()" << endl;
  }
};

測試代碼1:

int main() {
  vector<Test, Allocator<Test>> vec;
  return 0;
}

沒有構造對象，結果正确

int main() {  
  Test t1;
  Test t2;
  Test t3;
  cout << "----------------------------------" << endl;
  vector<Test, Allocator<Test>> vec;
  vec.push_back(t1);
  vec.push_back(t2);
  vec.push_back(t3);
  cout << "----------------------------------" << endl;
  vec.pop_back();
  cout << "----------------------------------" << endl;
  return 0;
}

C++ STL容器空間配置器詳解

文章目錄

一、一個簡單的vector容器

二、不使用空間配置器存在的問題

三、使用空間配置器

繼續閱讀

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

數組和類數組

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述