36 #ifndef VIGRA_ARRAY_VECTOR_HXX 37 #define VIGRA_ARRAY_VECTOR_HXX 41 #include "numerictraits.hxx" 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"); 51 #define VIGRA_ASSERT_INSIDE(diff) 57 template <
class T,
class Alloc = std::allocator<T> >
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;
156 void copy( this_type
const & rhs )
158 if(data_ != rhs.data_)
180 if(data_ != rhs.data_)
202 vigra_precondition(begin <= end && end <= size_,
203 "ArrayVectorView::subarray(): Limits out of range.");
204 return this_type(end-begin, data_ + begin);
209 inline const_pointer
data()
const 237 inline const_iterator
end()
const 258 inline const_iterator
cend()
const 267 return (reverse_iterator(
end()));
272 inline const_reverse_iterator
rbegin()
const 274 return (const_reverse_iterator(
end()));
281 return (reverse_iterator(
begin()));
286 inline const_reverse_iterator
rend()
const 288 return (const_reverse_iterator(
begin()));
295 return (const_reverse_iterator(
end()));
300 inline const_reverse_iterator
crend()
const 302 return (const_reverse_iterator(
begin()));
323 return data_[size_-1];
330 return data_[size_-1];
337 VIGRA_ASSERT_INSIDE(i);
345 VIGRA_ASSERT_INSIDE(i);
382 return p >= 0 && p < size_;
407 else if(data_ != rhs.data_)
418 for(size_type k=0; k<
size(); ++k)
419 if(data_[k] != rhs[k])
428 vigra_precondition (
size() == rhs.
size(),
429 "ArrayVectorView::copy(): shape mismatch.");
433 if(data_ <= rhs.
data())
448 vigra_precondition (
size() == rhs.
size(),
449 "ArrayVectorView::copy(): shape mismatch.");
458 vigra_precondition (
size () == rhs.
size() (),
459 "ArrayVectorView::swapData(): size mismatch.");
462 if(data_ + size_ <= rhs.data_ || rhs.data_ + size_ <= data_)
464 for(size_type k=0; k<size_; ++k)
465 std::swap(data_[k], rhs.data_[k]);
511 template <
class T,
class Alloc >
516 enum { minimumCapacity = 2, resizeFactor = 2 };
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;
536 capacity_(minimumCapacity),
539 this->data_ = reserve_raw(capacity_);
544 capacity_(minimumCapacity),
547 this->data_ = reserve_raw(capacity_);
554 initImpl(size,
value_type(), VigraTrueType());
557 ArrayVector( size_type size, value_type
const & initial, Alloc
const & alloc = Alloc())
561 initImpl(size, initial, VigraTrueType());
569 initImpl(rhs.
begin(), rhs.
end(), VigraFalseType());
577 initImpl(rhs.
begin(), rhs.
end(), VigraFalseType());
580 template <
class InputIterator>
581 ArrayVector(InputIterator i, InputIterator
end)
583 initImpl(i, end,
typename NumericTraits<InputIterator>::isIntegral());
586 template <
class InputIterator>
587 ArrayVector(InputIterator i, InputIterator end, Alloc
const & alloc)
590 initImpl(i, end,
typename NumericTraits<InputIterator>::isIntegral());
593 this_type &
operator=( this_type
const & rhs )
597 if(this->size_ == rhs.size_)
612 deallocate(this->data_, this->size_, this->capacity_);
617 void push_back( value_type
const & t );
619 iterator insert(iterator p, value_type
const & v);
621 iterator insert(iterator p, size_type n, value_type
const & v);
623 template <
class InputIterator>
624 iterator insert(iterator p, InputIterator i, InputIterator iend);
626 iterator erase(iterator p);
628 iterator erase(iterator p, iterator q);
632 pointer reserveImpl(
bool dealloc, size_type new_capacity );
634 pointer reserveImpl(
bool dealloc);
641 void reserve( size_type new_capacity )
643 reserveImpl(
true, new_capacity);
646 void resize( size_type new_size, value_type
const & initial );
648 void resize( size_type new_size )
653 size_type capacity()
const 658 void swap(this_type & rhs);
662 void deallocate(pointer
data, size_type size, size_type capacity);
664 pointer reserve_raw(size_type capacity);
666 void initImpl( size_type size, value_type
const & initial, VigraTrueType );
668 template <
class Iter>
669 void initImpl( Iter i, Iter end, VigraFalseType );
671 template <
class Iter>
672 void initImpl( Iter i, Iter end, Error_NumericTraits_not_specialized_for_this_case)
674 initImpl(i, end, VigraFalseType());
681 template <
class T,
class Alloc>
685 if(this->size_ == rhs.
size())
695 template <
class T,
class Alloc>
699 alloc_.destroy(this->data_ + this->size_);
702 template <
class T,
class Alloc>
705 size_type old_capacity = this->capacity_;
706 pointer old_data = reserveImpl(
false);
707 alloc_.construct(this->data_ + this->size_, t);
710 deallocate(old_data, this->size_, old_capacity);
714 template <
class T,
class Alloc>
717 detail::destroy_n(this->data_, this->size_);
721 template <
class T,
class Alloc>
722 typename ArrayVector<T, Alloc>::iterator
725 difference_type pos = p - this->
begin();
729 p = this->
begin() + pos;
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);
742 template <
class T,
class Alloc>
743 typename ArrayVector<T, Alloc>::iterator
746 difference_type pos = p - this->
begin();
747 size_type new_size = this->
size() + n;
748 if(new_size > capacity_)
750 size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
751 pointer new_data = reserve_raw(new_capacity);
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);
760 alloc_.deallocate(new_data, new_capacity);
763 deallocate(this->data_, this->size_, this->capacity_);
764 capacity_ = new_capacity;
765 this->data_ = new_data;
767 else if(pos + n > this->size_)
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);
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);
781 this->size_ = new_size;
782 return this->
begin() + pos;
785 template <
class T,
class Alloc>
786 template <
class InputIterator>
787 typename ArrayVector<T, Alloc>::iterator
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_)
795 size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
796 pointer new_data = reserve_raw(new_capacity);
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);
805 alloc_.deallocate(new_data, new_capacity);
808 deallocate(this->data_, this->size_, this->capacity_);
809 capacity_ = new_capacity;
810 this->data_ = new_data;
812 else if(pos + n > this->size_)
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);
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);
828 this->size_ = new_size;
829 return this->
begin() + pos;
832 template <
class T,
class Alloc>
833 typename ArrayVector<T, Alloc>::iterator
836 std::copy(p+1, this->
end(), p);
841 template <
class T,
class Alloc>
842 typename ArrayVector<T, Alloc>::iterator
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;
852 template <
class T,
class Alloc>
853 typename ArrayVector<T, Alloc>::pointer
856 if(new_capacity <= capacity_)
858 pointer new_data = reserve_raw(new_capacity),
859 old_data = this->data_;
861 std::uninitialized_copy(old_data, old_data+this->size_, new_data);
862 this->data_ = new_data;
865 this->capacity_ = new_capacity;
868 deallocate(old_data, this->size_, this->capacity_);
869 this->capacity_ = new_capacity;
873 template <
class T,
class Alloc>
874 inline typename ArrayVector<T, Alloc>::pointer
878 return reserveImpl(dealloc, minimumCapacity);
879 else if(this->size_ == capacity_)
880 return reserveImpl(dealloc, resizeFactor*capacity_);
885 template <
class T,
class Alloc>
889 if(new_size < this->size_)
890 erase(this->
begin() + new_size, this->
end());
891 else if(this->size_ < new_size)
893 insert(this->
end(), new_size - this->
size(), initial);
897 template <
class T,
class Alloc>
903 this->data_ = reserve_raw(capacity_);
905 std::uninitialized_fill(this->data_, this->data_+this->size_, initial);
908 template <
class T,
class Alloc>
909 template <
class Iter>
913 this->size_ = std::distance(i, end);
914 capacity_ = this->size_;
915 this->data_ = reserve_raw(capacity_);
917 detail::uninitializedCopy(i, end, this->data_);
920 template <
class T,
class Alloc>
924 std::swap(this->size_, rhs.size_);
925 std::swap(capacity_, rhs.capacity_);
926 std::swap(this->data_, rhs.data_);
929 template <
class T,
class Alloc>
935 detail::destroy_n(data, size);
936 alloc_.deallocate(data, capacity);
940 template <
class T,
class Alloc>
941 inline typename ArrayVector<T, Alloc>::pointer
947 data = alloc_.allocate(capacity);
957 ostream & operator<<(ostream & s, vigra::ArrayVectorView<T>
const & a)
959 for(std::ptrdiff_t k=0; k<(std::ptrdiff_t)a.size()-1; ++k)
968 #undef VIGRA_ASSERT_INSIDE iterator end()
Definition: array_vector.hxx:244
reference back()
Definition: array_vector.hxx:321
void swapData(this_type rhs)
Definition: array_vector.hxx:178
this_type & operator=(ArrayVectorView< U > const &rhs)
Definition: array_vector.hxx:137
bool operator!=(ArrayVectorView< U > const &rhs) const
Definition: array_vector.hxx:373
const_reference back() const
Definition: array_vector.hxx:328
this_type subarray(size_type begin, size_type end) const
Definition: array_vector.hxx:200
ArrayVectorView(size_type size, pointer const &data)
Definition: array_vector.hxx:107
Definition: array_vector.hxx:76
const_reverse_iterator rend() const
Definition: array_vector.hxx:286
Definition: array_vector.hxx:954
bool operator==(ArrayVectorView< U > const &rhs) const
Definition: array_vector.hxx:414
reverse_iterator rend()
Definition: array_vector.hxx:279
const_reverse_iterator crend() const
Definition: array_vector.hxx:300
ArrayVectorView & operator=(ArrayVectorView const &rhs)
void copy(ArrayVectorView< U > const &rhs)
Definition: array_vector.hxx:168
const_reverse_iterator crbegin() const
Definition: array_vector.hxx:293
reference operator[](difference_type i)
Definition: array_vector.hxx:335
Definition: array_vector.hxx:58
const_iterator cbegin() const
Definition: array_vector.hxx:251
reference front()
Definition: array_vector.hxx:307
ArrayVectorView()
Definition: array_vector.hxx:99
void init(U const &initial)
Definition: array_vector.hxx:146
pointer data()
Definition: array_vector.hxx:216
const_reverse_iterator rbegin() const
Definition: array_vector.hxx:272
const_pointer data() const
Definition: array_vector.hxx:209
bool isInside(difference_type const &p) const
Definition: array_vector.hxx:380
iterator begin()
Definition: array_vector.hxx:230
bool empty() const
Definition: array_vector.hxx:351
const_iterator cend() const
Definition: array_vector.hxx:258
const_iterator begin() const
Definition: array_vector.hxx:223
const_reference front() const
Definition: array_vector.hxx:314
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:265
size_type size() const
Definition: array_vector.hxx:358
ArrayVectorView(this_type const &rhs)
Definition: array_vector.hxx:114
const_iterator end() const
Definition: array_vector.hxx:237
void swapData(ArrayVectorView< U > rhs)
Definition: array_vector.hxx:190
const_reference operator[](difference_type i) const
Definition: array_vector.hxx:343