[置顶] 从零开始学C++之STL（二）：实现简单容器模板类Vec（vector capacity 增长问题、allocator 内存分配器）

首先，vector 在VC 2008 中的实现比较复杂，虽然vector 的声明跟VC6.0 是一致的，如下：

C++ Code

1
2

template <
class _Ty,
class _Ax = allocator<_Ty> >

class vector;

但在VC2008 中vector 还有基类，如下：

C++ Code

1

2

3

4

5

6

7

// TEMPLATE CLASS vector

template <
class _Ty,

class _Ax >

class vector

:
public _Vector_val<_Ty, _Ax>

{

};

稍微来看一下基类_Vector_val：

C++ Code

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

// TEMPLATE CLASS _Vector_val

template <
class _Ty,


class _Alloc >

class _Vector_val

    :
public _CONTAINER_BASE_AUX_ALLOC<_Alloc>

{


// base class for vector to hold allocator _Alval

protected:

    _Vector_val(_Alloc _Al = _Alloc())

        : _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Alval(_Al)

    {


// construct allocator from _Al
    }

typedef
typename _Alloc::
template

rebind<_Ty>::other _Alty;

_Alty _Alval;
// allocator object for values
};

为了理解_Alty 的类型，还得看一下allocator模板类：

C++ Code

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

template<
class _Ty>
class allocator

{

template<>
class _CRTIMP2_PURE allocator<
void>

    {


// generic allocator for type void

public:


template<
class _Other>


struct rebind

        {


// convert an allocator<void> to an allocator <_Other>

typedef allocator<_Other> other;

        };

        ....

    };

    ...

};

typedef typename _Alloc::template rebind<_Ty>::other _Alty; 整体来看是类型定义，假设现在我们这样使用

vector<int>，那么_Ty 即 int, _Ax 即 allocator<int>，由vector 类传递给基类_Vector_val，则_Alloc 即

allocator<int> ；可以看到 allocator<void> 是allocator 模板类的特化， rebind<_Ty> 是成员模板类，other是成员模板类

中自定义类型，_Ty 即是int ，那么other 类型也就是allocator<int>，也就是说_Alty 是类型 allocator<int> 。

_Alty _Alval; 即基类定义了一个allocator<int> 类型的成员，被vector 继承后以后用于为vector 里面元素分配内存等操作。

而在VC6.0，_Alval 是直接作为vector 自身的成员存在的。此外还有一个比较大的不同点在于，两个版本对于capacity 也就是容量的

计算方式不同，接下去的测试可以看到这种不同，在这里可以先说明一下：

VC2008：容量每次增长为原先容量 + 原先容量 / 2;

VC6.0 ：容量每次增长为原先容量的2倍。

容量跟vector 大小的概念是不一样的，capacity 》= size，如下图所示：
[置顶] 从零开始学C++之STL（二）：实现简单容器模板类Vec（vector capacity 增长问题、allocator 内存分配器）

size 指的是avail - data 的区间；capacity 指的是 limit - data 的区间；也就是说存在尚未使用的空间。

下面是模仿VC6.0 中vector 的实现写的Vec 类，程序主要参考《Accelerated C++》，略有修改，比如将接口修改成与VC6.0 一致，

这样做的好处是可以传递第二个参数，也就是说可以自己决定内存的分配管理方式；实现capacity() 函数等；

Vec.h：

C++ Code

1

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

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

/*************************************************************************
> File Name: template_class_Vec.h
> Author: Simba
> Mail: dameng34@163.com
> Created Time: Thu 07 Feb 2013 06:51:12 PM CST
************************************************************************/

#include<iostream>

#include<cstddef>

#include<memory>

#include<algorithm>

template <
class T,
class A_ = std::allocator<T> >

class Vec

{

public:
// interface

typedef T *iterator;


typedef
const T *const_iterator;


typedef size_t size_type;


typedef T value_type;


typedef std::ptrdiff_t difference_type;


typedef T &reference;


typedef
const T &const_reference;

Vec()

    {

        create();
// default constructor
    }


// const T & t = T();意思是默认参数，当没有传递t时，默认使用T() (type T's default constructor)

//explicit表示不允许构造函数进行隐式类型转换

explicit Vec(size_type n,
const T &val = T())

    {

        create(n, val);

    }

    Vec(
const Vec &v)

    {

        create(v.begin(), v.end());
// copy constructor
    }

    Vec &
operator=(
const Vec &);
// assigment operator
    ~Vec()

    {

        uncreate();
// destructor
    }

size_type size()
const

    {


return avail - data;
// a value of ptrdiff_t
    }

    size_type capacity()
const

    {


return (data ==
?
: limit - data);

    }

