[ VIGRA Homepage | Class Index | Function Index | File Index | Main Page ]
![]() |
vigra/array_vector.hxx | ![]() |
---|
00001 /************************************************************************/ 00002 /* */ 00003 /* Copyright 2002-2004 by Ullrich Koethe */ 00004 /* Cognitive Systems Group, University of Hamburg, Germany */ 00005 /* */ 00006 /* This file is part of the VIGRA computer vision library. */ 00007 /* ( Version 1.5.0, Dec 07 2006 ) */ 00008 /* The VIGRA Website is */ 00009 /* http://kogs-www.informatik.uni-hamburg.de/~koethe/vigra/ */ 00010 /* Please direct questions, bug reports, and contributions to */ 00011 /* koethe@informatik.uni-hamburg.de or */ 00012 /* vigra@kogs1.informatik.uni-hamburg.de */ 00013 /* */ 00014 /* Permission is hereby granted, free of charge, to any person */ 00015 /* obtaining a copy of this software and associated documentation */ 00016 /* files (the "Software"), to deal in the Software without */ 00017 /* restriction, including without limitation the rights to use, */ 00018 /* copy, modify, merge, publish, distribute, sublicense, and/or */ 00019 /* sell copies of the Software, and to permit persons to whom the */ 00020 /* Software is furnished to do so, subject to the following */ 00021 /* conditions: */ 00022 /* */ 00023 /* The above copyright notice and this permission notice shall be */ 00024 /* included in all copies or substantial portions of the */ 00025 /* Software. */ 00026 /* */ 00027 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */ 00028 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */ 00029 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */ 00030 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */ 00031 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */ 00032 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ 00033 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */ 00034 /* OTHER DEALINGS IN THE SOFTWARE. */ 00035 /* */ 00036 /************************************************************************/ 00037 00038 #ifndef VIGRA_ARRAY_VECTOR_HXX 00039 #define VIGRA_ARRAY_VECTOR_HXX 00040 00041 #include "memory.hxx" 00042 #include <memory> 00043 #include <algorithm> 00044 00045 namespace vigra 00046 { 00047 00048 /** Replacement for <tt>std::vector</tt>. 00049 00050 This template implements the same functionality as <tt>std::vector</tt>. 00051 However, it gives two usful guarantees, that <tt>std::vector</tt> fails 00052 to provide: 00053 00054 <ul> 00055 <li>The memory is always allocated as one contigous piece</li> 00056 <li>The iterator is always a <TT>T *</TT> </li> 00057 </ul> 00058 00059 This means that memory managed by <tt>ArrayVector</tt> can be passed 00060 to algorithms that expect raw memory. This is especially important 00061 when lagacy or C code has to be called, but it is also useful for certain 00062 optimizations. 00063 00064 Refer to the documentation of <tt>std::vector</tt> for a detailed 00065 description of <tt>ArrayVector</tt> functionality. 00066 00067 <b>\#include</b> "<a href="array_vector_8hxx-source.html">vigra/array_vector.hxx</a>"<br> 00068 Namespace: vigra 00069 */ 00070 template <class T, class Alloc = std::allocator<T> > 00071 class ArrayVector 00072 { 00073 typedef ArrayVector<T, Alloc> this_type; 00074 enum { minimumCapacity = 2 }; 00075 00076 public: 00077 typedef T value_type; 00078 typedef value_type & reference; 00079 typedef value_type const & const_reference; 00080 typedef value_type * pointer; 00081 typedef value_type const * const_pointer; 00082 typedef value_type * iterator; 00083 typedef value_type const * const_iterator; 00084 typedef unsigned int size_type; 00085 typedef int difference_type; 00086 typedef Alloc allocator_type; 00087 typedef std::reverse_iterator<iterator> reverse_iterator; 00088 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00089 00090 public: 00091 ArrayVector(); 00092 00093 explicit ArrayVector(Alloc const & alloc); 00094 00095 explicit ArrayVector( size_type size, Alloc const & alloc = Alloc()); 00096 00097 ArrayVector( size_type size, value_type const & initial, Alloc const & alloc = Alloc()); 00098 00099 ArrayVector( this_type const & rhs ); 00100 00101 template <class InputIterator> 00102 ArrayVector(InputIterator i, InputIterator end); 00103 00104 template <class InputIterator> 00105 ArrayVector(InputIterator i, InputIterator end, Alloc const & alloc); 00106 00107 this_type & operator=( this_type const & rhs ); 00108 00109 ~ArrayVector(); 00110 00111 inline const_pointer data() const 00112 { 00113 return data_; 00114 } 00115 00116 inline pointer data() 00117 { 00118 return data_; 00119 } 00120 00121 inline const_iterator begin() const 00122 { 00123 return data(); 00124 } 00125 00126 inline iterator begin() 00127 { 00128 return data(); 00129 } 00130 00131 inline const_iterator end() const 00132 { 00133 return data() + size(); 00134 } 00135 00136 inline iterator end() 00137 { 00138 return data() + size(); 00139 } 00140 00141 inline reverse_iterator rbegin() 00142 { 00143 return (reverse_iterator(end())); 00144 } 00145 00146 inline const_reverse_iterator rbegin() const 00147 { 00148 return (const_reverse_iterator(end())); 00149 } 00150 00151 inline reverse_iterator rend() 00152 { 00153 return (reverse_iterator(begin())); 00154 } 00155 00156 inline const_reverse_iterator rend() const 00157 { 00158 return (const_reverse_iterator(begin())); 00159 } 00160 00161 reference front() 00162 { 00163 return *data_; 00164 } 00165 00166 const_reference front() const 00167 { 00168 return *data_; 00169 } 00170 00171 reference back() 00172 { 00173 return data_[size_-1]; 00174 } 00175 00176 const_reference back() const 00177 { 00178 return data_[size_-1]; 00179 } 00180 00181 reference operator[]( size_type i ) 00182 { 00183 return data()[i]; 00184 } 00185 00186 const_reference operator[]( size_type i ) const 00187 { 00188 return data()[i]; 00189 } 00190 00191 void pop_back(); 00192 00193 void push_back( value_type const & t ); 00194 00195 iterator insert(iterator p, value_type const & v); 00196 00197 iterator insert(iterator p, size_type n, value_type const & v); 00198 00199 template <class InputIterator> 00200 iterator insert(iterator p, InputIterator i, InputIterator iend); 00201 00202 iterator erase(iterator p); 00203 00204 iterator erase(iterator p, iterator q); 00205 00206 void clear(); 00207 00208 void reserve( size_type new_capacity ); 00209 00210 void reserve(); 00211 00212 void resize( size_type new_size, value_type const & initial ); 00213 00214 void resize( size_type new_size ) 00215 { 00216 resize(new_size, value_type()); 00217 } 00218 00219 bool empty() const 00220 { 00221 return size_ == 0; 00222 } 00223 00224 size_type size() const 00225 { 00226 return size_; 00227 } 00228 00229 size_type capacity() const 00230 { 00231 return capacity_; 00232 } 00233 00234 void swap(this_type & rhs); 00235 00236 private: 00237 00238 void deallocate(pointer data, size_type size); 00239 00240 pointer reserve_raw(size_type capacity); 00241 00242 Alloc alloc_; 00243 size_type size_, capacity_; 00244 pointer data_; 00245 }; 00246 00247 template <class T, class Alloc> 00248 ArrayVector<T, Alloc>::ArrayVector() 00249 : alloc_(Alloc()), 00250 size_(0), 00251 capacity_(minimumCapacity), 00252 data_(reserve_raw(minimumCapacity)) 00253 {} 00254 00255 template <class T, class Alloc> 00256 ArrayVector<T, Alloc>::ArrayVector(Alloc const & alloc) 00257 : alloc_(alloc), 00258 size_(0), 00259 capacity_(minimumCapacity), 00260 data_(reserve_raw(minimumCapacity)) 00261 {} 00262 00263 template <class T, class Alloc> 00264 ArrayVector<T, Alloc>::ArrayVector( size_type size, Alloc const & alloc) 00265 : alloc_(alloc), 00266 size_(size), 00267 capacity_(size), 00268 data_(reserve_raw(size)) 00269 { 00270 if(size_ > 0) 00271 std::uninitialized_fill(data_, data_+size_, value_type()); 00272 } 00273 00274 template <class T, class Alloc> 00275 ArrayVector<T, Alloc>::ArrayVector( size_type size, 00276 value_type const & initial, Alloc const & alloc) 00277 : alloc_(alloc), 00278 size_(size), 00279 capacity_(size), 00280 data_(reserve_raw(size)) 00281 { 00282 if(size_ > 0) 00283 std::uninitialized_fill(data_, data_+size_, initial); 00284 } 00285 00286 template <class T, class Alloc> 00287 ArrayVector<T, Alloc>::ArrayVector( this_type const & rhs ) 00288 : alloc_(rhs.alloc_), 00289 size_(rhs.size_), 00290 capacity_(rhs.capacity_), 00291 data_(reserve_raw(rhs.capacity_)) 00292 { 00293 if(size_ > 0) 00294 std::uninitialized_copy(rhs.data_, rhs.data_+size_, data_); 00295 } 00296 00297 template <class T, class Alloc> 00298 template <class InputIterator> 00299 ArrayVector<T, Alloc>::ArrayVector(InputIterator i, InputIterator end) 00300 : alloc_(), 00301 size_(std::distance(i, end)), 00302 capacity_(size_), 00303 data_(reserve_raw(size_)) 00304 { 00305 std::uninitialized_copy(i, end, data_); 00306 } 00307 00308 template <class T, class Alloc> 00309 template <class InputIterator> 00310 ArrayVector<T, Alloc>::ArrayVector(InputIterator i, InputIterator end, Alloc const & alloc) 00311 : alloc_(alloc), 00312 size_(std::distance(i, end)), 00313 capacity_(size_), 00314 data_(reserve_raw(size_)) 00315 { 00316 std::uninitialized_copy(i, end, data_); 00317 } 00318 00319 00320 template <class T, class Alloc> 00321 ArrayVector<T, Alloc> & ArrayVector<T, Alloc>::operator=( this_type const & rhs ) 00322 { 00323 if(this == &rhs) 00324 return *this; 00325 ArrayVector new_vector(rhs); 00326 swap(new_vector); 00327 return *this; 00328 } 00329 00330 template <class T, class Alloc> 00331 ArrayVector<T, Alloc>::~ArrayVector() 00332 { 00333 deallocate(data_, size_); 00334 } 00335 00336 template <class T, class Alloc> 00337 void ArrayVector<T, Alloc>::pop_back() 00338 { 00339 --size_; 00340 alloc_.destroy(data_ + size_); 00341 } 00342 00343 template <class T, class Alloc> 00344 void ArrayVector<T, Alloc>::push_back( value_type const & t ) 00345 { 00346 reserve(); 00347 alloc_.construct(data_ + size_, t); 00348 ++size_; 00349 } 00350 00351 template <class T, class Alloc> 00352 void ArrayVector<T, Alloc>::clear() 00353 { 00354 detail::destroy_n(data_, size_); 00355 size_ = 0; 00356 } 00357 00358 template <class T, class Alloc> 00359 typename ArrayVector<T, Alloc>::iterator 00360 ArrayVector<T, Alloc>::insert(iterator p, value_type const & v) 00361 { 00362 difference_type pos = p - begin(); 00363 if(p == end()) 00364 { 00365 push_back(v); 00366 p = begin() + pos; 00367 } 00368 else 00369 { 00370 push_back(back()); 00371 p = begin() + pos; 00372 std::copy_backward(p, end() - 2, end() - 1); 00373 *p = v; 00374 } 00375 return p; 00376 } 00377 00378 template <class T, class Alloc> 00379 typename ArrayVector<T, Alloc>::iterator 00380 ArrayVector<T, Alloc>::insert(iterator p, size_type n, value_type const & v) 00381 { 00382 difference_type pos = p - begin(); 00383 size_type new_size = size() + n; 00384 if(new_size >= capacity_) 00385 { 00386 pointer new_data = reserve_raw(new_size); 00387 std::uninitialized_copy(begin(), p, new_data); 00388 std::uninitialized_fill(new_data + pos, new_data + pos + n, v); 00389 std::uninitialized_copy(p, end(), new_data + pos + n); 00390 deallocate(data_, size_); 00391 capacity_ = new_size; 00392 data_ = new_data; 00393 } 00394 else if(pos + n >= size_) 00395 { 00396 size_type diff = pos + n - size_; 00397 std::uninitialized_copy(p, end(), end() + diff); 00398 std::uninitialized_fill(end(), end() + diff, v); 00399 std::fill(p, end(), v); 00400 } 00401 else 00402 { 00403 size_type diff = size_ - (pos + n); 00404 std::uninitialized_copy(end() - n, end(), end()); 00405 std::copy_backward(p, p + diff, end()); 00406 std::fill(p, p + n, v); 00407 } 00408 size_ = new_size; 00409 return begin() + pos; 00410 } 00411 00412 template <class T, class Alloc> 00413 template <class InputIterator> 00414 typename ArrayVector<T, Alloc>::iterator 00415 ArrayVector<T, Alloc>::insert(iterator p, InputIterator i, InputIterator iend) 00416 { 00417 size_type n = iend - i; 00418 size_type pos = p - begin(); 00419 size_type new_size = size() + n; 00420 if(new_size >= capacity_) 00421 { 00422 pointer new_data = reserve_raw(new_size); 00423 std::uninitialized_copy(begin(), p, new_data); 00424 std::uninitialized_copy(i, iend, new_data + pos); 00425 std::uninitialized_copy(p, end(), new_data + pos + n); 00426 deallocate(data_, size_); 00427 capacity_ = new_size; 00428 data_ = new_data; 00429 } 00430 else if(pos + n >= size_) 00431 { 00432 size_type diff = pos + n - size_; 00433 std::uninitialized_copy(p, end(), end() + diff); 00434 std::uninitialized_copy(iend - diff, iend, end()); 00435 std::copy(i, iend - diff, p); 00436 } 00437 else 00438 { 00439 size_type diff = size_ - (pos + n); 00440 std::uninitialized_copy(end() - n, end(), end()); 00441 std::copy_backward(p, p + diff, end()); 00442 std::copy(i, iend, p); 00443 } 00444 size_ = new_size; 00445 return begin() + pos; 00446 } 00447 00448 template <class T, class Alloc> 00449 typename ArrayVector<T, Alloc>::iterator 00450 ArrayVector<T, Alloc>::erase(iterator p) 00451 { 00452 std::copy(p+1, end(), p); 00453 pop_back(); 00454 return p; 00455 } 00456 00457 template <class T, class Alloc> 00458 typename ArrayVector<T, Alloc>::iterator 00459 ArrayVector<T, Alloc>::erase(iterator p, iterator q) 00460 { 00461 std::copy(q, end(), p); 00462 size_type eraseCount = q - p; 00463 detail::destroy_n(end() - eraseCount, eraseCount); 00464 size_ -= eraseCount; 00465 return p; 00466 } 00467 00468 template <class T, class Alloc> 00469 void ArrayVector<T, Alloc>::reserve( size_type new_capacity ) 00470 { 00471 if(new_capacity <= capacity_) 00472 return; 00473 pointer new_data = reserve_raw(new_capacity); 00474 if(size_ > 0) 00475 std::uninitialized_copy(data_, data_+size_, new_data); 00476 deallocate(data_, size_); 00477 data_ = new_data; 00478 capacity_ = new_capacity; 00479 } 00480 00481 template <class T, class Alloc> 00482 void ArrayVector<T, Alloc>::reserve() 00483 { 00484 if(capacity_ == 0) 00485 reserve(minimumCapacity); 00486 else if(size_ == capacity_) 00487 reserve(2*capacity_); 00488 } 00489 00490 template <class T, class Alloc> 00491 void ArrayVector<T, Alloc>::resize( size_type new_size, value_type const & initial) 00492 { 00493 if(new_size < size_) 00494 erase(begin() + new_size, end()); 00495 else if(size_ < new_size) 00496 { 00497 insert(end(), new_size - size(), initial); 00498 } 00499 } 00500 00501 template <class T, class Alloc> 00502 void ArrayVector<T, Alloc>::swap(this_type & rhs) 00503 { 00504 std::swap(size_, rhs.size_); 00505 std::swap(capacity_, rhs.capacity_); 00506 std::swap(data_, rhs.data_); 00507 } 00508 00509 template <class T, class Alloc> 00510 void ArrayVector<T, Alloc>::deallocate(pointer data, size_type size) 00511 { 00512 if(data) 00513 { 00514 detail::destroy_n(data, size); 00515 alloc_.deallocate(data, size); 00516 } 00517 } 00518 00519 template <class T, class Alloc> 00520 typename ArrayVector<T, Alloc>::pointer 00521 ArrayVector<T, Alloc>::reserve_raw(size_type capacity) 00522 { 00523 pointer data = 0; 00524 if(capacity) 00525 { 00526 data = alloc_.allocate(capacity); 00527 } 00528 return data; 00529 } 00530 00531 } // namespace vigra 00532 00533 00534 #endif /* VIGRA_ARRAY_VECTOR_HXX */
© Ullrich Köthe (koethe@informatik.uni-hamburg.de) |
html generated using doxygen and Python
|