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