]>
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
22 inline void wxVectorSort(wxVector
<T
>& v
)
24 std::sort(v
.begin(), v
.end());
30 #include "wx/scopeguard.h"
31 #include "wx/meta/movable.h"
32 #include "wx/meta/if.h"
34 #include "wx/beforestd.h"
35 #include <new> // for placement new
36 #include "wx/afterstd.h"
41 // These templates encapsulate memory operations for use by wxVector; there are
42 // two implementations, both in generic way for any C++ types and as an
43 // optimized version for "movable" types that uses realloc() and memmove().
45 // version for movable types:
47 struct wxVectorMemOpsMovable
49 static void Free(T
* array
)
52 static T
* Realloc(T
* old
, size_t newCapacity
, size_t WXUNUSED(occupiedSize
))
53 { return (T
*)realloc(old
, newCapacity
* sizeof(T
)); }
55 static void MemmoveBackward(T
* dest
, T
* source
, size_t count
)
56 { memmove(dest
, source
, count
* sizeof(T
)); }
58 static void MemmoveForward(T
* dest
, T
* source
, size_t count
)
59 { memmove(dest
, source
, count
* sizeof(T
)); }
62 // generic version for non-movable types:
64 struct wxVectorMemOpsGeneric
66 static void Free(T
* array
)
67 { ::operator delete(array
); }
69 static T
* Realloc(T
* old
, size_t newCapacity
, size_t occupiedSize
)
71 T
*mem
= (T
*)::operator new(newCapacity
* sizeof(T
));
72 for ( size_t i
= 0; i
< occupiedSize
; i
++ )
74 ::new(mem
+ i
) T(old
[i
]);
77 ::operator delete(old
);
81 static void MemmoveBackward(T
* dest
, T
* source
, size_t count
)
83 wxASSERT( dest
< source
);
85 T
* sourceptr
= source
;
86 for ( size_t i
= count
; i
> 0; --i
, ++destptr
, ++sourceptr
)
88 ::new(destptr
) T(*sourceptr
);
93 static void MemmoveForward(T
* dest
, T
* source
, size_t count
)
95 wxASSERT( dest
> source
);
96 T
* destptr
= dest
+ count
- 1;
97 T
* sourceptr
= source
+ count
- 1;
98 for ( size_t i
= count
; i
> 0; --i
, --destptr
, --sourceptr
)
100 ::new(destptr
) T(*sourceptr
);
107 } // namespace wxPrivate
113 // This cryptic expression means "typedef Ops to wxVectorMemOpsMovable if
114 // type T is movable type, otherwise to wxVectorMemOpsGeneric".
116 // Note that we use typedef instead of privately deriving from this (which
117 // would allowed us to omit "Ops::" prefixes below) to keep VC6 happy,
118 // it can't compile code that derives from wxIf<...>::value.
119 typedef typename wxIf
< wxIsMovable
<T
>::value
,
120 wxPrivate::wxVectorMemOpsMovable
<T
>,
121 wxPrivate::wxVectorMemOpsGeneric
<T
> >::value
125 typedef size_t size_type
;
126 typedef size_t difference_type
;
127 typedef T value_type
;
128 typedef value_type
* pointer
;
129 typedef value_type
* iterator
;
130 typedef const value_type
* const_iterator
;
131 typedef value_type
& reference
;
133 class reverse_iterator
136 reverse_iterator() : m_ptr(NULL
) { }
137 wxEXPLICIT
reverse_iterator(iterator it
) : m_ptr(it
) { }
138 reverse_iterator(const reverse_iterator
& it
) : m_ptr(it
.m_ptr
) { }
140 reference
operator*() const { return *m_ptr
; }
141 pointer
operator->() const { return m_ptr
; }
143 iterator
base() const { return m_ptr
; }
145 reverse_iterator
& operator++()
146 { --m_ptr
; return *this; }
147 reverse_iterator
operator++(int)
148 { reverse_iterator tmp
= *this; --m_ptr
; return tmp
; }
149 reverse_iterator
& operator--()
150 { ++m_ptr
; return *this; }
151 reverse_iterator
operator--(int)
152 { reverse_iterator tmp
= *this; ++m_ptr
; return tmp
; }
154 reverse_iterator
operator+(difference_type n
) const
155 { return reverse_iterator(m_ptr
- n
); }
156 reverse_iterator
& operator+=(difference_type n
)
157 { m_ptr
-= n
; return *this; }
158 reverse_iterator
operator-(difference_type n
) const
159 { return reverse_iterator(m_ptr
+ n
); }
160 reverse_iterator
& operator-=(difference_type n
)
161 { m_ptr
+= n
; return *this; }
163 reference
operator[](difference_type n
) const
164 { return *(*this + n
); }
166 bool operator ==(const reverse_iterator
& it
) const
167 { return m_ptr
== it
.m_ptr
; }
168 bool operator !=(const reverse_iterator
& it
) const
169 { return m_ptr
!= it
.m_ptr
; }
175 wxVector() : m_size(0), m_capacity(0), m_values(NULL
) {}
177 wxVector(size_type p_size
)
178 : m_size(0), m_capacity(0), m_values(NULL
)
181 for ( size_t n
= 0; n
< p_size
; n
++ )
182 push_back(value_type());
185 wxVector(size_type p_size
, const value_type
& v
)
186 : m_size(0), m_capacity(0), m_values(NULL
)
189 for ( size_t n
= 0; n
< p_size
; n
++ )
193 wxVector(const wxVector
& c
) : m_size(0), m_capacity(0), m_values(NULL
)
203 void swap(wxVector
& v
)
205 wxSwap(m_size
, v
.m_size
);
206 wxSwap(m_capacity
, v
.m_capacity
);
207 wxSwap(m_values
, v
.m_values
);
212 // call destructors of stored objects:
213 for ( size_type i
= 0; i
< m_size
; i
++ )
224 void reserve(size_type n
)
226 if ( n
<= m_capacity
)
229 // increase the size twice, unless we're already too big or unless
232 // NB: casts to size_type are needed to suppress mingw32 warnings about
233 // mixing enums and ints in the same expression
234 const size_type increment
= m_size
> 0
235 ? wxMin(m_size
, (size_type
)ALLOC_MAX_SIZE
)
236 : (size_type
)ALLOC_INITIAL_SIZE
;
237 if ( m_capacity
+ increment
> n
)
238 n
= m_capacity
+ increment
;
240 m_values
= Ops::Realloc(m_values
, n
* sizeof(value_type
), m_size
);
244 void resize(size_type n
)
248 else if ( n
> m_size
)
249 Extend(n
, value_type());
252 void resize(size_type n
, const value_type
& v
)
256 else if ( n
> m_size
)
260 size_type
size() const
265 size_type
capacity() const
275 wxVector
& operator=(const wxVector
& vb
)
285 void push_back(const value_type
& v
)
289 // use placement new to initialize new object in preallocated place in
290 // m_values and store 'v' in it:
291 void* const place
= m_values
+ m_size
;
292 ::new(place
) value_type(v
);
294 // only increase m_size if the ctor didn't throw an exception; notice
295 // that if it _did_ throw, everything is OK, because we only increased
296 // vector's capacity so far and possibly written some data to
297 // uninitialized memory at the end of m_values
306 const value_type
& at(size_type idx
) const
308 wxASSERT(idx
< m_size
);
309 return m_values
[idx
];
312 value_type
& at(size_type idx
)
314 wxASSERT(idx
< m_size
);
315 return m_values
[idx
];
318 const value_type
& operator[](size_type idx
) const { return at(idx
); }
319 value_type
& operator[](size_type idx
) { return at(idx
); }
320 const value_type
& front() const { return at(0); }
321 value_type
& front() { return at(0); }
322 const value_type
& back() const { return at(size() - 1); }
323 value_type
& back() { return at(size() - 1); }
325 const_iterator
begin() const { return m_values
; }
326 iterator
begin() { return m_values
; }
327 const_iterator
end() const { return m_values
+ size(); }
328 iterator
end() { return m_values
+ size(); }
330 reverse_iterator
rbegin() { return reverse_iterator(end() - 1); }
331 reverse_iterator
rend() { return reverse_iterator(begin() - 1); }
333 iterator
insert(iterator it
, const value_type
& v
= value_type())
335 // NB: this must be done before reserve(), because reserve()
336 // invalidates iterators!
337 const size_t idx
= it
- begin();
338 const size_t after
= end() - it
;
342 // the place where the new element is going to be inserted
343 value_type
* const place
= m_values
+ idx
;
345 // unless we're inserting at the end, move following elements out of
348 Ops::MemmoveForward(place
+ 1, place
, after
);
350 // if the ctor called below throws an exception, we need to move all
351 // the elements back to their original positions in m_values
352 wxScopeGuard moveBack
= wxMakeGuard(
353 Ops::MemmoveBackward
, place
, place
+ 1, after
);
357 // use placement new to initialize new object in preallocated place in
358 // m_values and store 'v' in it:
359 ::new(place
) value_type(v
);
361 // now that we did successfully add the new element, increment the size
362 // and disable moving the items back
366 return begin() + idx
;
369 iterator
erase(iterator it
)
371 return erase(it
, it
+ 1);
374 iterator
erase(iterator first
, iterator last
)
378 wxASSERT( first
< end() && last
<= end() );
380 const size_type idx
= first
- begin();
381 const size_type count
= last
- first
;
382 const size_type after
= end() - last
;
384 // erase elements by calling their destructors:
385 for ( iterator i
= first
; i
< last
; ++i
)
388 // once that's done, move following elements over to the freed space:
391 Ops::MemmoveBackward(m_values
+ idx
, m_values
+ idx
+ count
, after
);
396 return begin() + idx
;
399 #if WXWIN_COMPATIBILITY_2_8
400 wxDEPRECATED( size_type
erase(size_type n
) );
401 #endif // WXWIN_COMPATIBILITY_2_8
404 // VC6 can't compile static const int members
405 enum { ALLOC_INITIAL_SIZE
= 16 };
406 enum { ALLOC_MAX_SIZE
= 4096 };
408 void Copy(const wxVector
& vb
)
412 for ( const_iterator i
= vb
.begin(); i
!= vb
.end(); ++i
)
417 void Shrink(size_type n
)
419 for ( size_type i
= n
; i
< m_size
; i
++ )
424 void Extend(size_type n
, const value_type
& v
)
427 for ( size_type i
= m_size
; i
< n
; i
++ )
433 value_type
*m_values
;
436 #if WXWIN_COMPATIBILITY_2_8
438 inline typename wxVector
<T
>::size_type wxVector
<T
>::erase(size_type n
)
443 #endif // WXWIN_COMPATIBILITY_2_8
449 // This function is a helper for the wxVectorSort function, and should
450 // not be used directly in user's code.
453 int wxCMPFUNC_CONV
wxVectorSort_compare(const void* pitem1
, const void* pitem2
, const void* )
455 const T
& item1
= *reinterpret_cast<const T
*>(pitem1
);
456 const T
& item2
= *reinterpret_cast<const T
*>(pitem2
);
460 else if (item2
< item1
)
466 } // namespace wxPrivate
471 void wxVectorSort(wxVector
<T
>& v
)
473 wxQsort(v
.begin(), v
.size(), sizeof(T
),
474 wxPrivate::wxVectorSort_compare
<T
>, NULL
);
479 #endif // wxUSE_STL/!wxUSE_STL
481 #if WXWIN_COMPATIBILITY_2_8
482 #define WX_DECLARE_VECTORBASE(obj, cls) typedef wxVector<obj> cls
483 #define _WX_DECLARE_VECTOR(obj, cls, exp) WX_DECLARE_VECTORBASE(obj, cls)
484 #define WX_DECLARE_VECTOR(obj, cls) WX_DECLARE_VECTORBASE(obj, cls)
485 #endif // WXWIN_COMPATIBILITY_2_8
487 #endif // _WX_VECTOR_H_