myvector分析 我们知道,vector类将其元素存放在连续的内存中。为了获得可接受的性能,vetor预先分配足够大的内存来保存可能需要的更多元素。vector的每个添加元素的成员函数会检查是否有空间容纳更多的元素。如果有,成员函数会在下一个可用位置构造一个对象。如果没有可用空间,vector就会重新分配空间;它获得新的空间,将已有元素移动到新空间中,释放旧空间,并添加新元素。 既然是动态开辟的内存,于是我们在myvector中使用动态数组来存储,而每次插入元素的时候需要先判断开辟的内存是否已满,如果满了需要重新分配内存。
下面给出最初版本的代码:
//myvector.h #include template class myvector { public: typedef myvector _myt; myvector() : elements(nullptr), first_free(nullptr), cap(nullptr){} // allocator成员进行默认初始化 myvector(const _myt&); _myt& operator=(const _myt&); ~myvector(); t& operator[](size_t i){ return *(elements + i); } void push_back(const t&); // 添加元素 size_t size()const{ return first_free - elements; } size_t capacity()const{ return cap - elements; } t *begin()const{ return elements; } t *end()const{ return first_free; } private: void chk_n() //被添加元素函数使用 { if (size() == capacity())reallocate(); } std::pair n_copy (const t*, const t*); //被拷贝构造,赋值运算符,析构函数使用 void free(); //销毁元素并释放内存 void reallocate(); //获得更多内存并拷贝已有元素 t *elements; t *first_free; t *cap; }; template myvector::myvector(const _myt& v) { //调用alloc_n_copy 分配空间以容纳与s中一样多的元素 auto newdata = 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一样. auto data = n_copy(rhs.begin(), rhs.end()); free(); elements = data.first; first_free = cap = data.second; return *this; } template std::pair myvector:: n_copy(const t *b, const t *e) { auto data = new t[e - b]; for (auto i = b; i < e; i++) data[i-b] = *i; return{ data, data + (e - b) }; } template void myvector::push_back(const t& s) { chk_n(); //确保已有新空间 *(first_free++) = s; } template void myvector::free() { delete[] elements; } template void myvector::reallocate() { //我们将分配当前大小两倍的内存空间 auto newcapacity = size() ? 2 * size() : 1; //分配新内存 auto newdata = new t[newcapacity]; auto dest = newdata; auto elem = elements; //将数据从旧地址移动到新地址 for (size_t i = 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中,它帮助我们将内存分配和对象构造分离开来。 |
函数 | 介绍 |
---|---|
allocator |
定义了一个名为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进行内存分配,对象构造,对象释放,内存回收。 |
int main() { allocator alloc; //这个对象可以用来分配 string 类型的内存。 string* p = alloc.allocate(5); //使用alloc对象分配5个string对象大的连续内存并将头指针给p。 //allocate分配的内存在没有构造之前是不能使用的!! alloc.construct(p,"hello world"); //使用"hello world"构造string cout << *p << endl; //输出刚才构造的string,输出hello world alloc.destroy(p); //销毁刚才构造的对象 alloc.deallocate(p,5); //释放内存 return 0; }
不仅这样,标准库还提供了一些算法让我们使用的时候更加方便: |函数|介绍| |—|—-| |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这些类都包含不能共享的资源,因此这些类的对象也不能拷贝只能移动。 为了支持移动操作,在新标准中引入了一种新的引用类型 —— 右值引用。右值引用有个重要的性质:只能绑定到一个即将要销毁的对象上。因此我们可以自由地将一个右值引用的资源”移动”到另一个对象中。下面给出一些例子来表示哪些是右值: |
int i = 42; int &r = i; //正确:r引用i int &&rr = i; //错误:不能将一个右值引用绑定到左值上 int &r2 = i * 42; //错误:i * 42 是个右值 const int & r3 = i * 432; //正确:我们可以把一个const引用绑定到右值上 int &&rr2 = i * 42; //正确:右值引用绑定右值
考察左值和右值的区别:左值有持久的状态,而右值要么是字面常量,要么是在表达式求值过程中或者是函数返回的时候创建的临时变量。 因为变量是左值,所以我们不能将一个右值引用绑定到一个变量上,即使这个变量是一个右值引用类型也不行。所以为了解决这个问题,标准库提供了一个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(primer p474)。 对于移动赋值运算符我们要保证能正确处理自我赋值: |
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进行优化: |
#pragma once #include template class myvector { public: typedef myvector _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_t i){ return *(elements + i); } void push_back(const t&); // 添加元素 size_t size()const{ return first_free - elements; } size_t capacity()const{ return cap - elements; } t *begin()const{ return elements; } t *end()const{ return first_free; } private: static std::allocator alloc; void chk_n_alloc() //被添加元素函数使用 { if (size() == capacity())reallocate(); } std::pair alloc_n_copy (const t*, const t*); //被拷贝构造,赋值运算符,析构函数使用 void free(); //销毁元素并释放内存 void reallocate(); //获得更多内存并拷贝已有元素 t *elements; t *first_free; t *cap; }; template std::allocator myvector::alloc; template myvector::myvector(const _myt& v) { //调用alloc_n_copy 分配空间以容纳与s中一样多的元素 auto newdata = 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一样. auto data = alloc_n_copy(rhs.begin(), rhs.end()); free(); elements = data.first; first_free = cap = data.second; return *this; } 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::pair myvector:: alloc_n_copy(const t *b, const t *e) { auto data = alloc.allocate(e - b); //初始化并返回一个pair,该pair由data和uninitialized_copy组成 return{ data, uninitialized_copy(b, e, data) }; } template void myvector::push_back(const t& s) { chk_n_alloc(); //确保已有新空间 alloc.construct(first_free++, s); } template void myvector::free() { //不能传递给deallocate一个空指针,如果elements为null,那么函数什么都不做 if (elements) { //逆序销毁所有元素 for (auto p = first_free; p != elements;/* 空 */) alloc.destroy(--p); alloc.deallocate(elements, cap - elements); } } template void myvector::reallocate() { //我们将分配当前大小两倍的内存空间 auto newcapacity = size() ? 2 * size() : 1; //分配新内存 auto newdata = alloc.allocate(newcapacity); //将数据从旧地址移动到新地址 auto dest = newdata; auto elem = elements; for (size_t i = 0; i != size(); ++i) alloc.construct(dest++, std::move(*elem++)); free(); //一旦更新完就要释放旧内存 elements = newdata; first_free = dest; cap = elements + newcapacity; }
尽管,以上的代码vector只实现了vector很少的一部分功能,而且可能实现方式也有不足的地方。不过,在这里只是想体现动态内存的使用。所以,以上的代码还是可以作为c++动态内存管理的的示例的。 |
基本上c++动态内存管理的就介绍到这里了。 |
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/607991.html