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