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