前言
对于操作系统来说，虚拟内存地址空间，是一块连续的存储空间，其实数组就是对虚拟内存地址空间的一种基本抽象。以C++为例，指针代表一个内存地址
内存空间
- 虚拟内存地址的由来
计算机发展初期，那时候使用的都是汇编语言，可以直接操作物理主存，这种方式有三个问题。第一是多进程下，造成了内存浪费；第二是不安全，想象一下每个程序之间不隔离，都能修改别人的程序；第三是地址空间的不确定性。因此抽象了虚拟内存地址空间。 -
CPU如何访问物理内存
当一个进程运行时，系统为其分配相应的内存空间（这里指的是虚拟内存地址，真正的物理内存地址和虚拟内存地址之间有一个映射关系（图1），CPU是通过这个映射(图2中的MMU)去访问物理内存地址（图2））。
图1 Virtual_address_space_and_physical_address_space_relationship.png（图片来自维基百科）
图2中MMU是虚拟内存地址和物理内存的映射
图2 CPU访问物理内存地址.PNG
-
操作系统内核空间和用户空间
当每个进程运行时，对于每个进程而言拥有所有虚拟内存空间，为了保证安全，内存地址被划分为用户空间和内核空间（以Linux32位操作系统来说，内存空间和用户空间的比例划分是1:3 如图3），内核空间是给操作系统内核预留的，用户态的程序不能操作，这样就保证了安全。
图3 内核空间.png
- 栈和堆
图3中的栈和堆，是编程中经常提到的两个概念，编程语言的每一行代码都是压栈操作，所有引用对象的都是分配在堆里面。但是释放内存的机制有所不同，例如C++中内存管理器会释放一个之前分配的内存，而Java内存管理器会采用垃圾回收机制查找不再使用的内存予以释放。
动态数组的实现
在C++中都建议标准库vector封装了C的原生数组，做好了内存释放。下面参考vector实现的动态数据。
#include <iostream>
//初始化数据默认大小
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
//--------------------
//移动构造
explicit dynarray(T&& r_ref)
: capacity_{default_array_cap},
length_{default_array_length},
front_index{default_array_from_index} {
//分配内存
array_ = new T[capacity_];
//调用移动函数，赋值数组0位值
array_[0] = std::move(r_ref);
}
//拷贝构造
explicit dynarray(const T& data)
: capacity_{default_array_cap},
length_{default_array_length},
front_index{default_array_from_index} {
//分配内存
array_ = new T[capacity_];
//调用拷贝赋值，赋值数组0位值
array_[0] = data;
}
//析构释放内存
~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() {
//初始化动态数组，第一位赋值为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输出结果
b
a
网友评论