STL造轮子-Vector

  1. C++标准库「memory」,用它的Allocator类来作配置器
  2. allocate(std::size_t n, const void * hint)
  3. std :: uninitialized_fill( ForwardIt first, ForwardIt last, const T& value)
  4. uninitialized_copy(InputIt first, InputIt last, ForwardIt d_first );
  5. copy_backward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last )
  6. void construct (U* p, Args&&… args);
  7. 定义vector的嵌套类型
  8. 定义迭代器(指针)
  9. vector类的构造函数
  10. vector容器的操作

准备工作:

C++标准库「memory」,用它的Allocator类来作配置器

allocate(std::size_t n, const void * hint)

参数:

size_t n - 为其分配存储空间的对象数量

const void* hint - 指向附近内存位置的指针

返回指向适当对齐的内存块的第一个字节的指针,并且足以容纳一个n类型的对象数组T

std :: uninitialized_fill( ForwardIt first, ForwardIt last, const T& value)

参数:

ForwardIt first,ForwardIt last - 要初始化的元素的范围
const T& value - 用来构造元素的值

uninitialized_copy(InputIt first, InputIt last, ForwardIt d_first );

参数:

irst, last -    要复制的元素范围
d_first -    目标范围的起始

copy_backward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last )

参数:

first, last    -    要复制的元素范围
d_last    -    目标范围的结尾。

返回指向最后复制元素的迭代器

void construct (U* p, Args&&… args);

参数:

p - 指向具有足够存储空间以包含U类型元素的位置的指针。
ARGS - 转发给构造函数的参数。参数是零个或多个类型的列表。

定义vector的嵌套类型

1
2
3
4
5
6
7
typedef T                       value_type;
typedef value_type* iterator;
typedef const value_type* const_iterator;
typedef value_type& reference;
typedef value_type* pointer;
typedef size_t size_type;
typedef ptrdiff_t difference_type; //ptrdiff_t通常用来保存两个指针减法的结果,这里用来定义两个迭代器的距离

定义迭代器(指针)

1
2
3
iterator _start;                   
iterator _end;
iterator _end_of_storage; //当前可用空间的尾

vector类的构造函数

1
2
3
4
5
6
Vector() :_begin(0), _end(0), _end_of_storage(0){}
Vector(size_type n, const T& value);
Vector(size_type n);
Vector(iterator first, iterator last);
Vector(const myVector& v);
Vector& operator=(const myVector& rhs);

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
iterator begin() { return _begin; }
iterator end() { return _end; }
const_iterator cbegin() const { return _start; }
const_iterator cend() const { return _end; }

size_type size() { return size_type(end() - begin()); }
size_type capacity() { return size_type(_end_of_storage - begin()); }
bool empty() { return begin() == end(); }
void swap(myVector &other);


reference front() { return *begin(); }
reference back() { return *(end() - 1); }
reference operator[] (size_type n) { return *(begin() + n); }
reference at(size_type index) { return *(index() + index); }


void insert_aux(iterator positon, const T& x);
void push_back(const T& value);
void pop_back();
void insert(iterator position, size_type n, const T& x);

iterator erase(iterator position);
iterator erase(iterator first, iterator last);
void clear() { erase(begin(), end()); }

完整代码:

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
#ifndef Vector_H
#define Vector_H
#include <iostream>
#include <memory>
#include <algorithm>

template <class T, class Allocator = std::allocator<T>> class Vector {
public:
typedef T value_type;
typedef value_type* iterator;
typedef const value_type* const_iterator;
typedef value_type& reference;
typedef value_type* pointer;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
protected:
std::allocator<value_type> _alloc;
iterator _begin;
iterator _end;
iterator _end_of_storage;
public:
Vector(): _begin(0),_end(0),_end_of_storage(0){};
Vector(size_type n,const T& value);
Vector(size_type n);
Vector(iterator first,iterator last);
Vector(const Vector& v);
Vector& operator=(const Vector& ass);
~Vector(){_destroy();}

iterator begin() {return _begin;}
iterator end() {return _end;}
const_iterator kbegin() {return _begin;}
const_iterator kend() {return _end;}

size_type size() {return size_type(end() - begin());};
size_type capacity() {return size_type(_end_of_storage - begin());}
bool empty() {return begin() == end();}
void swap(Vector &other_element);

reference front() {return *begin();}
reference back() {return *(end() - 1);}
reference operator[](size_type index) {return *(begin() + index);}
reference at(size_type index) {return *(begin() + index);}

void insert_auxiliary(iterator position, const T& x);
void push_back(const T& value);
void pop_back();
void insert(iterator position,size_type n,const T& x);

iterator erase(iterator position);
iterator erase(iterator first,iterator last);
void clear() {erase(begin(),end());}

void _destroy();
};



