[ 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.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)