[ VIGRA Homepage | Class Index | Function Index | File Index | Main Page ]

| vigra/array_vector.hxx |
--- | --- | ---

    00001 /************************************************************************/
    00002 /*                                                                      */
    00003 /*               Copyright 2002-2004 by Ullrich Koethe                  */
    00004 /*       Cognitive Systems Group, University of Hamburg, Germany        */
    00005 /*                                                                      */
    00006 /*    This file is part of the VIGRA computer vision library.           */
    00007 /*    ( Version 1.3.2, Jan 27 2005 )                                    */
    00008 /*    You may use, modify, and distribute this software according       */
    00009 /*    to the terms stated in the LICENSE file included in               */
    00010 /*    the VIGRA distribution.                                           */
    00011 /*                                                                      */
    00012 /*    The VIGRA Website is                                              */
    00013 /*        http://kogs-www.informatik.uni-hamburg.de/~koethe/vigra/      */
    00014 /*    Please direct questions, bug reports, and contributions to        */
    00015 /*        koethe@informatik.uni-hamburg.de                              */
    00016 /*                                                                      */
    00017 /*  THIS SOFTWARE IS PROVIDED AS IS AND WITHOUT ANY EXPRESS OR          */
    00018 /*  IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED      */
    00019 /*  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. */
    00020 /*                                                                      */
    00021 /************************************************************************/
    00022
    00023 #ifndef VIGRA_ARRAY_VECTOR_HXX
    00024 #define VIGRA_ARRAY_VECTOR_HXX
    00025
    00026 #include <memory>
    00027 #include <algorithm>
    00028 #include <vigra/memory.hxx>
    00029
    00030 namespace vigra
    00031 {
    00032
    00033 /** Replacement for <tt>std::vector</tt>.
    00034
    00035     This template implements the same functionality as <tt>std::vector</tt>.
    00036     However, it gives two usful guarantees, that <tt>std::vector</tt> fails
    00037     to provide:
    00038
    00039     <ul>
    00040     <li>The memory is always allocated as one contigous piece</li>
    00041     <li>The iterator is always a <TT>T *</TT> </li>
    00042     </ul>
    00043
    00044     This means that memory managed by <tt>ArrayVector</tt> can be passed
    00045     to algorithms that expect raw memory. This is especially important
    00046     when lagacy or C code has to be called, but it is also useful for certain
    00047     optimizations.
    00048
    00049     Refer to the documentation of <tt>std::vector</tt> for a detailed
    00050     description of <tt>ArrayVector</tt> functionality.
    00051
    00052     <b>\#include</b> "<a href="array_vector_8hxx-source.html">vigra/array_vector.hxx</a>"<br>
    00053     Namespace: vigra
    00054 */
    00055 template <class T, class Alloc = std::allocator<T> >
    00056 class ArrayVector
    00057 {
    00058     typedef ArrayVector<T, Alloc> this_type;
    00059
    00060 public:
    00061     typedef T value_type;
    00062     typedef value_type & reference;
    00063     typedef value_type const & const_reference;
    00064     typedef value_type * pointer;
    00065     typedef value_type const * const_pointer;
    00066     typedef value_type * iterator;
    00067     typedef value_type const * const_iterator;
    00068     typedef unsigned int size_type;
    00069     typedef int          difference_type;
    00070     typedef Alloc        allocator_type;
    00071     typedef std::reverse_iterator<iterator> reverse_iterator;
    00072     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    00073
    00074 public:
    00075     ArrayVector();
    00076
    00077     explicit ArrayVector(Alloc const & alloc);
    00078
    00079     explicit ArrayVector( size_type size, Alloc const & alloc = Alloc());
    00080
    00081     ArrayVector( size_type size, value_type const & initial, Alloc const & alloc = Alloc());
    00082
    00083     ArrayVector( this_type const & rhs );
    00084
    00085     template <class InputIterator>
    00086     ArrayVector(InputIterator i, InputIterator end);
    00087
    00088     template <class InputIterator>
    00089     ArrayVector(InputIterator i, InputIterator end, Alloc const & alloc);
    00090
    00091     this_type & operator=( this_type const & rhs );
    00092
    00093     ~ArrayVector();
    00094
    00095     inline const_pointer data() const
    00096     {
    00097         return data_;
    00098     }
    00099
    00100     inline pointer data()
    00101     {
    00102         return data_;
    00103     }
    00104
    00105     inline const_iterator begin() const
    00106     {
    00107         return data();
    00108     }
    00109
    00110     inline iterator begin()
    00111     {
    00112         return data();
    00113     }
    00114
    00115     inline const_iterator end() const
    00116     {
    00117         return data() + size();
    00118     }
    00119
    00120     inline iterator end()
    00121     {
    00122         return data() + size();
    00123     }
    00124
    00125     inline reverse_iterator rbegin()
    00126     {
    00127         return (reverse_iterator(end()));
    00128     }
    00129
    00130     inline const_reverse_iterator rbegin() const
    00131     {
    00132         return (const_reverse_iterator(end()));
    00133     }
    00134
    00135     inline reverse_iterator rend()
    00136     {
    00137         return (reverse_iterator(begin()));
    00138     }
    00139
    00140     inline const_reverse_iterator rend() const
    00141     {
    00142         return (const_reverse_iterator(begin()));
    00143     }
    00144
    00145     reference front()
    00146     {
    00147         return *data_;
    00148     }
    00149
    00150     const_reference front() const
    00151     {
    00152         return *data_;
    00153     }
    00154
    00155     reference back()
    00156     {
    00157         return data_[size_-1];
    00158     }
    00159
    00160     const_reference back() const
    00161     {
    00162         return data_[size_-1];
    00163     }
    00164
    00165     reference operator[]( size_type i )
    00166     {
    00167         return data()[i];
    00168     }
    00169
    00170     const_reference operator[]( size_type i ) const
    00171     {
    00172         return data()[i];
    00173     }
    00174
    00175     void pop_back();
    00176
    00177     void push_back( value_type const & t );
    00178
    00179     iterator insert(iterator p, value_type const & v);
    00180
    00181     iterator insert(iterator p, size_type n, value_type const & v);
    00182
    00183     template <class InputIterator>
    00184     iterator insert(iterator p, InputIterator i, InputIterator iend);
    00185
    00186     iterator erase(iterator p);
    00187
    00188     iterator erase(iterator p, iterator q);
    00189
    00190     void clear();
    00191
    00192     void reserve( size_type new_capacity );
    00193
    00194     void reserve();
    00195
    00196     void resize( size_type new_size, value_type const & initial );
    00197
    00198     void resize( size_type new_size )
    00199     {
    00200         resize(new_size, value_type());
    00201     }
    00202
    00203     bool empty() const
    00204     {
    00205         return size_ == 0;
    00206     }
    00207
    00208     size_type size() const
    00209     {
    00210         return size_;
    00211     }
    00212
    00213     size_type capacity() const
    00214     {
    00215         return capacity_;
    00216     }
    00217
    00218     void swap(this_type & rhs);
    00219
    00220   private:
    00221
    00222     void deallocate(pointer data, size_type size);
    00223
    00224     pointer reserve_raw(size_type capacity);
    00225
    00226     Alloc alloc_;
    00227     size_type size_, capacity_;
    00228     pointer data_;
    00229 };
    00230
    00231 template <class T, class Alloc>
    00232 ArrayVector<T, Alloc>::ArrayVector()
    00233 : alloc_(Alloc()),
    00234   size_(0),
    00235   capacity_(5),
    00236   data_(reserve_raw(5))
    00237 {}
    00238
    00239 template <class T, class Alloc>
    00240 ArrayVector<T, Alloc>::ArrayVector(Alloc const & alloc)
    00241 : alloc_(alloc),
    00242   size_(0),
    00243   capacity_(5),
    00244   data_(reserve_raw(5))
    00245 {}
    00246
    00247 template <class T, class Alloc>
    00248 ArrayVector<T, Alloc>::ArrayVector( size_type size, Alloc const & alloc)
    00249 : alloc_(alloc),
    00250   size_(size),
    00251   capacity_(size),
    00252   data_(reserve_raw(size))
    00253 {
    00254     if(size_ > 0)
    00255         std::uninitialized_fill(data_, data_+size_, value_type());
    00256 }
    00257
    00258 template <class T, class Alloc>
    00259 ArrayVector<T, Alloc>::ArrayVector( size_type size,
    00260                          value_type const & initial, Alloc const & alloc)
    00261 : alloc_(alloc),
    00262   size_(size),
    00263   capacity_(size),
    00264   data_(reserve_raw(size))
    00265 {
    00266     if(size_ > 0)
    00267         std::uninitialized_fill(data_, data_+size_, initial);
    00268 }
    00269
    00270 template <class T, class Alloc>
    00271 ArrayVector<T, Alloc>::ArrayVector( this_type const & rhs )
    00272 : alloc_(rhs.alloc_),
    00273   size_(rhs.size_),
    00274   capacity_(rhs.capacity_),
    00275   data_(reserve_raw(rhs.capacity_))
    00276 {
    00277     if(size_ > 0)
    00278         std::uninitialized_copy(rhs.data_, rhs.data_+size_, data_);
    00279 }
    00280
    00281 template <class T, class Alloc>
    00282 template <class InputIterator>
    00283 ArrayVector<T, Alloc>::ArrayVector(InputIterator i, InputIterator end)
    00284 : alloc_(),
    00285   size_(std::distance(i, end)),
    00286   capacity_(size_),
    00287   data_(reserve_raw(size_))
    00288 {
    00289     std::uninitialized_copy(i, end, data_);
    00290 }
    00291
    00292 template <class T, class Alloc>
    00293 template <class InputIterator>
    00294 ArrayVector<T, Alloc>::ArrayVector(InputIterator i, InputIterator end, Alloc const & alloc)
    00295 : alloc_(alloc),
    00296   size_(std::distance(i, end)),
    00297   capacity_(size_),
    00298   data_(reserve_raw(size_))
    00299 {
    00300     std::uninitialized_copy(i, end, data_);
    00301 }
    00302
    00303
    00304 template <class T, class Alloc>
    00305 ArrayVector<T, Alloc> & ArrayVector<T, Alloc>::operator=( this_type const & rhs )
    00306 {
    00307     if(this == &rhs)
    00308         return *this;
    00309     ArrayVector new_vector(rhs);
    00310     swap(new_vector);
    00311     return *this;
    00312 }
    00313
    00314 template <class T, class Alloc>
    00315 ArrayVector<T, Alloc>::~ArrayVector()
    00316 {
    00317     deallocate(data_, size_);
    00318 }
    00319
    00320 template <class T, class Alloc>
    00321 void ArrayVector<T, Alloc>::pop_back()
    00322 {
    00323     --size_;
    00324     alloc_.destroy(data_ + size_);
    00325 }
    00326
    00327 template <class T, class Alloc>
    00328 void ArrayVector<T, Alloc>::push_back( value_type const & t )
    00329 {
    00330     reserve();
    00331     alloc_.construct(data_ + size_, t);
    00332     ++size_;
    00333 }
    00334
    00335 template <class T, class Alloc>
    00336 void ArrayVector<T, Alloc>::clear()
    00337 {
    00338     detail::destroy_n(data_, size_);
    00339     size_ = 0;
    00340 }
    00341
    00342 template <class T, class Alloc>
    00343 typename ArrayVector<T, Alloc>::iterator
    00344 ArrayVector<T, Alloc>::insert(iterator p, value_type const & v)
    00345 {
    00346     difference_type pos = p - begin();
    00347     if(p == end())
    00348     {
    00349         push_back(v);
    00350         p = begin() + pos;
    00351     }
    00352     else
    00353     {
    00354         push_back(back());
    00355         p = begin() + pos;
    00356         std::copy_backward(p, end() - 2, end() - 1);
    00357         *p = v;
    00358     }
    00359     return p;
    00360 }
    00361
    00362 template <class T, class Alloc>
    00363 typename ArrayVector<T, Alloc>::iterator
    00364 ArrayVector<T, Alloc>::insert(iterator p, size_type n, value_type const & v)
    00365 {
    00366     difference_type pos = p - begin();
    00367     size_type new_size = size() + n;
    00368     if(new_size >= capacity_)
    00369     {
    00370         pointer new_data = reserve_raw(new_size);
    00371         std::uninitialized_copy(begin(), p, new_data);
    00372         std::uninitialized_fill(new_data + pos, new_data + pos + n, v);
    00373         std::uninitialized_copy(p, end(), new_data + pos + n);
    00374         deallocate(data_, size_);
    00375         capacity_ = new_size;
    00376         data_ = new_data;
    00377     }
    00378     else if(pos + n >= size_)
    00379     {
    00380         size_type diff = pos + n - size_;
    00381         std::uninitialized_copy(p, end(), end() + diff);
    00382         std::uninitialized_fill(end(), end() + diff, v);
    00383         std::fill(p, end(), v);
    00384     }
    00385     else
    00386     {
    00387         size_type diff = size_ - (pos + n);
    00388         std::uninitialized_copy(end() - n, end(), end());
    00389         std::copy_backward(p, p + diff, end());
    00390         std::fill(p, p + n, v);
    00391     }
    00392     size_ = new_size;
    00393     return begin() + pos;
    00394 }
    00395
    00396 template <class T, class Alloc>
    00397 template <class InputIterator>
    00398 typename ArrayVector<T, Alloc>::iterator
    00399 ArrayVector<T, Alloc>::insert(iterator p, InputIterator i, InputIterator iend)
    00400 {
    00401     difference_type n = iend - i;
    00402     difference_type pos = p - begin();
    00403     size_type new_size = size() + n;
    00404     if(new_size >= capacity_)
    00405     {
    00406         pointer new_data = reserve_raw(new_size);
    00407         std::uninitialized_copy(begin(), p, new_data);
    00408         std::uninitialized_copy(i, iend, new_data + pos);
    00409         std::uninitialized_copy(p, end(), new_data + pos + n);
    00410         deallocate(data_, size_);
    00411         capacity_ = new_size;
    00412         data_ = new_data;
    00413     }
    00414     else if(pos + n >= size_)
    00415     {
    00416         size_type diff = pos + n - size_;
    00417         std::uninitialized_copy(p, end(), end() + diff);
    00418         std::uninitialized_copy(iend - diff, iend, end());
    00419         std::copy(i, iend - diff, p);
    00420     }
    00421     else
    00422     {
    00423         size_type diff = size_ - (pos + n);
    00424         std::uninitialized_copy(end() - n, end(), end());
    00425         std::copy_backward(p, p + diff, end());
    00426         std::copy(i, iend, p);
    00427     }
    00428     size_ = new_size;
    00429     return begin() + pos;
    00430 }
    00431
    00432 template <class T, class Alloc>
    00433 typename ArrayVector<T, Alloc>::iterator
    00434 ArrayVector<T, Alloc>::erase(iterator p)
    00435 {
    00436     std::copy(p+1, end(), p);
    00437     pop_back();
    00438     return p;
    00439 }
    00440
    00441 template <class T, class Alloc>
    00442 typename ArrayVector<T, Alloc>::iterator
    00443 ArrayVector<T, Alloc>::erase(iterator p, iterator q)
    00444 {
    00445     std::copy(q, end(), p);
    00446     size_type eraseCount = q - p;
    00447     detail::destroy_n(end() - eraseCount, eraseCount);
    00448     size_ -= eraseCount;
    00449     return p;
    00450 }
    00451
    00452 template <class T, class Alloc>
    00453 void ArrayVector<T, Alloc>::reserve( size_type new_capacity )
    00454 {
    00455     if(new_capacity <= capacity_)
    00456         return;
    00457     pointer new_data = reserve_raw(new_capacity);
    00458     if(size_ > 0)
    00459         std::uninitialized_copy(data_, data_+size_, new_data);
    00460     deallocate(data_, size_);
    00461     data_ = new_data;
    00462     capacity_ = new_capacity;
    00463 }
    00464
    00465 template <class T, class Alloc>
    00466 void ArrayVector<T, Alloc>::reserve()
    00467 {
    00468     if(size_ == capacity_)
    00469         reserve(2*capacity_);
    00470 }
    00471
    00472 template <class T, class Alloc>
    00473 void ArrayVector<T, Alloc>::resize( size_type new_size, value_type const & initial)
    00474 {
    00475     if(new_size < size_)
    00476         erase(begin() + new_size, end());
    00477     else if(size_ < new_size)
    00478     {
    00479         insert(end(), new_size - size(), initial);
    00480     }
    00481 }
    00482
    00483 template <class T, class Alloc>
    00484 void ArrayVector<T, Alloc>::swap(this_type & rhs)
    00485 {
    00486     std::swap(size_, rhs.size_);
    00487     std::swap(capacity_, rhs.capacity_);
    00488     std::swap(data_, rhs.data_);
    00489 }
    00490
    00491 template <class T, class Alloc>
    00492 void ArrayVector<T, Alloc>::deallocate(pointer data, size_type size)
    00493 {
    00494     if(data)
    00495     {
    00496         detail::destroy_n(data, size);
    00497         alloc_.deallocate(data, size);
    00498     }
    00499 }
    00500
    00501 template <class T, class Alloc>
    00502 typename ArrayVector<T, Alloc>::pointer
    00503 ArrayVector<T, Alloc>::reserve_raw(size_type capacity)
    00504 {
    00505     pointer data = 0;
    00506     if(capacity)
    00507     {
    00508         data = alloc_.allocate(capacity);
    00509     }
    00510     return data;
    00511 }
    00512
    00513 } // namespace vigra
    00514
    00515
    00516 #endif /* VIGRA_ARRAY_VECTOR_HXX */

© Ullrich Köthe (koethe@informatik.uni-hamburg.de) Cognitive Systems Group, University of Hamburg, Germany | html generated using doxygen and Python VIGRA 1.3.2 (27 Jan 2005)