]> git.saurik.com Git - wxWidgets.git/blob - include/wx/vector.h
check for self assignment in operator=
[wxWidgets.git] / include / wx / vector.h
1 ///////////////////////////////////////////////////////////////////////////////
2 // Name: wx/vector.h
3 // Purpose: STL vector clone
4 // Author: Lindsay Mathieson
5 // Modified by: Vaclav Slavik - make it a template
6 // Created: 30.07.2001
7 // Copyright: (c) 2001 Lindsay Mathieson <lindsay@mathieson.org>,
8 // 2007 Vaclav Slavik <vslavik@fastmail.fm>
9 // Licence: wxWindows licence
10 ///////////////////////////////////////////////////////////////////////////////
11
12 #ifndef _WX_VECTOR_H_
13 #define _WX_VECTOR_H_
14
15 #include "wx/defs.h"
16
17 #if wxUSE_STL
18
19 #include <vector>
20 #define wxVector std::vector
21
22 #else // !wxUSE_STL
23
24 #include "wx/utils.h"
25 #include "wx/scopeguard.h"
26 #include "wx/meta/movable.h"
27 #include "wx/meta/if.h"
28
29 #include "wx/beforestd.h"
30 #include <new> // for placement new
31 #include "wx/afterstd.h"
32
33 namespace wxPrivate
34 {
35
36 // These templates encapsulate memory operations for use by wxVector; there are
37 // two implementations, both in generic way for any C++ types and as an
38 // optimized version for "movable" types that uses realloc() and memmove().
39
40 // version for movable types:
41 template<typename T>
42 struct wxVectorMemOpsMovable
43 {
44 static void Free(T* array)
45 { free(array); }
46
47 static T* Realloc(T* old, size_t newCapacity, size_t WXUNUSED(occupiedSize))
48 { return (T*)realloc(old, newCapacity * sizeof(T)); }
49
50 static void MemmoveBackward(T* dest, T* source, size_t count)
51 { memmove(dest, source, count * sizeof(T)); }
52
53 static void MemmoveForward(T* dest, T* source, size_t count)
54 { memmove(dest, source, count * sizeof(T)); }
55 };
56
57 // generic version for non-movable types:
58 template<typename T>
59 struct wxVectorMemOpsGeneric
60 {
61 static void Free(T* array)
62 { ::operator delete(array); }
63
64 static T* Realloc(T* old, size_t newCapacity, size_t occupiedSize)
65 {
66 T *mem = (T*)::operator new(newCapacity * sizeof(T));
67 for ( size_t i = 0; i < occupiedSize; i++ )
68 {
69 ::new(mem + i) T(old[i]);
70 old[i].~T();
71 }
72 ::operator delete(old);
73 return mem;
74 }
75
76 static void MemmoveBackward(T* dest, T* source, size_t count)
77 {
78 wxASSERT( dest < source );
79 T* destptr = dest;
80 T* sourceptr = source;
81 for ( size_t i = count; i > 0; --i, ++destptr, ++sourceptr )
82 {
83 ::new(destptr) T(*sourceptr);
84 sourceptr->~T();
85 }
86 }
87
88 static void MemmoveForward(T* dest, T* source, size_t count)
89 {
90 wxASSERT( dest > source );
91 T* destptr = dest + count - 1;
92 T* sourceptr = source + count - 1;
93 for ( size_t i = count; i > 0; --i, --destptr, --sourceptr )
94 {
95 ::new(destptr) T(*sourceptr);
96 sourceptr->~T();
97 }
98 }
99 };
100
101
102 } // namespace wxPrivate
103
104 template<typename T>
105 class wxVector
106 {
107 private:
108 // This cryptic expression means "typedef Ops to wxVectorMemOpsMovable if
109 // type T is movable type, otherwise to wxVectorMemOpsGeneric".
110 //
111 // Note that we use typedef instead of privately deriving from this (which
112 // would allowed us to omit "Ops::" prefixes below) to keep VC6 happy,
113 // it can't compile code that derives from wxIf<...>::value.
114 typedef typename wxIf< wxIsMovable<T>::value,
115 wxPrivate::wxVectorMemOpsMovable<T>,
116 wxPrivate::wxVectorMemOpsGeneric<T> >::value
117 Ops;
118
119 public:
120 typedef size_t size_type;
121 typedef size_t difference_type;
122 typedef T value_type;
123 typedef value_type* pointer;
124 typedef value_type* iterator;
125 typedef const value_type* const_iterator;
126 typedef value_type& reference;
127
128 class reverse_iterator
129 {
130 public:
131 reverse_iterator() : m_ptr(NULL) { }
132 wxEXPLICIT reverse_iterator(iterator it) : m_ptr(it) { }
133 reverse_iterator(const reverse_iterator& it) : m_ptr(it.m_ptr) { }
134
135 reference operator*() const { return *m_ptr; }
136 pointer operator->() const { return m_ptr; }
137
138 iterator base() const { return m_ptr; }
139
140 reverse_iterator& operator++()
141 { --m_ptr; return *this; }
142 reverse_iterator operator++(int)
143 { reverse_iterator tmp = *this; --m_ptr; return tmp; }
144 reverse_iterator& operator--()
145 { ++m_ptr; return *this; }
146 reverse_iterator operator--(int)
147 { reverse_iterator tmp = *this; ++m_ptr; return tmp; }
148
149 reverse_iterator operator+(difference_type n) const
150 { return reverse_iterator(m_ptr - n); }
151 reverse_iterator& operator+=(difference_type n)
152 { m_ptr -= n; return *this; }
153 reverse_iterator operator-(difference_type n) const
154 { return reverse_iterator(m_ptr + n); }
155 reverse_iterator& operator-=(difference_type n)
156 { m_ptr += n; return *this; }
157
158 reference operator[](difference_type n) const
159 { return *(*this + n); }
160
161 bool operator ==(const reverse_iterator& it) const
162 { return m_ptr == it.m_ptr; }
163 bool operator !=(const reverse_iterator& it) const
164 { return m_ptr != it.m_ptr; }
165
166 private:
167 value_type *m_ptr;
168 };
169
170 wxVector() : m_size(0), m_capacity(0), m_values(NULL) {}
171
172 wxVector(const wxVector& c) : m_size(0), m_capacity(0), m_values(NULL)
173 {
174 Copy(c);
175 }
176
177 ~wxVector()
178 {
179 clear();
180 }
181
182 void clear()
183 {
184 // call destructors of stored objects:
185 for ( size_type i = 0; i < m_size; i++ )
186 {
187 m_values[i].~T();
188 }
189
190 Ops::Free(m_values);
191 m_values = NULL;
192 m_size =
193 m_capacity = 0;
194 }
195
196 void reserve(size_type n)
197 {
198 if ( n <= m_capacity )
199 return;
200
201 // increase the size twice, unless we're already too big or unless
202 // more is requested
203 //
204 // NB: casts to size_type are needed to suppress mingw32 warnings about
205 // mixing enums and ints in the same expression
206 const size_type increment = m_size > 0
207 ? wxMin(m_size, (size_type)ALLOC_MAX_SIZE)
208 : (size_type)ALLOC_INITIAL_SIZE;
209 if ( m_capacity + increment > n )
210 n = m_capacity + increment;
211
212 m_values = Ops::Realloc(m_values, n * sizeof(value_type), m_size);
213 m_capacity = n;
214 }
215
216 size_type size() const
217 {
218 return m_size;
219 }
220
221 size_type capacity() const
222 {
223 return m_capacity;
224 }
225
226 bool empty() const
227 {
228 return size() == 0;
229 }
230
231 wxVector& operator=(const wxVector& vb)
232 {
233 if (this != &vb)
234 {
235 clear();
236 Copy(vb);
237 }
238 return *this;
239 }
240
241 void push_back(const value_type& v)
242 {
243 reserve(size() + 1);
244
245 // use placement new to initialize new object in preallocated place in
246 // m_values and store 'v' in it:
247 void* const place = m_values + m_size;
248 ::new(place) value_type(v);
249
250 // only increase m_size if the ctor didn't throw an exception; notice
251 // that if it _did_ throw, everything is OK, because we only increased
252 // vector's capacity so far and possibly written some data to
253 // uninitialized memory at the end of m_values
254 m_size++;
255 }
256
257 void pop_back()
258 {
259 erase(end() - 1);
260 }
261
262 const value_type& at(size_type idx) const
263 {
264 wxASSERT(idx < m_size);
265 return m_values[idx];
266 }
267
268 value_type& at(size_type idx)
269 {
270 wxASSERT(idx < m_size);
271 return m_values[idx];
272 }
273
274 const value_type& operator[](size_type idx) const { return at(idx); }
275 value_type& operator[](size_type idx) { return at(idx); }
276 const value_type& front() const { return at(0); }
277 value_type& front() { return at(0); }
278 const value_type& back() const { return at(size() - 1); }
279 value_type& back() { return at(size() - 1); }
280
281 const_iterator begin() const { return m_values; }
282 iterator begin() { return m_values; }
283 const_iterator end() const { return m_values + size(); }
284 iterator end() { return m_values + size(); }
285
286 reverse_iterator rbegin() { return reverse_iterator(end() - 1); }
287 reverse_iterator rend() { return reverse_iterator(begin() - 1); }
288
289 iterator insert(iterator it, const value_type& v = value_type())
290 {
291 // NB: this must be done before reserve(), because reserve()
292 // invalidates iterators!
293 const size_t idx = it - begin();
294 const size_t after = end() - it;
295
296 reserve(size() + 1);
297
298 // the place where the new element is going to be inserted
299 value_type * const place = m_values + idx;
300
301 // unless we're inserting at the end, move following elements out of
302 // the way:
303 if ( after > 0 )
304 Ops::MemmoveForward(place + 1, place, after);
305
306 // if the ctor called below throws an exception, we need to move all
307 // the elements back to their original positions in m_values
308 wxScopeGuard moveBack = wxMakeGuard(
309 Ops::MemmoveBackward, place, place + 1, after);
310 if ( !after )
311 moveBack.Dismiss();
312
313 // use placement new to initialize new object in preallocated place in
314 // m_values and store 'v' in it:
315 ::new(place) value_type(v);
316
317 // now that we did successfully add the new element, increment the size
318 // and disable moving the items back
319 moveBack.Dismiss();
320 m_size++;
321
322 return begin() + idx;
323 }
324
325 iterator erase(iterator it)
326 {
327 return erase(it, it + 1);
328 }
329
330 iterator erase(iterator first, iterator last)
331 {
332 if ( first == last )
333 return first;
334 wxASSERT( first < end() && last <= end() );
335
336 const size_type idx = first - begin();
337 const size_type count = last - first;
338 const size_type after = end() - last;
339
340 // erase elements by calling their destructors:
341 for ( iterator i = first; i < last; ++i )
342 i->~T();
343
344 // once that's done, move following elements over to the freed space:
345 if ( after > 0 )
346 {
347 Ops::MemmoveBackward(m_values + idx, m_values + idx + count, after);
348 }
349
350 m_size -= count;
351
352 return begin() + idx;
353 }
354
355 #if WXWIN_COMPATIBILITY_2_8
356 wxDEPRECATED( size_type erase(size_type n) );
357 #endif // WXWIN_COMPATIBILITY_2_8
358
359 private:
360 // VC6 can't compile static const int members
361 enum { ALLOC_INITIAL_SIZE = 16 };
362 enum { ALLOC_MAX_SIZE = 4096 };
363
364 void Copy(const wxVector& vb)
365 {
366 reserve(vb.size());
367
368 for ( const_iterator i = vb.begin(); i != vb.end(); ++i )
369 push_back(*i);
370 }
371
372 private:
373 size_type m_size,
374 m_capacity;
375 value_type *m_values;
376 };
377
378 #if WXWIN_COMPATIBILITY_2_8
379 template<typename T>
380 inline typename wxVector<T>::size_type wxVector<T>::erase(size_type n)
381 {
382 erase(begin() + n);
383 return n;
384 }
385 #endif // WXWIN_COMPATIBILITY_2_8
386
387 #endif // wxUSE_STL/!wxUSE_STL
388
389 #if WXWIN_COMPATIBILITY_2_8
390 #define WX_DECLARE_VECTORBASE(obj, cls) typedef wxVector<obj> cls
391 #define _WX_DECLARE_VECTOR(obj, cls, exp) WX_DECLARE_VECTORBASE(obj, cls)
392 #define WX_DECLARE_VECTOR(obj, cls) WX_DECLARE_VECTORBASE(obj, cls)
393 #endif // WXWIN_COMPATIBILITY_2_8
394
395 #endif // _WX_VECTOR_H_