X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/fc31181d2cff6ca1e05b6a820c18b87d8915344b..438959cca892a7651634cc3a7aad4819ac49b23c:/include/wx/vector.h diff --git a/include/wx/vector.h b/include/wx/vector.h index e2faf83569..dffb19fc9d 100644 --- a/include/wx/vector.h +++ b/include/wx/vector.h @@ -14,14 +14,20 @@ #include "wx/defs.h" -#if wxUSE_STL +#if wxUSE_STD_CONTAINERS #include +#include + #define wxVector std::vector +template +inline void wxVectorSort(wxVector& v) +{ + std::sort(v.begin(), v.end()); +} -#else // !wxUSE_STL +#else // !wxUSE_STD_CONTAINERS -#include "wx/utils.h" #include "wx/scopeguard.h" #include "wx/meta/movable.h" #include "wx/meta/if.h" @@ -30,6 +36,15 @@ #include // for placement new #include "wx/afterstd.h" +// wxQsort is declared in wx/utils.h, but can't include that file here, +// it indirectly includes this file. Just lovely... +typedef int (*wxSortCallback)(const void* pItem1, + const void* pItem2, + const void* user_data); +WXDLLIMPEXP_BASE void wxQsort(void* pbase, size_t total_elems, + size_t size, wxSortCallback cmp, + const void* user_data); + namespace wxPrivate { @@ -66,7 +81,7 @@ struct wxVectorMemOpsGeneric T *mem = (T*)::operator new(newCapacity * sizeof(T)); for ( size_t i = 0; i < occupiedSize; i++ ) { - new(mem + i) T(old[i]); + ::new(mem + i) T(old[i]); old[i].~T(); } ::operator delete(old); @@ -80,7 +95,7 @@ struct wxVectorMemOpsGeneric T* sourceptr = source; for ( size_t i = count; i > 0; --i, ++destptr, ++sourceptr ) { - new(destptr) T(*sourceptr); + ::new(destptr) T(*sourceptr); sourceptr->~T(); } } @@ -92,7 +107,7 @@ struct wxVectorMemOpsGeneric T* sourceptr = source + count - 1; for ( size_t i = count; i > 0; --i, --destptr, --sourceptr ) { - new(destptr) T(*sourceptr); + ::new(destptr) T(*sourceptr); sourceptr->~T(); } } @@ -111,7 +126,10 @@ private: // Note that we use typedef instead of privately deriving from this (which // would allowed us to omit "Ops::" prefixes below) to keep VC6 happy, // it can't compile code that derives from wxIf<...>::value. - typedef typename wxIf< wxIsMovable::value, + // + // Note that bcc needs the extra parentheses for non-type template + // arguments to compile this expression. + typedef typename wxIf< (wxIsMovable::value), wxPrivate::wxVectorMemOpsMovable, wxPrivate::wxVectorMemOpsGeneric >::value Ops; @@ -121,9 +139,11 @@ public: typedef size_t difference_type; typedef T value_type; typedef value_type* pointer; + typedef const value_type* const_pointer; typedef value_type* iterator; typedef const value_type* const_iterator; typedef value_type& reference; + typedef const value_type& const_reference; class reverse_iterator { @@ -131,54 +151,150 @@ public: reverse_iterator() : m_ptr(NULL) { } wxEXPLICIT reverse_iterator(iterator it) : m_ptr(it) { } reverse_iterator(const reverse_iterator& it) : m_ptr(it.m_ptr) { } - + reference operator*() const { return *m_ptr; } pointer operator->() const { return m_ptr; } - + iterator base() const { return m_ptr; } - - reverse_iterator& operator++() - { --m_ptr; return *this; } + + reverse_iterator& operator++() + { --m_ptr; return *this; } reverse_iterator operator++(int) - { reverse_iterator tmp = *this; --m_ptr; return tmp; } - reverse_iterator& operator--() - { ++m_ptr; return *this; } - reverse_iterator operator--(int) - { reverse_iterator tmp = *this; ++m_ptr; return tmp; } - + { reverse_iterator tmp = *this; --m_ptr; return tmp; } + reverse_iterator& operator--() + { ++m_ptr; return *this; } + reverse_iterator operator--(int) + { reverse_iterator tmp = *this; ++m_ptr; return tmp; } + reverse_iterator operator+(difference_type n) const - { return reverse_iterator(m_ptr - n); } + { return reverse_iterator(m_ptr - n); } reverse_iterator& operator+=(difference_type n) - { return m_ptr -= n; return *this; } + { m_ptr -= n; return *this; } reverse_iterator operator-(difference_type n) const - { return reverse_iterator(m_ptr + n); } + { return reverse_iterator(m_ptr + n); } reverse_iterator& operator-=(difference_type n) - { return m_ptr += n; return *this; } - + { m_ptr += n; return *this; } + reference operator[](difference_type n) const - { return *(*this + n); } - - bool operator ==(const reverse_iterator& it) const - { return m_ptr == it.m_ptr; } + { return *(*this + n); } + + bool operator ==(const reverse_iterator& it) const + { return m_ptr == it.m_ptr; } bool operator !=(const reverse_iterator& it) const - { return m_ptr != it.m_ptr; } - + { return m_ptr != it.m_ptr; } + private: value_type *m_ptr; + + friend class const_reverse_iterator; + }; + + class const_reverse_iterator + { + public: + const_reverse_iterator() : m_ptr(NULL) { } + wxEXPLICIT const_reverse_iterator(const_iterator it) : m_ptr(it) { } + const_reverse_iterator(const reverse_iterator& it) : m_ptr(it.m_ptr) { } + const_reverse_iterator(const const_reverse_iterator& it) : m_ptr(it.m_ptr) { } + + const_reference operator*() const { return *m_ptr; } + const_pointer operator->() const { return m_ptr; } + + const_iterator base() const { return m_ptr; } + + const_reverse_iterator& operator++() + { --m_ptr; return *this; } + const_reverse_iterator operator++(int) + { const_reverse_iterator tmp = *this; --m_ptr; return tmp; } + const_reverse_iterator& operator--() + { ++m_ptr; return *this; } + const_reverse_iterator operator--(int) + { const_reverse_iterator tmp = *this; ++m_ptr; return tmp; } + + const_reverse_iterator operator+(difference_type n) const + { return const_reverse_iterator(m_ptr - n); } + const_reverse_iterator& operator+=(difference_type n) + { m_ptr -= n; return *this; } + const_reverse_iterator operator-(difference_type n) const + { return const_reverse_iterator(m_ptr + n); } + const_reverse_iterator& operator-=(difference_type n) + { m_ptr += n; return *this; } + + const_reference operator[](difference_type n) const + { return *(*this + n); } + + bool operator ==(const const_reverse_iterator& it) const + { return m_ptr == it.m_ptr; } + bool operator !=(const const_reverse_iterator& it) const + { return m_ptr != it.m_ptr; } + + protected: + const value_type *m_ptr; }; wxVector() : m_size(0), m_capacity(0), m_values(NULL) {} + wxVector(size_type p_size) + : m_size(0), m_capacity(0), m_values(NULL) + { + reserve(p_size); + for ( size_t n = 0; n < p_size; n++ ) + push_back(value_type()); + } + + wxVector(size_type p_size, const value_type& v) + : m_size(0), m_capacity(0), m_values(NULL) + { + reserve(p_size); + for ( size_t n = 0; n < p_size; n++ ) + push_back(v); + } + wxVector(const wxVector& c) : m_size(0), m_capacity(0), m_values(NULL) { Copy(c); } + template + wxVector(InputIterator first, InputIterator last) + : m_size(0), m_capacity(0), m_values(NULL) + { + assign(first, last); + } + ~wxVector() { clear(); } + void assign(size_type p_size, const value_type& v) + { + clear(); + reserve(p_size); + for ( size_t n = 0; n < p_size; n++ ) + push_back(v); + } + + template + void assign(InputIterator first, InputIterator last) + { + clear(); + + // Notice that it would be nice to call reserve() here but we can't do + // it for arbitrary input iterators, we should have a dispatch on + // iterator type and call it if possible. + + for ( InputIterator it = first; it != last; ++it ) + push_back(*it); + } + + void swap(wxVector& v) + { + wxSwap(m_size, v.m_size); + wxSwap(m_capacity, v.m_capacity); + wxSwap(m_values, v.m_values); + } + void clear() { // call destructors of stored objects: @@ -201,10 +317,12 @@ public: // increase the size twice, unless we're already too big or unless // more is requested // - // NB: casts to size_type are needed to suppress mingw32 warnings about - // mixing enums and ints in the same expression + // NB: casts to size_type are needed to suppress warnings about + // mixing enumeral and non-enumeral type in conditional expression const size_type increment = m_size > 0 - ? wxMin(m_size, (size_type)ALLOC_MAX_SIZE) + ? m_size < ALLOC_MAX_SIZE + ? m_size + : (size_type)ALLOC_MAX_SIZE : (size_type)ALLOC_INITIAL_SIZE; if ( m_capacity + increment > n ) n = m_capacity + increment; @@ -213,6 +331,22 @@ public: m_capacity = n; } + void resize(size_type n) + { + if ( n < m_size ) + Shrink(n); + else if ( n > m_size ) + Extend(n, value_type()); + } + + void resize(size_type n, const value_type& v) + { + if ( n < m_size ) + Shrink(n); + else if ( n > m_size ) + Extend(n, v); + } + size_type size() const { return m_size; @@ -230,8 +364,11 @@ public: wxVector& operator=(const wxVector& vb) { - clear(); - Copy(vb); + if (this != &vb) + { + clear(); + Copy(vb); + } return *this; } @@ -242,7 +379,7 @@ public: // use placement new to initialize new object in preallocated place in // m_values and store 'v' in it: void* const place = m_values + m_size; - new(place) value_type(v); + ::new(place) value_type(v); // only increase m_size if the ctor didn't throw an exception; notice // that if it _did_ throw, everything is OK, because we only increased @@ -283,6 +420,9 @@ public: reverse_iterator rbegin() { return reverse_iterator(end() - 1); } reverse_iterator rend() { return reverse_iterator(begin() - 1); } + const_reverse_iterator rbegin() const { return const_reverse_iterator(end() - 1); } + const_reverse_iterator rend() const { return const_reverse_iterator(begin() - 1); } + iterator insert(iterator it, const value_type& v = value_type()) { // NB: this must be done before reserve(), because reserve() @@ -309,7 +449,7 @@ public: // use placement new to initialize new object in preallocated place in // m_values and store 'v' in it: - new(place) value_type(v); + ::new(place) value_type(v); // now that we did successfully add the new element, increment the size // and disable moving the items back @@ -367,6 +507,20 @@ private: } private: + void Shrink(size_type n) + { + for ( size_type i = n; i < m_size; i++ ) + m_values[i].~T(); + m_size = n; + } + + void Extend(size_type n, const value_type& v) + { + reserve(n); + for ( size_type i = m_size; i < n; i++ ) + push_back(v); + } + size_type m_size, m_capacity; value_type *m_values; @@ -381,7 +535,45 @@ inline typename wxVector::size_type wxVector::erase(size_type n) } #endif // WXWIN_COMPATIBILITY_2_8 -#endif // wxUSE_STL/!wxUSE_STL + + +namespace wxPrivate +{ + +// This is a helper for the wxVectorSort function, and should not be used +// directly in user's code. +template +struct wxVectorComparator +{ + static int + Compare(const void* pitem1, const void* pitem2, const void* ) + { + const T& item1 = *reinterpret_cast(pitem1); + const T& item2 = *reinterpret_cast(pitem2); + + if (item1 < item2) + return -1; + else if (item2 < item1) + return 1; + else + return 0; + } +}; + +} // namespace wxPrivate + + + +template +void wxVectorSort(wxVector& v) +{ + wxQsort(v.begin(), v.size(), sizeof(T), + wxPrivate::wxVectorComparator::Compare, NULL); +} + + + +#endif // wxUSE_STD_CONTAINERS/!wxUSE_STD_CONTAINERS #if WXWIN_COMPATIBILITY_2_8 #define WX_DECLARE_VECTORBASE(obj, cls) typedef wxVector cls