casacore
uvector.h
Go to the documentation of this file.
1 #ifndef AO_UVECTOR_H
2 #define AO_UVECTOR_H
3 
4 #include <algorithm>
5 #include <cstring>
6 #include <iterator>
7 #include <memory>
8 #include <utility>
9 #include <stdexcept>
10 
18 namespace ao {
19 
72 template<typename Tp, typename Alloc = std::allocator<Tp> >
73 class uvector : private Alloc
74 {
75  static_assert(std::is_standard_layout<Tp>(), "A uvector can only hold classes with standard layout");
76 private:
77 #if __cplusplus > 201402L
78  typedef std::allocator_traits<allocator_type>::is_always_equal allocator_is_always_equal;
79 #else
80  typedef std::false_type allocator_is_always_equal;
81 #endif
82 public:
84  typedef Tp value_type;
86  typedef Alloc allocator_type;
88  typedef Tp& reference;
90  typedef const Tp& const_reference;
92  typedef Tp* pointer;
94  typedef const Tp* const_pointer;
96  typedef Tp* iterator;
98  typedef const Tp* const_iterator;
100  typedef std::reverse_iterator<iterator> reverse_iterator;
102  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
104  typedef std::ptrdiff_t difference_type;
106  typedef std::size_t size_t;
108  typedef std::size_t size_type;
109 
110 private:
112 
113 public:
117  explicit uvector(const allocator_type& allocator = Alloc()) noexcept
118  : Alloc(allocator), _begin(nullptr), _end(nullptr), _endOfStorage(nullptr)
119  {
120  }
121 
128  explicit uvector(size_t n) :
129  _begin(allocate(n)),
130  _end(_begin + n),
132  {
133  }
134 
141  uvector(size_t n, const value_type& val, const allocator_type& allocator = Alloc()) :
142  Alloc(allocator),
143  _begin(allocate(n)),
144  _end(_begin + n),
146  {
147  std::uninitialized_fill_n<Tp*,size_t>(_begin, n, val);
148  }
149 
155  template<class InputIterator>
156  uvector(InputIterator first, InputIterator last, const allocator_type& allocator = Alloc()) :
157  Alloc(allocator)
158  {
159  construct_from_range<InputIterator>(first, last, std::is_integral<InputIterator>());
160  }
161 
167  uvector(const uvector<Tp,Alloc>& other) :
168  Alloc(std::allocator_traits<Alloc>::select_on_container_copy_construction(static_cast<allocator_type>(other))),
169  _begin(allocate(other.size())),
170  _end(_begin + other.size()),
172  {
173  std::copy(other._begin, other._end, _begin);
174  }
175 
180  uvector(const uvector<Tp,Alloc>& other, const allocator_type& allocator) :
181  Alloc(allocator),
182  _begin(allocate(other.size())),
183  _end(_begin + other.size()),
185  {
186  std::copy(other._begin, other._end, _begin);
187  }
188 
192  uvector(uvector<Tp,Alloc>&& other) noexcept :
193  Alloc(std::move(other)),
194  _begin(other._begin),
195  _end(other._end),
196  _endOfStorage(other._endOfStorage)
197  {
198  other._begin = nullptr;
199  other._end = nullptr;
200  other._endOfStorage = nullptr;
201  }
202 
207  uvector(uvector<Tp,Alloc>&& other, const allocator_type& allocator) noexcept :
208  Alloc(allocator),
209  _begin(other._begin),
210  _end(other._end),
211  _endOfStorage(other._endOfStorage)
212  {
213  other._begin = nullptr;
214  other._end = nullptr;
215  other._endOfStorage = nullptr;
216  }
217 
222  uvector(std::initializer_list<Tp> initlist, const allocator_type& allocator = Alloc()) :
223  Alloc(allocator),
224  _begin(allocate(initlist.size())),
225  _end(_begin + initlist.size()),
227  {
228  iterator destIter = _begin;
229  for(typename std::initializer_list<Tp>::const_iterator i=initlist.begin(); i!=initlist.end(); ++i)
230  {
231  *destIter = *i;
232  ++destIter;
233  }
234  }
235 
237  ~uvector() noexcept
238  {
239  deallocate();
240  }
241 
247  {
248  return assign_copy_from(other, typename std::allocator_traits<Alloc>::propagate_on_container_copy_assignment());
249  }
250 
255  uvector& operator=(uvector<Tp,Alloc>&& other) noexcept(
258  {
259  return assign_move_from(std::move(other), typename std::allocator_traits<Alloc>::propagate_on_container_move_assignment());
260  }
261 
263  iterator begin() noexcept { return _begin; }
264 
266  const_iterator begin() const noexcept { return _begin; }
267 
269  iterator end() noexcept { return _end; }
270 
272  const_iterator end() const noexcept { return _end; }
273 
275  reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
276 
278  const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
279 
281  reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
282 
284  const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
285 
287  const_iterator cbegin() const noexcept { return _begin; }
288 
290  const_iterator cend() const noexcept { return _end; }
291 
294 
297 
299  size_t size() const noexcept { return _end - _begin; }
300 
302  size_t max_size() const noexcept { return Alloc::max_size(); }
303 
313  void resize(size_t n)
314  {
315  if(capacity() < n)
316  {
317  size_t newSize = enlarge_size(n);
318  pointer newStorage = allocate(newSize);
319  std::move(_begin, _end, newStorage);
320  deallocate();
321  _begin = newStorage;
322  _endOfStorage = _begin + newSize;
323  }
324  _end = _begin + n;
325  }
326 
336  void resize(size_t n, const Tp& val)
337  {
338  size_t oldSize = size();
339  if(capacity() < n)
340  {
341  pointer newStorage = allocate(n);
342  std::move(_begin, _end, newStorage);
343  deallocate();
344  _begin = newStorage;
345  _endOfStorage = _begin + n;
346  }
347  _end = _begin + n;
348  if(oldSize < n)
349  std::uninitialized_fill<Tp*,size_t>(_begin + oldSize, _end, val);
350  }
351 
353  size_t capacity() const noexcept { return _endOfStorage - _begin; }
354 
357  bool empty() const noexcept { return _begin == _end; }
358 
368  void reserve(size_t n)
369  {
370  if(capacity() < n)
371  {
372  const size_t curSize = size();
373  pointer newStorage = allocate(n);
374  std::move(_begin, _begin + curSize, newStorage);
375  deallocate();
376  _begin = newStorage;
377  _end = newStorage + curSize;
378  _endOfStorage = _begin + n;
379  }
380  }
381 
389  {
390  const size_t curSize = size();
391  if(curSize == 0)
392  {
393  deallocate();
394  _begin = nullptr;
395  _end = nullptr;
396  _endOfStorage = nullptr;
397  }
398  else if(curSize < capacity()) {
399  pointer newStorage = allocate(curSize);
400  std::move(_begin, _begin + curSize, newStorage);
401  deallocate();
402  _begin = newStorage;
403  _end = newStorage + curSize;
404  _endOfStorage = _begin + curSize;
405  }
406  }
407 
409  Tp& operator[](size_t index) noexcept { return _begin[index]; }
410 
412  const Tp& operator[](size_t index) const noexcept { return _begin[index]; }
413 
417  Tp& at(size_t index)
418  {
419  check_bounds(index);
420  return _begin[index];
421  }
422 
426  const Tp& at(size_t index) const
427  {
428  check_bounds(index);
429  return _begin[index];
430  }
431 
433  Tp& front() noexcept { return *_begin; }
434 
436  const Tp& front() const noexcept { return *_begin; }
437 
439  Tp& back() noexcept { return *(_end - 1); }
440 
442  const Tp& back() const noexcept { return *(_end - 1); }
443 
445  Tp* data() noexcept { return _begin; }
446 
448  const Tp* data() const noexcept { return _begin; }
449 
456  template<class InputIterator>
457  void assign(InputIterator first, InputIterator last)
458  {
459  assign_from_range<InputIterator>(first, last, std::is_integral<InputIterator>());
460  }
461 
467  void assign(size_t n, const Tp& val)
468  {
469  if(n > capacity())
470  {
471  iterator newStorage = allocate(n);
472  deallocate();
473  _begin = newStorage;
474  _endOfStorage = _begin + n;
475  }
476  _end = _begin + n;
477  std::uninitialized_fill_n<Tp*,size_t>(_begin, n, val);
478  }
479 
485  void assign(std::initializer_list<Tp> initlist)
486  {
487  if(initlist.size() > capacity())
488  {
489  iterator newStorage = allocate(initlist.size());
490  deallocate();
491  _begin = newStorage;
492  _endOfStorage = _begin + initlist.size();
493  }
494  _end = _begin + initlist.size();
495  iterator destIter = _begin;
496  for(typename std::initializer_list<Tp>::const_iterator i=initlist.begin(); i!=initlist.end(); ++i)
497  {
498  *destIter = *i;
499  ++destIter;
500  }
501  }
502 
507  void push_back(const Tp& item)
508  {
509  if(_end == _endOfStorage)
510  enlarge(enlarge_size(1));
511  *_end = item;
512  ++_end;
513  }
514 
522  void push_back(Tp&& item)
523  {
524  if(_end == _endOfStorage)
525  enlarge(enlarge_size(1));
526  *_end = std::move(item);
527  ++_end;
528  }
529 
531  void pop_back()
532  {
533  --_end;
534  }
535 
544  iterator insert(const_iterator position, const Tp& item)
545  {
546  if(_end == _endOfStorage)
547  {
548  size_t index = position - _begin;
549  enlarge_for_insert(enlarge_size(1), index, 1);
550  position = _begin + index;
551  }
552  else {
553  std::move_backward(const_cast<iterator>(position), _end, _end+1);
554  ++_end;
555  }
556  *const_cast<iterator>(position) = item;
557  return const_cast<iterator>(position);
558  }
559 
569  iterator insert(const_iterator position, size_t n, const Tp& val)
570  {
571  if(capacity() < size() + n)
572  {
573  size_t index = position - _begin;
574  enlarge_for_insert(enlarge_size(n), index, n);
575  position = _begin + index;
576  }
577  else {
578  std::move_backward(const_cast<iterator>(position), _end, _end+n);
579  _end += n;
580  }
581  std::uninitialized_fill_n<Tp*,size_t>(const_cast<iterator>(position), n, val);
582  return const_cast<iterator>(position);
583  }
584 
594  template <class InputIterator>
595  iterator insert(const_iterator position, InputIterator first, InputIterator last)
596  {
597  return insert_from_range<InputIterator>(position, first, last, std::is_integral<InputIterator>());
598  }
599 
612  iterator insert(const_iterator position, Tp&& item)
613  {
614  if(_end == _endOfStorage)
615  {
616  size_t index = position - _begin;
617  enlarge_for_insert(enlarge_size(1), index, 1);
618  position = _begin + index;
619  }
620  else {
621  std::move_backward(const_cast<iterator>(position), _end, _end+1);
622  ++_end;
623  }
624  *const_cast<iterator>(position) = std::move(item);
625  return const_cast<iterator>(position);
626  }
627 
636  iterator insert(const_iterator position, std::initializer_list<Tp> initlist)
637  {
638  if(capacity() < size() + initlist.size())
639  {
640  size_t index = position - _begin;
641  enlarge_for_insert(enlarge_size(initlist.size()), index, initlist.size());
642  position = _begin + index;
643  }
644  else {
645  std::move_backward(const_cast<iterator>(position), _end, _end+initlist.size());
646  _end += initlist.size();
647  }
648  iterator destIter = const_cast<iterator>(position);
649  for(typename std::initializer_list<Tp>::const_iterator i=initlist.begin(); i!=initlist.end(); ++i)
650  {
651  *destIter = *i;
652  ++destIter;
653  }
654  return const_cast<iterator>(position);
655  }
656 
664  {
665  std::move(const_cast<iterator>(position)+1, _end, const_cast<iterator>(position));
666  --_end;
667  return const_cast<iterator>(position);
668  }
669 
678  {
679  std::move(const_cast<iterator>(last), _end, const_cast<iterator>(first));
680  _end -= last - first;
681  return const_cast<iterator>(first);
682  }
683 
695  void swap(uvector<Tp, Alloc>& other) noexcept
696  {
697  swap(other, typename std::allocator_traits<Alloc>::propagate_on_container_swap());
698  }
699 
701  void clear()
702  {
703  _end = _begin;
704  }
705 
714  template<typename... Args>
715  iterator emplace(const_iterator position, Args&&... args)
716  {
717  if(_end == _endOfStorage)
718  {
719  size_t index = position - _begin;
720  enlarge_for_insert(enlarge_size(1), index, 1);
721  position = _begin + index;
722  }
723  else {
724  std::move_backward(const_cast<iterator>(position), _end, _end+1);
725  ++_end;
726  }
727  *const_cast<iterator>(position) = Tp(std::forward<Args>(args)...);
728  return const_cast<iterator>(position);
729  }
730 
735  template<typename... Args>
736  void emplace_back(Args&&... args)
737  {
738  if(_end == _endOfStorage)
739  enlarge(enlarge_size(1));
740  *_end = Tp(std::forward<Args>(args)...);
741  ++_end;
742  }
743 
745  allocator_type get_allocator() const noexcept
746  {
747  return *this;
748  }
749 
750  // --- NON STANDARD METHODS ---
751 
763  {
764  if(capacity() < size() + n)
765  {
766  size_t index = position - _begin;
767  enlarge_for_insert(enlarge_size(n), index, n);
768  position = _begin + index;
769  }
770  else {
771  std::move_backward(const_cast<iterator>(position), _end, _end+n);
772  _end += n;
773  }
774  return const_cast<iterator>(position);
775  }
776 
784  template <class InputIterator>
785  void push_back(InputIterator first, InputIterator last)
786  {
787  push_back_range<InputIterator>(first, last, std::is_integral<InputIterator>());
788  }
789 
797  void push_back(size_t n, const Tp& val)
798  {
799  if(capacity() - size() < n)
800  {
801  enlarge(enlarge_size(n));
802  }
803  std::uninitialized_fill_n<Tp*,size_t>(_end, n, val);
804  _end += n;
805  }
806 
813  void push_back(std::initializer_list<Tp> initlist)
814  {
815  if(capacity() - size() < initlist.size())
816  {
817  enlarge(enlarge_size(initlist.size()));
818  }
819  for(typename std::initializer_list<Tp>::iterator i = initlist.begin(); i != initlist.end(); ++i)
820  {
821  *_end = *i;
822  ++_end;
823  }
824  }
825 
832  void push_back_uninitialized(size_t n)
833  {
834  resize(size() + n);
835  }
836 
837 private:
838 
839  pointer allocate(size_t n)
840  {
841  return Alloc::allocate(n);
842  }
843 
844  void deallocate() noexcept
845  {
847  }
848 
849  void deallocate(pointer begin, size_t n) noexcept
850  {
851  if(begin != nullptr)
852  Alloc::deallocate(begin, n);
853  }
854 
855  template<typename InputIterator>
856  void construct_from_range(InputIterator first, InputIterator last, std::false_type)
857  {
858  construct_from_range<InputIterator>(first, last, typename std::iterator_traits<InputIterator>::iterator_category());
859  }
860 
861  template<typename Integral>
862  void construct_from_range(Integral n, Integral val, std::true_type)
863  {
864  _begin = allocate(n);
865  _end = _begin + n;
867  std::uninitialized_fill_n<Tp*,size_t>(_begin, n, val);
868  }
869 
870  template<typename InputIterator>
871  void construct_from_range(InputIterator first, InputIterator last, std::forward_iterator_tag)
872  {
873  size_t n = std::distance(first, last);
874  _begin = allocate(n);
875  _end = _begin + n;
876  _endOfStorage = _begin + n;
877  Tp* destIter = _begin;
878  while(first != last)
879  {
880  *destIter = *first;
881  ++destIter; ++first;
882  }
883  }
884 
885  template<typename InputIterator>
886  void assign_from_range(InputIterator first, InputIterator last, std::false_type)
887  {
888  assign_from_range<InputIterator>(first, last, typename std::iterator_traits<InputIterator>::iterator_category());
889  }
890 
891  // This function is called from assign(iter,iter) when Tp is an integral. In that case,
892  // the user tried to call assign(n, &val), but it got caught by the wrong overload.
893  template<typename Integral>
894  void assign_from_range(Integral n, Integral val, std::true_type)
895  {
896  if(size_t(n) > capacity())
897  {
898  iterator newStorage = allocate(n);
899  deallocate();
900  _begin = newStorage;
901  _endOfStorage = _begin + n;
902  }
903  _end = _begin + n;
904  std::uninitialized_fill_n<Tp*,size_t>(_begin, n, val);
905  }
906 
907  template<typename InputIterator>
908  void assign_from_range(InputIterator first, InputIterator last, std::forward_iterator_tag)
909  {
910  size_t n = std::distance(first, last);
911  if(n > capacity())
912  {
913  iterator newStorage = allocate(n);
914  deallocate();
915  _begin = newStorage;
916  _endOfStorage = _begin + n;
917  }
918  _end = _begin + n;
919  Tp* destIter = _begin;
920  while(first != last)
921  {
922  *destIter = *first;
923  ++destIter; ++first;
924  }
925  }
926 
927  template<typename InputIterator>
928  iterator insert_from_range(const_iterator position, InputIterator first, InputIterator last, std::false_type)
929  {
930  return insert_from_range<InputIterator>(position, first, last,
931  typename std::iterator_traits<InputIterator>::iterator_category());
932  }
933 
934  template<typename Integral>
935  iterator insert_from_range(const_iterator position, Integral n, Integral val, std::true_type)
936  {
937  if(capacity() < size() + n)
938  {
939  size_t index = position - _begin;
940  enlarge_for_insert(enlarge_size(n), index, n);
941  position = _begin + index;
942  }
943  else {
944  std::move_backward(const_cast<iterator>(position), _end, _end+n);
945  _end += n;
946  }
947  std::uninitialized_fill_n<Tp*,size_t>(const_cast<iterator>(position), n, val);
948  return const_cast<iterator>(position);
949  }
950 
951  template<typename InputIterator>
952  iterator insert_from_range(const_iterator position, InputIterator first, InputIterator last, std::forward_iterator_tag)
953  {
954  size_t n = std::distance(first, last);
955  if(capacity() < size() + n)
956  {
957  size_t index = position - _begin;
958  enlarge_for_insert(enlarge_size(n), index, n);
959  position = _begin + index;
960  }
961  else {
962  std::move_backward(const_cast<iterator>(position), _end, _end+n);
963  _end += n;
964  }
965  Tp* destIter = const_cast<iterator>(position);
966  while(first != last)
967  {
968  *destIter = *first;
969  ++destIter; ++first;
970  }
971  return const_cast<iterator>(position);
972  }
973 
974  void check_bounds(size_t index) const
975  {
976  if(index >= size())
977  throw std::out_of_range("Access to element in uvector past end");
978  }
979 
980  size_t enlarge_size(size_t extra_space_needed) const noexcept
981  {
982  return size() + std::max(size(), extra_space_needed);
983  }
984 
985  void enlarge(size_t newSize)
986  {
987  pointer newStorage = allocate(newSize);
988  std::copy(_begin, _end, newStorage);
989  deallocate();
990  _end = newStorage + size();
991  _begin = newStorage;
992  _endOfStorage = _begin + newSize;
993  }
994 
995  void enlarge_for_insert(size_t newSize, size_t insert_position, size_t insert_count)
996  {
997  pointer newStorage = allocate(newSize);
998  std::copy(_begin, _begin + insert_position, newStorage);
999  std::copy(_begin + insert_position, _end, newStorage + insert_position + insert_count);
1000  deallocate();
1001  _end = newStorage + size() + insert_count;
1002  _begin = newStorage;
1003  _endOfStorage = _begin + newSize;
1004  }
1005 
1006  // implementation of operator=(const&) without propagate_on_container_copy_assignment
1007  uvector& assign_copy_from(const uvector<Tp,Alloc>& other, std::false_type)
1008  {
1009  const size_t n = other.size();
1010  if(n > capacity()) {
1011  iterator newStorage = allocate(n);
1012  deallocate();
1013  _begin = newStorage;
1014  _end = _begin + n;
1015  _endOfStorage = _end;
1016  }
1017  std::copy(other._begin, other._begin + n, _begin);
1018  return *this;
1019  }
1020 
1021  // implementation of operator=(const&) with propagate_on_container_copy_assignment
1022  uvector& assign_copy_from(const uvector<Tp,Alloc>& other, std::true_type)
1023  {
1024  if(allocator_is_always_equal() || static_cast<Alloc&>(other) == static_cast<Alloc&>(*this))
1025  {
1026  assign_copy_from(other, std::false_type());
1027  }
1028  else {
1029  const size_t n = other.size();
1030  iterator newStorage = static_cast<Alloc&>(other).allocate(n);
1031  deallocate();
1032  _begin = newStorage;
1033  _end = _begin + n;
1034  _endOfStorage = _end;
1035  std::copy(other._begin, other._begin + n, _begin);
1036  Alloc::operator=(static_cast<Alloc&>(other));
1037  }
1038  return *this;
1039  }
1040 
1041  // implementation of operator=() without propagate_on_container_move_assignment
1043  {
1044  if(allocator_is_always_equal::value || static_cast<Alloc&>(other) == static_cast<Alloc&>(*this))
1045  {
1046  deallocate();
1047  _begin = other._begin;
1048  _end = other._end;
1049  _endOfStorage = other._endOfStorage;
1050  other._begin = nullptr;
1051  other._end = nullptr;
1052  other._endOfStorage = nullptr;
1053  }
1054  else {
1055  // We should not propagate the allocator and the allocators are different.
1056  // This means we can not swap the allocated space, since then we would
1057  // deallocate the space with a different allocator type. Therefore, we
1058  // need to copy:
1059  assign_copy_from(other, std::false_type());
1060  }
1061  return *this;
1062  }
1063 
1064  // implementation of operator=() with propagate_on_container_move_assignment
1065  uvector& assign_move_from(uvector<Tp,Alloc>&& other, std::true_type) noexcept
1066  {
1067  deallocate();
1068  Alloc::operator=(std::move(static_cast<Alloc&>(other)));
1069  _begin = other._begin;
1070  _end = other._end;
1071  _endOfStorage = other._endOfStorage;
1072  other._begin = nullptr;
1073  other._end = nullptr;
1074  other._endOfStorage = nullptr;
1075  return *this;
1076  }
1077 
1078  // implementation of swap with propagate_on_container_swap
1079  void swap(uvector<Tp,Alloc>& other, std::true_type) noexcept
1080  {
1081  std::swap(_begin, other._begin);
1082  std::swap(_end, other._end);
1083  std::swap(_endOfStorage, other._endOfStorage);
1084  std::swap(static_cast<Alloc&>(other), static_cast<Alloc&>(*this));
1085  }
1086 
1087  // implementation of swap without propagate_on_container_swap
1088  void swap(uvector<Tp,Alloc>& other, std::false_type) noexcept
1089  {
1090  std::swap(_begin, other._begin);
1091  std::swap(_end, other._end);
1092  std::swap(_endOfStorage, other._endOfStorage);
1114  }
1115 
1116  template<typename InputIterator>
1117  void push_back_range(InputIterator first, InputIterator last, std::false_type)
1118  {
1119  push_back_range<InputIterator>(first, last, typename std::iterator_traits<InputIterator>::iterator_category());
1120  }
1121 
1122  // This function is called from push_back(iter,iter) when Tp is an integral. In that case,
1123  // the user tried to call push_back(n, &val), but it got caught by the wrong overload.
1124  template<typename Integral>
1125  void push_back_range(Integral n, Integral val, std::true_type)
1126  {
1127  if(capacity() - size() < size_t(n))
1128  {
1129  enlarge(enlarge_size(n));
1130  }
1131  std::uninitialized_fill_n<Tp*,size_t>(_end, n, val);
1132  _end += n;
1133  }
1134 
1135  template<typename InputIterator>
1136  void push_back_range(InputIterator first, InputIterator last, std::forward_iterator_tag)
1137  {
1138  size_t n = std::distance(first, last);
1139  if(n > capacity() - size())
1140  {
1141  enlarge(enlarge_size(n));
1142  }
1143  while(first != last)
1144  {
1145  *_end = *first;
1146  ++_end;
1147  ++first;
1148  }
1149  }
1150 
1151 };
1152 
1154 template<class Tp, class Alloc>
1155 inline bool operator==(const uvector<Tp,Alloc>& lhs, const uvector<Tp,Alloc>& rhs) noexcept
1156 {
1157  return lhs.size()==rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
1158 }
1159 
1161 template<class Tp, class Alloc>
1162 inline bool operator!=(const uvector<Tp,Alloc>& lhs, const uvector<Tp,Alloc>& rhs) noexcept
1163 {
1164  return !(lhs == rhs);
1165 }
1166 
1171 template <class Tp, class Alloc>
1172 inline bool operator<(const uvector<Tp,Alloc>& lhs, const uvector<Tp,Alloc>& rhs) noexcept
1173 {
1174  const size_t minSize = std::min(lhs.size(), rhs.size());
1175  for(size_t i=0; i!=minSize; ++i)
1176  {
1177  if(lhs[i] < rhs[i])
1178  return true;
1179  else if(lhs[i] > rhs[i])
1180  return false;
1181  }
1182  return lhs.size() < rhs.size();
1183 }
1184 
1189 template <class Tp, class Alloc>
1190 inline bool operator<=(const uvector<Tp,Alloc>& lhs, const uvector<Tp,Alloc>& rhs) noexcept
1191 {
1192  const size_t minSize = std::min(lhs.size(), rhs.size());
1193  for(size_t i=0; i!=minSize; ++i)
1194  {
1195  if(lhs[i] < rhs[i])
1196  return true;
1197  else if(lhs[i] > rhs[i])
1198  return false;
1199  }
1200  return lhs.size() <= rhs.size();
1201 }
1202 
1207 template <class Tp, class Alloc>
1208 inline bool operator>(const uvector<Tp,Alloc>& lhs, const uvector<Tp,Alloc>& rhs) noexcept
1209 {
1210  return rhs < lhs;
1211 }
1212 
1217 template <class Tp, class Alloc>
1218 inline bool operator>=(const uvector<Tp,Alloc>& lhs, const uvector<Tp,Alloc>& rhs) noexcept
1219 {
1220  return rhs <= lhs;
1221 }
1222 
1233 template <class Tp, class Alloc>
1235 {
1236  x.swap(y);
1237 }
1238 
1241 } // end of namespace ao
1242 
1243 #endif // AO_UVECTOR_H
1244 
A container similar to std::vector, but one that allows construction without initializing its element...
Definition: uvector.h:74
const Tp * const_iterator
Iterator type of constant elements.
Definition: uvector.h:98
void assign_from_range(InputIterator first, InputIterator last, std::forward_iterator_tag)
Definition: uvector.h:908
uvector & assign_copy_from(const uvector< Tp, Alloc > &other, std::true_type)
implementation of operator=(const&) with propagate_on_container_copy_assignment
Definition: uvector.h:1022
iterator insert_uninitialized(const_iterator position, size_t n)
— NON STANDARD METHODS —
Definition: uvector.h:762
~uvector() noexcept
Destructor.
Definition: uvector.h:237
uvector & assign_move_from(uvector< Tp, Alloc > &&other, std::false_type) noexcept(allocator_is_always_equal::value)
implementation of operator=() without propagate_on_container_move_assignment
Definition: uvector.h:1042
void deallocate() noexcept
Definition: uvector.h:844
void shrink_to_fit()
Change the capacity of the container such that no extra space is hold.
Definition: uvector.h:388
uvector(const allocator_type &allocator=Alloc()) noexcept
Construct an empty uvector.
Definition: uvector.h:117
uvector & operator=(const uvector< Tp, Alloc > &other)
Assign another uvector to this uvector.
Definition: uvector.h:246
void push_back_uninitialized(size_t n)
Add elements at the end without initializing them.
Definition: uvector.h:832
void push_back(std::initializer_list< Tp > initlist)
Add elements from an initializer list to the end of the container.
Definition: uvector.h:813
void push_back_range(InputIterator first, InputIterator last, std::false_type)
Definition: uvector.h:1117
const_reverse_iterator crend() const noexcept
Get constant reverse iterator to element before first element.
Definition: uvector.h:296
Tp * data() noexcept
Get pointer to internal storage.
Definition: uvector.h:445
const Tp & const_reference
Constant reference to element type.
Definition: uvector.h:90
void deallocate(pointer begin, size_t n) noexcept
Definition: uvector.h:849
const_reverse_iterator rbegin() const noexcept
Get constant reverse iterator to last element.
Definition: uvector.h:278
const Tp & operator[](size_t index) const noexcept
Get a constant reference to the element at the given index.
Definition: uvector.h:412
uvector(const uvector< Tp, Alloc > &other, const allocator_type &allocator)
Copy construct a uvector with custom allocator.
Definition: uvector.h:180
uvector(uvector< Tp, Alloc > &&other) noexcept
Move construct a uvector.
Definition: uvector.h:192
Tp & back() noexcept
Get reference to last element in container.
Definition: uvector.h:439
size_t capacity() const noexcept
Get the number of elements the container can currently hold without reallocating storage.
Definition: uvector.h:353
pointer _endOfStorage
Definition: uvector.h:111
size_t size() const noexcept
Get number of elements in container.
Definition: uvector.h:299
void push_back_range(InputIterator first, InputIterator last, std::forward_iterator_tag)
Definition: uvector.h:1136
void construct_from_range(InputIterator first, InputIterator last, std::false_type)
Definition: uvector.h:856
std::reverse_iterator< iterator > reverse_iterator
Reverse iterator type.
Definition: uvector.h:100
void resize(size_t n)
Change the number of elements in the container.
Definition: uvector.h:313
iterator insert_from_range(const_iterator position, InputIterator first, InputIterator last, std::forward_iterator_tag)
Definition: uvector.h:952
void assign_from_range(Integral n, Integral val, std::true_type)
This function is called from assign(iter,iter) when Tp is an integral.
Definition: uvector.h:894
void swap(uvector< Tp, Alloc > &other, std::false_type) noexcept
implementation of swap without propagate_on_container_swap
Definition: uvector.h:1088
const_iterator cbegin() const noexcept
Get constant iterator to first element.
Definition: uvector.h:287
Tp * pointer
Pointer to element type.
Definition: uvector.h:92
void push_back_range(Integral n, Integral val, std::true_type)
This function is called from push_back(iter,iter) when Tp is an integral.
Definition: uvector.h:1125
reverse_iterator rend() noexcept
Get reverse iterator to element before first element.
Definition: uvector.h:281
void push_back(size_t n, const Tp &val)
Add elements at the end and initialize them with a value.
Definition: uvector.h:797
Tp * iterator
Iterator type.
Definition: uvector.h:96
void reserve(size_t n)
Reserve space for a number of elements, to prevent the overhead of extra reallocations.
Definition: uvector.h:368
const_reverse_iterator rend() const noexcept
Get constant reverse iterator to element before first element.
Definition: uvector.h:284
uvector & assign_move_from(uvector< Tp, Alloc > &&other, std::true_type) noexcept
implementation of operator=() with propagate_on_container_move_assignment
Definition: uvector.h:1065
void assign(std::initializer_list< Tp > initlist)
Assign this container to an initializer list.
Definition: uvector.h:485
Tp & reference
Reference to element type.
Definition: uvector.h:88
const Tp * const_pointer
Pointer to constant element type.
Definition: uvector.h:94
Alloc allocator_type
Type of allocator used to allocate and deallocate space.
Definition: uvector.h:86
void enlarge(size_t newSize)
Definition: uvector.h:985
void assign(size_t n, const Tp &val)
Resize the container and assign the given value to all elements.
Definition: uvector.h:467
const Tp & at(size_t index) const
Get a constant reference to the element at the given index with bounds checking.
Definition: uvector.h:426
Tp value_type
Element type.
Definition: uvector.h:84
iterator begin() noexcept
Get iterator to first element.
Definition: uvector.h:263
const Tp & back() const noexcept
Get constant reference to last element in container.
Definition: uvector.h:442
const_iterator begin() const noexcept
Get constant iterator to first element.
Definition: uvector.h:266
uvector(InputIterator first, InputIterator last, const allocator_type &allocator=Alloc())
Construct a vector by copying elements from a range.
Definition: uvector.h:156
iterator insert(const_iterator position, InputIterator first, InputIterator last)
Insert elements at a given position and initialize them from a range.
Definition: uvector.h:595
void clear()
Remove all elements from the container.
Definition: uvector.h:701
uvector & assign_copy_from(const uvector< Tp, Alloc > &other, std::false_type)
implementation of operator=(const&) without propagate_on_container_copy_assignment
Definition: uvector.h:1007
bool empty() const noexcept
Determine if the container is currently empty.
Definition: uvector.h:357
iterator erase(const_iterator position)
Delete an element from the container.
Definition: uvector.h:663
void resize(size_t n, const Tp &val)
Change the number of elements in the container.
Definition: uvector.h:336
const_iterator cend() const noexcept
Get constant iterator to element past last element.
Definition: uvector.h:290
iterator insert_from_range(const_iterator position, Integral n, Integral val, std::true_type)
Definition: uvector.h:935
iterator insert(const_iterator position, std::initializer_list< Tp > initlist)
Insert elements at a given position and initialize them from a initializer list.
Definition: uvector.h:636
std::false_type allocator_is_always_equal
Definition: uvector.h:75
void swap(uvector< Tp, Alloc > &other, std::true_type) noexcept
implementation of swap with propagate_on_container_swap
Definition: uvector.h:1079
iterator end() noexcept
Get iterator to element past last element.
Definition: uvector.h:269
const Tp * data() const noexcept
Get constant pointer to internal storage.
Definition: uvector.h:448
void emplace_back(Args &&... args)
Add the given value to the end of the container by constructing it in place.
Definition: uvector.h:736
const_iterator end() const noexcept
Get constant iterator to element past last element.
Definition: uvector.h:272
pointer allocate(size_t n)
Definition: uvector.h:839
iterator insert(const_iterator position, size_t n, const Tp &val)
Insert elements at a given position and initialize them with a value.
Definition: uvector.h:569
const Tp & front() const noexcept
Get constant reference to first element in container.
Definition: uvector.h:436
size_t enlarge_size(size_t extra_space_needed) const noexcept
Definition: uvector.h:980
void pop_back()
Remove the last element from the container.
Definition: uvector.h:531
iterator insert(const_iterator position, Tp &&item)
Insert an element at a given position by moving it in.
Definition: uvector.h:612
Tp & operator[](size_t index) noexcept
Get a reference to the element at the given index.
Definition: uvector.h:409
Tp & at(size_t index)
Get a reference to the element at the given index with bounds checking.
Definition: uvector.h:417
void enlarge_for_insert(size_t newSize, size_t insert_position, size_t insert_count)
Definition: uvector.h:995
uvector(const uvector< Tp, Alloc > &other)
Copy construct a uvector.
Definition: uvector.h:167
void push_back(InputIterator first, InputIterator last)
Add a range of items to the end of the container.
Definition: uvector.h:785
reverse_iterator rbegin() noexcept
Get reverse iterator to last element.
Definition: uvector.h:275
std::reverse_iterator< const_iterator > const_reverse_iterator
Reverse iterator of constant elements.
Definition: uvector.h:102
uvector(std::initializer_list< Tp > initlist, const allocator_type &allocator=Alloc())
Construct a uvector from a initializer list.
Definition: uvector.h:222
pointer _end
Definition: uvector.h:111
void assign(InputIterator first, InputIterator last)
Assign this container to be equal to the given range.
Definition: uvector.h:457
const_reverse_iterator crbegin() const noexcept
Get constant reverse iterator to last element.
Definition: uvector.h:293
void construct_from_range(Integral n, Integral val, std::true_type)
Definition: uvector.h:862
void assign_from_range(InputIterator first, InputIterator last, std::false_type)
Definition: uvector.h:886
iterator erase(const_iterator first, const_iterator last)
Delete a range of elements from the container.
Definition: uvector.h:677
void push_back(const Tp &item)
Add the given value to the end of the container.
Definition: uvector.h:507
void swap(uvector< Tp, Alloc > &other) noexcept
Swap the contents of this uvector with the given uvector.
Definition: uvector.h:695
std::ptrdiff_t difference_type
Difference between to iterators.
Definition: uvector.h:104
void push_back(Tp &&item)
Add the given value to the end of the container by moving it in.
Definition: uvector.h:522
void construct_from_range(InputIterator first, InputIterator last, std::forward_iterator_tag)
Definition: uvector.h:871
uvector & operator=(uvector< Tp, Alloc > &&other) noexcept(std::allocator_traits< Alloc >::propagate_on_container_move_assignment::value||allocator_is_always_equal::value)
Assign another uvector to this uvector.
Definition: uvector.h:255
uvector(size_t n)
Construct a vector with given amount of elements, without initializing these.
Definition: uvector.h:128
uvector(size_t n, const value_type &val, const allocator_type &allocator=Alloc())
Construct a vector with given amount of elements and set these to a specific value.
Definition: uvector.h:141
pointer _begin
Definition: uvector.h:111
size_t max_size() const noexcept
Get maximum number of elements that this container can hold.
Definition: uvector.h:302
Tp & front() noexcept
Get reference to first element in container.
Definition: uvector.h:433
allocator_type get_allocator() const noexcept
Get a copy of the allocator.
Definition: uvector.h:745
iterator emplace(const_iterator position, Args &&... args)
Insert an element at a given position by constructing it in place.
Definition: uvector.h:715
void check_bounds(size_t index) const
Definition: uvector.h:974
std::size_t size_t
Type used for indexing elements.
Definition: uvector.h:106
iterator insert(const_iterator position, const Tp &item)
Insert an element at a given position.
Definition: uvector.h:544
uvector(uvector< Tp, Alloc > &&other, const allocator_type &allocator) noexcept
Move construct a uvector with custom allocator.
Definition: uvector.h:207
iterator insert_from_range(const_iterator position, InputIterator first, InputIterator last, std::false_type)
Definition: uvector.h:928
std::size_t size_type
Type used for indexing elements.
Definition: uvector.h:108
bool operator>(const uvector< Tp, Alloc > &lhs, const uvector< Tp, Alloc > &rhs) noexcept
Compare two uvectors for larger than.
Definition: uvector.h:1208
bool operator<=(const uvector< Tp, Alloc > &lhs, const uvector< Tp, Alloc > &rhs) noexcept
Compare two uvectors for smaller than or equal.
Definition: uvector.h:1190
bool operator==(const uvector< Tp, Alloc > &lhs, const uvector< Tp, Alloc > &rhs) noexcept
Compare two uvectors for equality.
Definition: uvector.h:1155
bool operator>=(const uvector< Tp, Alloc > &lhs, const uvector< Tp, Alloc > &rhs) noexcept
Compare two uvectors for larger than or equal.
Definition: uvector.h:1218
bool operator<(const uvector< Tp, Alloc > &lhs, const uvector< Tp, Alloc > &rhs) noexcept
Compare two uvectors for smaller than.
Definition: uvector.h:1172
void swap(uvector< Tp, Alloc > &x, uvector< Tp, Alloc > &y)
Swap the contents of the two uvectors.
Definition: uvector.h:1234
bool operator!=(const uvector< Tp, Alloc > &lhs, const uvector< Tp, Alloc > &rhs) noexcept
Compare two uvectors for inequality.
Definition: uvector.h:1162
struct Node * first
Definition: malloc.h:330
Definition: uvector.h:18
StatsData< AccumType > copy(const StatsData< AccumType > &stats)
LatticeExprNode max(const LatticeExprNode &left, const LatticeExprNode &right)
LatticeExprNode min(const LatticeExprNode &left, const LatticeExprNode &right)
PtrHolder< T > & operator=(const PtrHolder< T > &other)
LatticeExprNode value(const LatticeExprNode &expr)
This function returns the value of the expression without a mask.
Define real & complex conjugation for non-complex types and put comparisons into std namespace.
Definition: Complex.h:352