一、一个简单的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));
end_ = last_ = first_;
}
~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;
}
没有构造对象，结果正确
测试代码2：
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;
}
