2 * Copyright 2008-2013 NVIDIA Corporation
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
18 /*! \file vector_base.inl
19 * \brief Inline file for vector_base.h.
22 #include <thrust/detail/vector_base.h>
23 #include <thrust/detail/copy.h>
24 #include <thrust/detail/overlapped_copy.h>
25 #include <thrust/equal.h>
26 #include <thrust/distance.h>
27 #include <thrust/advance.h>
28 #include <thrust/detail/type_traits.h>
29 #include <thrust/detail/minmax.h>
30 #include <thrust/iterator/iterator_traits.h>
31 #include <thrust/detail/temporary_array.h>
41 template<typename T, typename Alloc>
48 } // end vector_base::vector_base()
50 template<typename T, typename Alloc>
52 ::vector_base(size_type n)
57 } // end vector_base::vector_base()
59 template<typename T, typename Alloc>
61 ::vector_base(size_type n, const value_type &value)
66 } // end vector_base::vector_base()
68 template<typename T, typename Alloc>
70 ::vector_base(const vector_base &v)
74 range_init(v.begin(), v.end());
75 } // end vector_base::vector_base()
77 template<typename T, typename Alloc>
78 vector_base<T,Alloc> &
80 ::operator=(const vector_base &v)
84 assign(v.begin(), v.end());
88 } // end vector_base::operator=()
90 template<typename T, typename Alloc>
91 template<typename OtherT, typename OtherAlloc>
93 ::vector_base(const vector_base<OtherT,OtherAlloc> &v)
97 range_init(v.begin(), v.end());
98 } // end vector_base::vector_base()
100 template<typename T, typename Alloc>
101 template<typename OtherT, typename OtherAlloc>
102 vector_base<T,Alloc> &
104 ::operator=(const vector_base<OtherT,OtherAlloc> &v)
106 assign(v.begin(), v.end());
109 } // end vector_base::operator=()
111 template<typename T, typename Alloc>
112 template<typename OtherT, typename OtherAlloc>
114 ::vector_base(const std::vector<OtherT,OtherAlloc> &v)
118 range_init(v.begin(), v.end());
119 } // end vector_base::vector_base()
121 template<typename T, typename Alloc>
122 template<typename OtherT, typename OtherAlloc>
123 vector_base<T,Alloc> &
125 ::operator=(const std::vector<OtherT,OtherAlloc> &v)
127 assign(v.begin(), v.end());
130 } // end vector_base::operator=()
132 template<typename T, typename Alloc>
133 template<typename IteratorOrIntegralType>
134 void vector_base<T,Alloc>
135 ::init_dispatch(IteratorOrIntegralType n,
136 IteratorOrIntegralType value,
140 } // end vector_base::init_dispatch()
142 template<typename T, typename Alloc>
143 void vector_base<T,Alloc>
144 ::default_init(size_type n)
148 m_storage.allocate(n);
151 m_storage.default_construct_n(begin(), size());
153 } // end vector_base::default_init()
155 template<typename T, typename Alloc>
156 void vector_base<T,Alloc>
157 ::fill_init(size_type n, const T &x)
161 m_storage.allocate(n);
164 m_storage.uninitialized_fill_n(begin(), size(), x);
166 } // end vector_base::fill_init()
168 template<typename T, typename Alloc>
169 template<typename InputIterator>
170 void vector_base<T,Alloc>
171 ::init_dispatch(InputIterator first,
175 range_init(first, last);
176 } // end vector_base::init_dispatch()
178 template<typename T, typename Alloc>
179 template<typename InputIterator>
180 void vector_base<T,Alloc>
181 ::range_init(InputIterator first,
184 range_init(first, last,
185 typename thrust::iterator_traversal<InputIterator>::type());
186 } // end vector_base::range_init()
188 template<typename T, typename Alloc>
189 template<typename InputIterator>
190 void vector_base<T,Alloc>
191 ::range_init(InputIterator first,
193 thrust::incrementable_traversal_tag)
195 for(; first != last; ++first)
197 } // end vector_base::range_init()
199 template<typename T, typename Alloc>
200 template<typename ForwardIterator>
201 void vector_base<T,Alloc>
202 ::range_init(ForwardIterator first,
203 ForwardIterator last,
204 thrust::random_access_traversal_tag)
206 size_type new_size = thrust::distance(first, last);
208 allocate_and_copy(new_size, first, last, m_storage);
210 } // end vector_base::range_init()
212 template<typename T, typename Alloc>
213 template<typename InputIterator>
215 ::vector_base(InputIterator first,
220 // check the type of InputIterator: if it's an integral type,
221 // we need to interpret this call as (size_type, value_type)
222 typedef thrust::detail::is_integral<InputIterator> Integer;
224 init_dispatch(first, last, Integer());
225 } // end vector_basee::vector_base()
227 template<typename T, typename Alloc>
228 void vector_base<T,Alloc>
229 ::resize(size_type new_size)
231 if(new_size < size())
233 iterator new_end = begin();
234 thrust::advance(new_end, new_size);
235 erase(new_end, end());
239 append(new_size - size());
241 } // end vector_base::resize()
243 template<typename T, typename Alloc>
244 void vector_base<T,Alloc>
245 ::resize(size_type new_size, const value_type &x)
247 if(new_size < size())
249 iterator new_end = begin();
250 thrust::advance(new_end, new_size);
251 erase(new_end, end());
255 insert(end(), new_size - size(), x);
257 } // end vector_base::resize()
259 template<typename T, typename Alloc>
260 typename vector_base<T,Alloc>::size_type
265 } // end vector_base::size()
267 template<typename T, typename Alloc>
268 typename vector_base<T,Alloc>::size_type
270 ::max_size(void) const
272 return m_storage.max_size();
273 } // end vector_base::max_size()
275 template<typename T, typename Alloc>
276 void vector_base<T,Alloc>
277 ::reserve(size_type n)
281 allocate_and_copy(n, begin(), end(), m_storage);
283 } // end vector_base::reserve()
285 template<typename T, typename Alloc>
286 typename vector_base<T,Alloc>::size_type
288 ::capacity(void) const
290 return m_storage.size();
291 } // end vector_base::capacity()
293 template<typename T, typename Alloc>
294 void vector_base<T,Alloc>
295 ::shrink_to_fit(void)
297 // use the swap trick
298 vector_base(*this).swap(*this);
299 } // end vector_base::shrink_to_fit()
301 template<typename T, typename Alloc>
302 typename vector_base<T,Alloc>::reference
304 ::operator[](const size_type n)
307 } // end vector_base::operator[]
309 template<typename T, typename Alloc>
310 typename vector_base<T,Alloc>::const_reference
312 ::operator[](const size_type n) const
315 } // end vector_base::operator[]
317 template<typename T, typename Alloc>
318 typename vector_base<T,Alloc>::iterator
322 return m_storage.begin();
323 } // end vector_base::begin()
325 template<typename T, typename Alloc>
326 typename vector_base<T,Alloc>::const_iterator
330 return m_storage.begin();
331 } // end vector_base::begin()
333 template<typename T, typename Alloc>
334 typename vector_base<T,Alloc>::const_iterator
339 } // end vector_base::cbegin()
341 template<typename T, typename Alloc>
342 typename vector_base<T,Alloc>::reverse_iterator
346 return reverse_iterator(end());
347 } // end vector_base::rbegin()
349 template<typename T, typename Alloc>
350 typename vector_base<T,Alloc>::const_reverse_iterator
354 return const_reverse_iterator(end());
355 } // end vector_base::rbegin()
357 template<typename T, typename Alloc>
358 typename vector_base<T,Alloc>::const_reverse_iterator
360 ::crbegin(void) const
363 } // end vector_base::crbegin()
365 template<typename T, typename Alloc>
366 typename vector_base<T,Alloc>::iterator
370 iterator result = begin();
371 thrust::advance(result, size());
373 } // end vector_base::end()
375 template<typename T, typename Alloc>
376 typename vector_base<T,Alloc>::const_iterator
380 const_iterator result = begin();
381 thrust::advance(result, size());
383 } // end vector_base::end()
385 template<typename T, typename Alloc>
386 typename vector_base<T,Alloc>::const_iterator
391 } // end vector_base::cend()
393 template<typename T, typename Alloc>
394 typename vector_base<T,Alloc>::reverse_iterator
398 return reverse_iterator(begin());
399 } // end vector_base::rend()
401 template<typename T, typename Alloc>
402 typename vector_base<T,Alloc>::const_reverse_iterator
406 return const_reverse_iterator(begin());
407 } // end vector_base::rend()
409 template<typename T, typename Alloc>
410 typename vector_base<T,Alloc>::const_reverse_iterator
415 } // end vector_base::crend()
417 template<typename T, typename Alloc>
418 typename vector_base<T,Alloc>::const_reference
423 } // end vector_base::front()
425 template<typename T, typename Alloc>
426 typename vector_base<T,Alloc>::reference
431 } // end vector_base::front()
433 template<typename T, typename Alloc>
434 typename vector_base<T,Alloc>::const_reference
438 const_iterator ptr_to_back = end();
441 } // end vector_base::vector_base
443 template<typename T, typename Alloc>
444 typename vector_base<T,Alloc>::reference
448 iterator ptr_to_back = end();
451 } // end vector_base::vector_base
453 template<typename T, typename Alloc>
454 typename vector_base<T,Alloc>::pointer
459 } // end vector_base::data()
461 template<typename T, typename Alloc>
462 typename vector_base<T,Alloc>::const_pointer
467 } // end vector_base::data()
469 template<typename T, typename Alloc>
473 // destroy every living thing
474 m_storage.destroy(begin(),end());
475 } // end vector_base::~vector_base()
477 template<typename T, typename Alloc>
478 void vector_base<T,Alloc>
482 } // end vector_base::~vector_dev()
484 template<typename T, typename Alloc>
485 bool vector_base<T,Alloc>
489 } // end vector_base::empty();
491 template<typename T, typename Alloc>
492 void vector_base<T,Alloc>
493 ::push_back(const value_type &x)
496 } // end vector_base::push_back()
498 template<typename T, typename Alloc>
499 void vector_base<T,Alloc>
503 iterator ptr_to_back = e;
505 m_storage.destroy(ptr_to_back, e);
507 } // end vector_base::pop_back()
509 template<typename T, typename Alloc>
510 typename vector_base<T,Alloc>::iterator vector_base<T,Alloc>
511 ::erase(iterator pos)
515 return erase(pos,end);
516 } // end vector_base::erase()
518 template<typename T, typename Alloc>
519 typename vector_base<T,Alloc>::iterator vector_base<T,Alloc>
520 ::erase(iterator first, iterator last)
522 // overlap copy the range [last,end()) to first
523 // XXX this copy only potentially overlaps
524 iterator i = thrust::detail::overlapped_copy(last, end(), first);
526 // destroy everything after i
527 m_storage.destroy(i, end());
530 m_size -= (last - first);
532 // return an iterator pointing to the position of the first element
533 // following the erased range
535 } // end vector_base::erase()
537 template<typename T, typename Alloc>
538 void vector_base<T,Alloc>
539 ::swap(vector_base &v)
541 thrust::swap(m_storage, v.m_storage);
542 thrust::swap(m_size, v.m_size);
543 } // end vector_base::swap()
545 template<typename T, typename Alloc>
546 void vector_base<T,Alloc>
547 ::assign(size_type n, const T &x)
550 } // end vector_base::assign()
552 template<typename T, typename Alloc>
553 template<typename InputIterator>
554 void vector_base<T,Alloc>
555 ::assign(InputIterator first, InputIterator last)
557 // we could have received assign(n, x), so disambiguate on the
558 // type of InputIterator
559 typedef typename thrust::detail::is_integral<InputIterator> integral;
561 assign_dispatch(first, last, integral());
562 } // end vector_base::assign()
564 template<typename T, typename Alloc>
565 typename vector_base<T,Alloc>::allocator_type
567 ::get_allocator(void) const
569 return m_storage.get_allocator();
570 } // end vector_base::get_allocator()
572 template<typename T, typename Alloc>
573 typename vector_base<T,Alloc>::iterator
575 ::insert(iterator position, const T &x)
577 // find the index of the insertion
578 size_type index = thrust::distance(begin(), position);
580 // make the insertion
581 insert(position, 1, x);
583 // return an iterator pointing back to position
584 iterator result = begin();
585 thrust::advance(result, index);
587 } // end vector_base::insert()
589 template<typename T, typename Alloc>
590 void vector_base<T,Alloc>
591 ::insert(iterator position, size_type n, const T &x)
593 fill_insert(position, n, x);
594 } // end vector_base::insert()
596 template<typename T, typename Alloc>
597 template<typename InputIterator>
598 void vector_base<T,Alloc>
599 ::insert(iterator position, InputIterator first, InputIterator last)
601 // we could have received insert(position, n, x), so disambiguate on the
602 // type of InputIterator
603 typedef typename thrust::detail::is_integral<InputIterator> integral;
605 insert_dispatch(position, first, last, integral());
606 } // end vector_base::insert()
608 template<typename T, typename Alloc>
609 template<typename InputIterator>
610 void vector_base<T,Alloc>
611 ::assign_dispatch(InputIterator first, InputIterator last, false_type)
613 range_assign(first, last);
614 } // end vector_base::assign_dispatch()
616 template<typename T, typename Alloc>
617 template<typename Integral>
618 void vector_base<T,Alloc>
619 ::assign_dispatch(Integral n, Integral x, true_type)
622 } // end vector_base::assign_dispatch()
624 template<typename T, typename Alloc>
625 template<typename InputIterator>
626 void vector_base<T,Alloc>
627 ::insert_dispatch(iterator position, InputIterator first, InputIterator last, false_type)
629 copy_insert(position, first, last);
630 } // end vector_base::insert_dispatch()
632 template<typename T, typename Alloc>
633 template<typename Integral>
634 void vector_base<T,Alloc>
635 ::insert_dispatch(iterator position, Integral n, Integral x, true_type)
637 fill_insert(position, n, x);
638 } // end vector_base::insert_dispatch()
640 template<typename T, typename Alloc>
641 template<typename ForwardIterator>
642 void vector_base<T,Alloc>
643 ::copy_insert(iterator position,
644 ForwardIterator first,
645 ForwardIterator last)
649 // how many new elements will we create?
650 const size_type num_new_elements = thrust::distance(first, last);
651 if(capacity() - size() >= num_new_elements)
653 // we've got room for all of them
654 // how many existing elements will we displace?
655 const size_type num_displaced_elements = end() - position;
656 iterator old_end = end();
658 if(num_displaced_elements > num_new_elements)
660 // construct copy n displaced elements to new elements
661 // following the insertion
662 m_storage.uninitialized_copy(end() - num_new_elements, end(), end());
665 m_size += num_new_elements;
667 // copy num_displaced_elements - num_new_elements elements to existing elements
668 // this copy overlaps
669 const size_type copy_length = (old_end - num_new_elements) - position;
670 thrust::detail::overlapped_copy(position, old_end - num_new_elements, old_end - copy_length);
672 // finally, copy the range to the insertion point
673 thrust::copy(first, last, position);
677 ForwardIterator mid = first;
678 thrust::advance(mid, num_displaced_elements);
680 // construct copy new elements at the end of the vector
681 m_storage.uninitialized_copy(mid, last, end());
684 m_size += num_new_elements - num_displaced_elements;
686 // construct copy the displaced elements
687 m_storage.uninitialized_copy(position, old_end, end());
690 m_size += num_displaced_elements;
692 // copy to elements which already existed
693 thrust::copy(first, mid, position);
698 const size_type old_size = size();
700 // compute the new capacity after the allocation
701 size_type new_capacity = old_size + thrust::max THRUST_PREVENT_MACRO_SUBSTITUTION (old_size, num_new_elements);
703 // allocate exponentially larger new storage
704 new_capacity = thrust::max THRUST_PREVENT_MACRO_SUBSTITUTION <size_type>(new_capacity, 2 * capacity());
706 // do not exceed maximum storage
707 new_capacity = thrust::min THRUST_PREVENT_MACRO_SUBSTITUTION <size_type>(new_capacity, max_size());
709 if(new_capacity > max_size())
711 throw std::length_error("insert(): insertion exceeds max_size().");
714 storage_type new_storage(new_capacity);
716 // record how many constructors we invoke in the try block below
717 iterator new_end = new_storage.begin();
721 // construct copy elements before the insertion to the beginning of the newly
723 new_end = m_storage.uninitialized_copy(begin(), position, new_storage.begin());
725 // construct copy elements to insert
726 new_end = m_storage.uninitialized_copy(first, last, new_end);
728 // construct copy displaced elements from the old storage to the new storage
729 // remember [position, end()) refers to the old storage
730 new_end = m_storage.uninitialized_copy(position, end(), new_end);
734 // something went wrong, so destroy & deallocate the new storage
735 m_storage.destroy(new_storage.begin(), new_end);
736 new_storage.deallocate();
742 // call destructors on the elements in the old storage
743 m_storage.destroy(begin(), end());
745 // record the vector's new state
746 m_storage.swap(new_storage);
747 m_size = old_size + num_new_elements;
750 } // end vector_base::copy_insert()
752 template<typename T, typename Alloc>
753 void vector_base<T,Alloc>
754 ::append(size_type n)
758 if(capacity() - size() >= n)
760 // we've got room for all of them
762 // default construct new elements at the end of the vector
763 m_storage.default_construct_n(end(), n);
770 const size_type old_size = size();
772 // compute the new capacity after the allocation
773 size_type new_capacity = old_size + thrust::max THRUST_PREVENT_MACRO_SUBSTITUTION (old_size, n);
775 // allocate exponentially larger new storage
776 new_capacity = thrust::max THRUST_PREVENT_MACRO_SUBSTITUTION <size_type>(new_capacity, 2 * capacity());
778 // do not exceed maximum storage
779 new_capacity = thrust::min THRUST_PREVENT_MACRO_SUBSTITUTION <size_type>(new_capacity, max_size());
781 // create new storage
782 storage_type new_storage(new_capacity);
784 // record how many constructors we invoke in the try block below
785 iterator new_end = new_storage.begin();
789 // construct copy all elements into the newly allocated storage
790 new_end = m_storage.uninitialized_copy(begin(), end(), new_storage.begin());
792 // construct new elements to insert
793 m_storage.default_construct_n(new_end, n);
798 // something went wrong, so destroy & deallocate the new storage
799 m_storage.destroy(new_storage.begin(), new_end);
800 new_storage.deallocate();
806 // call destructors on the elements in the old storage
807 m_storage.destroy(begin(), end());
809 // record the vector's new state
810 m_storage.swap(new_storage);
811 m_size = old_size + n;
814 } // end vector_base::append()
816 template<typename T, typename Alloc>
817 void vector_base<T,Alloc>
818 ::fill_insert(iterator position, size_type n, const T &x)
822 if(capacity() - size() >= n)
824 // we've got room for all of them
825 // how many existing elements will we displace?
826 const size_type num_displaced_elements = end() - position;
827 iterator old_end = end();
829 if(num_displaced_elements > n)
831 // construct copy n displaced elements to new elements
832 // following the insertion
833 m_storage.uninitialized_copy(end() - n, end(), end());
838 // copy num_displaced_elements - n elements to existing elements
839 // this copy overlaps
840 const size_type copy_length = (old_end - n) - position;
841 thrust::detail::overlapped_copy(position, old_end - n, old_end - copy_length);
843 // finally, fill the range to the insertion point
844 thrust::fill_n(position, n, x);
848 // construct new elements at the end of the vector
849 m_storage.uninitialized_fill_n(end(), n - num_displaced_elements, x);
852 m_size += n - num_displaced_elements;
854 // construct copy the displaced elements
855 m_storage.uninitialized_copy(position, old_end, end());
858 m_size += num_displaced_elements;
860 // fill to elements which already existed
861 thrust::fill(position, old_end, x);
866 const size_type old_size = size();
868 // compute the new capacity after the allocation
869 size_type new_capacity = old_size + thrust::max THRUST_PREVENT_MACRO_SUBSTITUTION (old_size, n);
871 // allocate exponentially larger new storage
872 new_capacity = thrust::max THRUST_PREVENT_MACRO_SUBSTITUTION <size_type>(new_capacity, 2 * capacity());
874 // do not exceed maximum storage
875 new_capacity = thrust::min THRUST_PREVENT_MACRO_SUBSTITUTION <size_type>(new_capacity, max_size());
877 if(new_capacity > max_size())
879 throw std::length_error("insert(): insertion exceeds max_size().");
882 storage_type new_storage(new_capacity);
884 // record how many constructors we invoke in the try block below
885 iterator new_end = new_storage.begin();
889 // construct copy elements before the insertion to the beginning of the newly
891 new_end = m_storage.uninitialized_copy(begin(), position, new_storage.begin());
893 // construct new elements to insert
894 m_storage.uninitialized_fill_n(new_end, n, x);
897 // construct copy displaced elements from the old storage to the new storage
898 // remember [position, end()) refers to the old storage
899 new_end = m_storage.uninitialized_copy(position, end(), new_end);
903 // something went wrong, so destroy & deallocate the new storage
904 m_storage.destroy(new_storage.begin(), new_end);
905 new_storage.deallocate();
911 // call destructors on the elements in the old storage
912 m_storage.destroy(begin(), end());
914 // record the vector's new state
915 m_storage.swap(new_storage);
916 m_size = old_size + n;
919 } // end vector_base::fill_insert()
921 template<typename T, typename Alloc>
922 template<typename InputIterator>
923 void vector_base<T,Alloc>
924 ::range_assign(InputIterator first,
927 // dispatch on traversal
928 range_assign(first, last,
929 typename thrust::iterator_traversal<InputIterator>::type());
930 } // end range_assign()
932 template<typename T, typename Alloc>
933 template<typename InputIterator>
934 void vector_base<T,Alloc>
935 ::range_assign(InputIterator first,
937 thrust::incrementable_traversal_tag)
939 iterator current(begin());
941 // assign to elements which already exist
942 for(; first != last && current != end(); ++current, ++first)
947 // either just the input was exhausted or both
948 // the input and vector elements were exhausted
951 // if we exhausted the input, erase leftover elements
952 erase(current, end());
956 // insert the rest of the input at the end of the vector
957 insert(end(), first, last);
959 } // end vector_base::range_assign()
961 template<typename T, typename Alloc>
962 template<typename RandomAccessIterator>
963 void vector_base<T,Alloc>
964 ::range_assign(RandomAccessIterator first,
965 RandomAccessIterator last,
966 thrust::random_access_traversal_tag)
968 const size_type n = thrust::distance(first, last);
972 storage_type new_storage;
973 allocate_and_copy(n, first, last, new_storage);
975 // call destructors on the elements in the old storage
976 m_storage.destroy(begin(), end());
978 // record the vector's new state
979 m_storage.swap(new_storage);
984 // we can already accomodate the new range
985 iterator new_end = thrust::copy(first, last, begin());
987 // destroy the elements we don't need
988 m_storage.destroy(new_end, end());
995 // range fits inside allocated storage, but some elements
996 // have not been constructed yet
998 // XXX TODO we could possibly implement this with one call
999 // to transform rather than copy + uninitialized_copy
1001 // copy to elements which already exist
1002 RandomAccessIterator mid = first;
1003 thrust::advance(mid, size());
1004 thrust::copy(first, mid, begin());
1006 // uninitialize_copy to elements which must be constructed
1007 m_storage.uninitialized_copy(mid, last, end());
1012 } // end vector_base::assign()
1014 template<typename T, typename Alloc>
1015 void vector_base<T,Alloc>
1016 ::fill_assign(size_type n, const T &x)
1020 // XXX we should also include a copy of the allocator:
1021 // vector_base<T,Alloc> temp(n, x, get_allocator());
1022 vector_base<T,Alloc> temp(n, x);
1027 // fill to existing elements
1028 thrust::fill(begin(), end(), x);
1030 // construct uninitialized elements
1031 m_storage.uninitialized_fill_n(end(), n - size(), x);
1034 m_size += (n - size());
1038 // fill to existing elements
1039 iterator new_end = thrust::fill_n(begin(), n, x);
1041 // erase the elements after the fill
1042 erase(new_end, end());
1044 } // end vector_base::fill_assign()
1046 template<typename T, typename Alloc>
1047 template<typename ForwardIterator>
1048 void vector_base<T,Alloc>
1049 ::allocate_and_copy(size_type requested_size,
1050 ForwardIterator first, ForwardIterator last,
1051 storage_type &new_storage)
1053 if(requested_size == 0)
1055 new_storage.deallocate();
1059 // allocate exponentially larger new storage
1060 size_type allocated_size = thrust::max<size_type>(requested_size, 2 * capacity());
1062 // do not exceed maximum storage
1063 allocated_size = thrust::min<size_type>(allocated_size, max_size());
1065 if(requested_size > allocated_size)
1067 throw std::length_error("assignment exceeds max_size().");
1070 new_storage.allocate(allocated_size);
1074 // construct the range to the newly allocated storage
1075 m_storage.uninitialized_copy(first, last, new_storage.begin());
1079 // something went wrong, so destroy & deallocate the new storage
1080 // XXX seems like this destroys too many elements -- should just be last - first instead of requested_size
1081 iterator new_storage_end = new_storage.begin();
1082 thrust::advance(new_storage_end, requested_size);
1083 m_storage.destroy(new_storage.begin(), new_storage_end);
1084 new_storage.deallocate();
1089 } // end vector_base::allocate_and_copy()
1094 template<typename T, typename Alloc>
1095 void swap(detail::vector_base<T,Alloc> &a,
1096 detail::vector_base<T,Alloc> &b)
1106 // iterator tags match
1107 template <typename InputIterator1, typename InputIterator2>
1108 bool vector_equal(InputIterator1 first1, InputIterator1 last1,
1109 InputIterator2 first2,
1110 thrust::detail::true_type)
1112 return thrust::equal(first1, last1, first2);
1115 // iterator tags differ
1116 template <typename InputIterator1, typename InputIterator2>
1117 bool vector_equal(InputIterator1 first1, InputIterator1 last1,
1118 InputIterator2 first2,
1119 thrust::detail::false_type)
1121 typename thrust::iterator_difference<InputIterator1>::type n = thrust::distance(first1,last1);
1123 typedef typename thrust::iterator_system<InputIterator1>::type FromSystem1;
1124 typedef typename thrust::iterator_system<InputIterator2>::type FromSystem2;
1126 // bring both ranges to the host system
1127 // note that these copies are no-ops if the range is already convertible to the host system
1128 FromSystem1 from_system1;
1129 FromSystem2 from_system2;
1130 thrust::host_system_tag to_system;
1131 thrust::detail::move_to_system<InputIterator1, FromSystem1, thrust::host_system_tag> rng1(from_system1, to_system, first1, last1);
1132 thrust::detail::move_to_system<InputIterator2, FromSystem2, thrust::host_system_tag> rng2(from_system2, to_system, first2, first2 + n);
1134 return thrust::equal(rng1.begin(), rng1.end(), rng2.begin());
1137 template <typename InputIterator1, typename InputIterator2>
1138 bool vector_equal(InputIterator1 first1, InputIterator1 last1,
1139 InputIterator2 first2)
1141 typedef typename thrust::iterator_system<InputIterator1>::type system1;
1142 typedef typename thrust::iterator_system<InputIterator2>::type system2;
1144 // dispatch on the sameness of the two systems
1145 return vector_equal(first1, last1, first2,
1146 thrust::detail::is_same<system1,system2>());
1149 } // end namespace detail
1154 template<typename T1, typename Alloc1,
1155 typename T2, typename Alloc2>
1156 bool operator==(const detail::vector_base<T1,Alloc1>& lhs,
1157 const detail::vector_base<T2,Alloc2>& rhs)
1159 return lhs.size() == rhs.size() && detail::vector_equal(lhs.begin(), lhs.end(), rhs.begin());
1162 template<typename T1, typename Alloc1,
1163 typename T2, typename Alloc2>
1164 bool operator==(const detail::vector_base<T1,Alloc1>& lhs,
1165 const std::vector<T2,Alloc2>& rhs)
1167 return lhs.size() == rhs.size() && detail::vector_equal(lhs.begin(), lhs.end(), rhs.begin());
1170 template<typename T1, typename Alloc1,
1171 typename T2, typename Alloc2>
1172 bool operator==(const std::vector<T1,Alloc1>& lhs,
1173 const detail::vector_base<T2,Alloc2>& rhs)
1175 return lhs.size() == rhs.size() && detail::vector_equal(lhs.begin(), lhs.end(), rhs.begin());
1178 template<typename T1, typename Alloc1,
1179 typename T2, typename Alloc2>
1180 bool operator!=(const detail::vector_base<T1,Alloc1>& lhs,
1181 const detail::vector_base<T2,Alloc2>& rhs)
1183 return !(lhs == rhs);
1186 template<typename T1, typename Alloc1,
1187 typename T2, typename Alloc2>
1188 bool operator!=(const detail::vector_base<T1,Alloc1>& lhs,
1189 const std::vector<T2,Alloc2>& rhs)
1191 return !(lhs == rhs);
1194 template<typename T1, typename Alloc1,
1195 typename T2, typename Alloc2>
1196 bool operator!=(const std::vector<T1,Alloc1>& lhs,
1197 const detail::vector_base<T2,Alloc2>& rhs)
1199 return !(lhs == rhs);