必须要注意的C++动态内存资源管理(六)vector的简单实现
myVector分析我们知道，vector类将其元素存放在连续的内存中。为了获得可接受的性能，vetor预先分配足够大的内存来保存可能需要的更多元素。vector的每个添加元素的成员函数会检查是否有空间容纳更多的元素。如果有，成员函数会在下一个可用位置构造一个对象。如果没有可用空间，vector就会重新分配空间；它获得新的空间，将已有元素移动到新空间中，释放旧空间，并添加新元素。既然是动态开辟的内存，于是我们在myVector中使用动态数组来存储，而每次插入元素的时候需要先判断开辟的内存是否已满，如果满了需要重新分配内存。
下面给出最初版本的代码：
//myVector.h
#include
template
classmyVector
{
public:
typedefmyVector_Myt;
myVector():
elements(nullptr),first_free(nullptr),cap(nullptr){}//allocator成员进行默认初始化
myVector(const_Myt&);
_Myt&operator=(const_Myt&);
~myVector();
T&operator[](size_ti){return(elements+i);}
voidpush_back(constT&);//添加元素
size_tsize()const{returnfirst_free-elements;}
size_tcapacity()const{returncap-elements;}
Tbegin()const{returnelements;}
Tend()const{returnfirst_free;}
private:
voidchk_n()//被添加元素函数使用
{
if(size()==capacity())reallocate();
}
std::pairn_copy
(constT,constT);//被拷贝构造，赋值运算符，析构函数使用
voidfree();//销毁元素并释放内存
voidreallocate();//获得更多内存并拷贝已有元素
Telements;
Tfirst_free;
Tcap;
};
template
myVector::myVector(const_Myt&v)
{
//调用alloc_n_copy分配空间以容纳与s中一样多的元素
autonewdata=n_copy(v.begin(),v.end());
elements=newdata.first;
first_free=cap=newdata.second;
}
template
myVector::~myVector()
{
free();
}
template
myVector&myVector::operator=(const_Myt&rhs)
{
//调用alloc_n_copy分配内存,大小与rhs一样.
autodata=n_copy(rhs.begin(),rhs.end());
free();
elements=data.first;
first_free=cap=data.second;
returnthis;
}
template
std::pairmyVector::
n_copy(constTb,constTe)
{
autodata=newT[e-b];
for(autoi=b;i
data[i-b]=i;
return{data,data+(e-b)};
}
template
voidmyVector::push_back(constT&s)
{
chk_n();//确保已有新空间
(first_free++)=s;
}
template
voidmyVector::free()
{
delete[]elements;
}
template
voidmyVector::reallocate()
{
//我们将分配当前大小两倍的内存空间
autonewcapacity=size()?2size():1;
//分配新内存
autonewdata=newT[newcapacity];
autodest=newdata;
autoelem=elements;
//将数据从旧地址移动到新地址
for(size_ti=0;i!=size();++i)
(dest++)=(elem++);
free();//一旦更新完就要释放旧内存
elements=newdata;
first_free=dest;
cap=elements+newcapacity;
}
恩，以上代码实现了vector的部分功能，实现了vector内存的动态分配。不过，我们可以发现以上代码还是有几个可以优化的地方：1.在分配内存的时候，new将内存分配和对象构造组合在了一起。但是在vector分配内存的时候，事实上有许多内存我们可能并用不上；而如果对于这些内存进行构造对象，可能就会带来不必要的开销。2.在内存重新分配的时候，我们涉及到了旧数据的转移；不对，这里应该说是拷贝。虽然的确应该是转移，然而我们实现是通过拷贝。在c++11的时候提供了移动构造语义。它可以对于即将销毁(保证重新赋值前不再使用)的对象进行移动。这样对于某些支持移动语义的对象。移动比拷贝就可以带来更小的开销。
恩，要进行以上的优化我们要先介绍：allocator类，移动语义。
十七.allocator类介绍
new有一些灵活性的局限，一方面表现在它将内存分配和对象构造组合在一起。类似的，delete将对象析构和内存释放组合在一起。我们分配单个对象时，通常我们希望将内存和对象初始化放在一起。因为在这样的情况下，我们几乎已经知道了对象应当是什么值。
当分配一大块内存时，我们通常计划在这块内存上按需构造对象。在这种情况下，我们就应该希望将内存分配和对象构造分离。这意味着我们可以分配大块内存，然而只有我们真正需要的时候才执行对象创建操作(同时付出一定开销)。
标准库allocator类定义在头文件memory中，它帮助我们将内存分配和对象构造分离开来。
函数 介绍
allocatora 定义了一个名为a的allocator对象，它可以为类型为T的对象分配内存。
a.allocate(n) 分配一段原始的，未构造的内存，保存n个类型为T的对象。
a.deallocate(p,n) 释放从T指针p开始的内存，这块内存保存了n个类型为T的对象；p必须是一个先前由allocate返回的指针，且n必须是p创建时指定的大小。在调用deallocate之前，用户必须对每个在这块内存创建的内存调用destroy。
a.construct(p,args) p必须是一个类型为T的指针，指向一块原始内存；args被传递给类型为T的构造函数，用来在p指向的内存上构造一个对象。
a.destroy(p) p为T类型指针，此算法对p指向的对象执行析构函数。
下面是一段简单的代码，介绍了如何使用allocator进行内存分配，对象构造，对象释放，内存回收。
?
intmain()
{
allocatoralloc;//这个对象可以用来分配string类型的内存。
stringp=alloc.allocate(5);//使用alloc对象分配5个string对象大的连续内存并将头指针给p。
//allocate分配的内存在没有构造之前是不能使用的！！
alloc.construct(p,"helloworld");//使用"helloworld"构造string
cout<
alloc.destroy(p);//销毁刚才构造的对象
alloc.deallocate(p,5);//释放内存
return0;
}
不仅这样，标准库还提供了一些算法让我们使用的时候更加方便：|函数|介绍||—|—-||uninitialized_copy(b,e,b2)|从迭代器b和e指出的输入范围中拷贝元素到迭代器b2指定的未构造的原始内存中。b2指向的内存必须足够大，能容纳输入序列中元素的拷贝。|uninitialized_copy_n(b,n,b2)|从迭代器b指向的元素开始，拷贝n个元素到b2开始的内存中。|uninitialized_fill(b,e,t)|在迭代器b,e指定的原始内存范围中创建对象，对象的值均为t的拷贝。|uninitialized_fill_n(b,n,t)|从迭代器b指向的内存地址开始创建n个对象。b必须指向足够大的未构造原始内存，能够容纳给定数量的对象。
值得注意的是，所有通过allocate分配的内存都必须通过deallocate去回收，而所有构造的对象都必须通过destroy去释放。所以这些拷贝算法都必须要求原始内存，如果内存上有对象，请先使用destroy释放！！
十八.移动语义介绍
很多情况下都会发生对象拷贝，然而在其中某些情况下，对象拷贝后就会立即被销毁。在这些情况下，移动而非拷贝对象会大幅度提升性能。还有的情况诸如IO类或者unique_ptr这些类都包含不能共享的资源，因此这些类的对象也不能拷贝只能移动。为了支持移动操作，在新标准中引入了一种新的引用类型——右值引用。右值引用有个重要的性质：只能绑定到一个即将要销毁的对象上。因此我们可以自由地将一个右值引用的资源”移动”到另一个对象中。下面给出一些例子来表示哪些是右值：
inti=42;
int&r=i;//正确：r引用i
int&&rr=i;//错误：不能将一个右值引用绑定到左值上
int&r2=i42;//错误：i42是个右值
constint&r3=i432;//正确：我们可以把一个const引用绑定到右值上
int&&rr2=i42;//正确：右值引用绑定右值
考察左值和右值的区别：左值有持久的状态，而右值要么是字面常量，要么是在表达式求值过程中或者是函数返回的时候创建的临时变量。
因为变量是左值，所以我们不能将一个右值引用绑定到一个变量上，即使这个变量是一个右值引用类型也不行。所以为了解决这个问题，标准库提供了一个move函数，它可以用来获得绑定到左值上的右值引用。此函数定义在头文件utility中。
我们可以销毁一个移后源对象，也可以赋予新值，但不能在赋新值之前使用移后源对象的值。
根据以上所说，如果类也支持移动拷贝和移动赋值，那么也能在某些时候的初始化(赋值)的时候提高性能。如果要想让类支持移动语义，我们需要为其定义移动构造函数和移动赋值运算符。这两个函数的参数都是一个右值引用。就如同上面的代码，对于vector的移动我们只需要拷贝三个指针参数，而不是拷贝三个指针参数指向的值。
template
myVector::myVector(_Myt&&v):elements(v.elements),first_free(v.first_free),cap(v.cap){
v.elements=v.first_free=v.cap=nullptr;
}
值得注意的是，我们要保证移后源对象必须是可析构状态，而且如果移动构造(赋值)函数不抛出异常的话必须要标记为noexcept(primerp474)。对于移动赋值运算符我们要保证能正确处理自我赋值：
template
myVector&myVector::operator=(_Myt&&rhs)
{
if(this!=&rhs)
{
free();
elements=rhs.elements;
first_free=rhs.first_free;
cap=rhs.cap;
//将rhs置为可析构状态
rhs.elements=rhs.first_free=rhs.cap=nullptr;
}
}
当然，和其他构造函数一样，如果我们没有定义移动构造函数的时候，编译器会给我们提供默认的移动构造函数。不过，前提是该类没有定义任何版本的拷贝控制函数以及每个非staitc成员变量都可以移动。编译器就会默认为它合成移动构造函数和移动赋值运算符。
十九.优化过后的Vector
我们使用allocate和移动语义对以上的vector进行优化：
#pragmaonce
#include
template
classmyVector
{
public:
typedefmyVector_Myt;
myVector():
elements(nullptr),first_free(nullptr),cap(nullptr){}//allocator成员进行默认初始化
myVector(const_Myt&);
myVector(_Myt&&);
_Myt&operator=(const_Myt&);
_Myt&operator=(_Myt&&);
~myVector();
T&operator[](size_ti){return(elements+i);}
voidpush_back(constT&);//添加元素
size_tsize()const{returnfirst_free-elements;}
size_tcapacity()const{returncap-elements;}
Tbegin()const{returnwww.baiyuewang.netelements;}
Tend()const{returnfirst_free;}
private:
staticstd::allocatoralloc;
voidchk_n_alloc()//被添加元素函数使用
{
if(size()==capacity())reallocate();
}
std::pairalloc_n_copy
(constT,constT);//被拷贝构造，赋值运算符，析构函数使用
voidfree();//销毁元素并释放内存
voidreallocate();//获得更多内存并拷贝已有元素
Telements;
Tfirst_free;
Tcap;
};
template
std::allocatormyVector::alloc;
template
myVector::myVector(const_Myt&v)
{
//调用alloc_n_copy分配空间以容纳与s中一样多的元素
autonewdata=alloc_n_copy(v.begin(),v.end());
elements=newdata.first;
first_free=cap=newdata.second;
}
template
myVector::myVector(_Myt&&v):elements(v.elements),first_free(v.first_free),cap(v.cap){
v.elements=v.first_free=v.cap=nullptr;
}
template
myVector::~myVector()
{
free();
}
template
myVector&myVector::operator=(const_Myt&rhs)
{
//调用alloc_n_copy分配内存,大小与rhs一样.
autodata=alloc_n_copy(rhs.begin(),rhs.end());
free();
elements=data.first;
first_free=cap=data.second;
returnthis;
}
template
myVector&myVector::operator=(_Myt&&rhs)
{
if(this!=&rhs)
{
free();
elements=rhs.elements;
first_free=rhs.first_free;
cap=rhs.cap;
//将rhs置为可析构状态
rhs.elements=rhs.first_free=rhs.cap=nullptr;
}
}
template
std::pairmyVector::
alloc_n_copy(constTb,constTe)
{
autodata=alloc.allocate(e-b);
//初始化并返回一个pair,该pair由data和uninitialized_copy组成
return{data,uninitialized_copy(b,e,data)};
}
template
voidmyVector::push_back(constT&s)
{
chk_n_alloc();//确保已有新空间
alloc.construct(first_free++,s);
}
template
voidmyVector::free()
{
//不能传递给deallocate一个空指针，如果elements为NULL,那么函数什么都不做
if(elements)
{
//逆序销毁所有元素
for(autop=first_free;p!=elements;/空/)
alloc.destroy(--p);
alloc.deallocate(elements,cap-elements);
}
}
template
voidmyVector::reallocate()
{
//我们将分配当前大小两倍的内存空间
autonewcapacity=size()?2size():1;
//分配新内存
autonewdata=alloc.allocate(newcapacity);
//将数据从旧地址移动到新地址
autodest=newdata;
autoelem=elements;
for(size_ti=0;i!=size();++i)
alloc.construct(dest++,std::move(elem++));
free();//一旦更新完就要释放旧内存
elements=newdata;
first_free=dest;
cap=elements+newcapacity;
}
尽管，以上的代码vector只实现了vector很少的一部分功能，而且可能实现方式也有不足的地方。不过，在这里只是想体现动态内存的使用。所以，以上的代码还是可以作为c++动态内存管理的的示例的。
|
|
