SHOW:
|
|
- or go back to the newest paste.
1 | #ifndef MYTEMPLATE_VECTOR | |
2 | #define MYTEMPLATE_VECTOR | |
3 | ||
4 | #include <stdexcept> | |
5 | #include <cstdlib> | |
6 | ||
7 | namespace mytemplate | |
8 | { | |
9 | template <class T> | |
10 | class vector | |
11 | { | |
12 | private: | |
13 | T* array; | |
14 | size_t m_size; | |
15 | size_t m_capacity; | |
16 | ||
17 | // oblicza następną potęgę 2 nie mniejszą niż 'number'(może być równa) | |
18 | size_t nextGreatestPower( size_t number ) | |
19 | { | |
20 | size_t next_power = number-1; | |
21 | next_power |= next_power >> 1; | |
22 | next_power |= next_power >> 2; | |
23 | next_power |= next_power >> 4; | |
24 | next_power |= next_power >> 8; | |
25 | next_power |= next_power >> 16; | |
26 | ++next_power; | |
27 | ||
28 | return next_power; | |
29 | } | |
30 | ||
31 | void copyArray( T* dst, const T* src, size_t n ) | |
32 | { | |
33 | for( size_t i = 0; i < n; ++i ) | |
34 | dst[i] = src[i]; | |
35 | } | |
36 | ||
37 | public: | |
38 | vector() : array(nullptr), m_size(0), m_capacity(0) {} | |
39 | vector( const vector<T>& vec ) | |
40 | { | |
41 | array = nullptr; | |
42 | *this = vec; | |
43 | } | |
44 | ||
45 | vector( size_t n, const T& val = T() ) | |
46 | { | |
47 | - | array = new T[m_capacity]; |
47 | + | |
48 | m_size = n; | |
49 | - | array[i] = val; |
49 | + | array = static_cast<T*>( malloc( m_capacity * sizeof( T ) ) ); |
50 | for( size_t i = 0; i < n; ++i ) | |
51 | new (&array[i]) T(val); | |
52 | } | |
53 | - | if( array != nullptr ) |
53 | + | |
54 | - | delete []array; |
54 | + | |
55 | clear(); | |
56 | free(array); | |
57 | } | |
58 | - | if( m_capacity == 0 ) |
58 | + | |
59 | { | |
60 | - | array = new T[2]; |
60 | + | if( m_capacity == 0 || m_size >= m_capacity ) |
61 | - | m_capacity = 2; |
61 | + | reserve( m_capacity + 2 ); |
62 | array[m_size] = value; | |
63 | - | else if( m_size >= m_capacity ) |
63 | + | |
64 | - | reserve( nextGreatestPower( m_capacity + 1 ) ); |
64 | + | |
65 | ||
66 | void pop_back() | |
67 | { | |
68 | --m_size; | |
69 | array[m_size].~T(); | |
70 | new (&array[m_size]) T(); | |
71 | } | |
72 | ||
73 | void insert( size_t position, const T& value ) | |
74 | { | |
75 | if( (m_size == 0 && position == 0) || position == m_size ) | |
76 | - | if( m_size == 0 && position == 0 ) |
76 | + | |
77 | push_back( value ); | |
78 | return; | |
79 | } | |
80 | else if( position > m_size ) | |
81 | - | else if( position == m_size && m_size == m_capacity ) |
81 | + | |
82 | ||
83 | - | reserve( nextGreatestPower( m_capacity + 1 ) ); |
83 | + | |
84 | { | |
85 | - | else if( position >= m_size ) |
85 | + | |
86 | { | |
87 | array[i] = value; | |
88 | break; | |
89 | } | |
90 | else | |
91 | array[i] = array[i-1]; | |
92 | } | |
93 | ++m_size; | |
94 | } | |
95 | ||
96 | void erase( size_t position ) | |
97 | { | |
98 | if( position >= m_size ) | |
99 | throw std::out_of_range( "Vector Subscript Out of Range" ); | |
100 | ||
101 | array[position].~T(); | |
102 | new (&array[position]) T(); | |
103 | for( size_t i = position; i < m_size - 1; ++i ) | |
104 | array[i] = array[i+1]; | |
105 | ||
106 | --m_size; | |
107 | } | |
108 | ||
109 | size_t size() const | |
110 | { | |
111 | return m_size; | |
112 | } | |
113 | ||
114 | size_t capacity() const | |
115 | { | |
116 | return m_capacity; | |
117 | } | |
118 | ||
119 | void clear() | |
120 | { | |
121 | for( size_t i = 0; i < m_size; ++i ) | |
122 | { | |
123 | array[i].~T(); | |
124 | new (&array[i]) T(); | |
125 | } | |
126 | ||
127 | - | array = new T[ m_capacity ]; |
127 | + | m_size = 0; |
128 | } | |
129 | - | if( tmp != nullptr ) |
129 | + | |
130 | - | delete tmp; |
130 | + | |
131 | { | |
132 | if( n <= m_capacity ) | |
133 | return; | |
134 | m_capacity = nextGreatestPower( n ); | |
135 | T* tmp = array; | |
136 | array = static_cast<T*>( malloc( m_capacity * sizeof(T) ) ); | |
137 | if( array == nullptr ) | |
138 | throw std::bad_alloc(); | |
139 | for( size_t i = 0; i < m_capacity; ++i ) | |
140 | new (&array[i]) T(); | |
141 | copyArray( array, tmp, m_size ); | |
142 | free(tmp); | |
143 | } | |
144 | ||
145 | T& operator[]( size_t index ) | |
146 | - | array = new T[ vec.capacity() ]; |
146 | + | |
147 | if( index >= m_size ) | |
148 | throw std::out_of_range( "Vector Subscript Out of Range" ); | |
149 | return array[index]; | |
150 | } | |
151 | const T& operator[]( size_t index ) const | |
152 | { | |
153 | if( index >= m_size ) | |
154 | throw std::out_of_range( "Vector Subscript Out of Range" ); | |
155 | return array[index]; | |
156 | } | |
157 | ||
158 | vector<T>& operator=( const vector<T> &vec ) | |
159 | { | |
160 | if( this == &vec ) | |
161 | return *this; | |
162 | m_size = vec.size(); | |
163 | m_capacity = vec.capacity(); | |
164 | T* tmp = array; | |
165 | if( vec.capacity() != 0 ) | |
166 | { | |
167 | array = static_cast<T*>( mallock( m_capacity * sizeof(T) ) ); | |
168 | for( size_t i = 0; i < m_capacity; ++i ) | |
169 | new (&array[i]) T(); | |
170 | copyArray( array, vec.array, m_size ); | |
171 | } | |
172 | else | |
173 | array = nullptr; | |
174 | free(tmp); | |
175 | return *this; // umożliwia łańcuchowe przypisywanie np: vec1 = vec2 = vec3 = vec4; | |
176 | } | |
177 | }; | |
178 | } | |
179 | ||
180 | #endif |