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