[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]
00001 /************************************************************************/ 00002 /* */ 00003 /* Copyright 2002-2004 by Ullrich Koethe */ 00004 /* */ 00005 /* This file is part of the VIGRA computer vision library. */ 00006 /* The VIGRA Website is */ 00007 /* http://hci.iwr.uni-heidelberg.de/vigra/ */ 00008 /* Please direct questions, bug reports, and contributions to */ 00009 /* ullrich.koethe@iwr.uni-heidelberg.de or */ 00010 /* vigra@informatik.uni-hamburg.de */ 00011 /* */ 00012 /* Permission is hereby granted, free of charge, to any person */ 00013 /* obtaining a copy of this software and associated documentation */ 00014 /* files (the "Software"), to deal in the Software without */ 00015 /* restriction, including without limitation the rights to use, */ 00016 /* copy, modify, merge, publish, distribute, sublicense, and/or */ 00017 /* sell copies of the Software, and to permit persons to whom the */ 00018 /* Software is furnished to do so, subject to the following */ 00019 /* conditions: */ 00020 /* */ 00021 /* The above copyright notice and this permission notice shall be */ 00022 /* included in all copies or substantial portions of the */ 00023 /* Software. */ 00024 /* */ 00025 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */ 00026 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */ 00027 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */ 00028 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */ 00029 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */ 00030 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ 00031 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */ 00032 /* OTHER DEALINGS IN THE SOFTWARE. */ 00033 /* */ 00034 /************************************************************************/ 00035 00036 #ifndef VIGRA_ARRAY_VECTOR_HXX 00037 #define VIGRA_ARRAY_VECTOR_HXX 00038 00039 #include "error.hxx" 00040 #include "memory.hxx" 00041 #include "numerictraits.hxx" 00042 #include <memory> 00043 #include <algorithm> 00044 #include <iosfwd> 00045 00046 #ifdef VIGRA_CHECK_BOUNDS 00047 #define VIGRA_ASSERT_INSIDE(diff) \ 00048 vigra_precondition(diff >= 0, "Index out of bounds");\ 00049 vigra_precondition((unsigned int)diff < size_, "Index out of bounds"); 00050 #else 00051 #define VIGRA_ASSERT_INSIDE(diff) 00052 #endif 00053 00054 namespace vigra 00055 { 00056 00057 template <class T, class Alloc = std::allocator<T> > 00058 class ArrayVector; 00059 00060 /** Provide STL conforming interface for C-arrays. 00061 00062 This template implements much of the functionality of <tt><a href="http://www.sgi.com/tech/stl/Vector.html">std::vector</a></tt> 00063 on top of a C-array. <tt>ArrayVectorView</tt> does not manage the memory 00064 it refers to (i.e. it does not allocate or deallocate any memory). 00065 Thus, if the underlying memory changes, all dependent <tt>ArrayVectorView</tt> 00066 objects are invalidated. This is especially important when <tt>ArrayVectorView</tt> 00067 is used as a base class for <tt>ArrayVector</tt>, where several functions 00068 (e.g. resize(), insert()) can allocate new memory and thus invalidate the 00069 dependent views. The rules what operations invalidate view objects are the 00070 same as the rules concerning standard iterators. 00071 00072 <b>\#include</b> <<a href="array__vector_8hxx-source.html">vigra/array_vector.hxx</a>><br> 00073 Namespace: vigra 00074 */ 00075 template <class T> 00076 class ArrayVectorView 00077 { 00078 typedef ArrayVectorView<T> this_type; 00079 00080 public: 00081 /** default constructor 00082 */ 00083 typedef T value_type; 00084 typedef value_type & reference; 00085 typedef value_type const & const_reference; 00086 typedef value_type * pointer; 00087 typedef value_type const * const_pointer; 00088 typedef value_type * iterator; 00089 typedef value_type const * const_iterator; 00090 typedef std::size_t size_type; 00091 typedef std::ptrdiff_t difference_type; 00092 typedef std::reverse_iterator<iterator> reverse_iterator; 00093 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00094 00095 public: 00096 /** default constructor. 00097 View contains NULL pointer. 00098 */ 00099 ArrayVectorView() 00100 : size_(0), 00101 data_(0) 00102 {} 00103 00104 /** Construct for given array \a data of length \a size. 00105 <tt>data, data+size</tt> must form a valid range. 00106 */ 00107 ArrayVectorView( size_type size, pointer const & data) 00108 : size_(size), 00109 data_(data) 00110 {} 00111 00112 /** Copy constructor. 00113 */ 00114 ArrayVectorView( this_type const & rhs ) 00115 : size_(rhs.size_), 00116 data_(rhs.data_) 00117 {} 00118 00119 /** Copy assignment. There are 3 cases: 00120 00121 <ul> 00122 <li> When this <tt>ArrayVectorView</tt> does not point to valid data 00123 (e.g. after default construction), it becomes a copy of \a rhs. 00124 <li> When the shapes of the two arrays match, the array contents 00125 (not the pointers) are copied. 00126 <li> Otherwise, a <tt>PreconditionViolation</tt> exception is thrown. 00127 </ul> 00128 */ 00129 ArrayVectorView & operator=( ArrayVectorView const & rhs ); 00130 00131 /** Copy assignment. 00132 When the shapes of the two arrays match, the array contents 00133 (not the pointers) are copied. Otherwise, a <tt>PreconditionViolation</tt> 00134 exception is thrown. 00135 */ 00136 template <class U> 00137 this_type & operator=( ArrayVectorView<U> const & rhs ) 00138 { 00139 copyImpl(rhs); 00140 return *this; 00141 } 00142 00143 /** Overwrite all array elements with the value \a initial. 00144 */ 00145 template <class U> 00146 void init(U const & initial) 00147 { 00148 std::fill(begin(), end(), initial); 00149 } 00150 00151 /** Copy array elements. 00152 When the shapes of the two arrays match, the array contents 00153 (not the pointers) are copied. Otherwise, a <tt>PreconditionViolation</tt> 00154 exception is thrown. 00155 */ 00156 void copy( this_type const & rhs ) 00157 { 00158 if(data_ != rhs.data_) 00159 copyImpl(rhs); 00160 } 00161 00162 /** Copy array elements. 00163 When the shapes of the two arrays match, the array contents 00164 (not the pointers) are copied. Otherwise, a <tt>PreconditionViolation</tt> 00165 exception is thrown. 00166 */ 00167 template <class U> 00168 void copy( ArrayVectorView<U> const & rhs ) 00169 { 00170 copyImpl(rhs); 00171 } 00172 00173 /** Swap array elements. 00174 When the shapes of the two arrays match, the array contents 00175 (not the pointers) are swapped. Otherwise, a <tt>PreconditionViolation</tt> 00176 exception is thrown. 00177 */ 00178 void swapData(this_type rhs) 00179 { 00180 if(data_ != rhs.data_) 00181 swapDataImpl(rhs); 00182 } 00183 00184 /** Swap array elements. 00185 When the shapes of the two arrays match, the array contents 00186 (not the pointers) are swapped. Otherwise, a <tt>PreconditionViolation</tt> 00187 exception is thrown. 00188 */ 00189 template <class U> 00190 void swapData(ArrayVectorView<U> rhs) 00191 { 00192 swapDataImpl(rhs); 00193 } 00194 00195 /** Construct <tt>ArrayVectorView</tt> refering to a subarray. 00196 \a begin and \a end must be a valid sub-range of the current array. 00197 Otherwise, a <tt>PreconditionViolation</tt> 00198 exception is thrown. 00199 */ 00200 this_type subarray (size_type begin, size_type end) const 00201 { 00202 vigra_precondition(begin <= end && end <= size_, 00203 "ArrayVectorView::subarray(): Limits out of range."); 00204 return this_type(end-begin, data_ + begin); 00205 } 00206 00207 /** Get contained const pointer to the data. 00208 */ 00209 inline const_pointer data() const 00210 { 00211 return data_; 00212 } 00213 00214 /** Get contained pointer to the data. 00215 */ 00216 inline pointer data() 00217 { 00218 return data_; 00219 } 00220 00221 /** Get const iterator refering to the first array element. 00222 */ 00223 inline const_iterator begin() const 00224 { 00225 return data(); 00226 } 00227 00228 /** Get iterator refering to the first array element. 00229 */ 00230 inline iterator begin() 00231 { 00232 return data(); 00233 } 00234 00235 /** Get const iterator pointing beyond the last array element. 00236 */ 00237 inline const_iterator end() const 00238 { 00239 return data() + size(); 00240 } 00241 00242 /** Get iterator pointing beyond the last array element. 00243 */ 00244 inline iterator end() 00245 { 00246 return data() + size(); 00247 } 00248 00249 /** Get reverse iterator referring to the last array element. 00250 */ 00251 inline reverse_iterator rbegin() 00252 { 00253 return (reverse_iterator(end())); 00254 } 00255 00256 /** Get const reverse iterator referring to the last array element. 00257 */ 00258 inline const_reverse_iterator rbegin() const 00259 { 00260 return (const_reverse_iterator(end())); 00261 } 00262 00263 /** Get reverse iterator pointing before the first array element. 00264 */ 00265 inline reverse_iterator rend() 00266 { 00267 return (reverse_iterator(begin())); 00268 } 00269 00270 /** Get const reverse iterator pointing before the first array element. 00271 */ 00272 inline const_reverse_iterator rend() const 00273 { 00274 return (const_reverse_iterator(begin())); 00275 } 00276 00277 /** Access first array element. 00278 */ 00279 reference front() 00280 { 00281 return *data_; 00282 } 00283 00284 /** Read first array element. 00285 */ 00286 const_reference front() const 00287 { 00288 return *data_; 00289 } 00290 00291 /** Access last array element. 00292 */ 00293 reference back() 00294 { 00295 return data_[size_-1]; 00296 } 00297 00298 /** Read last array element. 00299 */ 00300 const_reference back() const 00301 { 00302 return data_[size_-1]; 00303 } 00304 00305 /** Access array element \a i. 00306 */ 00307 reference operator[]( difference_type i ) 00308 { 00309 VIGRA_ASSERT_INSIDE(i); 00310 return data()[i]; 00311 } 00312 00313 /** Read array element \a i. 00314 */ 00315 const_reference operator[]( difference_type i ) const 00316 { 00317 VIGRA_ASSERT_INSIDE(i); 00318 return data()[i]; 00319 } 00320 00321 /** Equivalent to <tt>size() == 0</tt>. 00322 */ 00323 bool empty() const 00324 { 00325 return size_ == 0; 00326 } 00327 00328 /** Number of elements in the array. 00329 */ 00330 size_type size() const 00331 { 00332 return size_; 00333 } 00334 00335 /** Check for element-wise equality of two array. 00336 Also returns <tt>false</tt> if the two arrays have different sizes. 00337 */ 00338 template <class U> 00339 bool operator==(ArrayVectorView<U> const & rhs) const; 00340 00341 /** check whether two arrays are not elementwise equal. 00342 Also returns <tt>true</tt> if the two arrays have different sizes. 00343 */ 00344 template <class U> 00345 bool operator!=(ArrayVectorView<U> const & rhs) const 00346 { 00347 return !operator==(rhs); 00348 } 00349 00350 /** check whether the given point is in the array range. 00351 */ 00352 bool isInside (difference_type const & p) const 00353 { 00354 return p >= 0 && p < size_; 00355 } 00356 00357 protected: 00358 00359 template <class U> 00360 void copyImpl(const ArrayVectorView <U>& rhs); 00361 00362 void copyImpl(const ArrayVectorView & rhs); 00363 00364 template <class U> 00365 void swapDataImpl(const ArrayVectorView <U>& rhs); 00366 00367 size_type size_; 00368 pointer data_; 00369 }; 00370 00371 template <class T> 00372 ArrayVectorView<T> & ArrayVectorView<T>::operator=( ArrayVectorView<T> const & rhs ) 00373 { 00374 if(data_ == 0) 00375 { 00376 size_ = rhs.size_; 00377 data_ = rhs.data_; 00378 } 00379 else if(data_ != rhs.data_) 00380 copyImpl(rhs); 00381 return *this; 00382 } 00383 00384 template <class T> 00385 template <class U> 00386 bool ArrayVectorView<T>::operator==(ArrayVectorView<U> const & rhs) const 00387 { 00388 if(size() != rhs.size()) 00389 return false; 00390 for(unsigned int k=0; k<size(); ++k) 00391 if(data_[k] != rhs[k]) 00392 return false; 00393 return true; 00394 } 00395 00396 template <class T> 00397 void 00398 ArrayVectorView <T>::copyImpl(const ArrayVectorView & rhs) 00399 { 00400 vigra_precondition (size() == rhs.size(), 00401 "ArrayVectorView::copy(): shape mismatch."); 00402 // use copy() or copy_backward() according to possible overlap of this and rhs 00403 if(data_ <= rhs.data()) 00404 { 00405 std::copy(rhs.begin(), rhs.end(), begin()); 00406 } 00407 else 00408 { 00409 std::copy_backward(rhs.begin(), rhs.end(), end()); 00410 } 00411 } 00412 00413 template <class T> 00414 template <class U> 00415 void 00416 ArrayVectorView <T>::copyImpl(const ArrayVectorView <U>& rhs) 00417 { 00418 vigra_precondition (size() == rhs.size(), 00419 "ArrayVectorView::copy(): shape mismatch."); 00420 std::copy(rhs.begin(), rhs.end(), begin()); 00421 } 00422 00423 template <class T> 00424 template <class U> 00425 void 00426 ArrayVectorView <T>::swapDataImpl(const ArrayVectorView <U>& rhs) 00427 { 00428 vigra_precondition (size () == rhs.size() (), 00429 "ArrayVectorView::swapData(): size mismatch."); 00430 00431 // check for overlap 00432 if(data_ + size_ <= rhs.data_ || rhs.data_ + size_ <= data_) 00433 { 00434 for(unsigned int k=0; k<size_; ++k) 00435 std::swap(data_[k], rhs.data_[k]); 00436 } 00437 else 00438 { 00439 ArrayVector<T> t(*this); 00440 copyImpl(rhs); 00441 rhs.copyImpl(*this); 00442 } 00443 } 00444 00445 00446 /** Replacement for <tt>std::vector</tt>. 00447 00448 This template implements the same functionality as <tt>a href="http://www.sgi.com/tech/stl/Vector.html">std::vector</a></tt> (see there for detailed documentation). 00449 However, it gives two useful guarantees, that <tt>std::vector</tt> fails 00450 to provide: 00451 00452 <ul> 00453 <li>The memory is always allocated as one contiguous piece.</li> 00454 <li>The iterator is always a <TT>T *</TT> </li> 00455 </ul> 00456 00457 This means that memory managed by <tt>ArrayVector</tt> can be passed 00458 to algorithms that expect raw memory. This is especially important 00459 when lagacy or C code has to be called, but it is also useful for certain 00460 optimizations. 00461 00462 Moreover, <tt>ArrayVector</tt> is derived from <tt>ArrayVectorView</tt> so that one 00463 can create views of the array (in particular, subarrays). This implies another 00464 important difference to <tt>std::vector</tt>: the indexing operator 00465 (<tt>ArrayVector::operator[]</tt>) takes <tt>signed</tt> indices. In this way, 00466 an <tt>ArrayVectorView</tt> can be used with negative indices: 00467 00468 \code 00469 ArrayVector<int> data(100); 00470 ArrayVectorView<int> view = data.subarray(50, 100); 00471 00472 view[-50] = 1; // valid access 00473 \endcode 00474 00475 Refer to the documentation of <tt>std::vector</tt> for a detailed 00476 description of <tt>ArrayVector</tt> functionality. 00477 00478 <b>\#include</b> <<a href="array__vector_8hxx-source.html">vigra/array_vector.hxx</a>><br> 00479 Namespace: vigra 00480 */ 00481 template <class T, class Alloc /* = std::allocator<T> */ > 00482 class ArrayVector 00483 : public ArrayVectorView<T> 00484 { 00485 typedef ArrayVector<T, Alloc> this_type; 00486 enum { minimumCapacity = 2, resizeFactor = 2 }; 00487 00488 public: 00489 typedef ArrayVectorView<T> view_type; 00490 typedef typename view_type::value_type value_type; 00491 typedef typename view_type::reference reference; 00492 typedef typename view_type::const_reference const_reference; 00493 typedef typename view_type::pointer pointer; 00494 typedef typename view_type::const_pointer const_pointer; 00495 typedef typename view_type::iterator iterator; 00496 typedef typename view_type::const_iterator const_iterator; 00497 typedef typename view_type::size_type size_type; 00498 typedef typename view_type::difference_type difference_type; 00499 typedef typename view_type::reverse_iterator reverse_iterator; 00500 typedef typename view_type::const_reverse_iterator const_reverse_iterator; 00501 typedef Alloc allocator_type; 00502 00503 public: 00504 ArrayVector() 00505 : view_type(), 00506 capacity_(minimumCapacity), 00507 alloc_(Alloc()) 00508 { 00509 this->data_ = reserve_raw(capacity_); 00510 } 00511 00512 explicit ArrayVector(Alloc const & alloc) 00513 : view_type(), 00514 capacity_(minimumCapacity), 00515 alloc_(alloc) 00516 { 00517 this->data_ = reserve_raw(capacity_); 00518 } 00519 00520 explicit ArrayVector( size_type size, Alloc const & alloc = Alloc()) 00521 : view_type(), 00522 alloc_(alloc) 00523 { 00524 initImpl(size, value_type(), VigraTrueType()); 00525 } 00526 00527 ArrayVector( size_type size, value_type const & initial, Alloc const & alloc = Alloc()) 00528 : view_type(), 00529 alloc_(alloc) 00530 { 00531 initImpl(size, initial, VigraTrueType()); 00532 } 00533 00534 00535 ArrayVector( this_type const & rhs ) 00536 : view_type(), 00537 alloc_(rhs.alloc_) 00538 { 00539 initImpl(rhs.begin(), rhs.end(), VigraFalseType()); 00540 } 00541 00542 template <class U> 00543 explicit ArrayVector( ArrayVectorView<U> const & rhs, Alloc const & alloc = Alloc() ) 00544 : view_type(), 00545 alloc_(alloc) 00546 { 00547 initImpl(rhs.begin(), rhs.end(), VigraFalseType()); 00548 } 00549 00550 template <class InputIterator> 00551 ArrayVector(InputIterator i, InputIterator end) 00552 { 00553 initImpl(i, end, typename NumericTraits<InputIterator>::isIntegral()); 00554 } 00555 00556 template <class InputIterator> 00557 ArrayVector(InputIterator i, InputIterator end, Alloc const & alloc) 00558 : alloc_(alloc) 00559 { 00560 initImpl(i, end, typename NumericTraits<InputIterator>::isIntegral()); 00561 } 00562 00563 this_type & operator=( this_type const & rhs ) 00564 { 00565 if(this == &rhs) 00566 return *this; 00567 if(this->size_ == rhs.size_) 00568 this->copyImpl(rhs); 00569 else 00570 { 00571 ArrayVector t(rhs); 00572 this->swap(t); 00573 } 00574 return *this; 00575 } 00576 00577 template <class U> 00578 this_type & operator=( ArrayVectorView<U> const & rhs); 00579 00580 ~ArrayVector() 00581 { 00582 deallocate(this->data_, this->size_); 00583 } 00584 00585 void pop_back(); 00586 00587 void push_back( value_type const & t ); 00588 00589 iterator insert(iterator p, value_type const & v); 00590 00591 iterator insert(iterator p, size_type n, value_type const & v); 00592 00593 template <class InputIterator> 00594 iterator insert(iterator p, InputIterator i, InputIterator iend); 00595 00596 iterator erase(iterator p); 00597 00598 iterator erase(iterator p, iterator q); 00599 00600 void clear(); 00601 00602 void reserve( size_type new_capacity ); 00603 00604 void reserve(); 00605 00606 void resize( size_type new_size, value_type const & initial ); 00607 00608 void resize( size_type new_size ) 00609 { 00610 resize(new_size, value_type()); 00611 } 00612 00613 size_type capacity() const 00614 { 00615 return capacity_; 00616 } 00617 00618 void swap(this_type & rhs); 00619 00620 private: 00621 00622 void deallocate(pointer data, size_type size); 00623 00624 pointer reserve_raw(size_type capacity); 00625 00626 void initImpl( size_type size, value_type const & initial, VigraTrueType /*isIntegral*/); 00627 00628 template <class Iter> 00629 void initImpl( Iter i, Iter end, VigraFalseType /*isIntegral*/); 00630 00631 template <class Iter> 00632 void initImpl( Iter i, Iter end, Error_NumericTraits_not_specialized_for_this_case) 00633 { 00634 initImpl(i, end, VigraFalseType()); 00635 } 00636 00637 size_type capacity_; 00638 Alloc alloc_; 00639 }; 00640 00641 template <class T, class Alloc> 00642 template <class U> 00643 ArrayVector<T, Alloc> & ArrayVector<T, Alloc>::operator=( ArrayVectorView<U> const & rhs ) 00644 { 00645 if(this->size_ == rhs.size()) 00646 this->copyImpl(rhs); 00647 else 00648 { 00649 ArrayVector t(rhs); 00650 this->swap(t); 00651 } 00652 return *this; 00653 } 00654 00655 template <class T, class Alloc> 00656 inline void ArrayVector<T, Alloc>::pop_back() 00657 { 00658 --this->size_; 00659 alloc_.destroy(this->data_ + this->size_); 00660 } 00661 00662 template <class T, class Alloc> 00663 inline void ArrayVector<T, Alloc>::push_back( value_type const & t ) 00664 { 00665 reserve(); 00666 alloc_.construct(this->data_ + this->size_, t); 00667 ++this->size_; 00668 } 00669 00670 template <class T, class Alloc> 00671 inline void ArrayVector<T, Alloc>::clear() 00672 { 00673 detail::destroy_n(this->data_, (int)this->size_); 00674 this->size_ = 0; 00675 } 00676 00677 template <class T, class Alloc> 00678 typename ArrayVector<T, Alloc>::iterator 00679 ArrayVector<T, Alloc>::insert(iterator p, value_type const & v) 00680 { 00681 difference_type pos = p - this->begin(); 00682 if(p == this->end()) 00683 { 00684 push_back(v); 00685 p = this->begin() + pos; 00686 } 00687 else 00688 { 00689 push_back(this->back()); 00690 p = this->begin() + pos; 00691 std::copy_backward(p, this->end() - 2, this->end() - 1); 00692 *p = v; 00693 } 00694 return p; 00695 } 00696 00697 template <class T, class Alloc> 00698 typename ArrayVector<T, Alloc>::iterator 00699 ArrayVector<T, Alloc>::insert(iterator p, size_type n, value_type const & v) 00700 { 00701 difference_type pos = p - this->begin(); 00702 size_type new_size = this->size() + n; 00703 if(new_size >= capacity_) 00704 { 00705 size_type new_capacity = std::max(new_size, resizeFactor*capacity_); 00706 pointer new_data = reserve_raw(new_capacity); 00707 std::uninitialized_copy(this->begin(), p, new_data); 00708 std::uninitialized_fill(new_data + pos, new_data + pos + n, v); 00709 std::uninitialized_copy(p, this->end(), new_data + pos + n); 00710 deallocate(this->data_, this->size_); 00711 capacity_ = new_capacity; 00712 this->data_ = new_data; 00713 } 00714 else if(pos + n >= this->size_) 00715 { 00716 size_type diff = pos + n - this->size_; 00717 std::uninitialized_copy(p, this->end(), this->end() + diff); 00718 std::uninitialized_fill(this->end(), this->end() + diff, v); 00719 std::fill(p, this->end(), v); 00720 } 00721 else 00722 { 00723 size_type diff = this->size_ - (pos + n); 00724 std::uninitialized_copy(this->end() - n, this->end(), this->end()); 00725 std::copy_backward(p, p + diff, this->end()); 00726 std::fill(p, p + n, v); 00727 } 00728 this->size_ = new_size; 00729 return this->begin() + pos; 00730 } 00731 00732 template <class T, class Alloc> 00733 template <class InputIterator> 00734 typename ArrayVector<T, Alloc>::iterator 00735 ArrayVector<T, Alloc>::insert(iterator p, InputIterator i, InputIterator iend) 00736 { 00737 size_type n = iend - i; 00738 size_type pos = p - this->begin(); 00739 size_type new_size = this->size() + n; 00740 if(new_size >= capacity_) 00741 { 00742 size_type new_capacity = std::max(new_size, resizeFactor*capacity_); 00743 pointer new_data = reserve_raw(new_capacity); 00744 std::uninitialized_copy(this->begin(), p, new_data); 00745 std::uninitialized_copy(i, iend, new_data + pos); 00746 std::uninitialized_copy(p, this->end(), new_data + pos + n); 00747 deallocate(this->data_, this->size_); 00748 capacity_ = new_capacity; 00749 this->data_ = new_data; 00750 } 00751 else if(pos + n >= this->size_) 00752 { 00753 size_type diff = pos + n - this->size_; 00754 std::uninitialized_copy(p, this->end(), this->end() + diff); 00755 std::uninitialized_copy(iend - diff, iend, this->end()); 00756 std::copy(i, iend - diff, p); 00757 } 00758 else 00759 { 00760 size_type diff = this->size_ - (pos + n); 00761 std::uninitialized_copy(this->end() - n, this->end(), this->end()); 00762 std::copy_backward(p, p + diff, this->end()); 00763 std::copy(i, iend, p); 00764 } 00765 this->size_ = new_size; 00766 return this->begin() + pos; 00767 } 00768 00769 template <class T, class Alloc> 00770 typename ArrayVector<T, Alloc>::iterator 00771 ArrayVector<T, Alloc>::erase(iterator p) 00772 { 00773 std::copy(p+1, this->end(), p); 00774 pop_back(); 00775 return p; 00776 } 00777 00778 template <class T, class Alloc> 00779 typename ArrayVector<T, Alloc>::iterator 00780 ArrayVector<T, Alloc>::erase(iterator p, iterator q) 00781 { 00782 std::copy(q, this->end(), p); 00783 difference_type eraseCount = q - p; 00784 detail::destroy_n(this->end() - eraseCount, eraseCount); 00785 this->size_ -= eraseCount; 00786 return p; 00787 } 00788 00789 template <class T, class Alloc> 00790 inline void 00791 ArrayVector<T, Alloc>::reserve( size_type new_capacity ) 00792 { 00793 if(new_capacity <= capacity_) 00794 return; 00795 pointer new_data = reserve_raw(new_capacity); 00796 if(this->size_ > 0) 00797 std::uninitialized_copy(this->data_, this->data_+this->size_, new_data); 00798 deallocate(this->data_, this->size_); 00799 this->data_ = new_data; 00800 capacity_ = new_capacity; 00801 } 00802 00803 template <class T, class Alloc> 00804 inline void 00805 ArrayVector<T, Alloc>::reserve() 00806 { 00807 if(capacity_ == 0) 00808 reserve(minimumCapacity); 00809 else if(this->size_ == capacity_) 00810 reserve(resizeFactor*capacity_); 00811 } 00812 00813 template <class T, class Alloc> 00814 inline void 00815 ArrayVector<T, Alloc>::resize( size_type new_size, value_type const & initial) 00816 { 00817 if(new_size < this->size_) 00818 erase(this->begin() + new_size, this->end()); 00819 else if(this->size_ < new_size) 00820 { 00821 insert(this->end(), new_size - this->size(), initial); 00822 } 00823 } 00824 00825 template <class T, class Alloc> 00826 inline void 00827 ArrayVector<T, Alloc>::initImpl( size_type size, value_type const & initial, VigraTrueType /*isIntegral*/) 00828 { 00829 this->size_ = size; 00830 capacity_ = size; 00831 this->data_ = reserve_raw(capacity_); 00832 if(this->size_ > 0) 00833 std::uninitialized_fill(this->data_, this->data_+this->size_, initial); 00834 } 00835 00836 template <class T, class Alloc> 00837 template <class Iter> 00838 inline void 00839 ArrayVector<T, Alloc>::initImpl( Iter i, Iter end, VigraFalseType /*isIntegral*/) 00840 { 00841 this->size_ = std::distance(i, end); 00842 capacity_ = this->size_; 00843 this->data_ = reserve_raw(capacity_); 00844 if(this->size_ > 0) 00845 std::uninitialized_copy(i, end, this->data_); 00846 } 00847 00848 template <class T, class Alloc> 00849 inline void 00850 ArrayVector<T, Alloc>::swap(this_type & rhs) 00851 { 00852 std::swap(this->size_, rhs.size_); 00853 std::swap(capacity_, rhs.capacity_); 00854 std::swap(this->data_, rhs.data_); 00855 } 00856 00857 template <class T, class Alloc> 00858 inline void 00859 ArrayVector<T, Alloc>::deallocate(pointer data, size_type size) 00860 { 00861 if(data) 00862 { 00863 detail::destroy_n(data, (int)size); 00864 alloc_.deallocate(data, size); 00865 } 00866 } 00867 00868 template <class T, class Alloc> 00869 inline typename ArrayVector<T, Alloc>::pointer 00870 ArrayVector<T, Alloc>::reserve_raw(size_type capacity) 00871 { 00872 pointer data = 0; 00873 if(capacity) 00874 { 00875 data = alloc_.allocate(capacity); 00876 } 00877 return data; 00878 } 00879 00880 } // namespace vigra 00881 00882 namespace std { 00883 00884 template <class T> 00885 ostream & operator<<(ostream & s, vigra::ArrayVectorView<T> const & a) 00886 { 00887 for(int k=0; k<(int)a.size()-1; ++k) 00888 s << a[k] << ", "; 00889 if(a.size()) 00890 s << a.back(); 00891 return s; 00892 } 00893 00894 } // namespace std 00895 00896 #undef VIGRA_ASSERT_INSIDE 00897 #endif /* VIGRA_ARRAY_VECTOR_HXX */
© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) |
html generated using doxygen and Python
|