uvector.h

   1 // This file is part of the ustl library, an STL implementation.
   2 //
   3 // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
   4 // This file is free software, distributed under the MIT License.
   5 //
   6 // uvector.h
   7 //
   8
   9 #ifndef UVECTOR_H_00BB13AF082BEB7829C031B265518169
  10 #define UVECTOR_H_00BB13AF082BEB7829C031B265518169
  11
  12 #include "memblock.h"
  13 #include "umemory.h"
  14
  15 namespace ustl {
  16
  17 /// \class vector uvector.h ustl.h
  18 /// \ingroup Sequences
  19 ///
  20 /// \brief STL vector equivalent.
  21 ///
  22 /// Provides a typed array-like interface to a managed memory block, including
  23 /// element access, iteration, modification, resizing, and serialization. In
  24 /// this design elements frequently undergo bitwise move, so don't put it in
  25 /// here if it doesn't support it. This mostly means having no self-pointers.
  26 ///
  27 template <typename T>
  28 class vector {
  29 public:
  30     typedef T                           value_type;
  31     typedef value_type*                 pointer;
  32     typedef const value_type*           const_pointer;
  33     typedef value_type&                 reference;
  34     typedef const value_type&           const_reference;
  35     typedef pointer                     iterator;
  36     typedef const_pointer               const_iterator;
  37     typedef memblock::size_type         size_type;
  38     typedef memblock::written_size_type written_size_type;
  39     typedef memblock::difference_type   difference_type;
  40     typedef ::ustl::reverse_iterator<iterator>  reverse_iterator;
  41     typedef ::ustl::reverse_iterator<const_iterator>    const_reverse_iterator;
  42 public:
  43     inline                      vector (void);
  44     inline explicit             vector (size_type n);
  45                                 vector (size_type n, const T& v);
  46                                 vector (const vector<T>& v);
  47                                 vector (const_iterator i1, const_iterator i2);
  48     inline                     ~vector (void) throw();
  49     inline const vector<T>&     operator= (const vector<T>& v);
  50     inline bool                 operator== (const vector<T>& v) { return (m_Data == v.m_Data); }
  51     inline                      operator cmemlink (void) const  { return (cmemlink (m_Data)); }
  52     inline                      operator cmemlink (void)        { return (cmemlink (m_Data)); }
  53     inline                      operator memlink (void)         { return (memlink (m_Data)); }
  54     inline void                 reserve (size_type n, bool bExact = true);
  55     inline void                 resize (size_type n, bool bExact = true);
  56     inline size_type            capacity (void) const           { return (m_Data.capacity() / sizeof(T));       }
  57     inline size_type            size (void) const               { return (m_Data.size() / sizeof(T));           }
  58     inline size_type            max_size (void) const           { return (m_Data.max_size() / sizeof(T));       }
  59     inline bool                 empty (void) const              { return (m_Data.empty());                      }
  60     inline iterator             begin (void)                    { return (iterator (m_Data.begin()));           }
  61     inline const_iterator       begin (void) const              { return (const_iterator (m_Data.begin()));     }
  62     inline iterator             end (void)                      { return (iterator (m_Data.end()));             }
  63     inline const_iterator       end (void) const                { return (const_iterator (m_Data.end()));       }
  64     inline reverse_iterator             rbegin (void)           { return (reverse_iterator (end()));            }
  65     inline const_reverse_iterator       rbegin (void) const     { return (const_reverse_iterator (end()));      }
  66     inline reverse_iterator             rend (void)             { return (reverse_iterator (begin()));          }
  67     inline const_reverse_iterator       rend (void) const       { return (const_reverse_iterator (begin()));    }
  68     inline iterator             iat (size_type i)               { assert (i <= size()); return (begin() + i); }
  69     inline const_iterator       iat (size_type i) const         { assert (i <= size()); return (begin() + i); }
  70     inline reference            at (size_type i)                { assert (i < size()); return (begin()[i]); }
  71     inline const_reference      at (size_type i) const          { assert (i < size()); return (begin()[i]); }
  72     inline reference            operator[] (size_type i)        { return (at (i)); }
  73     inline const_reference      operator[] (size_type i) const  { return (at (i)); }
  74     inline reference            front (void)                    { return (at(0)); }
  75     inline const_reference      front (void) const              { return (at(0)); }
  76     inline reference            back (void)                     { assert (!empty()); return (end()[-1]); }
  77     inline const_reference      back (void) const               { assert (!empty()); return (end()[-1]); }
  78     inline void                 push_back (const T& v = T());
  79     inline void                 pop_back (void)                 { m_Data.memlink::resize (m_Data.size() - sizeof(T)); }
  80     inline void                 clear (void)                    { m_Data.clear(); }
  81     inline void                 deallocate (void) throw();
  82     inline void                 assign (const_iterator i1, const_iterator i2);
  83     inline void                 assign (size_type n, const T& v);
  84     inline void                 swap (vector<T>& v)             { m_Data.swap (v.m_Data); }
  85     inline iterator             insert (iterator ip, const T& v = T());
  86     inline iterator             insert (iterator ip, size_type n, const T& v);
  87     inline iterator             insert (iterator ip, const_iterator i1, const_iterator i2);
  88     inline iterator             erase (iterator ep, size_type n = 1);
  89     inline iterator             erase (iterator ep1, iterator ep2);
  90     inline void                 manage (pointer p, size_type n)         { m_Data.manage (p, n * sizeof(T)); }
  91     inline bool                 is_linked (void) const                  { return (m_Data.is_linked()); }
  92     inline void                 unlink (void)                           { m_Data.unlink(); }
  93     inline void                 copy_link (void)                        { m_Data.copy_link(); }
  94     inline void                 link (const_pointer p, size_type n)     { m_Data.link (p, n * sizeof(T)); }
  95     inline void                 link (pointer p, size_type n)           { m_Data.link (p, n * sizeof(T)); }
  96     inline void                 link (const vector<T>& v)               { m_Data.link (v); }
  97     inline void                 link (vector<T>& v)                     { m_Data.link (v); }
  98     inline void                 link (const_pointer first, const_pointer last)  { m_Data.link (first, last); }
  99     inline void                 link (pointer first, pointer last)              { m_Data.link (first, last); }
 100     inline void                 read (istream& is)                      { container_read (is, *this); }
 101     inline void                 write (ostream& os) const               { container_write (os, *this); }
 102     inline void                 text_write (ostringstream& os) const    { container_text_write (os, *this); }
 103     inline size_t               stream_size (void) const                { return (container_stream_size (*this)); }
 104 private:
 105     inline iterator             insert_space (iterator ip, size_type n);
 106 private:
 107     memblock                    m_Data; ///< Raw element data, consecutively stored.
 108 };
 109
 110 /// Allocates space for at least \p n elements.
 111 template <typename T>
 112 inline void vector<T>::reserve (size_type n, bool bExact)
 113 {
 114     const size_type oldCapacity = capacity();
 115     m_Data.reserve (n * sizeof(T), bExact);
 116     if (capacity() > oldCapacity)
 117         construct (begin() + oldCapacity, begin() + capacity());
 118 }
 119
 120 /// Resizes the vector to contain \p n elements.
 121 template <typename T>
 122 inline void vector<T>::resize (size_type n, bool bExact)
 123 {
 124     if (m_Data.capacity() < n * sizeof(T))
 125         reserve (n, bExact);
 126     m_Data.memlink::resize (n * sizeof(T));
 127 }
 128
 129 /// Calls element destructors and frees storage.
 130 template <typename T>
 131 inline void vector<T>::deallocate (void) throw()
 132 {
 133     if (!is_linked())
 134         destroy (begin(), begin() + capacity());
 135     m_Data.deallocate();
 136 }
 137
 138 /// Initializes empty vector.
 139 template <typename T>
 140 inline vector<T>::vector (void)
 141 : m_Data ()
 142 {
 143 }
 144
 145 /// Initializes a vector of size \p n.
 146 template <typename T>
 147 inline vector<T>::vector (size_type n)
 148 : m_Data ()
 149 {
 150     resize (n);
 151 }
 152
 153 /// Copies \p n elements from \p v.
 154 template <typename T>
 155 vector<T>::vector (size_type n, const T& v)
 156 : m_Data ()
 157 {
 158     resize (n);
 159     ::ustl::fill (begin(), end(), v);
 160 }
 161
 162 /// Copies \p v.
 163 template <typename T>
 164 vector<T>::vector (const vector<T>& v)
 165 : m_Data ()
 166 {
 167     resize (v.size());
 168     ::ustl::copy (v.begin(), v.end(), begin());
 169 }
 170
 171 /// Copies range [\p i1, \p i2]
 172 template <typename T>
 173 vector<T>::vector (const_iterator i1, const_iterator i2)
 174 : m_Data ()
 175 {
 176     resize (distance (i1, i2));
 177     ::ustl::copy (i1, i2, begin());
 178 }
 179
 180 /// Destructor
 181 template <typename T>
 182 inline vector<T>::~vector (void) throw()
 183 {
 184     if (!is_linked())
 185         destroy (begin(), begin() + capacity());
 186 }
 187
 188 /// Copies the range [\p i1, \p i2]
 189 template <typename T>
 190 inline void vector<T>::assign (const_iterator i1, const_iterator i2)
 191 {
 192     assert (i1 <= i2);
 193     resize (distance (i1, i2));
 194     ::ustl::copy (i1, i2, begin());
 195 }
 196
 197 /// Copies \p n elements with value \p v.
 198 template <typename T>
 199 inline void vector<T>::assign (size_type n, const T& v)
 200 {
 201     resize (n);
 202     ::ustl::fill (begin(), end(), v);
 203 }
 204
 205 /// Copies contents of \p v.
 206 template <typename T>
 207 inline const vector<T>& vector<T>::operator= (const vector<T>& v)
 208 {
 209     assign (v.begin(), v.end());
 210     return (*this);
 211 }
 212
 213 /// Inserts \p n uninitialized elements at \p ip.
 214 template <typename T>
 215 inline typename vector<T>::iterator vector<T>::insert_space (iterator ip, size_type n)
 216 {
 217     const uoff_t ipmi = distance (m_Data.begin(), memblock::iterator(ip));
 218     reserve (size() + n, false);
 219     return (iterator (m_Data.insert (m_Data.iat(ipmi), n * sizeof(T))));
 220 }
 221
 222 /// Inserts \p n elements with value \p v at offsets \p ip.
 223 template <typename T>
 224 inline typename vector<T>::iterator vector<T>::insert (iterator ip, size_type n, const T& v)
 225 {
 226     ip = insert_space (ip, n);
 227     ::ustl::fill (ip, ip + n, v);
 228     return (ip);
 229 }
 230
 231 /// Inserts value \p v at offset \p ip.
 232 template <typename T>
 233 inline typename vector<T>::iterator vector<T>::insert (iterator ip, const T& v)
 234 {
 235     *(ip = insert_space (ip, 1)) = v;
 236     return (ip);
 237 }
 238
 239 /// Inserts range [\p i1, \p i2] at offset \p ip.
 240 template <typename T>
 241 inline typename vector<T>::iterator vector<T>::insert (iterator ip, const_iterator i1, const_iterator i2)
 242 {
 243     assert (i1 <= i2);
 244     ip = insert_space (ip, distance (i1, i2));
 245     ::ustl::copy (i1, i2, ip);
 246     return (ip);
 247 }
 248
 249 /// Removes \p count elements at offset \p ep.
 250 template <typename T>
 251 inline typename vector<T>::iterator vector<T>::erase (iterator ep, size_type n)
 252 {
 253     return (iterator (m_Data.erase (memblock::iterator(ep), n * sizeof(T))));
 254 }
 255
 256 /// Removes elements from \p ep1 to \p ep2.
 257 template <typename T>
 258 inline typename vector<T>::iterator vector<T>::erase (iterator ep1, iterator ep2)
 259 {
 260     assert (ep1 <= ep2);
 261     return (erase (ep1, distance(ep1, ep2)));
 262 }
 263
 264 /// Inserts value \p v at the end of the vector.
 265 template <typename T>
 266 inline void vector<T>::push_back (const T& v)
 267 {
 268     resize (size() + 1, false);
 269     back() = v;
 270 }
 271
 272 /// Use with vector classes to allocate and link to stack space. \p n is in elements.
 273 #define typed_alloca_link(m,T,n)        (m).link ((T*) alloca ((n) * sizeof(T)), (n))
 274
 275 } // namespace ustl
 276
 277 #endif
 278