SeqAn3  3.2.0
The Modern C++ library for sequence analysis.
small_vector.hpp
Go to the documentation of this file.
1 // -----------------------------------------------------------------------------------------------------
2 // Copyright (c) 2006-2022, Knut Reinert & Freie Universität Berlin
3 // Copyright (c) 2016-2022, Knut Reinert & MPI für molekulare Genetik
4 // This file may be used, modified and/or redistributed under the terms of the 3-clause BSD-License
5 // shipped with this file and also available at: https://github.com/seqan/seqan3/blob/master/LICENSE.md
6 // -----------------------------------------------------------------------------------------------------
7 
13 #pragma once
14 
15 #include <array>
16 #include <type_traits>
17 
18 #if SEQAN3_WITH_CEREAL
19 # include <cereal/types/array.hpp>
20 #endif // SEQAN3_WITH_CEREAL
21 
26 
27 namespace seqan3
28 {
29 
45 template <typename value_type_, size_t capacity_>
47 {
48 private:
50  static constexpr bool is_noexcept = std::is_nothrow_copy_constructible_v<value_type_>;
51 
52 public:
60  using value_type = value_type_;
61 
66  using reference = value_type &;
67 
72  using const_reference = value_type const &;
73 
78  using iterator = value_type *;
79 
84  using const_iterator = value_type const *;
85 
90  using difference_type = ptrdiff_t;
91 
97 
99 
103  constexpr small_vector() noexcept = default;
104  constexpr small_vector(small_vector const &) noexcept = default;
105  constexpr small_vector(small_vector &&) noexcept = default;
106  constexpr small_vector & operator=(small_vector const &) noexcept = default;
107  constexpr small_vector & operator=(small_vector &&) noexcept = default;
108  ~small_vector() noexcept = default;
109 
123  explicit constexpr small_vector(std::array<value_type, capacity_> const & array) noexcept(is_noexcept) :
124  data_{array},
125  sz{capacity_}
126  {}
127 
129  template <size_t capacity2>
130  explicit constexpr small_vector(std::array<value_type, capacity2> const & array) noexcept(is_noexcept) :
131  sz{capacity2}
132  {
133  static_assert(capacity2 <= capacity_, "You can only initialize from array that has smaller or equal capacity.");
134  std::ranges::copy(array, data_.begin());
135  }
137 
151  template <size_t capacity2>
152  explicit constexpr small_vector(value_type const (&array)[capacity2]) noexcept(is_noexcept) : sz{capacity2}
153  {
154  static_assert(capacity2 <= capacity_, "You can only initialize from array that has smaller or equal capacity.");
155  std::ranges::copy(array, data_.begin());
156  }
157 
171  template <typename... other_value_type>
172  requires (std::same_as<value_type, other_value_type> && ...)
173  constexpr small_vector(other_value_type... args) noexcept(is_noexcept) :
174  data_{args...},
175  sz{sizeof...(other_value_type)}
176  {
177  static_assert(sizeof...(other_value_type) <= capacity_, "Value list must not exceed the capacity.");
178  }
179 
197  template <std::forward_iterator begin_it_type, typename end_it_type>
198  requires std::sentinel_for<end_it_type, begin_it_type>
199  && std::constructible_from<value_type, std::iter_reference_t<begin_it_type>>
200  constexpr small_vector(begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept) : small_vector{}
201  {
202  assign(begin_it, end_it);
203  }
204 
220  template <std::ranges::input_range other_range_t>
221  requires (!std::is_same_v<std::remove_cvref_t<other_range_t>, small_vector>)
222  && std::constructible_from<value_type, std::ranges::range_reference_t<other_range_t>>
223  explicit constexpr small_vector(other_range_t && range) noexcept(is_noexcept) :
224  small_vector{std::ranges::begin(range), std::ranges::end(range)}
225  {}
226 
241  constexpr small_vector(size_type n, value_type value) noexcept(is_noexcept) : small_vector{}
242  {
243  assign(n, value);
244  }
245 
259  constexpr small_vector & operator=(std::initializer_list<value_type> ilist) noexcept(is_noexcept)
260  {
261  assign(std::ranges::begin(ilist), std::ranges::end(ilist));
262  return *this;
263  }
264 
278  constexpr void assign(std::initializer_list<value_type> ilist) noexcept(is_noexcept)
279  {
280  assign(std::ranges::begin(ilist), std::ranges::end(ilist));
281  }
282 
297  constexpr void assign(size_type const count, value_type const value) noexcept(is_noexcept)
298  {
299  clear();
300  auto tmp = views::repeat_n(value, count);
301  assign(std::ranges::begin(tmp), std::ranges::end(tmp));
302  }
303 
319  template <std::ranges::input_range other_range_t>
320  requires std::constructible_from<value_type, std::ranges::range_reference_t<other_range_t>>
321  constexpr void assign(other_range_t && range) noexcept(is_noexcept)
322  {
323  assign(std::ranges::begin(range), std::ranges::end(range));
324  }
325 
343  template <std::forward_iterator begin_it_type, typename end_it_type>
344  requires std::sentinel_for<end_it_type, begin_it_type>
345  && std::constructible_from<value_type, std::iter_reference_t<begin_it_type>>
346  constexpr void assign(begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept)
347  {
348  clear();
349  insert(cbegin(), begin_it, end_it);
350  }
352 
360  constexpr iterator begin() noexcept
361  {
362  return data_.data();
363  }
364 
366  constexpr const_iterator begin() const noexcept
367  {
368  return data_.data();
369  }
370 
372  constexpr const_iterator cbegin() const noexcept
373  {
374  return data_.data();
375  }
376 
381  constexpr iterator end() noexcept
382  {
383  return data_.data() + sz;
384  }
385 
387  constexpr const_iterator end() const noexcept
388  {
389  return data_.data() + sz;
390  }
391 
393  constexpr const_iterator cend() const noexcept
394  {
395  return data_.data() + sz;
396  }
398 
419  reference at(size_type const i)
420  {
421  if (i >= size()) // [[unlikely]]
422  {
423  throw std::out_of_range{"Trying to access element behind the last in small_vector."};
424  }
425  return (*this)[i];
426  }
427 
429  const_reference at(size_type const i) const
430  {
431  if (i >= size()) // [[unlikely]]
432  {
433  throw std::out_of_range{"Trying to access element behind the last in small_vector."};
434  }
435  return (*this)[i];
436  }
437 
455  constexpr reference operator[](size_type const i) noexcept
456  {
457  assert(i < size());
458  return data_[i];
459  }
460 
462  constexpr const_reference operator[](size_type const i) const noexcept
463  {
464  assert(i < size());
465  return data_[i];
466  }
467 
483  constexpr reference front() noexcept
484  {
485  assert(size() > 0);
486  return (*this)[0];
487  }
488 
490  constexpr const_reference front() const noexcept
491  {
492  assert(size() > 0);
493  return (*this)[0];
494  }
495 
511  constexpr reference back() noexcept
512  {
513  assert(size() > 0);
514  return (*this)[size() - 1];
515  }
516 
518  constexpr const_reference back() const noexcept
519  {
520  assert(size() > 0);
521  return (*this)[size() - 1];
522  }
523 
528  constexpr value_type * data() noexcept
529  {
530  return data_.data();
531  }
532 
534  constexpr value_type const * data() const noexcept
535  {
536  return data_.data();
537  }
539 
556  constexpr bool empty() const noexcept
557  {
558  return size() == 0;
559  }
560 
574  constexpr size_type size() const noexcept
575  {
576  return sz;
577  }
578 
595  constexpr size_type max_size() const noexcept
596  {
597  return capacity_;
598  }
599 
613  constexpr size_type capacity() const noexcept
614  {
615  return capacity_;
616  }
617 
622  constexpr void reserve(size_type) const noexcept
623  {
624  // no-op
625  }
626 
631  constexpr void shrink_to_fit() const noexcept
632  {
633  // no-op
634  }
636 
652  constexpr void clear() noexcept
653  {
654  sz = 0;
655  }
656 
674  constexpr iterator insert(const_iterator pos, value_type const value) noexcept(is_noexcept)
675  {
676  return insert(pos, 1, value);
677  }
678 
697  constexpr iterator insert(const_iterator pos, size_type const count, value_type const value) noexcept(is_noexcept)
698  {
699  auto tmp = views::repeat_n(value, count);
700  return insert(pos, std::ranges::begin(tmp), std::ranges::end(tmp));
701  }
702 
725  template <std::forward_iterator begin_it_type, typename end_it_type>
726  requires std::sentinel_for<end_it_type, begin_it_type>
727  && std::constructible_from<value_type, std::iter_reference_t<begin_it_type>>
728  constexpr iterator insert(const_iterator pos, begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept)
729  {
730  auto const pos_as_num = std::ranges::distance(cbegin(), pos);
731  auto const length = std::ranges::distance(begin_it, end_it);
732 
733  assert(pos_as_num + length <= capacity());
734 
735  if (length == 0)
736  return begin(); // nothing to insert
737 
738  for (size_type i = sz + length - 1; i > pos_as_num + length - 1; --i)
739  data_[i] = data_[i - length];
740 
741 #if SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY
742 # pragma GCC diagnostic push
743 # pragma GCC diagnostic ignored "-Wstringop-overflow"
744 #endif // SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY
745  std::ranges::copy(begin_it, end_it, &data_[pos_as_num]);
746 #if SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY
747 # pragma GCC diagnostic pop
748 #endif // SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY
749  sz += length;
750  return begin() + pos_as_num;
751  }
752 
770  constexpr iterator insert(const_iterator pos, std::initializer_list<value_type> const & ilist) noexcept(is_noexcept)
771  {
772  return insert(pos, ilist.begin(), ilist.end());
773  }
774 
795  constexpr iterator erase(const_iterator begin_it, const_iterator end_it) noexcept
796  {
797  if (begin_it >= end_it) // [[unlikely]]
798  return begin() + std::ranges::distance(cbegin(), end_it);
799 
800  size_type const length = std::ranges::distance(begin_it, end_it);
801  auto out_it = begin() + std::ranges::distance(cbegin(), begin_it);
802 
803  while (end_it != cend())
804  *(out_it++) = *(end_it++);
805 
806  sz -= length;
807  return begin() + std::ranges::distance(cbegin(), begin_it);
808  }
809 
830  constexpr iterator erase(const_iterator pos) noexcept
831  {
832  return erase(pos, pos + 1);
833  }
834 
850  constexpr void push_back(value_type const value) noexcept
851  {
852  assert(sz < capacity_);
853  data_[sz] = value;
854  ++sz;
855  }
856 
873  constexpr void pop_back() noexcept
874  {
875  assert(sz > 0);
876  --sz;
877  }
878 
894  constexpr void resize(size_type const count) noexcept
895  {
896  assert(count <= capacity_);
897  sz = count;
898  }
899 
904  constexpr void resize(size_type const count, value_type const value) noexcept
905  {
906  assert(count <= capacity_);
907  for (size_t i = sz; i < count; ++i)
908  data_[i] = value;
909  sz = count;
910  }
911 
925  constexpr void swap(small_vector & rhs) noexcept(is_noexcept)
926  {
927  auto tmp = *this;
928 
929  data_ = rhs.data_;
930  sz = rhs.sz;
931 
932  rhs.data_ = tmp.data_;
933  rhs.sz = tmp.sz;
934  }
935 
937  constexpr void swap(small_vector && rhs) noexcept(is_noexcept)
938  {
939  data_ = rhs.data_;
940  sz = rhs.sz;
941  }
943 
958  friend constexpr void swap(small_vector & lhs, small_vector & rhs) noexcept(is_noexcept)
959  {
960  lhs.swap(rhs);
961  }
962 
964  friend constexpr void swap(small_vector && lhs, small_vector && rhs) noexcept(is_noexcept)
965  {
966  lhs.swap(rhs);
967  }
968 
976  template <size_t cap2>
977  friend constexpr bool operator==(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
978  {
979  return std::ranges::equal(lhs, rhs);
980  }
981 
986  template <size_t cap2>
987  friend constexpr bool operator!=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
988  {
989  return !(lhs == rhs);
990  }
991 
996  template <size_t cap2>
997  friend constexpr bool operator<(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
998  {
999  for (size_t i = 0; i < std::min(lhs.size(), rhs.size()); ++i)
1000  if (lhs[i] > rhs[i])
1001  return false;
1002  else if (lhs[i] < rhs[i])
1003  return true;
1004  return lhs.size() < rhs.size();
1005  }
1006 
1011  template <size_t cap2>
1012  friend constexpr bool operator>(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
1013  {
1014  for (size_t i = 0; i < std::min(lhs.size(), rhs.size()); ++i)
1015  if (lhs[i] < rhs[i])
1016  return false;
1017  else if (lhs[i] > rhs[i])
1018  return true;
1019  return lhs.size() > rhs.size();
1020  }
1021 
1026  template <size_t cap2>
1027  friend constexpr bool operator<=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
1028  {
1029  return !(lhs > rhs);
1030  }
1031 
1036  template <size_t cap2>
1037  friend constexpr bool operator>=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
1038  {
1039  return !(lhs < rhs);
1040  }
1042 
1043 public:
1045 
1049  size_type sz{0};
1050 
1052 
1058  template <cereal_archive archive_t>
1059  void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
1060  {
1061  archive(data_);
1062  archive(sz);
1063  }
1065 };
1066 
1075 template <size_t capacity2, typename value_type>
1076 small_vector(value_type const (&array)[capacity2]) -> small_vector<value_type, capacity2>;
1078 
1079 } // namespace seqan3
T begin(T... args)
Adaptions of concepts from the Cereal library.
A constexpr vector implementation with dynamic size at compile time.
Definition: small_vector.hpp:47
constexpr void swap(small_vector &rhs) noexcept(is_noexcept)
Swap contents with another instance.
Definition: small_vector.hpp:924
constexpr reference operator[](size_type const i) noexcept
Return the i-th element.
Definition: small_vector.hpp:454
constexpr bool empty() const noexcept
Checks whether the container is empty.
Definition: small_vector.hpp:555
constexpr friend bool operator>(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition: small_vector.hpp:1011
constexpr reference front() noexcept
Return the first element. Calling front on an empty container is undefined.
Definition: small_vector.hpp:482
constexpr friend bool operator==(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition: small_vector.hpp:976
constexpr friend bool operator<(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition: small_vector.hpp:996
constexpr small_vector & operator=(small_vector const &) noexcept=default
Defaulted.
constexpr void shrink_to_fit() const noexcept
Since the capacity is fixed on compile time, this is a no-op.
Definition: small_vector.hpp:630
constexpr const_iterator cbegin() const noexcept
Returns the begin to the string.
Definition: small_vector.hpp:371
constexpr void resize(size_type const count) noexcept
Resizes the container to contain count elements.
Definition: small_vector.hpp:893
constexpr size_type capacity() const noexcept
Returns the number of elements that the container is able to hold and resolves to capacity_.
Definition: small_vector.hpp:612
constexpr small_vector() noexcept=default
Defaulted.
constexpr void push_back(value_type const value) noexcept
Appends the given element value to the end of the container.
Definition: small_vector.hpp:849
constexpr void pop_back() noexcept
Removes the last element of the container.
Definition: small_vector.hpp:872
constexpr void assign(std::initializer_list< value_type > ilist) noexcept(is_noexcept)
Assign from std::initializer_list.
Definition: small_vector.hpp:277
value_type * iterator
The iterator type.
Definition: small_vector.hpp:78
value_type const * const_iterator
The const_iterator type.
Definition: small_vector.hpp:84
constexpr iterator erase(const_iterator begin_it, const_iterator end_it) noexcept
Removes specified elements from the container.
Definition: small_vector.hpp:794
constexpr iterator insert(const_iterator pos, value_type const value) noexcept(is_noexcept)
Inserts value before position in the container.
Definition: small_vector.hpp:673
requires(std::same_as< value_type, other_value_type > &&...) const expr small_vector(other_value_type... args) noexcept(is_noexcept)
Construct from a list of values of value_type.
Definition: small_vector.hpp:172
value_type_ value_type
The value_type type.
Definition: small_vector.hpp:60
detail::min_viable_uint_t< capacity_ > size_type
The size_type type.
Definition: small_vector.hpp:96
value_type const & const_reference
The const_reference type.
Definition: small_vector.hpp:72
requires std::sentinel_for< end_it_type, begin_it_type > &&constexpr std::constructible_from< value_type, std::iter_reference_t< begin_it_type > > small_vector(begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept)
Construct from two iterators.
Definition: small_vector.hpp:200
constexpr size_type size() const noexcept
Returns the number of elements in the container, i.e. std::distance(begin(), end()).
Definition: small_vector.hpp:573
constexpr const_iterator cend() const noexcept
Returns iterator past the end of the vector.
Definition: small_vector.hpp:392
requires(!std::is_same_v< std::remove_cvref_t< other_range_t >, small_vector >) &&std
Construct from a different range.
Definition: small_vector.hpp:221
constexpr reference back() noexcept
Return the last element.
Definition: small_vector.hpp:510
constexpr friend bool operator<=(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition: small_vector.hpp:1026
constexpr iterator begin() noexcept
Returns the begin to the string.
Definition: small_vector.hpp:359
constexpr small_vector(value_type const (&array)[capacity2]) noexcept(is_noexcept)
Construct from a (smaller or equally sized) built in array over the same value type.
Definition: small_vector.hpp:152
constexpr void clear() noexcept
Removes all elements from the container.
Definition: small_vector.hpp:651
ptrdiff_t difference_type
The difference_type type.
Definition: small_vector.hpp:90
constexpr iterator end() noexcept
Returns iterator past the end of the vector.
Definition: small_vector.hpp:380
value_type & reference
The reference type.
Definition: small_vector.hpp:66
constexpr friend bool operator!=(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition: small_vector.hpp:986
reference at(size_type const i)
Return the i-th element.
Definition: small_vector.hpp:418
constexpr value_type * data() noexcept
Direct access to the underlying array.
Definition: small_vector.hpp:527
constexpr void reserve(size_type) const noexcept
Since the capacity is fixed on compile time, this is a no-op.
Definition: small_vector.hpp:621
constexpr size_type max_size() const noexcept
Returns the maximum number of elements the container is able to hold and resolves to capacity_.
Definition: small_vector.hpp:594
constexpr friend bool operator>=(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition: small_vector.hpp:1036
T data(T... args)
constexpr ptrdiff_t count
Count the occurrences of a type in a pack.
Definition: type_pack/traits.hpp:164
constexpr auto repeat_n
A view factory that repeats a given value n times.
Definition: repeat_n.hpp:91
Provides metaprogramming utilities for integer types.
T is_same_v
T min(T... args)
The main SeqAn3 namespace.
Definition: aligned_sequence_concept.hpp:29
small_vector(value_type const (&array)[capacity2]) -> small_vector< value_type, capacity2 >
Deducts the size and value type from an built-in array on construction.
SeqAn specific customisations in the standard namespace.
Provides seqan3::views::repeat_n.
Provides type traits for working with templates.