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

details vigra/array_vector.hxx VIGRA

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.3, Aug 18 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.3 (18 Aug 2005)