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

array_vector.hxx
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(diff < (difference_type)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> >
58 class ArrayVector;
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>
76 class ArrayVectorView
77{
78 typedef ArrayVectorView<T> this_type;
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 */
99 ArrayVectorView()
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>
137 this_type & operator=( ArrayVectorView<U> const & rhs )
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>
190 void swapData(ArrayVectorView<U> rhs)
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 const iterator referring to the first array element.
250 */
251 inline const_iterator cbegin() const
252 {
253 return data();
254 }
255
256 /** Get const iterator pointing beyond the last array element.
257 */
258 inline const_iterator cend() const
259 {
260 return data() + size();
261 }
262
263 /** Get reverse iterator referring to the last array element.
264 */
265 inline reverse_iterator rbegin()
266 {
267 return (reverse_iterator(end()));
268 }
269
270 /** Get const reverse iterator referring to the last array element.
271 */
272 inline const_reverse_iterator rbegin() const
273 {
274 return (const_reverse_iterator(end()));
275 }
276
277 /** Get reverse iterator pointing before the first array element.
278 */
279 inline reverse_iterator rend()
280 {
281 return (reverse_iterator(begin()));
282 }
283
284 /** Get const reverse iterator pointing before the first array element.
285 */
286 inline const_reverse_iterator rend() const
287 {
288 return (const_reverse_iterator(begin()));
289 }
290
291 /** Get const reverse iterator referring to the last array element.
292 */
293 inline const_reverse_iterator crbegin() const
294 {
295 return (const_reverse_iterator(end()));
296 }
297
298 /** Get const reverse iterator pointing before the first array element.
299 */
300 inline const_reverse_iterator crend() const
301 {
302 return (const_reverse_iterator(begin()));
303 }
304
305 /** Access first array element.
306 */
307 reference front()
308 {
309 return *data_;
310 }
311
312 /** Read first array element.
313 */
314 const_reference front() const
315 {
316 return *data_;
317 }
318
319 /** Access last array element.
320 */
321 reference back()
322 {
323 return data_[size_-1];
324 }
325
326 /** Read last array element.
327 */
328 const_reference back() const
329 {
330 return data_[size_-1];
331 }
332
333 /** Access array element \a i.
334 */
335 reference operator[]( difference_type i )
336 {
337 VIGRA_ASSERT_INSIDE(i);
338 return data()[i];
339 }
340
341 /** Read array element \a i.
342 */
343 const_reference operator[]( difference_type i ) const
344 {
345 VIGRA_ASSERT_INSIDE(i);
346 return data()[i];
347 }
348
349 /** Equivalent to <tt>size() == 0</tt>.
350 */
351 bool empty() const
352 {
353 return size_ == 0;
354 }
355
356 /** Number of elements in the array.
357 */
358 size_type size() const
359 {
360 return size_;
361 }
362
363 /** Check for element-wise equality of two array.
364 Also returns <tt>false</tt> if the two arrays have different sizes.
365 */
366 template <class U>
367 bool operator==(ArrayVectorView<U> const & rhs) const;
368
369 /** check whether two arrays are not elementwise equal.
370 Also returns <tt>true</tt> if the two arrays have different sizes.
371 */
372 template <class U>
373 bool operator!=(ArrayVectorView<U> const & rhs) const
374 {
375 return !operator==(rhs);
376 }
377
378 /** check whether the given point is in the array range.
379 */
380 bool isInside (difference_type const & p) const
381 {
382 return p >= 0 && p < size_;
383 }
384
385 protected:
386
387 template <class U>
388 void copyImpl(const ArrayVectorView <U>& rhs);
389
390 void copyImpl(const ArrayVectorView & rhs);
391
392 template <class U>
393 void swapDataImpl(const ArrayVectorView <U>& rhs);
394
395 size_type size_;
396 pointer data_;
397};
398
399 template <class T>
400ArrayVectorView<T> & ArrayVectorView<T>::operator=( ArrayVectorView<T> const & rhs )
401{
402 if(data_ == 0)
403 {
404 size_ = rhs.size_;
405 data_ = rhs.data_;
406 }
407 else if(data_ != rhs.data_)
408 copyImpl(rhs);
409 return *this;
410}
411
412 template <class T>
413 template <class U>
414 bool ArrayVectorView<T>::operator==(ArrayVectorView<U> const & rhs) const
415{
416 if(size() != rhs.size())
417 return false;
418 for(size_type k=0; k<size(); ++k)
419 if(data_[k] != rhs[k])
420 return false;
421 return true;
422}
423
424 template <class T>
425 void
426 ArrayVectorView <T>::copyImpl(const ArrayVectorView & rhs)
427{
428 vigra_precondition (size() == rhs.size(),
429 "ArrayVectorView::copy(): shape mismatch.");
430 if(size() == 0) // needed because MSVC debug assertions in std::copy() may fire
431 return; // "invalid address: data_ == NULL" even when nothing is to be copied
432 // use copy() or copy_backward() according to possible overlap of this and rhs
433 if(data_ <= rhs.data())
434 {
435 std::copy(rhs.begin(), rhs.end(), begin());
436 }
437 else
438 {
439 std::copy_backward(rhs.begin(), rhs.end(), end());
440 }
441}
442
443 template <class T>
444 template <class U>
445 void
446ArrayVectorView <T>::copyImpl(const ArrayVectorView <U>& rhs)
447{
448 vigra_precondition (size() == rhs.size(),
449 "ArrayVectorView::copy(): shape mismatch.");
450 std::copy(rhs.begin(), rhs.end(), begin());
451}
452
453 template <class T>
454 template <class U>
455 void
456ArrayVectorView <T>::swapDataImpl(const ArrayVectorView <U>& rhs)
457{
458 vigra_precondition (size () == rhs.size() (),
459 "ArrayVectorView::swapData(): size mismatch.");
460
461 // check for overlap
462 if(data_ + size_ <= rhs.data_ || rhs.data_ + size_ <= data_)
463 {
464 for(size_type k=0; k<size_; ++k)
465 std::swap(data_[k], rhs.data_[k]);
466 }
467 else
468 {
469 ArrayVector<T> t(*this);
470 copyImpl(rhs);
471 rhs.copyImpl(t);
472 }
473}
474
475
476/** Replacement for <tt>std::vector</tt>.
477
478 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).
479 However, it gives two useful guarantees, that <tt>std::vector</tt> fails
480 to provide:
481
482 <ul>
483 <li>The memory is always allocated as one contiguous piece.</li>
484 <li>The iterator is always a <TT>T *</TT> </li>
485 </ul>
486
487 This means that memory managed by <tt>ArrayVector</tt> can be passed
488 to algorithms that expect raw memory. This is especially important
489 when legacy or C code has to be called, but it is also useful for certain
490 optimizations.
491
492 Moreover, <tt>ArrayVector</tt> is derived from <tt>ArrayVectorView</tt> so that one
493 can create views of the array (in particular, subarrays). This implies another
494 important difference to <tt>std::vector</tt>: the indexing operator
495 (<tt>ArrayVector::operator[]</tt>) takes <tt>signed</tt> indices. In this way,
496 an <tt>ArrayVectorView</tt> can be used with negative indices:
497
498 \code
499 ArrayVector<int> data(100);
500 ArrayVectorView<int> view = data.subarray(50, 100);
501
502 view[-50] = 1; // valid access
503 \endcode
504
505 Refer to the documentation of <tt>std::vector</tt> for a detailed
506 description of <tt>ArrayVector</tt> functionality.
507
508 <b>\#include</b> <vigra/array_vector.hxx><br>
509 Namespace: vigra
510*/
511 template <class T, class Alloc /* = std::allocator<T> */ >
512 class ArrayVector
513: public ArrayVectorView<T>
514{
515 typedef ArrayVector<T, Alloc> this_type;
516 enum { minimumCapacity = 2, resizeFactor = 2 };
517
518 public:
519 typedef ArrayVectorView<T> view_type;
520 typedef typename view_type::value_type value_type;
521 typedef typename view_type::reference reference;
522 typedef typename view_type::const_reference const_reference;
523 typedef typename view_type::pointer pointer;
524 typedef typename view_type::const_pointer const_pointer;
525 typedef typename view_type::iterator iterator;
526 typedef typename view_type::const_iterator const_iterator;
527 typedef typename view_type::size_type size_type;
528 typedef typename view_type::difference_type difference_type;
529 typedef typename view_type::reverse_iterator reverse_iterator;
530 typedef typename view_type::const_reverse_iterator const_reverse_iterator;
531 typedef Alloc allocator_type;
532
533 public:
534 ArrayVector()
535 : view_type(),
536 capacity_(minimumCapacity),
537 alloc_(Alloc())
538 {
539 this->data_ = reserve_raw(capacity_);
540 }
541
542 explicit ArrayVector(Alloc const & alloc)
543 : view_type(),
544 capacity_(minimumCapacity),
545 alloc_(alloc)
546 {
547 this->data_ = reserve_raw(capacity_);
548 }
549
550 explicit ArrayVector( size_type size, Alloc const & alloc = Alloc())
551 : view_type(),
552 alloc_(alloc)
553 {
554 initImpl(size, value_type(), VigraTrueType());
555 }
556
557 ArrayVector( size_type size, value_type const & initial, Alloc const & alloc = Alloc())
558 : view_type(),
559 alloc_(alloc)
560 {
561 initImpl(size, initial, VigraTrueType());
562 }
563
564
565 ArrayVector( this_type const & rhs )
566 : view_type(),
567 alloc_(rhs.alloc_)
568 {
569 initImpl(rhs.begin(), rhs.end(), VigraFalseType());
570 }
571
572 template <class U>
573 explicit ArrayVector( ArrayVectorView<U> const & rhs, Alloc const & alloc = Alloc() )
574 : view_type(),
575 alloc_(alloc)
576 {
577 initImpl(rhs.begin(), rhs.end(), VigraFalseType());
578 }
579
580 template <class InputIterator>
581 ArrayVector(InputIterator i, InputIterator end)
582 {
583 initImpl(i, end, typename NumericTraits<InputIterator>::isIntegral());
584 }
585
586 template <class InputIterator>
587 ArrayVector(InputIterator i, InputIterator end, Alloc const & alloc)
588 : alloc_(alloc)
589 {
590 initImpl(i, end, typename NumericTraits<InputIterator>::isIntegral());
591 }
592
593 this_type & operator=( this_type const & rhs )
594 {
595 if(this == &rhs)
596 return *this;
597 if(this->size_ == rhs.size_)
598 this->copyImpl(rhs);
599 else
600 {
601 ArrayVector t(rhs);
602 this->swap(t);
603 }
604 return *this;
605 }
606
607 template <class U>
608 this_type & operator=( ArrayVectorView<U> const & rhs);
609
610 ~ArrayVector()
611 {
612 deallocate(this->data_, this->size_, this->capacity_);
613 }
614
615 void pop_back();
616
617 void push_back( value_type const & t );
618
619 iterator insert(iterator p, value_type const & v);
620
621 iterator insert(iterator p, size_type n, value_type const & v);
622
623 template <class InputIterator>
624 iterator insert(iterator p, InputIterator i, InputIterator iend);
625
626 iterator erase(iterator p);
627
628 iterator erase(iterator p, iterator q);
629
630 void clear();
631
632 pointer reserveImpl( bool dealloc, size_type new_capacity );
633
634 pointer reserveImpl( bool dealloc);
635
636 void reserve()
637 {
638 reserveImpl(true);
639 }
640
641 void reserve( size_type new_capacity )
642 {
643 reserveImpl(true, new_capacity);
644 }
645
646 void resize( size_type new_size, value_type const & initial );
647
648 void resize( size_type new_size )
649 {
650 resize(new_size, value_type());
651 }
652
653 size_type capacity() const
654 {
655 return capacity_;
656 }
657
658 void swap(this_type & rhs);
659
660 private:
661
662 void deallocate(pointer data, size_type size, size_type capacity);
663
664 pointer reserve_raw(size_type capacity);
665
666 void initImpl( size_type size, value_type const & initial, VigraTrueType /*isIntegral*/);
667
668 template <class Iter>
669 void initImpl( Iter i, Iter end, VigraFalseType /*isIntegral*/);
670
671 template <class Iter>
672 void initImpl( Iter i, Iter end, Error_NumericTraits_not_specialized_for_this_case)
673 {
674 initImpl(i, end, VigraFalseType());
675 }
676
677 size_type capacity_;
678 Alloc alloc_;
679};
680
681 template <class T, class Alloc>
682 template <class U>
683 ArrayVector<T, Alloc> & ArrayVector<T, Alloc>::operator=( ArrayVectorView<U> const & rhs )
684{
685 if(this->size_ == rhs.size())
686 this->copyImpl(rhs);
687 else
688 {
689 ArrayVector t(rhs);
690 this->swap(t);
691 }
692 return *this;
693}
694
695 template <class T, class Alloc>
696 inline void ArrayVector<T, Alloc>::pop_back()
697{
698 --this->size_;
699 alloc_.destroy(this->data_ + this->size_);
700}
701
702 template <class T, class Alloc>
703 inline void ArrayVector<T, Alloc>::push_back( value_type const & t )
704{
705 size_type old_capacity = this->capacity_;
706 pointer old_data = reserveImpl(false);
707 alloc_.construct(this->data_ + this->size_, t);
708 // deallocate old data _after_ construction of new element, so that
709 // 't' can refer to the old data as in 'push_back(front())'
710 deallocate(old_data, this->size_, old_capacity);
711 ++this->size_;
712}
713
714 template <class T, class Alloc>
715 inline void ArrayVector<T, Alloc>::clear()
716{
717 detail::destroy_n(this->data_, this->size_);
718 this->size_ = 0;
719}
720
721 template <class T, class Alloc>
722 typename ArrayVector<T, Alloc>::iterator
723ArrayVector<T, Alloc>::insert(iterator p, value_type const & v)
724{
725 difference_type pos = p - this->begin();
726 if(p == this->end())
727 {
728 push_back(v);
729 p = this->begin() + pos;
730 }
731 else
732 {
733 T lastElement = this->back();
734 push_back(lastElement);
735 p = this->begin() + pos;
736 std::copy_backward(p, this->end() - 2, this->end() - 1);
737 *p = v;
738 }
739 return p;
740}
741
742 template <class T, class Alloc>
743 typename ArrayVector<T, Alloc>::iterator
744ArrayVector<T, Alloc>::insert(iterator p, size_type n, value_type const & v)
745{
746 difference_type pos = p - this->begin();
747 size_type new_size = this->size() + n;
748 if(new_size > capacity_)
749 {
750 size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
751 pointer new_data = reserve_raw(new_capacity);
752 try
753 {
754 std::uninitialized_copy(this->begin(), p, new_data);
755 std::uninitialized_fill(new_data + pos, new_data + pos + n, v);
756 std::uninitialized_copy(p, this->end(), new_data + pos + n);
757 }
758 catch(...)
759 {
760 alloc_.deallocate(new_data, new_capacity);
761 throw;
762 }
763 deallocate(this->data_, this->size_, this->capacity_);
764 capacity_ = new_capacity;
765 this->data_ = new_data;
766 }
767 else if(pos + n > this->size_)
768 {
769 size_type diff = pos + n - this->size_;
770 std::uninitialized_copy(p, this->end(), this->end() + diff);
771 std::uninitialized_fill(this->end(), this->end() + diff, v);
772 std::fill(p, this->end(), v);
773 }
774 else
775 {
776 size_type diff = this->size_ - (pos + n);
777 std::uninitialized_copy(this->end() - n, this->end(), this->end());
778 std::copy_backward(p, p + diff, this->end());
779 std::fill(p, p + n, v);
780 }
781 this->size_ = new_size;
782 return this->begin() + pos;
783}
784
785 template <class T, class Alloc>
786 template <class InputIterator>
787 typename ArrayVector<T, Alloc>::iterator
788ArrayVector<T, Alloc>::insert(iterator p, InputIterator i, InputIterator iend)
789{
790 size_type n = std::distance(i, iend);
791 size_type pos = p - this->begin();
792 size_type new_size = this->size() + n;
793 if(new_size > capacity_)
794 {
795 size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
796 pointer new_data = reserve_raw(new_capacity);
797 try
798 {
799 std::uninitialized_copy(this->begin(), p, new_data);
800 std::uninitialized_copy(i, iend, new_data + pos);
801 std::uninitialized_copy(p, this->end(), new_data + pos + n);
802 }
803 catch(...)
804 {
805 alloc_.deallocate(new_data, new_capacity);
806 throw;
807 }
808 deallocate(this->data_, this->size_, this->capacity_);
809 capacity_ = new_capacity;
810 this->data_ = new_data;
811 }
812 else if(pos + n > this->size_)
813 {
814 size_type diff = pos + n - this->size_;
815 std::uninitialized_copy(p, this->end(), this->end() + diff);
816 InputIterator split = i;
817 std::advance(split, n - diff);
818 std::uninitialized_copy(split, iend, this->end());
819 std::copy(i, split, p);
820 }
821 else
822 {
823 size_type diff = this->size_ - (pos + n);
824 std::uninitialized_copy(this->end() - n, this->end(), this->end());
825 std::copy_backward(p, p + diff, this->end());
826 std::copy(i, iend, p);
827 }
828 this->size_ = new_size;
829 return this->begin() + pos;
830}
831
832 template <class T, class Alloc>
833 typename ArrayVector<T, Alloc>::iterator
834ArrayVector<T, Alloc>::erase(iterator p)
835{
836 std::copy(p+1, this->end(), p);
837 pop_back();
838 return p;
839}
840
841 template <class T, class Alloc>
842 typename ArrayVector<T, Alloc>::iterator
843ArrayVector<T, Alloc>::erase(iterator p, iterator q)
844{
845 std::copy(q, this->end(), p);
846 difference_type eraseCount = q - p;
847 detail::destroy_n(this->end() - eraseCount, eraseCount);
848 this->size_ -= eraseCount;
849 return p;
850}
851
852 template <class T, class Alloc>
853 typename ArrayVector<T, Alloc>::pointer
854ArrayVector<T, Alloc>::reserveImpl( bool dealloc, size_type new_capacity)
855{
856 if(new_capacity <= capacity_)
857 return 0;
858 pointer new_data = reserve_raw(new_capacity),
859 old_data = this->data_;
860 if(this->size_ > 0)
861 std::uninitialized_copy(old_data, old_data+this->size_, new_data);
862 this->data_ = new_data;
863 if(!dealloc)
864 {
865 this->capacity_ = new_capacity;
866 return old_data;
867 }
868 deallocate(old_data, this->size_, this->capacity_);
869 this->capacity_ = new_capacity;
870 return 0;
871}
872
873 template <class T, class Alloc>
874 inline typename ArrayVector<T, Alloc>::pointer
875ArrayVector<T, Alloc>::reserveImpl(bool dealloc)
876{
877 if(capacity_ == 0)
878 return reserveImpl(dealloc, minimumCapacity);
879 else if(this->size_ == capacity_)
880 return reserveImpl(dealloc, resizeFactor*capacity_);
881 else
882 return 0;
883}
884
885 template <class T, class Alloc>
886 inline void
887ArrayVector<T, Alloc>::resize( size_type new_size, value_type const & initial)
888{
889 if(new_size < this->size_)
890 erase(this->begin() + new_size, this->end());
891 else if(this->size_ < new_size)
892 {
893 insert(this->end(), new_size - this->size(), initial);
894 }
895}
896
897 template <class T, class Alloc>
898 inline void
899ArrayVector<T, Alloc>::initImpl( size_type size, value_type const & initial, VigraTrueType /*isIntegral*/)
900{
901 this->size_ = size;
902 capacity_ = size;
903 this->data_ = reserve_raw(capacity_);
904 if(this->size_ > 0)
905 std::uninitialized_fill(this->data_, this->data_+this->size_, initial);
906}
907
908 template <class T, class Alloc>
909 template <class Iter>
910 inline void
911ArrayVector<T, Alloc>::initImpl( Iter i, Iter end, VigraFalseType /*isIntegral*/)
912{
913 this->size_ = std::distance(i, end);
914 capacity_ = this->size_;
915 this->data_ = reserve_raw(capacity_);
916 if(this->size_ > 0)
917 detail::uninitializedCopy(i, end, this->data_);
918}
919
920 template <class T, class Alloc>
921 inline void
922ArrayVector<T, Alloc>::swap(this_type & rhs)
923{
924 std::swap(this->size_, rhs.size_);
925 std::swap(capacity_, rhs.capacity_);
926 std::swap(this->data_, rhs.data_);
927}
928
929 template <class T, class Alloc>
930 inline void
931ArrayVector<T, Alloc>::deallocate(pointer data, size_type size, size_type capacity)
932{
933 if(data)
934 {
935 detail::destroy_n(data, size);
936 alloc_.deallocate(data, capacity);
937 }
938}
939
940 template <class T, class Alloc>
941 inline typename ArrayVector<T, Alloc>::pointer
942ArrayVector<T, Alloc>::reserve_raw(size_type capacity)
943{
944 pointer data = 0;
945 if(capacity)
946 {
947 data = alloc_.allocate(capacity);
948 }
949 return data;
950}
951
952} // namespace vigra
953
954 namespace std {
955
956 template <class T>
957ostream & operator<<(ostream & s, vigra::ArrayVectorView<T> const & a)
958{
959 for(std::ptrdiff_t k=0; k<(std::ptrdiff_t)a.size()-1; ++k)
960 s << a[k] << ", ";
961 if(a.size())
962 s << a.back();
963 return s;
964}
965
966} // namespace std
967
968#undef VIGRA_ASSERT_INSIDE
969#endif /* VIGRA_ARRAY_VECTOR_HXX */
vigra::ArrayVectorView
Definition array_vector.hxx:77
vigra::ArrayVectorView::operator!=
bool operator!=(ArrayVectorView< U > const &rhs) const
Definition array_vector.hxx:373
vigra::ArrayVectorView::rend
const_reverse_iterator rend() const
Definition array_vector.hxx:286
vigra::ArrayVectorView::front
const_reference front() const
Definition array_vector.hxx:314
vigra::ArrayVectorView::copy
void copy(ArrayVectorView< U > const &rhs)
Definition array_vector.hxx:168
vigra::ArrayVectorView::copy
void copy(this_type const &rhs)
Definition array_vector.hxx:156
vigra::ArrayVectorView::value_type
T value_type
Definition array_vector.hxx:83
vigra::ArrayVectorView::begin
const_iterator begin() const
Definition array_vector.hxx:223
vigra::ArrayVectorView::data
const_pointer data() const
Definition array_vector.hxx:209
vigra::ArrayVectorView::data
pointer data()
Definition array_vector.hxx:216
vigra::ArrayVectorView::cbegin
const_iterator cbegin() const
Definition array_vector.hxx:251
vigra::ArrayVectorView::operator=
ArrayVectorView & operator=(ArrayVectorView const &rhs)
vigra::ArrayVectorView::isInside
bool isInside(difference_type const &p) const
Definition array_vector.hxx:380
vigra::ArrayVectorView::size
size_type size() const
Definition array_vector.hxx:358
vigra::ArrayVectorView::back
const_reference back() const
Definition array_vector.hxx:328
vigra::ArrayVectorView::empty
bool empty() const
Definition array_vector.hxx:351
vigra::ArrayVectorView::rend
reverse_iterator rend()
Definition array_vector.hxx:279
vigra::ArrayVectorView::front
reference front()
Definition array_vector.hxx:307
vigra::ArrayVectorView::ArrayVectorView
ArrayVectorView()
Definition array_vector.hxx:99
vigra::ArrayVectorView::swapData
void swapData(ArrayVectorView< U > rhs)
Definition array_vector.hxx:190
vigra::ArrayVectorView::init
void init(U const &initial)
Definition array_vector.hxx:146
vigra::ArrayVectorView::crbegin
const_reverse_iterator crbegin() const
Definition array_vector.hxx:293
vigra::ArrayVectorView::operator==
bool operator==(ArrayVectorView< U > const &rhs) const
Definition array_vector.hxx:414
vigra::ArrayVectorView::cend
const_iterator cend() const
Definition array_vector.hxx:258
vigra::ArrayVectorView::operator[]
reference operator[](difference_type i)
Definition array_vector.hxx:335
vigra::ArrayVectorView::operator=
this_type & operator=(ArrayVectorView< U > const &rhs)
Definition array_vector.hxx:137
vigra::ArrayVectorView::crend
const_reverse_iterator crend() const
Definition array_vector.hxx:300
vigra::ArrayVectorView::end
iterator end()
Definition array_vector.hxx:244
vigra::ArrayVectorView::end
const_iterator end() const
Definition array_vector.hxx:237
vigra::ArrayVectorView::subarray
this_type subarray(size_type begin, size_type end) const
Definition array_vector.hxx:200
vigra::ArrayVectorView::rbegin
reverse_iterator rbegin()
Definition array_vector.hxx:265
vigra::ArrayVectorView::swapData
void swapData(this_type rhs)
Definition array_vector.hxx:178
vigra::ArrayVectorView::begin
iterator begin()
Definition array_vector.hxx:230
vigra::ArrayVectorView::operator[]
const_reference operator[](difference_type i) const
Definition array_vector.hxx:343
vigra::ArrayVectorView::ArrayVectorView
ArrayVectorView(size_type size, pointer const &data)
Definition array_vector.hxx:107
vigra::ArrayVectorView::ArrayVectorView
ArrayVectorView(this_type const &rhs)
Definition array_vector.hxx:114
vigra::ArrayVectorView::rbegin
const_reverse_iterator rbegin() const
Definition array_vector.hxx:272
vigra::ArrayVectorView::back
reference back()
Definition array_vector.hxx:321
vigra::ArrayVector
Definition array_vector.hxx:514
vigra::RGBValue
Class for a single RGB value.
Definition rgbvalue.hxx:128
vigra::RGBValue::RGBValue
RGBValue()
Definition rgbvalue.hxx:209
vigra::TinyVectorBase::size
size_type size() const
Definition tinyvector.hxx:913
vigra::TinyVectorBase::end
iterator end()
Definition tinyvector.hxx:864
vigra::TinyVectorBase::begin
iterator begin()
Definition tinyvector.hxx:861
vigra

© 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.11.1