C++STL-vector实现 空间配置器
一、没有空间配置器的vector
#include <iostream>
#include <cstring>
using namespace std;
template <typename T>
class vector {
private:
T *_first;
T *_last;
T *_end;
public:
vector(int size=10) {
_first = new T[size];
_end = _first+size;
_last = _first;
}
vector(const vector<T>& src) {
int size=src._end - src._first;
_first = new T[size];
int len = _last-_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;
int len = src._last - src._first;
_first = new T[size];
for (int i=0; i<len; ++i) {
_first[i] = src._first[i];
}
_last = _first + len;
_end = _first + size;
return *this;
}
~vector() {
delete[] _first;
_first = _last = _end = nullptr;
}
void push_back(const T &x) {
if (full()) {
resize();
}
*_last ++ = x;
}
void pop_back() {
if (empty()) {
return;
}
-- _last;
}
T back() const {
if (empty()) {
}
return *(_last-1);
}
bool full() {
return _end == _last;
}
bool empty() {
return _last == _first;
}
void resize() {
int size=_end-_first;
T *tmp = new T[2*size];
int len = _last-_first;
for(int i=0; i<len; ++i) {
tmp[i] = _first[i];
}
delete[] _first;
_first = tmp;
_end = _first + 2*size;
_last = _first + len;
}
};
struct Test {
Test() {
cout << "Test()" << endl;
}
~Test() {
cout << "~Test()" << endl;
}
Test(const Test &t) {
cout << "Test(const Test&)" << endl;
}
Test& operator=(const Test& t) {
cout << "operator=(const Test&)" << endl;
}
};
int main() {
Test t1;
Test t2;
vector<Test> vec;
vec.push_back(t1);
vec.push_back(t2);
cout << "===========================" << endl;
vec.pop_back();
cout << "===========================" << endl;
return 0;
}执行结果：
在这里插入图片描述
通过观察打印结果，得到一下几个存在的问题？ 1.vector中什么元素都没有，居然就进行了10次构造？按道理，没有push_back进去元素，我们只需要申请初始空间即可，不需要进行构造。 2.pop_back推出vector尾部的元素时，没有进行析构，如果此时vector的元素为对象并且持有堆资源，那么就会造成内存的泄露？ 3.pop_back推出尾部元素时，只需要析构该位置的元素即可，不需要释放空间？空间的释放时机是vector对象生命周期结束时 造成上述结果的缘由： 1.vector的构造函数直接使用了new，包含两个动作，开辟空间和调用构造函数进行构造。 2.pop_back时，直接 --_last，没有进行该位置对象的析构。但是如果单纯的使用delete，不仅不会调用析构函数析构该位置的对象，还会删除该位置的内存。 综上：本质的问题就是new没有将开辟内存和构造对象这两个操作步骤分离开来。 delete没有将析构对象和释放内存这两个操作分离开来。
二、增加空间配置器的vector 为了解决上述存在的问题，将开辟内存、释放内存、析构对象和构造对象四个步骤分离开来，抽象成一个空间配置器，是的上边四个操作每一个都是互不干涉，相互独立的操作。
空间配置器
template <typename T>
struct Allocator {
// 开辟内存
T* allocate(size_t size) {
return (T*)malloc(sizeof(T)*size);
}
// 释放内存
void deallocate(T *p) {
free(p);
}
// 构造对象，这里使用定位new
void construct(T *p, const T& x) {
new (p) T(x);
}
// 析构对象
void destroy(T *p) {
p->~T();
}
};增加空间配置器的vector
template <typename T, typename Alloc=Allocator<T>>
class vector {
private:
T *_first;
T *_last;
T *_end;
Alloc _allocator; // 增加空间配置器成员处理vector成员 内存开辟 内存释放 对象构造 对象析构
public:
vector(int size=10) {
// _first = new T[size];
_first = _allocator.allocate(size); // 仅仅开辟内存
_end = _first+size;
_last = _first;
}
vector(const vector<T>& src) {
int size=src._end - src._first;
// _first = new T[size];
_first = _allocator.allocate(size);
int len = _last-_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;
int size = src._end - src._first;
int len = src._last - src._first;
_first = new T[size];
for (int i=0; i<len; ++i) {
_first[i] = src._first[i];
}
_last = _first + len;
_end = _first + size;
return *this;
}
~vector() {
// delete[] _first; 1.首先析构有效的对象元素 2.释放空间
int len = _last - _first;
for (T* p=_first; p!=_last; ++p) {
_allocator.destroy(p);// 析构有效对象
}
_allocator.deallocate(_first); // 释放内存
_first = _last = _end = nullptr;
}
void push_back(const T &x) {
if (full()) {
resize();
}
// *_last ++ = x;
_allocator.construct(_last, x);
_last ++;
}
void pop_back() {
if (empty()) {
return;
}
-- _last;
_allocator.destroy(_last);
}
T back() const {
if (empty()) {
}
return *(_last-1);
}
bool full() {
return _end == _last;
}
bool empty() {
return _last == _first;
}
void resize() {
int size=_end-_first;
// T *tmp = new T[2*size];
T* tmp = _allocator.allocate(2*size);
int len = _last-_first;
for(int i=0; i<len; ++i) {
_allocator.construct(tmp+i, _first[i]);
}
// delete[] _first;
for (T *p=_first; p!=_last; ++p) {
_allocator.destroy(p);
}
_allocator.deallocate(_first);
_first = tmp;
_end = _first + 2*size;
_last = _first + len;
}
};
struct Test {
Test() {
cout << "Test()" << endl;
}
~Test() {
cout << "~Test()" << endl;
}
Test(const Test &t) {
cout << "Test(const Test&)" << endl;
}
Test& operator=(const Test& t) {
cout << "operator=(const Test&)" << endl;
}
};
int main() {
Test t1;
Test t2;
vector<Test> vec;
vec.push_back(t1);
vec.push_back(t2);
cout << "===========================" << endl;
vec.pop_back();
cout << "===========================" << endl;
return 0;
}执行结果：
在这里插入图片描述
观察执行结果，增加空间配置器的vector完全按照预期。内存开辟和释放，对象构造和析构完全分离开来，至此，简易的vector已经实现了。
三、增加带右值引用的push_back，进一步提高效率，旨在优化构造对象的背后调用函数的开销。
template <typename Ty>
void push_back(Ty &&x) {
if (full()) {
resize();
}
_allocator.constuct(_last, std::forward<Ty>(x));
}
对应的空间配置器中的对象构造
template <typename Ty>
void construct(T *p, Ty &&x) {
new (p) T(std::forward<Ty>(x));
}需要注意的是模板类Test中需要实现，带右值引用的拷贝构造函数和赋值运算符重载函数。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
