前言

對于操作系統(tǒng)來說，虛擬內(nèi)存地址空間，是一塊連續(xù)的存儲空間，其實數(shù)組就是對虛擬內(nèi)存地址空間的一種基本抽象。以C++為例，指針代表一個內(nèi)存地址

內(nèi)存空間

• 虛擬內(nèi)存地址的由來
  計算機發(fā)展初期，那時候使用的都是匯編語言，可以直接操作物理主存，這種方式有三個問題。第一是多進程下，造成了內(nèi)存浪費；第二是不安全，想象一下每個程序之間不隔離，都能修改別人的程序；第三是地址空間的不確定性。因此抽象了虛擬內(nèi)存地址空間。

• CPU如何訪問物理內(nèi)存
  當一個進程運行時，系統(tǒng)為其分配相應的內(nèi)存空間（這里指的是虛擬內(nèi)存地址，真正的物理內(nèi)存地址和虛擬內(nèi)存地址之間有一個映射關(guān)系（圖1），CPU是通過這個映射(圖2中的MMU)去訪問物理內(nèi)存地址（圖2））。

  
  
  圖1 Virtual_address_space_and_physical_address_space_relationship.png（圖片來自維基百科）
  
  

  圖2中MMU是虛擬內(nèi)存地址和物理內(nèi)存的映射

  
  
  圖2 CPU訪問物理內(nèi)存地址.PNG

• 操作系統(tǒng)內(nèi)核空間和用戶空間
  當每個進程運行時，對于每個進程而言擁有所有虛擬內(nèi)存空間，為了保證安全，內(nèi)存地址被劃分為用戶空間和內(nèi)核空間（以Linux32位操作系統(tǒng)來說，內(nèi)存空間和用戶空間的比例劃分是1:3 如圖3），內(nèi)核空間是給操作系統(tǒng)內(nèi)核預留的，用戶態(tài)的程序不能操作，這樣就保證了安全。

  
  
  圖3 內(nèi)核空間.png
• 棧和堆
  圖3中的棧和堆，是編程中經(jīng)常提到的兩個概念，編程語言的每一行代碼都是壓棧操作，所有引用對象的都是分配在堆里面。但是釋放內(nèi)存的機制有所不同，例如C++中內(nèi)存管理器會釋放一個之前分配的內(nèi)存，而Java內(nèi)存管理器會采用垃圾回收機制查找不再使用的內(nèi)存予以釋放。

動態(tài)數(shù)組的實現(xiàn)

在C++中都建議標準庫vector封裝了C的原生數(shù)組，做好了內(nèi)存釋放。下面參考vector實現(xiàn)的動態(tài)數(shù)據(jù)。

#include <iostream>

//初始化數(shù)據(jù)默認大小
constexpr int default_array_cap = 10;
constexpr int default_array_length = 1;
constexpr int default_array_from_index = 0;

template <class T>
class dynarray {
  //------------------
  //      data member
  //------------------
  int capacity_;  // array total size
  int length_;    // current array size
  int front_index;
  T* array_;  // pointer array

  bool dynaimcResize(const int new_capacity) {
    auto* temp = new T[new_capacity];
    // copy array to new array with new capacity
    for (auto i{0}; i < length_; ++i) {
      // transfer ownership of every element
      temp[i] = array_[(front_index + i) % capacity_];
    }
    // free old array
    delete[] array_;
    // point to *temp
    capacity_ = new_capacity;
    // reset front index to 0
    front_index = 0;
    array_ = temp;
    temp = nullptr;  // pointer dangling
    // return statement
    return true;
  }

 public:
  //--------------------
  //       constructors
  //--------------------
  //移動構(gòu)造
  explicit dynarray(T&& r_ref)
      : capacity_{default_array_cap},
        length_{default_array_length},
        front_index{default_array_from_index} {
    //分配內(nèi)存
    array_ = new T[capacity_];
    //調(diào)用移動函數(shù)，賦值數(shù)組0位值
    array_[0] = std::move(r_ref);
  }
  //拷貝構(gòu)造
  explicit dynarray(const T& data)
      : capacity_{default_array_cap},
        length_{default_array_length},
        front_index{default_array_from_index} {
    //分配內(nèi)存
    array_ = new T[capacity_];
    //調(diào)用拷貝賦值，賦值數(shù)組0位值
    array_[0] = data;
  }
  //析構(gòu)釋放內(nèi)存
  ~dynarray() {
    delete[] array_;
    array_ = nullptr;
  }
  //-----------------
  // 公共方法
  //-----------------

  // add l value at the end of dynarray
  bool append(const T& data)  {
    if (array_ == nullptr) {
      array_ = new T{default_array_cap};
    }
    //擴容
    else if (length_ >= capacity_) {
      dynaimcResize(static_cast<int>(capacity_ * 1.5));
    }
    // insert at length index module capacity
    array_[(front_index + length_) % capacity_] = data;
    // increase length
    ++length_;
    return true;
  }

  // add r value at the end of dynarray
  bool append(T&& r_ref)  {
    if (array_ == nullptr) {
      array_ = new T{default_array_cap};
    }
    // 擴容
    else if (length_ >= capacity_) {
      dynaimcResize(static_cast<int>(capacity_ * 1.5));
    }
    // add end index length
    array_[(front_index + length_) % capacity_] = std::move(r_ref);
    // increase length
    ++length_;
    return true;
  }

  // remove last element
  bool pop()  {
    if (length_ == 0) {
      throw std::range_error("Array length_ is 0");
    }
    //減容操作
    if (length_ < (capacity_ / 5)) {
      dynaimcResize(capacity_ / 2);
    }
    --length_;
    return true;
  }

  T& get_at(const int index) const {
    if (index >= length_) {
      throw std::out_of_range("Out of bounds index");
    }
    return array_[(front_index + index) % capacity_];
  }
};

int main() {
  //初始化動態(tài)數(shù)組，第一位賦值為1
  dynarray<char> arraylist('a');
  //尾部添加元素
  arraylist.append('b');
  std::cout << arraylist.get_at(1) << std::endl;
  arraylist.pop();
  std::cout << arraylist.get_at(0) << std::endl;
}

Test輸出結(jié)果

b
a