[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

array_vector.hxx VIGRA

1 /************************************************************************/
2 /* */
3 /* Copyright 2002-2004 by Ullrich Koethe */
4 /* */
5 /* This file is part of the VIGRA computer vision library. */
6 /* The VIGRA Website is */
7 /* http://hci.iwr.uni-heidelberg.de/vigra/ */
8 /* Please direct questions, bug reports, and contributions to */
9 /* ullrich.koethe@iwr.uni-heidelberg.de or */
10 /* vigra@informatik.uni-hamburg.de */
11 /* */
12 /* Permission is hereby granted, free of charge, to any person */
13 /* obtaining a copy of this software and associated documentation */
14 /* files (the "Software"), to deal in the Software without */
15 /* restriction, including without limitation the rights to use, */
16 /* copy, modify, merge, publish, distribute, sublicense, and/or */
17 /* sell copies of the Software, and to permit persons to whom the */
18 /* Software is furnished to do so, subject to the following */
19 /* conditions: */
20 /* */
21 /* The above copyright notice and this permission notice shall be */
22 /* included in all copies or substantial portions of the */
23 /* Software. */
24 /* */
25 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32 /* OTHER DEALINGS IN THE SOFTWARE. */
33 /* */
34 /************************************************************************/
35 
36 #ifndef VIGRA_ARRAY_VECTOR_HXX
37 #define VIGRA_ARRAY_VECTOR_HXX
38 
39 #include "error.hxx"
40 #include "memory.hxx"
41 #include "numerictraits.hxx"
42 #include <memory>
43 #include <algorithm>
44 #include <iosfwd>
45 
46 #ifdef VIGRA_CHECK_BOUNDS
47 #define VIGRA_ASSERT_INSIDE(diff) \
48  vigra_precondition(diff >= 0, "Index out of bounds");\
49  vigra_precondition((unsigned int)diff < size_, "Index out of bounds");
50 #else
51 #define VIGRA_ASSERT_INSIDE(diff)
52 #endif
53 
54 namespace vigra
55 {
56 
57 template <class T, class Alloc = std::allocator<T> >
59 
60 /** Provide STL conforming interface for C-arrays.
61 
62  This template implements much of the functionality of <a href="http://www.sgi.com/tech/stl/Vector.html">std::vector</a>
63  on top of a C-array. <tt>ArrayVectorView</tt> does not manage the memory
64  it refers to (i.e. it does not allocate or deallocate any memory).
65  Thus, if the underlying memory changes, all dependent <tt>ArrayVectorView</tt>
66  objects are invalidated. This is especially important when <tt>ArrayVectorView</tt>
67  is used as a base class for <tt>ArrayVector</tt>, where several functions
68  (e.g. resize(), insert()) can allocate new memory and thus invalidate the
69  dependent views. The rules what operations invalidate view objects are the
70  same as the rules concerning standard iterators.
71 
72  <b>\#include</b> <vigra/array_vector.hxx><br>
73  Namespace: vigra
74 */
75 template <class T>
77 {
79 
80 public:
81  /** default constructor
82  */
83  typedef T value_type;
84  typedef value_type & reference;
85  typedef value_type const & const_reference;
86  typedef value_type * pointer;
87  typedef value_type const * const_pointer;
88  typedef value_type * iterator;
89  typedef value_type const * const_iterator;
90  typedef std::size_t size_type;
91  typedef std::ptrdiff_t difference_type;
92  typedef std::reverse_iterator<iterator> reverse_iterator;
93  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
94 
95 public:
96  /** default constructor.
97  View contains NULL pointer.
98  */
100  : size_(0),
101  data_(0)
102  {}
103 
104  /** Construct for given array \a data of length \a size.
105  <tt>data, data+size</tt> must form a valid range.
106  */
107  ArrayVectorView( size_type size, pointer const & data)
108  : size_(size),
109  data_(data)
110  {}
111 
112  /** Copy constructor.
113  */
114  ArrayVectorView( this_type const & rhs )
115  : size_(rhs.size_),
116  data_(rhs.data_)
117  {}
118 
119  /** Copy assignment. There are 3 cases:
120 
121  <ul>
122  <li> When this <tt>ArrayVectorView</tt> does not point to valid data
123  (e.g. after default construction), it becomes a copy of \a rhs.
124  <li> When the shapes of the two arrays match, the array contents
125  (not the pointers) are copied.
126  <li> Otherwise, a <tt>PreconditionViolation</tt> exception is thrown.
127  </ul>
128  */
129  ArrayVectorView & operator=( ArrayVectorView const & rhs );
130 
131  /** Copy assignment.
132  When the shapes of the two arrays match, the array contents
133  (not the pointers) are copied. Otherwise, a <tt>PreconditionViolation</tt>
134  exception is thrown.
135  */
136  template <class U>
138  {
139  copyImpl(rhs);
140  return *this;
141  }
142 
143  /** Overwrite all array elements with the value \a initial.
144  */
145  template <class U>
146  void init(U const & initial)
147  {
148  std::fill(begin(), end(), initial);
149  }
150 
151  /** Copy array elements.
152  When the shapes of the two arrays match, the array contents
153  (not the pointers) are copied. Otherwise, a <tt>PreconditionViolation</tt>
154  exception is thrown.
155  */
156  void copy( this_type const & rhs )
157  {
158  if(data_ != rhs.data_)
159  copyImpl(rhs);
160  }
161 
162  /** Copy array elements.
163  When the shapes of the two arrays match, the array contents
164  (not the pointers) are copied. Otherwise, a <tt>PreconditionViolation</tt>
165  exception is thrown.
166  */
167  template <class U>
168  void copy( ArrayVectorView<U> const & rhs )
169  {
170  copyImpl(rhs);
171  }
172 
173  /** Swap array elements.
174  When the shapes of the two arrays match, the array contents
175  (not the pointers) are swapped. Otherwise, a <tt>PreconditionViolation</tt>
176  exception is thrown.
177  */
178  void swapData(this_type rhs)
179  {
180  if(data_ != rhs.data_)
181  swapDataImpl(rhs);
182  }
183 
184  /** Swap array elements.
185  When the shapes of the two arrays match, the array contents
186  (not the pointers) are swapped. Otherwise, a <tt>PreconditionViolation</tt>
187  exception is thrown.
188  */
189  template <class U>
191  {
192  swapDataImpl(rhs);
193  }
194 
195  /** Construct <tt>ArrayVectorView</tt> referring to a subarray.
196  \a begin and \a end must be a valid sub-range of the current array.
197  Otherwise, a <tt>PreconditionViolation</tt>
198  exception is thrown.
199  */
200  this_type subarray (size_type begin, size_type end) const
201  {
202  vigra_precondition(begin <= end && end <= size_,
203  "ArrayVectorView::subarray(): Limits out of range.");
204  return this_type(end-begin, data_ + begin);
205  }
206 
207  /** Get contained const pointer to the data.
208  */
209  inline const_pointer data() const
210  {
211  return data_;
212  }
213 
214  /** Get contained pointer to the data.
215  */
216  inline pointer data()
217  {
218  return data_;
219  }
220 
221  /** Get const iterator referring to the first array element.
222  */
223  inline const_iterator begin() const
224  {
225  return data();
226  }
227 
228  /** Get iterator referring to the first array element.
229  */
230  inline iterator begin()
231  {
232  return data();
233  }
234 
235  /** Get const iterator pointing beyond the last array element.
236  */
237  inline const_iterator end() const
238  {
239  return data() + size();
240  }
241 
242  /** Get iterator pointing beyond the last array element.
243  */
244  inline iterator end()
245  {
246  return data() + size();
247  }
248 
249  /** Get reverse iterator referring to the last array element.
250  */
251  inline reverse_iterator rbegin()
252  {
253  return (reverse_iterator(end()));
254  }
255 
256  /** Get const reverse iterator referring to the last array element.
257  */
258  inline const_reverse_iterator rbegin() const
259  {
260  return (const_reverse_iterator(end()));
261  }
262 
263  /** Get reverse iterator pointing before the first array element.
264  */
265  inline reverse_iterator rend()
266  {
267  return (reverse_iterator(begin()));
268  }
269 
270  /** Get const reverse iterator pointing before the first array element.
271  */
272  inline const_reverse_iterator rend() const
273  {
274  return (const_reverse_iterator(begin()));
275  }
276 
277  /** Access first array element.
278  */
279  reference front()
280  {
281  return *data_;
282  }
283 
284  /** Read first array element.
285  */
286  const_reference front() const
287  {
288  return *data_;
289  }
290 
291  /** Access last array element.
292  */
293  reference back()
294  {
295  return data_[size_-1];
296  }
297 
298  /** Read last array element.
299  */
300  const_reference back() const
301  {
302  return data_[size_-1];
303  }
304 
305  /** Access array element \a i.
306  */
307  reference operator[]( difference_type i )
308  {
309  VIGRA_ASSERT_INSIDE(i);
310  return data()[i];
311  }
312 
313  /** Read array element \a i.
314  */
315  const_reference operator[]( difference_type i ) const
316  {
317  VIGRA_ASSERT_INSIDE(i);
318  return data()[i];
319  }
320 
321  /** Equivalent to <tt>size() == 0</tt>.
322  */
323  bool empty() const
324  {
325  return size_ == 0;
326  }
327 
328  /** Number of elements in the array.
329  */
330  size_type size() const
331  {
332  return size_;
333  }
334 
335  /** Check for element-wise equality of two array.
336  Also returns <tt>false</tt> if the two arrays have different sizes.
337  */
338  template <class U>
339  bool operator==(ArrayVectorView<U> const & rhs) const;
340 
341  /** check whether two arrays are not elementwise equal.
342  Also returns <tt>true</tt> if the two arrays have different sizes.
343  */
344  template <class U>
345  bool operator!=(ArrayVectorView<U> const & rhs) const
346  {
347  return !operator==(rhs);
348  }
349 
350  /** check whether the given point is in the array range.
351  */
352  bool isInside (difference_type const & p) const
353  {
354  return p >= 0 && p < size_;
355  }
356 
357  protected:
358 
359  template <class U>
360  void copyImpl(const ArrayVectorView <U>& rhs);
361 
362  void copyImpl(const ArrayVectorView & rhs);
363 
364  template <class U>
365  void swapDataImpl(const ArrayVectorView <U>& rhs);
366 
367  size_type size_;
368  pointer data_;
369 };
370 
371 template <class T>
372 ArrayVectorView<T> & ArrayVectorView<T>::operator=( ArrayVectorView<T> const & rhs )
373 {
374  if(data_ == 0)
375  {
376  size_ = rhs.size_;
377  data_ = rhs.data_;
378  }
379  else if(data_ != rhs.data_)
380  copyImpl(rhs);
381  return *this;
382 }
383 
384 template <class T>
385 template <class U>
387 {
388  if(size() != rhs.size())
389  return false;
390  for(unsigned int k=0; k<size(); ++k)
391  if(data_[k] != rhs[k])
392  return false;
393  return true;
394 }
395 
396 template <class T>
397 void
399 {
400  vigra_precondition (size() == rhs.size(),
401  "ArrayVectorView::copy(): shape mismatch.");
402  if(size() == 0) // needed because MSVC debug assertions in std::copy() may fire
403  return; // "invalid address: data_ == NULL" even when nothing is to be copied
404  // use copy() or copy_backward() according to possible overlap of this and rhs
405  if(data_ <= rhs.data())
406  {
407  std::copy(rhs.begin(), rhs.end(), begin());
408  }
409  else
410  {
411  std::copy_backward(rhs.begin(), rhs.end(), end());
412  }
413 }
414 
415 template <class T>
416 template <class U>
417 void
418 ArrayVectorView <T>::copyImpl(const ArrayVectorView <U>& rhs)
419 {
420  vigra_precondition (size() == rhs.size(),
421  "ArrayVectorView::copy(): shape mismatch.");
422  std::copy(rhs.begin(), rhs.end(), begin());
423 }
424 
425 template <class T>
426 template <class U>
427 void
428 ArrayVectorView <T>::swapDataImpl(const ArrayVectorView <U>& rhs)
429 {
430  vigra_precondition (size () == rhs.size() (),
431  "ArrayVectorView::swapData(): size mismatch.");
432 
433  // check for overlap
434  if(data_ + size_ <= rhs.data_ || rhs.data_ + size_ <= data_)
435  {
436  for(unsigned int k=0; k<size_; ++k)
437  std::swap(data_[k], rhs.data_[k]);
438  }
439  else
440  {
441  ArrayVector<T> t(*this);
442  copyImpl(rhs);
443  rhs.copyImpl(*this);
444  }
445 }
446 
447 
448 /** Replacement for <tt>std::vector</tt>.
449 
450  This template implements the same functionality as <tt>a href="http://www.sgi.com/tech/stl/Vector.html">std::vector</a></tt> (see there for detailed documentation).
451  However, it gives two useful guarantees, that <tt>std::vector</tt> fails
452  to provide:
453 
454  <ul>
455  <li>The memory is always allocated as one contiguous piece.</li>
456  <li>The iterator is always a <TT>T *</TT> </li>
457  </ul>
458 
459  This means that memory managed by <tt>ArrayVector</tt> can be passed
460  to algorithms that expect raw memory. This is especially important
461  when legacy or C code has to be called, but it is also useful for certain
462  optimizations.
463 
464  Moreover, <tt>ArrayVector</tt> is derived from <tt>ArrayVectorView</tt> so that one
465  can create views of the array (in particular, subarrays). This implies another
466  important difference to <tt>std::vector</tt>: the indexing operator
467  (<tt>ArrayVector::operator[]</tt>) takes <tt>signed</tt> indices. In this way,
468  an <tt>ArrayVectorView</tt> can be used with negative indices:
469 
470  \code
471  ArrayVector<int> data(100);
472  ArrayVectorView<int> view = data.subarray(50, 100);
473 
474  view[-50] = 1; // valid access
475  \endcode
476 
477  Refer to the documentation of <tt>std::vector</tt> for a detailed
478  description of <tt>ArrayVector</tt> functionality.
479 
480  <b>\#include</b> <vigra/array_vector.hxx><br>
481  Namespace: vigra
482 */
483 template <class T, class Alloc /* = std::allocator<T> */ >
484 class ArrayVector
485 : public ArrayVectorView<T>
486 {
487  typedef ArrayVector<T, Alloc> this_type;
488  enum { minimumCapacity = 2, resizeFactor = 2 };
489 
490 public:
491  typedef ArrayVectorView<T> view_type;
492  typedef typename view_type::value_type value_type;
493  typedef typename view_type::reference reference;
494  typedef typename view_type::const_reference const_reference;
495  typedef typename view_type::pointer pointer;
496  typedef typename view_type::const_pointer const_pointer;
497  typedef typename view_type::iterator iterator;
498  typedef typename view_type::const_iterator const_iterator;
499  typedef typename view_type::size_type size_type;
500  typedef typename view_type::difference_type difference_type;
501  typedef typename view_type::reverse_iterator reverse_iterator;
502  typedef typename view_type::const_reverse_iterator const_reverse_iterator;
503  typedef Alloc allocator_type;
504 
505 public:
506  ArrayVector()
507  : view_type(),
508  capacity_(minimumCapacity),
509  alloc_(Alloc())
510  {
511  this->data_ = reserve_raw(capacity_);
512  }
513 
514  explicit ArrayVector(Alloc const & alloc)
515  : view_type(),
516  capacity_(minimumCapacity),
517  alloc_(alloc)
518  {
519  this->data_ = reserve_raw(capacity_);
520  }
521 
522  explicit ArrayVector( size_type size, Alloc const & alloc = Alloc())
523  : view_type(),
524  alloc_(alloc)
525  {
526  initImpl(size, value_type(), VigraTrueType());
527  }
528 
529  ArrayVector( size_type size, value_type const & initial, Alloc const & alloc = Alloc())
530  : view_type(),
531  alloc_(alloc)
532  {
533  initImpl(size, initial, VigraTrueType());
534  }
535 
536 
537  ArrayVector( this_type const & rhs )
538  : view_type(),
539  alloc_(rhs.alloc_)
540  {
541  initImpl(rhs.begin(), rhs.end(), VigraFalseType());
542  }
543 
544  template <class U>
545  explicit ArrayVector( ArrayVectorView<U> const & rhs, Alloc const & alloc = Alloc() )
546  : view_type(),
547  alloc_(alloc)
548  {
549  initImpl(rhs.begin(), rhs.end(), VigraFalseType());
550  }
551 
552  template <class InputIterator>
553  ArrayVector(InputIterator i, InputIterator end)
554  {
555  initImpl(i, end, typename NumericTraits<InputIterator>::isIntegral());
556  }
557 
558  template <class InputIterator>
559  ArrayVector(InputIterator i, InputIterator end, Alloc const & alloc)
560  : alloc_(alloc)
561  {
562  initImpl(i, end, typename NumericTraits<InputIterator>::isIntegral());
563  }
564 
565  this_type & operator=( this_type const & rhs )
566  {
567  if(this == &rhs)
568  return *this;
569  if(this->size_ == rhs.size_)
570  this->copyImpl(rhs);
571  else
572  {
573  ArrayVector t(rhs);
574  this->swap(t);
575  }
576  return *this;
577  }
578 
579  template <class U>
580  this_type & operator=( ArrayVectorView<U> const & rhs);
581 
582  ~ArrayVector()
583  {
584  deallocate(this->data_, this->size_);
585  }
586 
587  void pop_back();
588 
589  void push_back( value_type const & t );
590 
591  iterator insert(iterator p, value_type const & v);
592 
593  iterator insert(iterator p, size_type n, value_type const & v);
594 
595  template <class InputIterator>
596  iterator insert(iterator p, InputIterator i, InputIterator iend);
597 
598  iterator erase(iterator p);
599 
600  iterator erase(iterator p, iterator q);
601 
602  void clear();
603 
604  void reserve( size_type new_capacity );
605 
606  void reserve();
607 
608  void resize( size_type new_size, value_type const & initial );
609 
610  void resize( size_type new_size )
611  {
612  resize(new_size, value_type());
613  }
614 
615  size_type capacity() const
616  {
617  return capacity_;
618  }
619 
620  void swap(this_type & rhs);
621 
622  private:
623 
624  void deallocate(pointer data, size_type size);
625 
626  pointer reserve_raw(size_type capacity);
627 
628  void initImpl( size_type size, value_type const & initial, VigraTrueType /*isIntegral*/);
629 
630  template <class Iter>
631  void initImpl( Iter i, Iter end, VigraFalseType /*isIntegral*/);
632 
633  template <class Iter>
634  void initImpl( Iter i, Iter end, Error_NumericTraits_not_specialized_for_this_case)
635  {
636  initImpl(i, end, VigraFalseType());
637  }
638 
639  size_type capacity_;
640  Alloc alloc_;
641 };
642 
643 template <class T, class Alloc>
644 template <class U>
645 ArrayVector<T, Alloc> & ArrayVector<T, Alloc>::operator=( ArrayVectorView<U> const & rhs )
646 {
647  if(this->size_ == rhs.size())
648  this->copyImpl(rhs);
649  else
650  {
651  ArrayVector t(rhs);
652  this->swap(t);
653  }
654  return *this;
655 }
656 
657 template <class T, class Alloc>
658 inline void ArrayVector<T, Alloc>::pop_back()
659 {
660  --this->size_;
661  alloc_.destroy(this->data_ + this->size_);
662 }
663 
664 template <class T, class Alloc>
665 inline void ArrayVector<T, Alloc>::push_back( value_type const & t )
666 {
667  reserve();
668  alloc_.construct(this->data_ + this->size_, t);
669  ++this->size_;
670 }
671 
672 template <class T, class Alloc>
673 inline void ArrayVector<T, Alloc>::clear()
674 {
675  detail::destroy_n(this->data_, (int)this->size_);
676  this->size_ = 0;
677 }
678 
679 template <class T, class Alloc>
680 typename ArrayVector<T, Alloc>::iterator
681 ArrayVector<T, Alloc>::insert(iterator p, value_type const & v)
682 {
683  difference_type pos = p - this->begin();
684  if(p == this->end())
685  {
686  push_back(v);
687  p = this->begin() + pos;
688  }
689  else
690  {
691  T lastElement = this->back();
692  push_back(lastElement);
693  p = this->begin() + pos;
694  std::copy_backward(p, this->end() - 2, this->end() - 1);
695  *p = v;
696  }
697  return p;
698 }
699 
700 template <class T, class Alloc>
701 typename ArrayVector<T, Alloc>::iterator
702 ArrayVector<T, Alloc>::insert(iterator p, size_type n, value_type const & v)
703 {
704  difference_type pos = p - this->begin();
705  size_type new_size = this->size() + n;
706  if(new_size > capacity_)
707  {
708  size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
709  pointer new_data = reserve_raw(new_capacity);
710  try
711  {
712  std::uninitialized_copy(this->begin(), p, new_data);
713  std::uninitialized_fill(new_data + pos, new_data + pos + n, v);
714  std::uninitialized_copy(p, this->end(), new_data + pos + n);
715  }
716  catch(...)
717  {
718  alloc_.deallocate(new_data, new_capacity);
719  throw;
720  }
721  deallocate(this->data_, this->size_);
722  capacity_ = new_capacity;
723  this->data_ = new_data;
724  }
725  else if(pos + n > this->size_)
726  {
727  size_type diff = pos + n - this->size_;
728  std::uninitialized_copy(p, this->end(), this->end() + diff);
729  std::uninitialized_fill(this->end(), this->end() + diff, v);
730  std::fill(p, this->end(), v);
731  }
732  else
733  {
734  size_type diff = this->size_ - (pos + n);
735  std::uninitialized_copy(this->end() - n, this->end(), this->end());
736  std::copy_backward(p, p + diff, this->end());
737  std::fill(p, p + n, v);
738  }
739  this->size_ = new_size;
740  return this->begin() + pos;
741 }
742 
743 template <class T, class Alloc>
744 template <class InputIterator>
745 typename ArrayVector<T, Alloc>::iterator
746 ArrayVector<T, Alloc>::insert(iterator p, InputIterator i, InputIterator iend)
747 {
748  size_type n = std::distance(i, iend);
749  size_type pos = p - this->begin();
750  size_type new_size = this->size() + n;
751  if(new_size > capacity_)
752  {
753  size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
754  pointer new_data = reserve_raw(new_capacity);
755  try
756  {
757  std::uninitialized_copy(this->begin(), p, new_data);
758  std::uninitialized_copy(i, iend, new_data + pos);
759  std::uninitialized_copy(p, this->end(), new_data + pos + n);
760  }
761  catch(...)
762  {
763  alloc_.deallocate(new_data, new_capacity);
764  throw;
765  }
766  deallocate(this->data_, this->size_);
767  capacity_ = new_capacity;
768  this->data_ = new_data;
769  }
770  else if(pos + n > this->size_)
771  {
772  size_type diff = pos + n - this->size_;
773  std::uninitialized_copy(p, this->end(), this->end() + diff);
774  InputIterator split = i;
775  std::advance(split, n - diff);
776  std::uninitialized_copy(split, iend, this->end());
777  std::copy(i, split, p);
778  }
779  else
780  {
781  size_type diff = this->size_ - (pos + n);
782  std::uninitialized_copy(this->end() - n, this->end(), this->end());
783  std::copy_backward(p, p + diff, this->end());
784  std::copy(i, iend, p);
785  }
786  this->size_ = new_size;
787  return this->begin() + pos;
788 }
789 
790 template <class T, class Alloc>
791 typename ArrayVector<T, Alloc>::iterator
792 ArrayVector<T, Alloc>::erase(iterator p)
793 {
794  std::copy(p+1, this->end(), p);
795  pop_back();
796  return p;
797 }
798 
799 template <class T, class Alloc>
800 typename ArrayVector<T, Alloc>::iterator
801 ArrayVector<T, Alloc>::erase(iterator p, iterator q)
802 {
803  std::copy(q, this->end(), p);
804  difference_type eraseCount = q - p;
805  detail::destroy_n(this->end() - eraseCount, eraseCount);
806  this->size_ -= eraseCount;
807  return p;
808 }
809 
810 template <class T, class Alloc>
811 inline void
812 ArrayVector<T, Alloc>::reserve( size_type new_capacity )
813 {
814  if(new_capacity <= capacity_)
815  return;
816  pointer new_data = reserve_raw(new_capacity);
817  if(this->size_ > 0)
818  std::uninitialized_copy(this->data_, this->data_+this->size_, new_data);
819  deallocate(this->data_, this->size_);
820  this->data_ = new_data;
821  capacity_ = new_capacity;
822 }
823 
824 template <class T, class Alloc>
825 inline void
826 ArrayVector<T, Alloc>::reserve()
827 {
828  if(capacity_ == 0)
829  reserve(minimumCapacity);
830  else if(this->size_ == capacity_)
831  reserve(resizeFactor*capacity_);
832 }
833 
834 template <class T, class Alloc>
835 inline void
836 ArrayVector<T, Alloc>::resize( size_type new_size, value_type const & initial)
837 {
838  if(new_size < this->size_)
839  erase(this->begin() + new_size, this->end());
840  else if(this->size_ < new_size)
841  {
842  insert(this->end(), new_size - this->size(), initial);
843  }
844 }
845 
846 template <class T, class Alloc>
847 inline void
848 ArrayVector<T, Alloc>::initImpl( size_type size, value_type const & initial, VigraTrueType /*isIntegral*/)
849 {
850  this->size_ = size;
851  capacity_ = size;
852  this->data_ = reserve_raw(capacity_);
853  if(this->size_ > 0)
854  std::uninitialized_fill(this->data_, this->data_+this->size_, initial);
855 }
856 
857 template <class T, class Alloc>
858 template <class Iter>
859 inline void
860 ArrayVector<T, Alloc>::initImpl( Iter i, Iter end, VigraFalseType /*isIntegral*/)
861 {
862  this->size_ = std::distance(i, end);
863  capacity_ = this->size_;
864  this->data_ = reserve_raw(capacity_);
865  if(this->size_ > 0)
866  detail::uninitializedCopy(i, end, this->data_);
867 }
868 
869 template <class T, class Alloc>
870 inline void
871 ArrayVector<T, Alloc>::swap(this_type & rhs)
872 {
873  std::swap(this->size_, rhs.size_);
874  std::swap(capacity_, rhs.capacity_);
875  std::swap(this->data_, rhs.data_);
876 }
877 
878 template <class T, class Alloc>
879 inline void
880 ArrayVector<T, Alloc>::deallocate(pointer data, size_type size)
881 {
882  if(data)
883  {
884  detail::destroy_n(data, (int)size);
885  alloc_.deallocate(data, size);
886  }
887 }
888 
889 template <class T, class Alloc>
890 inline typename ArrayVector<T, Alloc>::pointer
891 ArrayVector<T, Alloc>::reserve_raw(size_type capacity)
892 {
893  pointer data = 0;
894  if(capacity)
895  {
896  data = alloc_.allocate(capacity);
897  }
898  return data;
899 }
900 
901 } // namespace vigra
902 
903 namespace std {
904 
905 template <class T>
906 ostream & operator<<(ostream & s, vigra::ArrayVectorView<T> const & a)
907 {
908  for(int k=0; k<(int)a.size()-1; ++k)
909  s << a[k] << ", ";
910  if(a.size())
911  s << a.back();
912  return s;
913 }
914 
915 } // namespace std
916 
917 #undef VIGRA_ASSERT_INSIDE
918 #endif /* VIGRA_ARRAY_VECTOR_HXX */
iterator end()
Definition: array_vector.hxx:244
reference back()
Definition: array_vector.hxx:293
void swapData(this_type rhs)
Definition: array_vector.hxx:178
this_type & operator=(ArrayVectorView< U > const &rhs)
Definition: array_vector.hxx:137
ArrayVectorView(size_type size, pointer const &data)
Definition: array_vector.hxx:107
bool empty() const
Definition: array_vector.hxx:323
Definition: array_vector.hxx:76
const_iterator begin() const
Definition: array_vector.hxx:223
reverse_iterator rend()
Definition: array_vector.hxx:265
bool isInside(difference_type const &p) const
Definition: array_vector.hxx:352
const_reverse_iterator rbegin() const
Definition: array_vector.hxx:258
const_reference back() const
Definition: array_vector.hxx:300
ArrayVectorView & operator=(ArrayVectorView const &rhs)
void copy(ArrayVectorView< U > const &rhs)
Definition: array_vector.hxx:168
reference operator[](difference_type i)
Definition: array_vector.hxx:307
Definition: array_vector.hxx:58
reference front()
Definition: array_vector.hxx:279
ArrayVectorView()
Definition: array_vector.hxx:99
bool operator!=(ArrayVectorView< U > const &rhs) const
Definition: array_vector.hxx:345
void init(U const &initial)
Definition: array_vector.hxx:146
pointer data()
Definition: array_vector.hxx:216
const_reference front() const
Definition: array_vector.hxx:286
this_type subarray(size_type begin, size_type end) const
Definition: array_vector.hxx:200
iterator begin()
Definition: array_vector.hxx:230
T value_type
Definition: array_vector.hxx:83
void copy(this_type const &rhs)
Definition: array_vector.hxx:156
reverse_iterator rbegin()
Definition: array_vector.hxx:251
const_iterator end() const
Definition: array_vector.hxx:237
const_pointer data() const
Definition: array_vector.hxx:209
size_type size() const
Definition: array_vector.hxx:330
ArrayVectorView(this_type const &rhs)
Definition: array_vector.hxx:114
void swapData(ArrayVectorView< U > rhs)
Definition: array_vector.hxx:190
bool operator==(ArrayVectorView< U > const &rhs) const
Definition: array_vector.hxx:386
const_reference operator[](difference_type i) const
Definition: array_vector.hxx:315
const_reverse_iterator rend() const
Definition: array_vector.hxx:272

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.10.0 (Tue Dec 31 2013)