    T &
operator[](size_type i)

    {


return data[i];

    }


/* because their left operand is different(const), we can overload the operation */


const T &
operator[](size_type i)
const

    {


return data[i];

    }

iterator begin()

    {


return data;

    }

    const_iterator begin()
const

    {


return data;

    }

    iterator end()

    {


return avail;

    }

    const_iterator end()
const

    {


return avail;

    }

void push_back(
const T &val)

    {


if (avail == limit)
// get space if needed
            grow();

        unchecked_append(val);
// append the new element
    }


void clear()

    {

        uncreate();

    }


void empty()

    {


return data == avail;

    }

private:

    iterator data;
// first element in the Vec
    iterator avail;
// one past the last constructed element in the Vec
    iterator limit;
// one past the last available element

A_ alloc;
// object to handle memory allocation

// allocate and initialize the underlying array

void create();


void create(size_type,
const T &);


void create(const_iterator, const_iterator);

// destory the element in the array and free the memory

void uncreate();


// support functions for push_back

void grow();


void unchecked_append(
const T &);

};

template <
class T,
class A_>

Vec<T, A_> &Vec<T, A_>::
operator=(
const Vec<T, A_> &rhs)

{


// check for self-assigment

if (&rhs !=
this)

    {

        uncreate();

        create(rhs.begin(), rhs.end());

    }

return *
this;

}

template <
class T,
class A_>

void Vec<T, A_>::create()

{

data = avail = limit =
;

}

template <
class T,
class A_>

void Vec<T, A_>::create(size_type n,
const T &val)

{

    data = alloc.allocate(n);

    limit = avail = data + n;

    std::uninitialized_fill(data, limit, val);

}

template <
class T,
class A_>

void Vec<T, A_>::create(const_iterator i, const_iterator j)

{

    data = alloc.allocate(j - i);

    limit = avail = std::uninitialized_copy(i, j, data);


/* return a pointer to (one past) the last element that it initialized */

}

template <
class T,
class A_>

void Vec<T, A_>::uncreate()

{


if (data)

    {


// destroy(in reverse order) the elements that were constructed
        iterator it = avail;


while (it != data)


// destory runs T's destructor for that object, rendering the storage uninitialized again
            alloc.destroy(--it);

alloc.deallocate(data, limit - data);

    }


// reset pointers to indicate that Vec is empty again
    data = limit = avail =
;

}

template <
class T,
class A_>

void Vec<T, A_>::grow()

{

// when growing, allocate twice as much space as currently in use
size_type new_size = std::max(
* (limit - data), ptrdiff_t(
));

// allocate new space and copy elements to the new space
iterator new_data = alloc.allocate(new_size);

iterator new_avail = std::uninitialized_copy(data, avail, new_data);

// return the old space
uncreate();

// reset pointers to point to the newly allocated space
    data = new_data;

    avail = new_avail;

    limit = data + new_size;

}

template <
class T,
class A_>

// error C4519: 仅允许在类模板上使用默认模板参数

void Vec<T, A_>::unchecked_append(
const T &val)

{

alloc.construct(avail++, val);

}

先介绍一下用到的一些类和函数：

allocator 模板类：

C++ Code

1

2

3

4

5

6

7

8

9

10

#include <memory>

template <
class T>
class allocator

{

public:

    T *allocate(size_t);


void deallocate(T *, size_t);


void construct(T *, size_t);


void destroy(T *);


//.......
};

当然实际的接口没实现没那么简单，但大概实现的功能差不多:

allocate 调用operator new ；deallocate 调用 operator delete; construct 调用placement new （即在分配好的内

存上调用拷贝构造函数），destroy 调用析构函数。

两个std函数：

C++ Code

1

2

3

4

5

template <
class In,
class For>

For uninitialized_copy(In, In, For);

template <
class For,
class T>

void uninitialized_fill(For, For,
const T &);

如 std::uninitialized_copy(i, j, data); 即将i ~ j 指向区间的数值都拷贝到data 指向的区间，返回的是最后一个初始化值的下一个位置。

std::uninitialized_fill(data, limit, val); 即将 data ~ limit 指向的区间都初始化为val 。

为了理解push_back 的工作原理，写个小程序测试一下：

C++ Code

1

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

#include <iostream>

#include
"Vec.h"

using
namespace std;

class Test

{

public:

    Test()

    {

        cout <<
"Test ..." << endl;

    }

    Test(
const Test &other)

    {

        cout <<
"copy Test ..." << endl;

    }

    ~Test()

    {

        cout <<
"~Test ..." << endl;

    }

};

int main(
void)

{

    vector<Test> v2;

    Test t1;

    Test t2;

    Test t3;

    v2.push_back(t1);

    v2.push_back(t2);

    v2.push_back(t3);

return
;

}

