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
| template <class T, class Alloc = alloc> class vector { public: typedef T value_type; // (1) typedef value_type* pointer; // (2) typedef const value_type* const_pointer; typedef const value_type* const_iterator; typedef value_type reference; // (3) typedef const value_type const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; // (4) typedef value_type* iterator;
protected: typedef simple_alloc<value_type, Alloc> data_allocator;
iterator start; iterator finish; iterator end_of_storage;
void insert_aux(iterator position, const T x); void deallocate() { if (start) data_allocator::deallocate(start, end_of_storage - start); }
void fill_initialize(size_type n, const T value) { start = allocate_and_fill(n, value); // 配置空間並設初值 finish = start + n; // 調整水位 end_of_storage = finish; // 調整水位 }
public: iterator begin() { return start; } const_iterator begin() const { return start; } iterator end() { return finish; } const_iterator end() const { return finish; } reverse_iterator rbegin() { return reverse_iterator(end()); } const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } size_type size() const { return size_type(end() - begin()); } size_type max_size() const { return size_type(-1) / sizeof(T); } size_type capacity() const { return size_type(end_of_storage - begin()); } bool empty() const { return begin() == end(); } reference operator[](size_type n) { return *(begin() + n); } const_reference operator[](size_type n) const { return *(begin() + n); }
vector() : start(0), finish(0), end_of_storage(0) {} vector(size_type n, const T value) { fill_initialize(n, value); } vector(int n, const T value) { fill_initialize(n, value); } vector(long n, const T value) { fill_initialize(n, value); } explicit vector(size_type n) { fill_initialize(n, T()); }
vector(const vector<T, Alloc> x) { start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end()); finish = start + (x.end() - x.begin()); end_of_storage = finish; }
vector(const_iterator first, const_iterator last) { size_type n = 0; distance(first, last, n); start = allocate_and_copy(n, first, last); finish = start + n; end_of_storage = finish; }
~vector() { destroy(start, finish); // 全域函式,建構/解構基本工具。 deallocate(); // 先前定義好的成員函式 } vector<T, Alloc> operator=(const vector<T, Alloc> x); void reserve(size_type n) { if (capacity() < n) { const size_type old_size = size(); iterator tmp = allocate_and_copy(n, start, finish); destroy(start, finish); deallocate(); start = tmp; finish = tmp + old_size; end_of_storage = start + n; } }
reference front() { return *begin(); } const_reference front() const { return *begin(); } reference back() { return *(end() - 1); } const_reference back() const { return *(end() - 1); } void push_back(const T x) { if (finish != end_of_storage) { construct(finish, x); // 直接在備用空間中建構元素。 ++finish; // 調整水位高度 } else insert_aux(end(), x); }
void pop_back() { --finish; destroy(finish); // 全域函式,建構/解構基本工具。 } iterator erase(iterator position) { if (position + 1 != end()) // 如果 p 不是指向最後一個元素 copy(position + 1, finish, position);
--finish; // 調整水位 destroy(finish); // 全域函式,建構/解構基本工具。 return position; } iterator erase(iterator first, iterator last) { iterator i = copy(last, finish, first); destroy(i, finish); // 全域函式,建構/解構基本工具。 finish = finish - (last - first); return first; } void resize(size_type new_size, const T x) { if (new_size < size()) erase(begin() + new_size, end()); else insert(end(), new_size - size(), x); } void resize(size_type new_size) { resize(new_size, T()); } void clear() { erase(begin(), end()); }
protected: iterator allocate_and_fill(size_type n, const T x) { iterator result = data_allocator::allocate(n); // 配置n個元素空間 uninitialized_fill_n(result, n, x); return result; } }
|