33 template<
typename T,
typename Size =
size_t>
39 static T* allocate(Size n) {
40 return std::allocator<T>().allocate(n);
43 static void deallocate(T* p, Size n) {
44 std::allocator<T>().deallocate(p, n);
47 void ensureCapacity(Size capacity) {
48 if (capacity_ < capacity) {
50 reserve(capacity * 2);
54 void moveElement(T& from, T& to) {
62 : capacity_(0), size_(0), array_(0) {
66 : capacity_(0), size_(0), array_(0) {
70 MyVector(Size n, T
const& val)
71 : capacity_(0), size_(0), array_(0) {
73 for (Size i = 0; i < n; ++i) {
89 MyVector(MyVector
const& o)
90 : capacity_(o.size_), size_(o.size_),
91 array_(capacity_ ? allocate(capacity_) : 0) {
92 for (Size i = 0; i < size_; ++i) {
93 new (array_ + i) T(o[i]);
97 MyVector& operator=(MyVector
const& o) {
101 for (Size i = 0; i < size_; ++i) {
102 new (array_ + i) T(o[i]);
108 MyVector(std::vector<U>
const& o)
109 : capacity_(o.size()), size_(o.size()), array_(allocate(capacity_)) {
110 for (Size i = 0; i < size_; ++i) {
111 new (array_ + i) T(o[i]);
116 MyVector& operator=(std::vector<U>
const& o) {
120 for (Size i = 0; i < size_; ++i) {
121 new (array_ + i) T(o[i]);
160 void swap(MyVector& o) {
161 std::swap(capacity_, o.capacity_);
162 std::swap(size_, o.size_);
163 std::swap(array_, o.array_);
174 Size capacity()
const {
199 void reserve(Size capacity) {
200 if (capacity_ < capacity) {
201 T* tmp = allocate(capacity);
203 assert(0 <= size_ && size_ <= capacity_);
204 for (Size i = 0; i < size_; ++i) {
205 moveElement(array_[i], tmp[i]);
207 deallocate(array_, capacity_);
210 capacity_ = capacity;
220 array_[--size_].~T();
230 void resize(Size n) {
235 else if (capacity_ * 10 <= n * 11 && n <= capacity_) {
237 array_[--size_].~T();
241 new (array_ + size_++) T();
246 array_[--size_].~T();
250 T* tmp = allocate(n);
251 for (Size i = 0; i < size_; ++i) {
252 moveElement(array_[i], tmp[i]);
256 new (tmp + size_++) T();
259 deallocate(array_, capacity_);
271 T* erase(T* first, T* last) {
272 assert(array_ <= first && first <= last && last <= array_ + size_);
273 Size newSize = size_ - (last - first);
275 for (Size i = first - array_; i < newSize; ++i) {
279 while (newSize < size_) {
280 array_[--size_].~T();
292 assert(capacity_ > 0);
294 array_[--size_].~T();
296 deallocate(array_, capacity_);
308 void push_back(T
const& val) {
309 ensureCapacity(size_ + 1);
310 new (array_ + size_) T(val);
318 if (size_ > 0) array_[--size_].~T();
340 return array_[size_ - 1];
347 T
const& back()
const {
349 return array_[size_ - 1];
357 T& operator[](Size i) {
367 T
const& operator[](Size i)
const {
381 typedef T
const* const_iterator;
395 const_iterator begin()
const {
404 return array_ + size_;
411 const_iterator end()
const {
412 return array_ + size_;
416 class reverse_iterator_ {
420 reverse_iterator_(U* ptr)
424 U& operator*()
const {
428 U* operator->()
const {
432 reverse_iterator_& operator++() {
437 bool operator==(reverse_iterator_
const& o)
const {
441 bool operator!=(reverse_iterator_
const& o)
const {
446 typedef reverse_iterator_<T> reverse_iterator;
447 typedef reverse_iterator_<T const> const_reverse_iterator;
453 reverse_iterator rbegin() {
454 return reverse_iterator(array_ + size_ - 1);
461 const_reverse_iterator rbegin()
const {
462 return const_reverse_iterator(array_ + size_ - 1);
469 reverse_iterator rend() {
470 return reverse_iterator(array_ - 1);
477 const_reverse_iterator rend()
const {
478 return const_reverse_iterator(array_ - 1);
485 iterator erase(iterator pos) {
486 assert(begin() <= pos && pos < end());
487 std::memmove(pos, pos + 1, end() - pos - 1);
495 size_t hash()
const {
497 for (Size i = 0; i < size_; ++i) {
498 h = h * 31 + array_[i].hash();
508 bool operator==(MyVector
const& o)
const {
509 if (size_ != o.size_)
return false;
510 for (Size i = 0; i < size_; ++i) {
511 if (!(array_[i] == o.array_[i]))
return false;
522 friend std::ostream& operator<<(std::ostream& os, MyVector
const& o) {
525 for (T
const* t = o.begin(); t != o.end(); ++t) {