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