[置顶] 从零开始学C++之STL（二）：实现简单容器模板类Vec（vector capacity 增长问题、allocator 内存分配器）

从输出可以看出，构造函数调用3次，拷贝构造函数调用6次，析构函数调用9次，下面来分析一下，首先看下图：

[置顶] 从零开始学C++之STL（二）：实现简单容器模板类Vec（vector capacity 增长问题、allocator 内存分配器）

首先定义t1, t2, t3的时候调用三次构造函数，这个没什么好说的；接着第一次调用push_back，调用grow进而调用alloc.allocate，

allocate 函数调用operator new 分配一块内存，第一次uncreate 没有效果，接着push_back 里面调用uncheck_append，进而调用

alloc.construct，即调用placement new（new (_Vptr) _T1(_Val); ），在原先分配好的内存上调用一次拷贝构造函数。

接着第二次调用push_back，一样的流程，这次先分配两块内存，将t1 拷贝到第一个位置，调用uncreate()，先调用alloc.destroy，即

调用一次析构函数，接着调用alloc.deallcate，即调用operator delete 释放内存，最后调用uncheck_append将t2 拷贝到第二个位置。

第三次调用push_back，也一样分配三块内存，将t1, t2 拷贝下来，然后分别析构，最后将t3 拷贝上去。

程序结束包括定义的三个Test 对象t1, t2, t3 ，析构3次，Vec<Test> v2; v2是局部对象，生存期到则调用析构函数~Vec(); 里面调用

uncreate()，调用3次Test 对象的析构函数，调用operator delete 释放3个对象的内存。故总共析构了6次。

在VC2008 中换成 vector<Test> v2; 来测试的话，输出略有不同，如下：

[置顶] 从零开始学C++之STL（二）：实现简单容器模板类Vec（vector capacity 增长问题、allocator 内存分配器）

输出的次数是一致的，只是拷贝的顺序有所不同而已，比如第二次调用push_back 的时候，VC2008 中的vector 是先拷贝t2, 接着拷

贝t1, 然后将t1 释放掉。

最后再来提一下关于capacity 的计算，如下的测试程序：

C++ Code

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

#include <iostream>

#include
"Vec.h"

using
namespace std;

int main(
void)

{

Vec<
int> v;

v.push_back(
);

    cout << v.capacity() << endl;

    v.push_back(
);

    cout << v.capacity() << endl;

    v.push_back(
);

    cout << v.capacity() << endl;

    v.push_back(
);

    cout << v.capacity() << endl;

    v.push_back(
);

    cout << v.capacity() << endl;

    v.push_back(
);

    cout << v.capacity() << endl;

    v.push_back(
);

    cout << v.capacity() << endl;

}

输出为 1 2 4 4 8 8 8 即在不够的情况下每次增长为原来的2倍。

如果换成 vector<int> v; 测试，那么输出是 1 2 3 4 6 6 9，即在不够的情况每次增长为原来大小 + 原来大小 / 2；

看到这里，有些朋友会疑惑了，由1怎么会增长到2呢？按照原则不是还是1？其实只要看一下vector 的源码就清楚了：

C++ Code

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

void _Insert_n(const_iterator _Where,

size_type _Count,
const _Ty &_Val)

{

// insert _Count * _Val at _Where

.....

    size_type _Capacity = capacity();

    .....


else
if (_Capacity < size() + _Count)

    {


// not enough room, reallocate
        _Capacity = max_size() - _Capacity /
< _Capacity

                    ?
: _Capacity + _Capacity /
;
// try to grow by 50%

if (_Capacity < size() + _Count)

            _Capacity = size() + _Count;

        pointer _Newvec =
this->_Alval.allocate(_Capacity);

        pointer _Ptr = _Newvec;

        .....

    }

}

_Insert_n 是被push_back 调用的，当我们试图增长为_Capacity + _Capacity / 2; 时，下面还有一个判断：

if (_Capacity < size() + _Count)

_Capacity = size() + _Count;

现在试图增长为 1 + 1/ 2 = 1；此时因为 1 < 1 + 1 ; 所以 _Capacity = 1 + 1 = 2;

其他情况都是直接按公式增长。

从上面的分析也可以看出，当push_back 的时候往往带有拷贝和析构多个操作，所以一下子分配比size() 大的空间capacity，可以减

轻频繁操作造成的效率问题。

参考：

C++ primer 第四版
Effective C++ 3rd
C++编程规范

秒客网

[置顶] 从零开始学C++之STL（二）：实现简单容器模板类Vec（vector capacity 增长问题、allocator 内存分配器）

相关文章