include/wx/vector.h

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // Name:        wx/vector.h
   3 // Purpose:     STL vector clone
   4 // Author:      Lindsay Mathieson
   5 // Modified by: Vaclav Slavik - make it a template
   6 // Created:     30.07.2001
   7 // Copyright:   (c) 2001 Lindsay Mathieson <lindsay@mathieson.org>,
   8 //                  2007 Vaclav Slavik <vslavik@fastmail.fm>
   9 // Licence:     wxWindows licence
  10 ///////////////////////////////////////////////////////////////////////////////
  11
  12 #ifndef _WX_VECTOR_H_
  13 #define _WX_VECTOR_H_
  14
  15 #include "wx/defs.h"
  16
  17 #if wxUSE_STL
  18
  19 #include <vector>
  20 #define wxVector std::vector
  21
  22 #else // !wxUSE_STL
  23
  24 #include "wx/beforestd.h"
  25 #include <new> // for placement new
  26 #include "wx/afterstd.h"
  27
  28 template<typename T>
  29 class wxVector
  30 {
  31 public:
  32     typedef size_t size_type;
  33     typedef T value_type;
  34     typedef value_type* iterator;
  35     typedef const value_type* const_iterator;
  36     typedef value_type& reference;
  37
  38     wxVector() : m_size(0), m_capacity(0), m_values(NULL) {}
  39
  40     wxVector(const wxVector& c)
  41     {
  42         Copy(c);
  43     }
  44
  45     ~wxVector()
  46     {
  47         clear();
  48     }
  49
  50     void clear()
  51     {
  52         // call destructors of stored objects:
  53         for ( size_type i = 0; i < m_size; i++ )
  54         {
  55             m_values[i].~T();
  56         }
  57
  58         free(m_values);
  59         m_values = NULL;
  60         m_size = m_capacity = 0;
  61     }
  62
  63     void reserve(size_type n)
  64     {
  65         if ( n <= m_capacity )
  66             return;
  67
  68         // increase the size twice, unless we're already too big or unless
  69         // more is requested
  70         //
  71         // NB: casts to size_type are needed to suppress mingw32 warnings about
  72         //     mixing enums and ints in the same expression
  73         const size_type increment = m_size > 0
  74                                      ? wxMin(m_size, (size_type)ALLOC_MAX_SIZE)
  75                                      : (size_type)ALLOC_INITIAL_SIZE;
  76         if ( m_capacity + increment > n )
  77             n = m_capacity + increment;
  78
  79         m_values = (value_type*)realloc(m_values, n * sizeof(value_type));
  80
  81         m_capacity = n;
  82     }
  83
  84     size_type size() const
  85     {
  86         return m_size;
  87     }
  88
  89     size_type capacity() const
  90     {
  91         return m_capacity;
  92     }
  93
  94     bool empty() const
  95     {
  96         return size() == 0;
  97     }
  98
  99     wxVector& operator=(const wxVector& vb)
 100     {
 101         Copy(vb);
 102         return *this;
 103     }
 104
 105     void push_back(const value_type& v)
 106     {
 107         reserve(size() + 1);
 108
 109         // use placement new to initialize new object in preallocated place in
 110         // m_values and store 'v' in it:
 111         void* const place = m_values + m_size;
 112         new(place) value_type(v);
 113
 114         // only increase m_size if the ctor didn't throw an exception; notice
 115         // that if it _did_ throw, everything is OK, because we only increased
 116         // vector's capacity so far and possibly written some data to
 117         // uninitialized memory at the end of m_values
 118         m_size++;
 119     }
 120
 121     void pop_back()
 122     {
 123         erase(end() - 1);
 124     }
 125
 126     const value_type& at(size_type idx) const
 127     {
 128         wxASSERT(idx < m_size);
 129         return m_values[idx];
 130     }
 131
 132     value_type& at(size_type idx)
 133     {
 134         wxASSERT(idx < m_size);
 135         return m_values[idx];
 136     }
 137
 138     const value_type& operator[](size_type idx) const  { return at(idx); }
 139     value_type& operator[](size_type idx) { return at(idx); }
 140     const value_type& front() const { return at(0); }
 141     value_type& front() { return at(0); }
 142     const value_type& back() const { return at(size() - 1); }
 143     value_type& back() { return at(size() - 1); }
 144
 145     const_iterator begin() const { return m_values; }
 146     iterator begin() { return m_values; }
 147     const_iterator end() const { return m_values + size(); }
 148     iterator end() { return m_values + size(); }
 149
 150     iterator insert(iterator it, const value_type& v = value_type())
 151     {
 152         // NB: this must be done before reserve(), because reserve()
 153         //     invalidates iterators!
 154         const size_t idx = it - begin();
 155         const size_t after = end() - it;
 156
 157         reserve(size() + 1);
 158
 159         // unless we're inserting at the end, move following elements out of
 160         // the way:
 161         if ( after > 0 )
 162         {
 163             memmove(m_values + idx + 1,
 164                     m_values + idx,
 165                     after * sizeof(value_type));
 166         }
 167
 168 #if wxUSE_EXCEPTIONS
 169         try
 170         {
 171 #endif
 172             // use placement new to initialize new object in preallocated place
 173             // in m_values and store 'v' in it:
 174             void* const place = m_values + idx;
 175             new(place) value_type(v);
 176 #if wxUSE_EXCEPTIONS
 177         }
 178         catch ( ... )
 179         {
 180             // if the ctor threw an exception, we need to move all the elements
 181             // back to their original positions in m_values
 182             if ( after > 0 )
 183             {
 184                 memmove(m_values + idx,
 185                         m_values + idx + 1,
 186                         after * sizeof(value_type));
 187             }
 188
 189             throw; // rethrow the exception
 190         }
 191 #endif // wxUSE_EXCEPTIONS
 192
 193         // increment m_size only if ctor didn't throw -- if it did, we'll be
 194         // left with m_values larger than necessary, but number of elements will
 195         // be the same
 196         m_size++;
 197
 198         return begin() + idx;
 199     }
 200
 201     iterator erase(iterator it)
 202     {
 203         return erase(it, it + 1);
 204     }
 205
 206     iterator erase(iterator first, iterator last)
 207     {
 208         if ( first == last )
 209             return first;
 210         wxASSERT( first < end() && last <= end() );
 211
 212         const size_type idx = first - begin();
 213         const size_type count = last - first;
 214         const size_type after = end() - last;
 215
 216         // erase elements by calling their destructors:
 217         for ( iterator i = first; i < last; ++i )
 218             i->~value_type();
 219
 220         // once that's done, move following elements over to the freed space:
 221         if ( after > 0 )
 222         {
 223             memmove(m_values + idx,
 224                     m_values + idx + count,
 225                     after * sizeof(value_type));
 226         }
 227
 228         m_size -= count;
 229
 230         return begin() + idx;
 231     }
 232
 233 #if WXWIN_COMPATIBILITY_2_8
 234     wxDEPRECATED( size_type erase(size_type n) );
 235 #endif // WXWIN_COMPATIBILITY_2_8
 236
 237 private:
 238     // VC6 can't compile static const int members
 239     enum { ALLOC_INITIAL_SIZE = 16 };
 240     enum { ALLOC_MAX_SIZE = 4096 };
 241
 242     void Copy(const wxVector& vb)
 243     {
 244         clear();
 245         reserve(vb.size());
 246
 247         for ( const_iterator i = vb.begin(); i != vb.end(); ++i )
 248             push_back(*i);
 249     }
 250
 251 private:
 252     size_type m_size,
 253               m_capacity;
 254     value_type *m_values;
 255 };
 256
 257 #if WXWIN_COMPATIBILITY_2_8
 258 template<typename T>
 259 inline typename wxVector<T>::size_type wxVector<T>::erase(size_type n)
 260 {
 261     erase(begin() + n);
 262     return n;
 263 }
 264 #endif // WXWIN_COMPATIBILITY_2_8
 265
 266 #endif // wxUSE_STL/!wxUSE_STL
 267
 268 #if WXWIN_COMPATIBILITY_2_8
 269     #define WX_DECLARE_VECTORBASE(obj, cls) typedef wxVector<obj> cls
 270     #define _WX_DECLARE_VECTOR(obj, cls, exp) WX_DECLARE_VECTORBASE(obj, cls)
 271     #define WX_DECLARE_VECTOR(obj, cls) WX_DECLARE_VECTORBASE(obj, cls)
 272 #endif // WXWIN_COMPATIBILITY_2_8
 273
 274 #endif // _WX_VECTOR_H_