Vector<T,Allocator>::Vector(size_type n,const T& value) {
_begin = _alloc.allocate(n);
std::uninitialized_fill(_begin, _begin + n, value);
_end = _end_of_storage = _begin + n;
}


Vector<T,Allocator>::Vector(size_type n) {
_begin = _alloc.allocate(n);
std::uninitialized_fill(_begin, _begin + n, 0);
_end = _end_of_storage = _begin + n;
}



void Vector<T,Allocator>::swap(Vector &other_element) {
std::swap(_begin, other_element.begin());
std::swap(_end, other_element.end());
std::swap(_end_of_storage, other_element._end_of_storage);
}


Vector<T,Allocator> &Vector<T,Allocator>::operator=(const Vector& ass) {
if (this == &ass) {
return *this;
}
size_type n = ass.kend() - ass.kbegin();
_begin = _alloc.allocate(n);
_end = _end_of_storage = std::uninitialized_copy(ass.kbegin(), ass.kend(), _begin);
}


void Vector<T,Allocator>::insert(iterator position,
size_type n,const T& x) {
if (n >= 0) {
if (_end_of_storage - _end >= n) {
T x_copy = x;
const size_type element_after = _end - position;
iterator old_end = _end;
if (element_after > n) {
uninitialized_copy(_end - n,old_end - n,_end);
_end = _end + n;
copy_backward(position,old_end - n,old_end);
fill(position,position + n,x_copy);
} else {
uninitialized_fill_n(_end,n - element_after,x_copy);
_end += n - element_after;
uninitialized_copy(position,old_end,_end);
_end += element_after;
fill(position,old_end,x_copy);
}
}
} else {
const size_type old_size = size();
const size_type length = old_size + std::max(old_size,n);
iterator new_begin = _alloc.allocate(length);
iterator new_end = new_begin;
new_end = uninitialized_copy(_begin,position,new_begin);
new_end = uninitialized_fill_n(position,_end,new_end);
_destroy();
_begin = new_begin;
_end = new_end;
_end_of_storage = new_begin + length;
}
}


void Vector<T,Allocator>::insert_auxiliary(iterator position, const T& x) {
if (_end != _end_of_storage) {
//pass
} else {
const size_type old_size = size();
const size_type length = old_size ? 2 * old_size : 1;
iterator new_begin = _alloc.allocate(length);
iterator new_end = new_begin;
new_end = uninitialized_copy(_begin,position,new_begin);
_alloc.construct(new_end, x);
++new_end;
new_end = uninitialized_copy(position,_end,new_end);

_destroy();

_begin = new_begin;
_end = new_end;
_end_of_storage = new_begin + length;

}
}


void Vector<T,Allocator>::push_back(const T& value) {
if (_end != _end_of_storage) {
_alloc.construct(_end, value);
++_end;
} else {
insert_auxiliary(end(), value);
}
}


typename Vector<T,Allocator>::iterator
Vector<T,Allocator>::erase(iterator first,iterator last) {
difference_type left = _end - last;
std::copy(last, _end, first);
iterator now(first + left);
while (_end != now) {
_alloc.destroy(--_end);
}
return first;
}


void Vector<T,Allocator>::_destroy() {
if (_begin) {
iterator it(_end);
while (it != _begin) {
_alloc.destroy(--it);
}
}
_alloc.deallocate(_begin, _end_of_storage - _begin);
_begin = _end_of_storage = _end = NULL;
}

#endif
script>