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