容器vector

发表于 | 分类于 | 阅读次数: |

容器vector和空间配置器

实现一个C++ STL里面的简单向量容器类vector

vector 向量容器 2倍扩容的数组 VS-vector 1.5倍 gcc-vector 2倍

vector简单实现

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
template<typename T>
class Vector
{
public:
    Vector(int _size)
        :_first(nullptr)
        ,_last(nullptr)
        ,_end(nullptr)
    {
        _first=new T[_size];
        _last=_first;
        _end=_first+_size;
    }
    ~Vector()
    {
        delete[]_first;
        _first=nullptr;
    }
    Vector(const Vector<T> &src)
    {
        int _size=src._last-src._first;
        _first=new T[_size];
        _end=_first+_size;
        _last=_first;
        for(T *p=src._first;p<src._last;++p)
        {
            *_last++=*p;
        }
    }
    Vector<T>& operator=(const Vector<T> &src)
    {
        if(this==&src)
            return *this;
        delete[]_first;
        int _size=src._last-src._first;
        _first=new T[_size];
        _end=_first+_size;
        _last=_first;
        for(T *p=src._first;p<src._last;++p)
        {
            *_last++=*p;
        }
        return *this;
    }
    Vector(Vector<T> &&src)
    {
        _first=src._first;
        _last=src._last;
        _end=src._end;
        src._first=nullptr;
    }
    Vector<T>& operator=(Vector<T> &&src)
    {
        delete[]_first;
        _first=src._first;
        _last=src._last;
        _end=src._end;
        src._first=nullptr;
        return *this;
    }
    void pushback(const T &val)
    {
        if(_full())
            expand();
        *_last++=val;
    }
    void pushback(T &&val)
    {
        if(_full())
            expand();
        *_last++=std::move(val);
    }
    void popback()
    {
        if(_empty())
            return ;
        --_last;
    }
    T _front()const {return *_first;}
    T _back()const {return *(_last-1);}
    bool _empty()const {return _first==_last;}
    bool _full()const {return _last==_end;}
private:
    T *_first;  //起始
    T *_last;   //最后一个元素的后继位置
    T *_end;    //内存的后继位置
    void expand()
    {
        if(_end==_first)
        {
            _first=new T[1];
            _last=_first;
            _end=_first+1;
        }
        else
        {
            int _size=_end-_first;
            T *temp=new T[2*_size];
            T *p1=_first;
            T *p2=temp;
            for(;p1<_end;++p1,++p2)
                *p2=std::move(*p1);		//资源转移
            delete[]_first;
            _first=temp;
            _last=p2;
            _end=_first+2*_size;
        }
    }
};

在定义一个对象之后

1
Vector<A> vec(2000000);

这时候会发现代码构造是开辟了2000000个内存空间，但是你不知道你到底使用多少

这时候我们会发现，在容器代码的编写上，是不是应该做到

1、把对象的内存开辟、对象构造分开 new

2、把对象的析构、内存释放分开 delete

因此，就需要一个空间配置器

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
template<typename T>
struct myallocator
{
	// allocate: 开辟内存
	T* allocate(size_t _size)
	{
		return (T*)malloc(_size);
	}

	// deallocate: 释放内存
	void deallocate(void *ptr)
	{
		free(ptr);
	}

	// 在指定的内存上构造对象的
	void construct(T *ptr, const T &val)
	{
		new (ptr) T(val); // 定位new
	}

	// 负责析构对象
	void destroyy(T *ptr)
	{
		ptr->~T(); // ~A()  ~Test()
	}
};

此时只需要将类里面的析构和构造函数开辟空间和释放内存的代码改动一下

代码总体如下

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
#include <iostream>
#include <vector>
using namespace std;
template<typename T>
struct myallocator
{
	// allocate: 开辟内存
	T* allocate(size_t _size)
	{
		return (T*)malloc(_size);
	}

	// deallocate: 释放内存
	void deallocate(void *ptr)
	{
		free(ptr);
	}

