]> git.saurik.com Git - wxWidgets.git/blob - include/wx/vector.h
Make wxChoice and wxComboBox behaviour same as in native controls in wxMSW.
[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_STD_CONTAINERS
18
19 #include <vector>
20 #include <algorithm>
21
22 #define wxVector std::vector
23 template<typename T>
24 inline void wxVectorSort(wxVector<T>& v)
25 {
26 std::sort(v.begin(), v.end());
27 }
28
29 #else // !wxUSE_STD_CONTAINERS
30
31 #include "wx/scopeguard.h"
32 #include "wx/meta/movable.h"
33 #include "wx/meta/if.h"
34
35 #include "wx/beforestd.h"
36 #include <new> // for placement new
37 #include "wx/afterstd.h"
38
39 // wxQsort is declared in wx/utils.h, but can't include that file here,
40 // it indirectly includes this file. Just lovely...
41 typedef int (*wxSortCallback)(const void* pItem1,
42 const void* pItem2,
43 const void* user_data);
44 WXDLLIMPEXP_BASE void wxQsort(void* pbase, size_t total_elems,
45 size_t size, wxSortCallback cmp,
46 const void* user_data);
47
48 namespace wxPrivate
49 {
50
51 // These templates encapsulate memory operations for use by wxVector; there are
52 // two implementations, both in generic way for any C++ types and as an
53 // optimized version for "movable" types that uses realloc() and memmove().
54
55 // version for movable types:
56 template<typename T>
57 struct wxVectorMemOpsMovable
58 {
59 static void Free(T* array)
60 { free(array); }
61
62 static T* Realloc(T* old, size_t newCapacity, size_t WXUNUSED(occupiedSize))
63 { return (T*)realloc(old, newCapacity * sizeof(T)); }
64
65 static void MemmoveBackward(T* dest, T* source, size_t count)
66 { memmove(dest, source, count * sizeof(T)); }
67
68 static void MemmoveForward(T* dest, T* source, size_t count)
69 { memmove(dest, source, count * sizeof(T)); }
70 };
71
72 // generic version for non-movable types:
73 template<typename T>
74 struct wxVectorMemOpsGeneric
75 {
76 static void Free(T* array)
77 { ::operator delete(array); }
78
79 static T* Realloc(T* old, size_t newCapacity, size_t occupiedSize)
80 {
81 T *mem = (T*)::operator new(newCapacity * sizeof(T));
82 for ( size_t i = 0; i < occupiedSize; i++ )
83 {
84 ::new(mem + i) T(old[i]);
85 old[i].~T();
86 }
87 ::operator delete(old);
88 return mem;
89 }
90
91 static void MemmoveBackward(T* dest, T* source, size_t count)
92 {
93 wxASSERT( dest < source );
94 T* destptr = dest;
95 T* sourceptr = source;
96 for ( size_t i = count; i > 0; --i, ++destptr, ++sourceptr )
97 {
98 ::new(destptr) T(*sourceptr);
99 sourceptr->~T();
100 }
101 }
102
103 static void MemmoveForward(T* dest, T* source, size_t count)
104 {
105 wxASSERT( dest > source );
106 T* destptr = dest + count - 1;
107 T* sourceptr = source + count - 1;
108 for ( size_t i = count; i > 0; --i, --destptr, --sourceptr )
109 {
110 ::new(destptr) T(*sourceptr);
111 sourceptr->~T();
112 }
113 }
114 };
115
116
117 } // namespace wxPrivate
118
119 template<typename T>
120 class wxVector
121 {
122 private:
123 // This cryptic expression means "typedef Ops to wxVectorMemOpsMovable if
124 // type T is movable type, otherwise to wxVectorMemOpsGeneric".
125 //
126 // Note that we use typedef instead of privately deriving from this (which
127 // would allowed us to omit "Ops::" prefixes below) to keep VC6 happy,
128 // it can't compile code that derives from wxIf<...>::value.
129 //
130 // Note that bcc needs the extra parentheses for non-type template
131 // arguments to compile this expression.
132 typedef typename wxIf< (wxIsMovable<T>::value),
133 wxPrivate::wxVectorMemOpsMovable<T>,
134 wxPrivate::wxVectorMemOpsGeneric<T> >::value
135 Ops;
136
137 public:
138 typedef size_t size_type;
139 typedef size_t difference_type;
140 typedef T value_type;
141 typedef value_type* pointer;
142 typedef value_type* iterator;
143 typedef const value_type* const_iterator;
144 typedef value_type& reference;
145
146 class reverse_iterator
147 {
148 public:
149 reverse_iterator() : m_ptr(NULL) { }
150 wxEXPLICIT reverse_iterator(iterator it) : m_ptr(it) { }
151 reverse_iterator(const reverse_iterator& it) : m_ptr(it.m_ptr) { }
152
153 reference operator*() const { return *m_ptr; }
154 pointer operator->() const { return m_ptr; }
155
156 iterator base() const { return m_ptr; }
157
158 reverse_iterator& operator++()
159 { --m_ptr; return *this; }
160 reverse_iterator operator++(int)
161 { reverse_iterator tmp = *this; --m_ptr; return tmp; }
162 reverse_iterator& operator--()
163 { ++m_ptr; return *this; }
164 reverse_iterator operator--(int)
165 { reverse_iterator tmp = *this; ++m_ptr; return tmp; }
166
167 reverse_iterator operator+(difference_type n) const
168 { return reverse_iterator(m_ptr - n); }
169 reverse_iterator& operator+=(difference_type n)
170 { m_ptr -= n; return *this; }
171 reverse_iterator operator-(difference_type n) const
172 { return reverse_iterator(m_ptr + n); }
173 reverse_iterator& operator-=(difference_type n)
174 { m_ptr += n; return *this; }
175
176 reference operator[](difference_type n) const
177 { return *(*this + n); }
178
179 bool operator ==(const reverse_iterator& it) const
180 { return m_ptr == it.m_ptr; }
181 bool operator !=(const reverse_iterator& it) const
182 { return m_ptr != it.m_ptr; }
183
184 private:
185 value_type *m_ptr;
186 };
187
188 wxVector() : m_size(0), m_capacity(0), m_values(NULL) {}
189
190 wxVector(size_type p_size)
191 : m_size(0), m_capacity(0), m_values(NULL)
192 {
193 reserve(p_size);
194 for ( size_t n = 0; n < p_size; n++ )
195 push_back(value_type());
196 }
197
198 wxVector(size_type p_size, const value_type& v)
199 : m_size(0), m_capacity(0), m_values(NULL)
200 {
201 reserve(p_size);
202 for ( size_t n = 0; n < p_size; n++ )
203 push_back(v);
204 }
205
206 wxVector(const wxVector& c) : m_size(0), m_capacity(0), m_values(NULL)
207 {
208 Copy(c);
209 }
210
211 ~wxVector()
212 {
213 clear();
214 }
215
216 void assign(size_type p_size, const value_type& v)
217 {
218 clear();
219 reserve(p_size);
220 for ( size_t n = 0; n < p_size; n++ )
221 push_back(v);
222 }
223
224 void swap(wxVector& v)
225 {
226 wxSwap(m_size, v.m_size);
227 wxSwap(m_capacity, v.m_capacity);
228 wxSwap(m_values, v.m_values);
229 }
230
231 void clear()
232 {
233 // call destructors of stored objects:
234 for ( size_type i = 0; i < m_size; i++ )
235 {
236 m_values[i].~T();
237 }
238
239 Ops::Free(m_values);
240 m_values = NULL;
241 m_size =
242 m_capacity = 0;
243 }
244
245 void reserve(size_type n)
246 {
247 if ( n <= m_capacity )
248 return;
249
250 // increase the size twice, unless we're already too big or unless
251 // more is requested
252 //
253 // NB: casts to size_type are needed to suppress warnings about
254 // mixing enumeral and non-enumeral type in conditional expression
255 const size_type increment = m_size > 0
256 ? m_size < ALLOC_MAX_SIZE
257 ? m_size
258 : (size_type)ALLOC_MAX_SIZE
259 : (size_type)ALLOC_INITIAL_SIZE;
260 if ( m_capacity + increment > n )
261 n = m_capacity + increment;
262
263 m_values = Ops::Realloc(m_values, n * sizeof(value_type), m_size);
264 m_capacity = n;
265 }
266
267 void resize(size_type n)
268 {
269 if ( n < m_size )
270 Shrink(n);
271 else if ( n > m_size )
272 Extend(n, value_type());
273 }
274
275 void resize(size_type n, const value_type& v)
276 {
277 if ( n < m_size )
278 Shrink(n);
279 else if ( n > m_size )
280 Extend(n, v);
281 }
282
283 size_type size() const
284 {
285 return m_size;
286 }
287
288 size_type capacity() const
289 {
290 return m_capacity;
291 }
292
293 bool empty() const
294 {
295 return size() == 0;
296 }
297
298 wxVector& operator=(const wxVector& vb)
299 {
300 if (this != &vb)
301 {
302 clear();
303 Copy(vb);
304 }
305 return *this;
306 }
307
308 void push_back(const value_type& v)
309 {
310 reserve(size() + 1);
311
312 // use placement new to initialize new object in preallocated place in
313 // m_values and store 'v' in it:
314 void* const place = m_values + m_size;
315 ::new(place) value_type(v);
316
317 // only increase m_size if the ctor didn't throw an exception; notice
318 // that if it _did_ throw, everything is OK, because we only increased
319 // vector's capacity so far and possibly written some data to
320 // uninitialized memory at the end of m_values
321 m_size++;
322 }
323
324 void pop_back()
325 {
326 erase(end() - 1);
327 }
328
329 const value_type& at(size_type idx) const
330 {
331 wxASSERT(idx < m_size);
332 return m_values[idx];
333 }
334
335 value_type& at(size_type idx)
336 {
337 wxASSERT(idx < m_size);
338 return m_values[idx];
339 }
340
341 const value_type& operator[](size_type idx) const { return at(idx); }
342 value_type& operator[](size_type idx) { return at(idx); }
343 const value_type& front() const { return at(0); }
344 value_type& front() { return at(0); }
345 const value_type& back() const { return at(size() - 1); }
346 value_type& back() { return at(size() - 1); }
347
348 const_iterator begin() const { return m_values; }
349 iterator begin() { return m_values; }
350 const_iterator end() const { return m_values + size(); }
351 iterator end() { return m_values + size(); }
352
353 reverse_iterator rbegin() { return reverse_iterator(end() - 1); }
354 reverse_iterator rend() { return reverse_iterator(begin() - 1); }
355
356 iterator insert(iterator it, const value_type& v = value_type())
357 {
358 // NB: this must be done before reserve(), because reserve()
359 // invalidates iterators!
360 const size_t idx = it - begin();
361 const size_t after = end() - it;
362
363 reserve(size() + 1);
364
365 // the place where the new element is going to be inserted
366 value_type * const place = m_values + idx;
367
368 // unless we're inserting at the end, move following elements out of
369 // the way:
370 if ( after > 0 )
371 Ops::MemmoveForward(place + 1, place, after);
372
373 // if the ctor called below throws an exception, we need to move all
374 // the elements back to their original positions in m_values
375 wxScopeGuard moveBack = wxMakeGuard(
376 Ops::MemmoveBackward, place, place + 1, after);
377 if ( !after )
378 moveBack.Dismiss();
379
380 // use placement new to initialize new object in preallocated place in
381 // m_values and store 'v' in it:
382 ::new(place) value_type(v);
383
384 // now that we did successfully add the new element, increment the size
385 // and disable moving the items back
386 moveBack.Dismiss();
387 m_size++;
388
389 return begin() + idx;
390 }
391
392 iterator erase(iterator it)
393 {
394 return erase(it, it + 1);
395 }
396
397 iterator erase(iterator first, iterator last)
398 {
399 if ( first == last )
400 return first;
401 wxASSERT( first < end() && last <= end() );
402
403 const size_type idx = first - begin();
404 const size_type count = last - first;
405 const size_type after = end() - last;
406
407 // erase elements by calling their destructors:
408 for ( iterator i = first; i < last; ++i )
409 i->~T();
410
411 // once that's done, move following elements over to the freed space:
412 if ( after > 0 )
413 {
414 Ops::MemmoveBackward(m_values + idx, m_values + idx + count, after);
415 }
416
417 m_size -= count;
418
419 return begin() + idx;
420 }
421
422 #if WXWIN_COMPATIBILITY_2_8
423 wxDEPRECATED( size_type erase(size_type n) );
424 #endif // WXWIN_COMPATIBILITY_2_8
425
426 private:
427 // VC6 can't compile static const int members
428 enum { ALLOC_INITIAL_SIZE = 16 };
429 enum { ALLOC_MAX_SIZE = 4096 };
430
431 void Copy(const wxVector& vb)
432 {
433 reserve(vb.size());
434
435 for ( const_iterator i = vb.begin(); i != vb.end(); ++i )
436 push_back(*i);
437 }
438
439 private:
440 void Shrink(size_type n)
441 {
442 for ( size_type i = n; i < m_size; i++ )
443 m_values[i].~T();
444 m_size = n;
445 }
446
447 void Extend(size_type n, const value_type& v)
448 {
449 reserve(n);
450 for ( size_type i = m_size; i < n; i++ )
451 push_back(v);
452 }
453
454 size_type m_size,
455 m_capacity;
456 value_type *m_values;
457 };
458
459 #if WXWIN_COMPATIBILITY_2_8
460 template<typename T>
461 inline typename wxVector<T>::size_type wxVector<T>::erase(size_type n)
462 {
463 erase(begin() + n);
464 return n;
465 }
466 #endif // WXWIN_COMPATIBILITY_2_8
467
468
469
470 namespace wxPrivate
471 {
472
473 // This is a helper for the wxVectorSort function, and should not be used
474 // directly in user's code.
475 template<typename T>
476 struct wxVectorComparator
477 {
478 static int
479 Compare(const void* pitem1, const void* pitem2, const void* )
480 {
481 const T& item1 = *reinterpret_cast<const T*>(pitem1);
482 const T& item2 = *reinterpret_cast<const T*>(pitem2);
483
484 if (item1 < item2)
485 return -1;
486 else if (item2 < item1)
487 return 1;
488 else
489 return 0;
490 }
491 };
492
493 } // namespace wxPrivate
494
495
496
497 template<typename T>
498 void wxVectorSort(wxVector<T>& v)
499 {
500 wxQsort(v.begin(), v.size(), sizeof(T),
501 wxPrivate::wxVectorComparator<T>::Compare, NULL);
502 }
503
504
505
506 #endif // wxUSE_STD_CONTAINERS/!wxUSE_STD_CONTAINERS
507
508 #if WXWIN_COMPATIBILITY_2_8
509 #define WX_DECLARE_VECTORBASE(obj, cls) typedef wxVector<obj> cls
510 #define _WX_DECLARE_VECTOR(obj, cls, exp) WX_DECLARE_VECTORBASE(obj, cls)
511 #define WX_DECLARE_VECTOR(obj, cls) WX_DECLARE_VECTORBASE(obj, cls)
512 #endif // WXWIN_COMPATIBILITY_2_8
513
514 #endif // _WX_VECTOR_H_