]>
git.saurik.com Git - wxWidgets.git/blob - include/wx/vector.h
1 ///////////////////////////////////////////////////////////////////////////////
3 // Purpose: STL vector clone
4 // Author: Lindsay Mathieson
5 // Modified by: Vaclav Slavik - make it a template
7 // Copyright: (c) 2001 Lindsay Mathieson <lindsay@mathieson.org>,
8 // 2007 Vaclav Slavik <vslavik@fastmail.fm>
9 // Licence: wxWindows licence
10 ///////////////////////////////////////////////////////////////////////////////
20 #define wxVector std::vector
25 #include "wx/meta/movable.h"
26 #include "wx/meta/if.h"
28 #include "wx/beforestd.h"
29 #include <new> // for placement new
30 #include "wx/afterstd.h"
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().
39 // version for movable types:
41 struct wxVectorMemOpsMovable
43 static void Free(T
* array
)
46 static T
* Realloc(T
* old
, size_t newCapacity
, size_t WXUNUSED(occupiedSize
))
47 { return (T
*)realloc(old
, newCapacity
* sizeof(T
)); }
49 static void MemmoveBackward(T
* dest
, T
* source
, size_t count
)
50 { memmove(dest
, source
, count
* sizeof(T
)); }
52 static void MemmoveForward(T
* dest
, T
* source
, size_t count
)
53 { memmove(dest
, source
, count
* sizeof(T
)); }
56 // generic version for non-movable types:
58 struct wxVectorMemOpsGeneric
60 static void Free(T
* array
)
61 { ::operator delete(array
); }
63 static T
* Realloc(T
* old
, size_t newCapacity
, size_t occupiedSize
)
65 T
*mem
= (T
*)::operator new(newCapacity
* sizeof(T
));
66 for ( size_t i
= 0; i
< occupiedSize
; i
++ )
68 new(mem
+ i
) T(old
[i
]);
71 ::operator delete(old
);
75 static void MemmoveBackward(T
* dest
, T
* source
, size_t count
)
77 wxASSERT( dest
< source
);
79 T
* sourceptr
= source
;
80 for ( size_t i
= count
; i
> 0; --i
, ++destptr
, ++sourceptr
)
82 new(destptr
) T(*sourceptr
);
87 static void MemmoveForward(T
* dest
, T
* source
, size_t count
)
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
)
94 new(destptr
) T(*sourceptr
);
101 } // namespace wxPrivate
107 // This cryptic expression means "typedef Ops to wxVectorMemOpsMovable if
108 // type T is movable type, otherwise to wxVectorMemOpsGeneric".
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
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
;
125 wxVector() : m_size(0), m_capacity(0), m_values(NULL
) {}
127 wxVector(const wxVector
& c
)
139 // call destructors of stored objects:
140 for ( size_type i
= 0; i
< m_size
; i
++ )
147 m_size
= m_capacity
= 0;
150 void reserve(size_type n
)
152 if ( n
<= m_capacity
)
155 // increase the size twice, unless we're already too big or unless
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
;
166 m_values
= Ops::Realloc(m_values
, n
* sizeof(value_type
), m_size
);
170 size_type
size() const
175 size_type
capacity() const
185 wxVector
& operator=(const wxVector
& vb
)
191 void push_back(const value_type
& v
)
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
);
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
212 const value_type
& at(size_type idx
) const
214 wxASSERT(idx
< m_size
);
215 return m_values
[idx
];
218 value_type
& at(size_type idx
)
220 wxASSERT(idx
< m_size
);
221 return m_values
[idx
];
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); }
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(); }
236 iterator
insert(iterator it
, const value_type
& v
= value_type())
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
;
245 // unless we're inserting at the end, move following elements out of
249 Ops::MemmoveForward(m_values
+ idx
+ 1, m_values
+ idx
, after
);
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
);
264 // if the ctor threw an exception, we need to move all the elements
265 // back to their original positions in m_values
268 Ops::MemmoveBackward(m_values
+ idx
, m_values
+ idx
+ 1, after
);
271 throw; // rethrow the exception
273 #endif // wxUSE_EXCEPTIONS
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
280 return begin() + idx
;
283 iterator
erase(iterator it
)
285 return erase(it
, it
+ 1);
288 iterator
erase(iterator first
, iterator last
)
292 wxASSERT( first
< end() && last
<= end() );
294 const size_type idx
= first
- begin();
295 const size_type count
= last
- first
;
296 const size_type after
= end() - last
;
298 // erase elements by calling their destructors:
299 for ( iterator i
= first
; i
< last
; ++i
)
302 // once that's done, move following elements over to the freed space:
305 Ops::MemmoveBackward(m_values
+ idx
, m_values
+ idx
+ count
, after
);
310 return begin() + idx
;
313 #if WXWIN_COMPATIBILITY_2_8
314 wxDEPRECATED( size_type
erase(size_type n
) );
315 #endif // WXWIN_COMPATIBILITY_2_8
318 // VC6 can't compile static const int members
319 enum { ALLOC_INITIAL_SIZE
= 16 };
320 enum { ALLOC_MAX_SIZE
= 4096 };
322 void Copy(const wxVector
& vb
)
327 for ( const_iterator i
= vb
.begin(); i
!= vb
.end(); ++i
)
334 value_type
*m_values
;
337 #if WXWIN_COMPATIBILITY_2_8
339 inline typename wxVector
<T
>::size_type wxVector
<T
>::erase(size_type n
)
344 #endif // WXWIN_COMPATIBILITY_2_8
346 #endif // wxUSE_STL/!wxUSE_STL
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
354 #endif // _WX_VECTOR_H_