	// 在指定的内存上构造对象的
	void construct(T *ptr, const T &val)
	{
		new (ptr) T(val); // 定位new
	}

	// 负责析构对象
	void destroyy(T *ptr)
	{
		ptr->~T(); // ~A()  ~Test()
	}
};
template<typename T,typename _alloc=myallocator<T>>
class Vector
{
public:
    Vector(int _size)
        :_first(nullptr)
        ,_last(nullptr)
        ,_end(nullptr)
    {
        //_first=new T[_size];
        _first=_allocator.allocate(sizeof(T)*_size);
        _last=_first;
        _end=_first+_size;
    }
    ~Vector()
    {
        //delete[]_first;
        for(T *p=_first;p<_last;++p)
            _allocator.destroyy(p);
        _first=nullptr;
    }
    Vector(const Vector<T> &src)
    {
        int _size=src._last-src._first;
        _first=new T[_size];
        _end=_first+_size;
        _last=_first;
        for(T *p=src._first;p<src._last;++p)
        {
            *_last++=*p;
        }
    }
    Vector<T>& operator=(const Vector<T> &src)
    {
        if(this==&src)
            return *this;
        delete[]_first;
        int _size=src._last-src._first;
        _first=new T[_size];
        _end=_first+_size;
        _last=_first;
        for(T *p=src._first;p<src._last;++p)
        {
            *_last++=*p;
        }
        return *this;
    }
    Vector(Vector<T> &&src)
    {
        _first=src._first;
        _last=src._last;
        _end=src._end;
        src._first=nullptr;
    }
    Vector<T>& operator=(Vector<T> &&src)
    {
        delete[]_first;
        _first=src._first;
        _last=src._last;
        _end=src._end;
        src._first=nullptr;
        return *this;
    }
    void pushback(const T &val)
    {
        if(_full())
            expand();
        *_last++=val;
    }
    void pushback(T &&val)
    {
        if(_full())
            expand();
        *_last++=std::move(val);
    }
    void popback()
    {
        if(_empty())
            return ;
        --_last;
    }
    T _front()const {return *_first;}
    T _back()const {return *(_last-1);}
    bool _empty()const {return _first==_last;}
    bool _full()const {return _last==_end;}
private:
    T *_first;  //起始
    T *_last;   //最后一个元素的后继位置
    T *_end;    //内存的后继位置
    _alloc _allocator;//容器的空间配置器对象
    void expand()
    {
        if(_end==_first)
        {
            _first=new T[1];
            _last=_first;
            _end=_first+1;
        }
        else
        {
            int _size=_end-_first;
            T *temp=new T[2*_size];
            T *p1=_first;
            T *p2=temp;
            for(;p1<_end;++p1,++p2)
                *p2=std::move(*p1);		//资源转移
            delete[]_first;
            _first=temp;
            _last=p2;
            _end=_first+2*_size;
        }
    }
};
class A
{
public:
	A()
	{
		_ptr = new int[1000];
		cout << "A()" << endl;
	}
	A(const A &src)
	{
		_ptr = new int[1000];
		cout << "A(const A &)" << endl;
	}
	A& operator=(const A &src)
	{
		delete[]_ptr;
		_ptr = new int[1000];
		cout << "operator=" << endl;
		return *this;
	}
	~A()
	{
		cout << "~A()" << endl;
		delete[]_ptr;
		_ptr = nullptr;
	}
private:
	int *_ptr;
};
int main()
{
    A a1,a2,a3;
    Vector<A>vec(20000);

    vec.pushback(a1);
    vec.pushback(a2);
    vec.pushback(a3);

    vec.popback();
    return 0;
}

运行结果如下

1
2
3
4
5
6
7
8
9
10
11
A()
A()
A()
operator=
operator=
operator=
~A()
~A()
~A()
~A()
~A()

从这里可以看出176行定义vec(20000)这句话并没有直接把所有的空间开辟出来，而是等使用时才开辟空间

如有错误，请多包涵