[ 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.5.0, Dec 07 2006 )                                    */
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.hxx"
00042 #include <memory>
00043 #include <algorithm>
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     enum { minimumCapacity = 2 };
00075 
00076 public:
00077     typedef T value_type;
00078     typedef value_type & reference;
00079     typedef value_type const & const_reference;
00080     typedef value_type * pointer;
00081     typedef value_type const * const_pointer;
00082     typedef value_type * iterator;
00083     typedef value_type const * const_iterator;
00084     typedef unsigned int size_type;
00085     typedef int          difference_type;
00086     typedef Alloc        allocator_type;
00087     typedef std::reverse_iterator<iterator> reverse_iterator;
00088     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00089 
00090 public:
00091     ArrayVector();
00092 
00093     explicit ArrayVector(Alloc const & alloc);
00094 
00095     explicit ArrayVector( size_type size, Alloc const & alloc = Alloc());
00096 
00097     ArrayVector( size_type size, value_type const & initial, Alloc const & alloc = Alloc());
00098 
00099     ArrayVector( this_type const & rhs );
00100 
00101     template <class InputIterator>
00102     ArrayVector(InputIterator i, InputIterator end);
00103 
00104     template <class InputIterator>
00105     ArrayVector(InputIterator i, InputIterator end, Alloc const & alloc);
00106 
00107     this_type & operator=( this_type const & rhs );
00108 
00109     ~ArrayVector();
00110 
00111     inline const_pointer data() const
00112     {
00113         return data_;
00114     }
00115 
00116     inline pointer data()
00117     {
00118         return data_;
00119     }
00120 
00121     inline const_iterator begin() const
00122     {
00123         return data();
00124     }
00125 
00126     inline iterator begin()
00127     {
00128         return data();
00129     }
00130 
00131     inline const_iterator end() const
00132     {
00133         return data() + size();
00134     }
00135 
00136     inline iterator end()
00137     {
00138         return data() + size();
00139     }
00140 
00141     inline reverse_iterator rbegin()
00142     {
00143         return (reverse_iterator(end()));
00144     }
00145 
00146     inline const_reverse_iterator rbegin() const
00147     {
00148         return (const_reverse_iterator(end()));
00149     }
00150 
00151     inline reverse_iterator rend()
00152     {
00153         return (reverse_iterator(begin()));
00154     }
00155 
00156     inline const_reverse_iterator rend() const
00157     {
00158         return (const_reverse_iterator(begin()));
00159     }
00160 
00161     reference front()
00162     {
00163         return *data_;
00164     }
00165 
00166     const_reference front() const
00167     {
00168         return *data_;
00169     }
00170 
00171     reference back()
00172     {
00173         return data_[size_-1];
00174     }
00175 
00176     const_reference back() const
00177     {
00178         return data_[size_-1];
00179     }
00180 
00181     reference operator[]( size_type i )
00182     {
00183         return data()[i];
00184     }
00185 
00186     const_reference operator[]( size_type i ) const
00187     {
00188         return data()[i];
00189     }
00190 
00191     void pop_back();
00192 
00193     void push_back( value_type const & t );
00194 
00195     iterator insert(iterator p, value_type const & v);
00196 
00197     iterator insert(iterator p, size_type n, value_type const & v);
00198 
00199     template <class InputIterator>
00200     iterator insert(iterator p, InputIterator i, InputIterator iend);
00201 
00202     iterator erase(iterator p);
00203 
00204     iterator erase(iterator p, iterator q);
00205 
00206     void clear();
00207 
00208     void reserve( size_type new_capacity );
00209 
00210     void reserve();
00211 
00212     void resize( size_type new_size, value_type const & initial );
00213 
00214     void resize( size_type new_size )
00215     {
00216         resize(new_size, value_type());
00217     }
00218 
00219     bool empty() const
00220     {
00221         return size_ == 0;
00222     }
00223 
00224     size_type size() const
00225     {
00226         return size_;
00227     }
00228 
00229     size_type capacity() const
00230     {
00231         return capacity_;
00232     }
00233 
00234     void swap(this_type & rhs);
00235 
00236   private:
00237 
00238     void deallocate(pointer data, size_type size);
00239 
00240     pointer reserve_raw(size_type capacity);
00241 
00242     Alloc alloc_;
00243     size_type size_, capacity_;
00244     pointer data_;
00245 };
00246 
00247 template <class T, class Alloc>
00248 ArrayVector<T, Alloc>::ArrayVector()
00249 : alloc_(Alloc()),
00250   size_(0),
00251   capacity_(minimumCapacity),
00252   data_(reserve_raw(minimumCapacity))
00253 {}
00254 
00255 template <class T, class Alloc>
00256 ArrayVector<T, Alloc>::ArrayVector(Alloc const & alloc)
00257 : alloc_(alloc),
00258   size_(0),
00259   capacity_(minimumCapacity),
00260   data_(reserve_raw(minimumCapacity))
00261 {}
00262 
00263 template <class T, class Alloc>
00264 ArrayVector<T, Alloc>::ArrayVector( size_type size, Alloc const & alloc)
00265 : alloc_(alloc),
00266   size_(size),
00267   capacity_(size),
00268   data_(reserve_raw(size))
00269 {
00270     if(size_ > 0)
00271         std::uninitialized_fill(data_, data_+size_, value_type());
00272 }
00273 
00274 template <class T, class Alloc>
00275 ArrayVector<T, Alloc>::ArrayVector( size_type size,
00276                          value_type const & initial, Alloc const & alloc)
00277 : alloc_(alloc),
00278   size_(size),
00279   capacity_(size),
00280   data_(reserve_raw(size))
00281 {
00282     if(size_ > 0)
00283         std::uninitialized_fill(data_, data_+size_, initial);
00284 }
00285 
00286 template <class T, class Alloc>
00287 ArrayVector<T, Alloc>::ArrayVector( this_type const & rhs )
00288 : alloc_(rhs.alloc_),
00289   size_(rhs.size_),
00290   capacity_(rhs.capacity_),
00291   data_(reserve_raw(rhs.capacity_))
00292 {
00293     if(size_ > 0)
00294         std::uninitialized_copy(rhs.data_, rhs.data_+size_, data_);
00295 }
00296 
00297 template <class T, class Alloc>
00298 template <class InputIterator>
00299 ArrayVector<T, Alloc>::ArrayVector(InputIterator i, InputIterator end)
00300 : alloc_(),
00301   size_(std::distance(i, end)),
00302   capacity_(size_),
00303   data_(reserve_raw(size_))
00304 {
00305     std::uninitialized_copy(i, end, data_);
00306 }
00307 
00308 template <class T, class Alloc>
00309 template <class InputIterator>
00310 ArrayVector<T, Alloc>::ArrayVector(InputIterator i, InputIterator end, Alloc const & alloc)
00311 : alloc_(alloc),
00312   size_(std::distance(i, end)),
00313   capacity_(size_),
00314   data_(reserve_raw(size_))
00315 {
00316     std::uninitialized_copy(i, end, data_);
00317 }
00318 
00319 
00320 template <class T, class Alloc>
00321 ArrayVector<T, Alloc> & ArrayVector<T, Alloc>::operator=( this_type const & rhs )
00322 {
00323     if(this == &rhs)
00324         return *this;
00325     ArrayVector new_vector(rhs);
00326     swap(new_vector);
00327     return *this;
00328 }
00329 
00330 template <class T, class Alloc>
00331 ArrayVector<T, Alloc>::~ArrayVector()
00332 {
00333     deallocate(data_, size_);
00334 }
00335 
00336 template <class T, class Alloc>
00337 void ArrayVector<T, Alloc>::pop_back()
00338 {
00339     --size_;
00340     alloc_.destroy(data_ + size_);
00341 }
00342 
00343 template <class T, class Alloc>
00344 void ArrayVector<T, Alloc>::push_back( value_type const & t )
00345 {
00346     reserve();
00347     alloc_.construct(data_ + size_, t);
00348     ++size_;
00349 }
00350 
00351 template <class T, class Alloc>
00352 void ArrayVector<T, Alloc>::clear()
00353 {
00354     detail::destroy_n(data_, size_);
00355     size_ = 0;
00356 }
00357 
00358 template <class T, class Alloc>
00359 typename ArrayVector<T, Alloc>::iterator
00360 ArrayVector<T, Alloc>::insert(iterator p, value_type const & v)
00361 {
00362     difference_type pos = p - begin();
00363     if(p == end())
00364     {
00365         push_back(v);
00366         p = begin() + pos;
00367     }
00368     else
00369     {
00370         push_back(back());
00371         p = begin() + pos;
00372         std::copy_backward(p, end() - 2, end() - 1);
00373         *p = v;
00374     }
00375     return p;
00376 }
00377 
00378 template <class T, class Alloc>
00379 typename ArrayVector<T, Alloc>::iterator
00380 ArrayVector<T, Alloc>::insert(iterator p, size_type n, value_type const & v)
00381 {
00382     difference_type pos = p - begin();
00383     size_type new_size = size() + n;
00384     if(new_size >= capacity_)
00385     {
00386         pointer new_data = reserve_raw(new_size);
00387         std::uninitialized_copy(begin(), p, new_data);
00388         std::uninitialized_fill(new_data + pos, new_data + pos + n, v);
00389         std::uninitialized_copy(p, end(), new_data + pos + n);
00390         deallocate(data_, size_);
00391         capacity_ = new_size;
00392         data_ = new_data;
00393     }
00394     else if(pos + n >= size_)
00395     {
00396         size_type diff = pos + n - size_;
00397         std::uninitialized_copy(p, end(), end() + diff);
00398         std::uninitialized_fill(end(), end() + diff, v);
00399         std::fill(p, end(), v);
00400     }
00401     else
00402     {
00403         size_type diff = size_ - (pos + n);
00404         std::uninitialized_copy(end() - n, end(), end());
00405         std::copy_backward(p, p + diff, end());
00406         std::fill(p, p + n, v);
00407     }
00408     size_ = new_size;
00409     return begin() + pos;
00410 }
00411 
00412 template <class T, class Alloc>
00413 template <class InputIterator>
00414 typename ArrayVector<T, Alloc>::iterator
00415 ArrayVector<T, Alloc>::insert(iterator p, InputIterator i, InputIterator iend)
00416 {
00417     size_type n = iend - i;
00418     size_type pos = p - begin();
00419     size_type new_size = size() + n;
00420     if(new_size >= capacity_)
00421     {
00422         pointer new_data = reserve_raw(new_size);
00423         std::uninitialized_copy(begin(), p, new_data);
00424         std::uninitialized_copy(i, iend, new_data + pos);
00425         std::uninitialized_copy(p, end(), new_data + pos + n);
00426         deallocate(data_, size_);
00427         capacity_ = new_size;
00428         data_ = new_data;
00429     }
00430     else if(pos + n >= size_)
00431     {
00432         size_type diff = pos + n - size_;
00433         std::uninitialized_copy(p, end(), end() + diff);
00434         std::uninitialized_copy(iend - diff, iend, end());
00435         std::copy(i, iend - diff, p);
00436     }
00437     else
00438     {
00439         size_type diff = size_ - (pos + n);
00440         std::uninitialized_copy(end() - n, end(), end());
00441         std::copy_backward(p, p + diff, end());
00442         std::copy(i, iend, p);
00443     }
00444     size_ = new_size;
00445     return begin() + pos;
00446 }
00447 
00448 template <class T, class Alloc>
00449 typename ArrayVector<T, Alloc>::iterator
00450 ArrayVector<T, Alloc>::erase(iterator p)
00451 {
00452     std::copy(p+1, end(), p);
00453     pop_back();
00454     return p;
00455 }
00456 
00457 template <class T, class Alloc>
00458 typename ArrayVector<T, Alloc>::iterator
00459 ArrayVector<T, Alloc>::erase(iterator p, iterator q)
00460 {
00461     std::copy(q, end(), p);
00462     size_type eraseCount = q - p;
00463     detail::destroy_n(end() - eraseCount, eraseCount);
00464     size_ -= eraseCount;
00465     return p;
00466 }
00467 
00468 template <class T, class Alloc>
00469 void ArrayVector<T, Alloc>::reserve( size_type new_capacity )
00470 {
00471     if(new_capacity <= capacity_)
00472         return;
00473     pointer new_data = reserve_raw(new_capacity);
00474     if(size_ > 0)
00475         std::uninitialized_copy(data_, data_+size_, new_data);
00476     deallocate(data_, size_);
00477     data_ = new_data;
00478     capacity_ = new_capacity;
00479 }
00480 
00481 template <class T, class Alloc>
00482 void ArrayVector<T, Alloc>::reserve()
00483 {
00484     if(capacity_ == 0)
00485         reserve(minimumCapacity);
00486     else if(size_ == capacity_)
00487         reserve(2*capacity_);
00488 }
00489 
00490 template <class T, class Alloc>
00491 void ArrayVector<T, Alloc>::resize( size_type new_size, value_type const & initial)
00492 {
00493     if(new_size < size_)
00494         erase(begin() + new_size, end());
00495     else if(size_ < new_size)
00496     {
00497         insert(end(), new_size - size(), initial);
00498     }
00499 }
00500 
00501 template <class T, class Alloc>
00502 void ArrayVector<T, Alloc>::swap(this_type & rhs)
00503 {
00504     std::swap(size_, rhs.size_);
00505     std::swap(capacity_, rhs.capacity_);
00506     std::swap(data_, rhs.data_);
00507 }
00508 
00509 template <class T, class Alloc>
00510 void ArrayVector<T, Alloc>::deallocate(pointer data, size_type size)
00511 {
00512     if(data)
00513     {
00514         detail::destroy_n(data, size);
00515         alloc_.deallocate(data, size);
00516     }
00517 }
00518 
00519 template <class T, class Alloc>
00520 typename ArrayVector<T, Alloc>::pointer
00521 ArrayVector<T, Alloc>::reserve_raw(size_type capacity)
00522 {
00523     pointer data = 0;
00524     if(capacity)
00525     {
00526         data = alloc_.allocate(capacity);
00527     }
00528     return data;
00529 }
00530 
00531 } // namespace vigra
00532 
00533 
00534 #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.5.0 (7 Dec 2006)