]>
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/scopeguard.h"
26 #include "wx/meta/movable.h"
27 #include "wx/meta/if.h"
29 #include "wx/beforestd.h"
30 #include <new> // for placement new
31 #include "wx/afterstd.h"
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().
40 // version for movable types:
42 struct wxVectorMemOpsMovable
44 static void Free(T
* array
)
47 static T
* Realloc(T
* old
, size_t newCapacity
, size_t WXUNUSED(occupiedSize
))
48 { return (T
*)realloc(old
, newCapacity
* sizeof(T
)); }
50 static void MemmoveBackward(T
* dest
, T
* source
, size_t count
)
51 { memmove(dest
, source
, count
* sizeof(T
)); }
53 static void MemmoveForward(T
* dest
, T
* source
, size_t count
)
54 { memmove(dest
, source
, count
* sizeof(T
)); }
57 // generic version for non-movable types:
59 struct wxVectorMemOpsGeneric
61 static void Free(T
* array
)
62 { ::operator delete(array
); }
64 static T
* Realloc(T
* old
, size_t newCapacity
, size_t occupiedSize
)
66 T
*mem
= (T
*)::operator new(newCapacity
* sizeof(T
));
67 for ( size_t i
= 0; i
< occupiedSize
; i
++ )
69 new(mem
+ i
) T(old
[i
]);
72 ::operator delete(old
);
76 static void MemmoveBackward(T
* dest
, T
* source
, size_t count
)
78 wxASSERT( dest
< source
);
80 T
* sourceptr
= source
;
81 for ( size_t i
= count
; i
> 0; --i
, ++destptr
, ++sourceptr
)
83 new(destptr
) T(*sourceptr
);
88 static void MemmoveForward(T
* dest
, T
* source
, size_t count
)
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
)
95 new(destptr
) T(*sourceptr
);
102 } // namespace wxPrivate
108 // This cryptic expression means "typedef Ops to wxVectorMemOpsMovable if
109 // type T is movable type, otherwise to wxVectorMemOpsGeneric".
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
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
;
128 class reverse_iterator
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
) { }
135 reference
operator*() const { return *m_ptr
; }
136 pointer
operator->() const { return m_ptr
; }
138 iterator
base() const { return m_ptr
; }
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
; }
149 reverse_iterator
operator+(difference_type n
) const
150 { return reverse_iterator(m_ptr
- n
); }
151 reverse_iterator
& operator+=(difference_type n
)
152 { return 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 { return m_ptr
+= n
; return *this; }
158 reference
operator[](difference_type n
) const
159 { return *(*this + n
); }
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
; }
170 wxVector() : m_size(0), m_capacity(0), m_values(NULL
) {}
172 wxVector(const wxVector
& c
) : m_size(0), m_capacity(0), m_values(NULL
)
184 // call destructors of stored objects:
185 for ( size_type i
= 0; i
< m_size
; i
++ )
196 void reserve(size_type n
)
198 if ( n
<= m_capacity
)
201 // increase the size twice, unless we're already too big or unless
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
;
212 m_values
= Ops::Realloc(m_values
, n
* sizeof(value_type
), m_size
);
216 size_type
size() const
221 size_type
capacity() const
231 wxVector
& operator=(const wxVector
& vb
)
238 void push_back(const value_type
& v
)
242 // use placement new to initialize new object in preallocated place in
243 // m_values and store 'v' in it:
244 void* const place
= m_values
+ m_size
;
245 new(place
) value_type(v
);
247 // only increase m_size if the ctor didn't throw an exception; notice
248 // that if it _did_ throw, everything is OK, because we only increased
249 // vector's capacity so far and possibly written some data to
250 // uninitialized memory at the end of m_values
259 const value_type
& at(size_type idx
) const
261 wxASSERT(idx
< m_size
);
262 return m_values
[idx
];
265 value_type
& at(size_type idx
)
267 wxASSERT(idx
< m_size
);
268 return m_values
[idx
];
271 const value_type
& operator[](size_type idx
) const { return at(idx
); }
272 value_type
& operator[](size_type idx
) { return at(idx
); }
273 const value_type
& front() const { return at(0); }
274 value_type
& front() { return at(0); }
275 const value_type
& back() const { return at(size() - 1); }
276 value_type
& back() { return at(size() - 1); }
278 const_iterator
begin() const { return m_values
; }
279 iterator
begin() { return m_values
; }
280 const_iterator
end() const { return m_values
+ size(); }
281 iterator
end() { return m_values
+ size(); }
283 reverse_iterator
rbegin() { return reverse_iterator(end() - 1); }
284 reverse_iterator
rend() { return reverse_iterator(begin() - 1); }
286 iterator
insert(iterator it
, const value_type
& v
= value_type())
288 // NB: this must be done before reserve(), because reserve()
289 // invalidates iterators!
290 const size_t idx
= it
- begin();
291 const size_t after
= end() - it
;
295 // the place where the new element is going to be inserted
296 value_type
* const place
= m_values
+ idx
;
298 // unless we're inserting at the end, move following elements out of
301 Ops::MemmoveForward(place
+ 1, place
, after
);
303 // if the ctor called below throws an exception, we need to move all
304 // the elements back to their original positions in m_values
305 wxScopeGuard moveBack
= wxMakeGuard(
306 Ops::MemmoveBackward
, place
, place
+ 1, after
);
310 // use placement new to initialize new object in preallocated place in
311 // m_values and store 'v' in it:
312 new(place
) value_type(v
);
314 // now that we did successfully add the new element, increment the size
315 // and disable moving the items back
319 return begin() + idx
;
322 iterator
erase(iterator it
)
324 return erase(it
, it
+ 1);
327 iterator
erase(iterator first
, iterator last
)
331 wxASSERT( first
< end() && last
<= end() );
333 const size_type idx
= first
- begin();
334 const size_type count
= last
- first
;
335 const size_type after
= end() - last
;
337 // erase elements by calling their destructors:
338 for ( iterator i
= first
; i
< last
; ++i
)
341 // once that's done, move following elements over to the freed space:
344 Ops::MemmoveBackward(m_values
+ idx
, m_values
+ idx
+ count
, after
);
349 return begin() + idx
;
352 #if WXWIN_COMPATIBILITY_2_8
353 wxDEPRECATED( size_type
erase(size_type n
) );
354 #endif // WXWIN_COMPATIBILITY_2_8
357 // VC6 can't compile static const int members
358 enum { ALLOC_INITIAL_SIZE
= 16 };
359 enum { ALLOC_MAX_SIZE
= 4096 };
361 void Copy(const wxVector
& vb
)
365 for ( const_iterator i
= vb
.begin(); i
!= vb
.end(); ++i
)
372 value_type
*m_values
;
375 #if WXWIN_COMPATIBILITY_2_8
377 inline typename wxVector
<T
>::size_type wxVector
<T
>::erase(size_type n
)
382 #endif // WXWIN_COMPATIBILITY_2_8
384 #endif // wxUSE_STL/!wxUSE_STL
386 #if WXWIN_COMPATIBILITY_2_8
387 #define WX_DECLARE_VECTORBASE(obj, cls) typedef wxVector<obj> cls
388 #define _WX_DECLARE_VECTOR(obj, cls, exp) WX_DECLARE_VECTORBASE(obj, cls)
389 #define WX_DECLARE_VECTOR(obj, cls) WX_DECLARE_VECTORBASE(obj, cls)
390 #endif // WXWIN_COMPATIBILITY_2_8
392 #endif // _WX_VECTOR_H_