X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/655719367ac5e131d9642e5783f3ecf64d1a3385..da52a4e023e73c2922f63d95026816a624695559:/include/wx/vector.h diff --git a/include/wx/vector.h b/include/wx/vector.h index 2034a9eaa8..6fc0be174a 100644 --- a/include/wx/vector.h +++ b/include/wx/vector.h @@ -2,9 +2,10 @@ // Name: wx/vector.h // Purpose: STL vector clone // Author: Lindsay Mathieson -// Modified by: +// Modified by: Vaclav Slavik - make it a template // Created: 30.07.2001 -// Copyright: (c) 2001 Lindsay Mathieson +// Copyright: (c) 2001 Lindsay Mathieson , +// 2007 Vaclav Slavik // Licence: wxWindows licence /////////////////////////////////////////////////////////////////////////////// @@ -13,101 +14,72 @@ #include "wx/defs.h" -class WXDLLIMPEXP_BASE wxVectorBase -{ -public: - typedef size_t size_type; -private: - size_type m_allocsize; - size_type m_size, - m_capacity; - void **m_objects; +#if wxUSE_STL -protected: - bool Alloc(size_type sz) - { - // work in multiples of m_allocsize; - sz = (sz / m_allocsize + 1) * m_allocsize; - if (sz <= m_capacity) - return true; +#include +#define wxVector std::vector - // try to realloc - void *mem = realloc(m_objects, sizeof(void *) * sz); - if (! mem) - return false; // failed - // success - m_objects = (void **) mem; - m_capacity = sz; - return true; - }; +#else // !wxUSE_STL - // untyped destructor of elements - must be overriden - virtual void Free(void *) = 0; - // untyped copy constructor of elements - must be overriden - virtual void *Copy(const void *) const = 0; +#include "wx/utils.h" - const void *GetItem(size_type idx) const - { - wxASSERT(idx >= 0 && idx < m_size); - return m_objects[idx]; - }; +template +class wxVector +{ +public: + typedef size_t size_type; + typedef T value_type; + typedef value_type* iterator; + typedef const value_type* const_iterator; + typedef value_type& reference; - void Append(void *obj) - { - wxASSERT(m_size < m_capacity); - m_objects[m_size] = obj; - m_size++; - }; + wxVector() : m_size(0), m_capacity(0), m_values(NULL) {} - void RemoveAt(size_type idx) + wxVector(const wxVector& c) { - wxASSERT(idx >= 0 && idx < m_size); - Free(m_objects[idx]); - if (idx < m_size - 1) - memcpy( - m_objects + idx, - m_objects + idx + 1, - ( m_size - idx - 1 ) * sizeof(void*) ); - m_size--; - }; + Copy(c); + } - bool copy(const wxVectorBase& vb) + ~wxVector() { clear(); - if (! Alloc(vb.size())) - return false; - - for (size_type i = 0; i < vb.size(); i++) - { - void *o = vb.Copy(vb.GetItem(i)); - if (! o) - return false; - Append(o); - }; - - return true; - }; - -public: - wxVectorBase() : m_allocsize(16), m_size(0), m_capacity(0), m_objects(0) {} - virtual ~wxVectorBase() {} // calm down GCC + } void clear() { - for (size_type i = 0; i < size(); i++) - Free(m_objects[i]); - free(m_objects); - m_objects = 0; + delete[] m_values; + m_values = NULL; m_size = m_capacity = 0; - }; + } void reserve(size_type n) { - if ( !Alloc(n) ) + if ( n <= m_capacity ) + return; + + // increase the size twice, unless we're already too big or unless + // more is requested + // + // NB: casts to size_t are needed to suppress mingw32 warnings about + // mixing enums and ints in the same expression + const size_type increment = m_size > 0 + ? wxMin(m_size, (size_type)ALLOC_MAX_SIZE) + : (size_type)ALLOC_INITIAL_SIZE; + if ( m_capacity + increment > n ) + n = m_capacity + increment; + + value_type *mem = new value_type[n]; + + if ( m_values ) { - wxFAIL_MSG( _T("out of memory in wxVector::reserve()") ); + for ( size_type i = 0; i < m_size; ++i ) + mem[i] = m_values[i]; + delete[] m_values; } - }; + + m_values = mem; + m_capacity = n; + } size_type size() const { @@ -117,96 +89,137 @@ public: size_type capacity() const { return m_capacity; - }; + } bool empty() const { return size() == 0; - }; + } - wxVectorBase& operator = (const wxVectorBase& vb) + wxVector& operator=(const wxVector& vb) { - wxCHECK(copy(vb), *this); + Copy(vb); return *this; } + + void push_back(const value_type& v) + { + reserve(size() + 1); + m_values[m_size++] = v; + } + + void pop_back() + { + erase(end() - 1); + } + + const value_type& at(size_type idx) const + { + wxASSERT(idx < m_size); + return m_values[idx]; + } + + value_type& at(size_type idx) + { + wxASSERT(idx < m_size); + return m_values[idx]; + } + + const value_type& operator[](size_type idx) const { return at(idx); } + value_type& operator[](size_type idx) { return at(idx); } + const value_type& front() const { return at(0); } + value_type& front() { return at(0); } + const value_type& back() const { return at(size() - 1); } + value_type& back() { return at(size() - 1); } + + const_iterator begin() const { return m_values; } + iterator begin() { return m_values; } + const_iterator end() const { return m_values + size(); } + iterator end() { return m_values + size(); } + + iterator insert(iterator it, const value_type& v = value_type()) + { + size_t idx = it - begin(); + + reserve(size() + 1); + + // unless we're inserting at the end, move following values out of + // the way: + for ( size_t n = m_size; n != idx; --n ) + m_values[n] = m_values[n-1]; + + m_values[idx] = v; + m_size++; + + return begin() + idx; + } + + iterator erase(iterator it) + { + return erase(it, it + 1); + } + + iterator erase(iterator first, iterator last) + { + if ( first == last ) + return first; + wxASSERT( first < end() && last <= end() ); + + size_type index = first - begin(); + size_type count = last - first; + + // move the remaining values over to the freed space: + for ( iterator i = last; i < end(); ++i ) + *(i - count) = *i; + + // erase items behind the new end of m_values: + for ( iterator j = end() - count; j < end(); ++j ) + *j = value_type(); + + m_size -= count; + + return begin() + index; + } + +#if WXWIN_COMPATIBILITY_2_8 + wxDEPRECATED( size_type erase(size_type n) ); +#endif // WXWIN_COMPATIBILITY_2_8 + +private: + // VC6 can't compile static const int members + enum { ALLOC_INITIAL_SIZE = 16 }; + enum { ALLOC_MAX_SIZE = 4096 }; + + void Copy(const wxVector& vb) + { + clear(); + reserve(vb.size()); + + for ( const_iterator i = vb.begin(); i != vb.end(); ++i ) + push_back(*i); + } + +private: + size_type m_size, + m_capacity; + value_type *m_values; }; -#define WX_DECLARE_VECTORBASE(obj, cls)\ -private:\ - virtual void Free(void *o)\ - {\ - delete (obj *) o;\ - };\ - virtual void *Copy(const void *o) const\ - {\ - return new obj(*(obj *) o);\ - };\ -public:\ - cls() {}\ - cls(const cls& c)\ - {\ - wxCHECK2(copy(c), return);\ - }\ - ~cls()\ - {\ - clear();\ - } - -#define _WX_DECLARE_VECTOR(obj, cls, exp)\ -class exp cls : public wxVectorBase\ -{\ - WX_DECLARE_VECTORBASE(obj, cls);\ -public:\ - void push_back(const obj& o)\ - {\ - wxCHECK2(Alloc(size() + 1), return);\ - Append(new obj(o));\ - };\ - void pop_back()\ - {\ - RemoveAt(size() - 1);\ - };\ - const obj& at(size_type idx) const\ - {\ - return *(obj *) GetItem(idx);\ - };\ - obj& at(size_type idx)\ - {\ - return *(obj *) GetItem(idx);\ - };\ - const obj& operator[](size_type idx) const\ - {\ - return at(idx);\ - };\ - obj& operator[](size_type idx)\ - {\ - return at(idx);\ - };\ - const obj& front() const\ - {\ - return at(0);\ - };\ - obj& front()\ - {\ - return at(0);\ - };\ - const obj& back() const\ - {\ - return at(size() - 1);\ - };\ - obj& back()\ - {\ - return at(size() - 1);\ - };\ - size_type erase(size_type idx)\ - {\ - RemoveAt(idx);\ - return idx;\ - };\ +#if WXWIN_COMPATIBILITY_2_8 +template +typename wxVector::size_type wxVector::erase(size_type n) +{ + erase(begin() + n); + return n; } +#endif // WXWIN_COMPATIBILITY_2_8 -#define WX_DECLARE_VECTOR(obj, cls) \ - _WX_DECLARE_VECTOR(obj, cls, WXDLLEXPORT) +#endif // wxUSE_STL/!wxUSE_STL -#endif // _WX_VECTOR_H_ +#if WXWIN_COMPATIBILITY_2_8 + #define WX_DECLARE_VECTORBASE(obj, cls) typedef wxVector cls + #define _WX_DECLARE_VECTOR(obj, cls, exp) WX_DECLARE_VECTORBASE(obj, cls) + #define WX_DECLARE_VECTOR(obj, cls) WX_DECLARE_VECTORBASE(obj, cls) +#endif // WXWIN_COMPATIBILITY_2_8 +#endif // _WX_VECTOR_H_