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