十六.myVector分析
我们知道，vector类将其元素存放在连续的内存中。为了获得可接受的性能，vetor预先分配足够大的内存来保存可能需要的更多元素。vector的每个添加元素的成员函数会检查是否有空间容纳更多的元素。如果有，成员函数会在下一个可用位置构造一个对象。如果没有可用空间，vector就会重新分配空间；它获得新的空间，将已有元素移动到新空间中，释放旧空间，并添加新元素。 既然是动态开辟的内存，于是我们在myVector中使用动态数组来存储，而每次插入元素的时候需要先判断开辟的内存是否已满，如果满了需要重新分配内存。 下面给出最初版本的代码：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
2#include <memory>
3
4template<typename T>
5class myVector
6{
7public:
8 typedef myVector<T> _Myt;
9 myVector() :
10 elements(nullptr), first_free(nullptr), cap(nullptr){} // allocator成员进行默认初始化
11 myVector(const _Myt&);
12 _Myt& operator=(const _Myt&);
13 ~myVector();
14 T& operator[](size_t i){ return *(elements + i); }
15 void push_back(const T&); // 添加元素
16 size_t size()const{ return first_free - elements; }
17 size_t capacity()const{ return cap - elements; }
18 T *begin()const{ return elements; }
19 T *end()const{ return first_free; }
20private:
21 void chk_n() //被添加元素函数使用
22 {
23 if (size() == capacity())reallocate();
24 }
25 std::pair<T*, T*> n_copy
26 (const T*, const T*); //被拷贝构造，赋值运算符，析构函数使用
27 void free(); //销毁元素并释放内存
28 void reallocate(); //获得更多内存并拷贝已有元素
29
30 T *elements;
31 T *first_free;
32 T *cap;
33};
34
35template<typename T>
36myVector<T>::myVector(const _Myt& v)
37{
38 //调用alloc_n_copy 分配空间以容纳与s中一样多的元素
39 auto newdata = n_copy(v.begin(), v.end());
40 elements = newdata.first;
41 first_free = cap = newdata.second;
42}
43template<typename T>
44myVector<T>::~myVector()
45{
46 free();
47}
48template<typename T>
49myVector<T>& myVector<T>::operator=(const _Myt& rhs)
50{
51 //调用alloc_n_copy分配内存,大小与rhs一样.
52 auto data = n_copy(rhs.begin(), rhs.end());
53
54 free();
55
56 elements = data.first;
57 first_free = cap = data.second;
58
59 return *this;
60}
61template<typename T>
62std::pair<T*, T*> myVector<T>::
63n_copy(const T *b, const T *e)
64{
65 auto data = new T[e - b];
66 for (auto i = b; i < e; i++)
67 data[i-b] = *i;
68
69 return{ data, data + (e - b) };
70}
71template<typename T>
72void myVector<T>::push_back(const T& s)
73{
74 chk_n(); //确保已有新空间
75 *(first_free++) = s;
76}
77
78template<typename T>
79void myVector<T>::free()
80{
81 delete[] elements;
82}
83
84template<typename T>
85void myVector<T>::reallocate()
86{
87 //我们将分配当前大小两倍的内存空间
88 auto newcapacity = size() ? 2 * size() : 1;
89
90 //分配新内存
91 auto newdata = new T[newcapacity];
92 auto dest = newdata;
93 auto elem = elements;
94
95 //将数据从旧地址移动到新地址
96 for (size_t i = 0; i != size(); ++i)
97 *(dest++) = *(elem++);
98 free(); //一旦更新完就要释放旧内存
99
100 elements = newdata;
101 first_free = dest;
102
103 cap = elements + newcapacity;
104}
105
恩，以上代码实现了vector的部分功能，实现了vector内存的动态分配。不过，我们可以发现以上代码还是有几个可以优化的地方：
- 1.在分配内存的时候，new将内存分配和对象构造组合在了一起。但是在vector分配内存的时候，事实上有许多内存我们可能并用不上；而如果对于这些内存进行构造对象，可能就会带来不必要的开销。
- 2.在内存重新分配的时候，我们涉及到了旧数据的转移；不对，这里应该说是拷贝。虽然的确应该是转移，然而我们实现是通过拷贝。在c++11的时候提供了移动构造语义。它可以对于即将销毁(保证重新赋值前不再使用)的对象进行移动。这样对于某些支持移动语义的对象。移动比拷贝就可以带来更小的开销。
恩，要进行以上的优化我们要先介绍：allocator类，移动语义。
十七.allocator类介绍
new有一些灵活性的局限，一方面表现在它将内存分配和对象构造组合在一起。类似的，delete将对象析构和内存释放组合在一起。我们分配单个对象时，通常我们希望将内存和对象初始化放在一起。因为在这样的情况下，我们几乎已经知道了对象应当是什么值。 当分配一大块内存时，我们通常计划在这块内存上按需构造对象。在这种情况下，我们就应该希望将内存分配和对象构造分离。这意味着我们可以分配大块内存，然而只有我们真正需要的时候才执行对象创建操作(同时付出一定开销)。 标准库allocator类定义在头文件memory中，它帮助我们将内存分配和对象构造分离开来。
allocator<T> a
定义了一个名为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进行内存分配，对象构造，对象释放，内存回收。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2{
3 allocator<string> alloc; //这个对象可以用来分配 string 类型的内存。
4 string* p = alloc.allocate(5); //使用alloc对象分配5个string对象大的连续内存并将头指针给p。
5
6 //allocate分配的内存在没有构造之前是不能使用的！！
7 alloc.construct(p,"hello world"); //使用"hello world"构造string
8
9 cout << *p << endl; //输出刚才构造的string，输出hello world
10
11 alloc.destroy(p); //销毁刚才构造的对象
12
13 alloc.deallocate(p,5); //释放内存
14 return 0;
15}
16
不仅这样，标准库还提供了一些算法让我们使用的时候更加方便： |函数|介绍| |—|—-| |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这些类都包含不能共享的资源，因此这些类的对象也不能拷贝只能移动。 为了支持移动操作，在新标准中引入了一种新的引用类型 —— 右值引用。右值引用有个重要的性质：只能绑定到一个即将要销毁的对象上。因此我们可以自由地将一个右值引用的资源”移动”到另一个对象中。下面给出一些例子来表示哪些是右值：
2
3
4
5
6
7
2int &r = i; //正确：r引用i
3int &&rr = i; //错误：不能将一个右值引用绑定到左值上
4int &r2 = i * 42; //错误：i * 42 是个右值
5const int & r3 = i * 432; //正确：我们可以把一个const引用绑定到右值上
6int &&rr2 = i * 42; //正确：右值引用绑定右值
7
考察左值和右值的区别：左值有持久的状态，而右值要么是字面常量，要么是在表达式求值过程中或者是函数返回的时候创建的临时变量。 因为变量是左值，所以我们不能将一个右值引用绑定到一个变量上，即使这个变量是一个右值引用类型也不行。所以为了解决这个问题，标准库提供了一个move函数，它可以用来获得绑定到左值上的右值引用。此函数定义在头文件utility中。 我们可以销毁一个移后源对象，也可以赋予新值，但不能在赋新值之前使用移后源对象的值。 根据以上所说，如果类也支持移动拷贝和移动赋值，那么也能在某些时候的初始化(赋值)的时候提高性能。如果要想让类支持移动语义，我们需要为其定义移动构造函数和移动赋值运算符。这两个函数的参数都是一个右值引用。就如同上面的代码，对于vector的移动我们只需要拷贝三个指针参数，而不是拷贝三个指针参数指向的值。
2
3
4
5
2myVector<T>::myVector(_Myt&& v):elements(v.elements),first_free(v.first_free),cap(v.cap){
3 v.elements = v.first_free = v.cap = nullptr;
4}
5
值得注意的是，我们要保证移后源对象必须是可析构状态，而且如果移动构造(赋值)函数不抛出异常的话必须要标记为noexcept(primer p474)。 对于移动赋值运算符我们要保证能正确处理自我赋值：
2
3
4
5
6
7
8
9
10
11
12
13
14
2myVector<T>& myVector<T>::operator=(_Myt&& rhs)
3{
4 if (this != &rhs)
5 {
6 free();
7 elements = rhs.elements;
8 first_free = rhs.first_free;
9 cap = rhs.cap;
10 //将rhs置为可析构状态
11 rhs.elements = rhs.first_free = rhs.cap = nullptr;
12 }
13}
14
当然，和其他构造函数一样，如果我们没有定义移动构造函数的时候，编译器会给我们提供默认的移动构造函数。不过，前提是该类没有定义任何版本的拷贝控制函数以及每个非staitc成员变量都可以移动。编译器就会默认为它合成移动构造函数和移动赋值运算符。
十九.优化过后的Vector
我们使用 allocate 和移动语义对以上的vector进行优化：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
2
3#include <memory>
4
5template<typename T>
6class myVector
7{
8public:
9 typedef myVector<T> _Myt;
10 myVector() :
11 elements(nullptr), first_free(nullptr), cap(nullptr){} // allocator成员进行默认初始化
12 myVector(const _Myt&);
13 myVector(_Myt&&);
14 _Myt& operator=(const _Myt&);
15 _Myt& operator=(_Myt&&);
16 ~myVector();
17 T& operator[](size_t i){ return *(elements + i); }
18 void push_back(const T&); // 添加元素
19 size_t size()const{ return first_free - elements; }
20 size_t capacity()const{ return cap - elements; }
21 T *begin()const{ return elements; }
22 T *end()const{ return first_free; }
23private:
24 static std::allocator<T> alloc;
25 void chk_n_alloc() //被添加元素函数使用
26 {
27 if (size() == capacity())reallocate();
28 }
29 std::pair<T*, T*> alloc_n_copy
30 (const T*, const T*); //被拷贝构造，赋值运算符，析构函数使用
31 void free(); //销毁元素并释放内存
32 void reallocate(); //获得更多内存并拷贝已有元素
33
34 T *elements;
35 T *first_free;
36 T *cap;
37};
38
39template<typename T>
40std::allocator<T> myVector<T>::alloc;
41
42template<typename T>
43myVector<T>::myVector(const _Myt& v)
44{
45 //调用alloc_n_copy 分配空间以容纳与s中一样多的元素
46 auto newdata = alloc_n_copy(v.begin(), v.end());
47 elements = newdata.first;
48 first_free = cap = newdata.second;
49}
50template<typename T>
51myVector<T>::myVector(_Myt&& v):elements(v.elements),first_free(v.first_free),cap(v.cap){
52 v.elements = v.first_free = v.cap = nullptr;
53}
54
55template<typename T>
56myVector<T>::~myVector()
57{
58 free();
59}
60template<typename T>
61myVector<T>& myVector<T>::operator=(const _Myt& rhs)
62{
63 //调用alloc_n_copy分配内存,大小与rhs一样.
64 auto data = alloc_n_copy(rhs.begin(), rhs.end());
65
66 free();
67
68 elements = data.first;
69 first_free = cap = data.second;
70
71 return *this;
72}
73template<typename T>
74myVector<T>& myVector<T>::operator=(_Myt&& rhs)
75{
76 if (this != &rhs)
77 {
78 free();
79 elements = rhs.elements;
80 first_free = rhs.first_free;
81 cap = rhs.cap;
82 //将rhs置为可析构状态
83 rhs.elements = rhs.first_free = rhs.cap = nullptr;
84 }
85}
86
87template<typename T>
88std::pair<T*, T*> myVector<T>::
89alloc_n_copy(const T *b, const T *e)
90{
91 auto data = alloc.allocate(e - b);
92
93 //初始化并返回一个pair,该pair由data和uninitialized_copy组成
94 return{ data, uninitialized_copy(b, e, data) };
95}
96template<typename T>
97void myVector<T>::push_back(const T& s)
98{
99 chk_n_alloc(); //确保已有新空间
100 alloc.construct(first_free++, s);
101}
102
103template<typename T>
104void myVector<T>::free()
105{
106 //不能传递给deallocate一个空指针，如果elements为NULL,那么函数什么都不做
107 if (elements)
108 {
109 //逆序销毁所有元素
110 for (auto p = first_free; p != elements;/* 空 */)
111 alloc.destroy(--p);
112 alloc.deallocate(elements, cap - elements);
113 }
114}
115
116template<typename T>
117void myVector<T>::reallocate()
118{
119 //我们将分配当前大小两倍的内存空间
120 auto newcapacity = size() ? 2 * size() : 1;
121
122 //分配新内存
123 auto newdata = alloc.allocate(newcapacity);
124
125 //将数据从旧地址移动到新地址
126 auto dest = newdata;
127 auto elem = elements;
128
129 for (size_t i = 0; i != size(); ++i)
130 alloc.construct(dest++, std::move(*elem++));
131 free(); //一旦更新完就要释放旧内存
132
133 elements = newdata;
134 first_free = dest;
135
136 cap = elements + newcapacity;
137}
138
尽管，以上的代码vector只实现了vector很少的一部分功能，而且可能实现方式也有不足的地方。不过，在这里只是想体现动态内存的使用。所以，以上的代码还是可以作为c++动态内存管理的的示例的。
基本上c++动态内存管理的就介绍到这里了。
