SeqAn3 3.4.0-rc.1
The Modern C++ library for sequence analysis.
Loading...
Searching...
No Matches
small_vector.hpp
Go to the documentation of this file.
1// SPDX-FileCopyrightText: 2006-2024 Knut Reinert & Freie Universität Berlin
2// SPDX-FileCopyrightText: 2016-2024 Knut Reinert & MPI für molekulare Genetik
3// SPDX-License-Identifier: BSD-3-Clause
4
10#pragma once
11
12#include <array>
13#include <type_traits>
14
15#if SEQAN3_WITH_CEREAL
16# include <cereal/types/array.hpp>
17#endif // SEQAN3_WITH_CEREAL
18
23
24namespace seqan3
25{
26
42template <typename value_type_, size_t capacity_>
44{
45private:
47 static constexpr bool is_noexcept = std::is_nothrow_copy_constructible_v<value_type_>;
48
49public:
58
64
69 using const_reference = value_type const &;
70
76
81 using const_iterator = value_type const *;
82
87 using difference_type = ptrdiff_t;
88
94
96
106
121 data_{array},
122 sz{capacity_}
123 {}
124
126 template <size_t capacity2>
127 explicit constexpr small_vector(std::array<value_type, capacity2> const & array) noexcept(is_noexcept) :
128 sz{capacity2}
129 {
130 static_assert(capacity2 <= capacity_, "You can only initialize from array that has smaller or equal capacity.");
131 std::ranges::copy(array, data_.begin());
132 }
134
148 template <size_t capacity2>
149 explicit constexpr small_vector(value_type const (&array)[capacity2]) noexcept(is_noexcept) : sz{capacity2}
150 {
151 static_assert(capacity2 <= capacity_, "You can only initialize from array that has smaller or equal capacity.");
152 std::ranges::copy(array, data_.begin());
153 }
154
168 template <typename... other_value_type>
169 requires (std::same_as<value_type, other_value_type> && ...)
170 constexpr small_vector(other_value_type... args) noexcept(is_noexcept) :
171 data_{args...},
173 {
174 static_assert(sizeof...(other_value_type) <= capacity_, "Value list must not exceed the capacity.");
175 }
176
194 template <std::forward_iterator begin_it_type, typename end_it_type>
195 requires std::sentinel_for<end_it_type, begin_it_type>
196 && std::constructible_from<value_type, std::iter_reference_t<begin_it_type>>
197 constexpr small_vector(begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept) : small_vector{}
198 {
199 assign(begin_it, end_it);
200 }
201
217 template <std::ranges::input_range other_range_t>
218 requires (!std::is_same_v<std::remove_cvref_t<other_range_t>, small_vector>)
219 && std::constructible_from<value_type, std::ranges::range_reference_t<other_range_t>>
220 explicit constexpr small_vector(other_range_t && range) noexcept(is_noexcept) :
221 small_vector{std::ranges::begin(range), std::ranges::end(range)}
222 {}
223
238 constexpr small_vector(size_type n, value_type value) noexcept(is_noexcept) : small_vector{}
239 {
240 assign(n, value);
241 }
242
257 {
258 assign(std::ranges::begin(ilist), std::ranges::end(ilist));
259 return *this;
260 }
261
275 constexpr void assign(std::initializer_list<value_type> ilist) noexcept(is_noexcept)
276 {
277 assign(std::ranges::begin(ilist), std::ranges::end(ilist));
278 }
279
294 constexpr void assign(size_type const count, value_type const value) noexcept(is_noexcept)
295 {
296 clear();
297 auto tmp = views::repeat_n(value, count);
298 assign(std::ranges::begin(tmp), std::ranges::end(tmp));
299 }
300
316 template <std::ranges::input_range other_range_t>
317 requires std::constructible_from<value_type, std::ranges::range_reference_t<other_range_t>>
318 constexpr void assign(other_range_t && range) noexcept(is_noexcept)
319 {
320 assign(std::ranges::begin(range), std::ranges::end(range));
321 }
322
340 template <std::forward_iterator begin_it_type, typename end_it_type>
341 requires std::sentinel_for<end_it_type, begin_it_type>
342 && std::constructible_from<value_type, std::iter_reference_t<begin_it_type>>
343 constexpr void assign(begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept)
344 {
345 clear();
346 insert(cbegin(), begin_it, end_it);
347 }
349
358 {
359 return data_.data();
360 }
361
364 {
365 return data_.data();
366 }
367
370 {
371 return data_.data();
372 }
373
379 {
380 return data_.data() + sz;
381 }
382
385 {
386 return data_.data() + sz;
387 }
388
391 {
392 return data_.data() + sz;
393 }
395
417 {
418 if (i >= size()) // [[unlikely]]
419 {
420 throw std::out_of_range{"Trying to access element behind the last in small_vector."};
421 }
422 return (*this)[i];
423 }
424
427 {
428 if (i >= size()) // [[unlikely]]
429 {
430 throw std::out_of_range{"Trying to access element behind the last in small_vector."};
431 }
432 return (*this)[i];
433 }
434
452 constexpr reference operator[](size_type const i) noexcept
453 {
454 assert(i < size());
455 return data_[i];
456 }
457
459 constexpr const_reference operator[](size_type const i) const noexcept
460 {
461 assert(i < size());
462 return data_[i];
463 }
464
481 {
482 assert(size() > 0);
483 return (*this)[0];
484 }
485
488 {
489 assert(size() > 0);
490 return (*this)[0];
491 }
492
509 {
510 assert(size() > 0);
511 return (*this)[size() - 1];
512 }
513
516 {
517 assert(size() > 0);
518 return (*this)[size() - 1];
519 }
520
526 {
527 return data_.data();
528 }
529
531 constexpr value_type const * data() const noexcept
532 {
533 return data_.data();
534 }
536
553 constexpr bool empty() const noexcept
554 {
555 return size() == 0;
556 }
557
572 {
573 return sz;
574 }
575
593 {
594 return capacity_;
595 }
596
611 {
612 return capacity_;
613 }
614
619 constexpr void reserve(size_type) const noexcept
620 {
621 // no-op
622 }
623
628 constexpr void shrink_to_fit() const noexcept
629 {
630 // no-op
631 }
633
649 constexpr void clear() noexcept
650 {
651 sz = 0;
652 }
653
671 constexpr iterator insert(const_iterator pos, value_type const value) noexcept(is_noexcept)
672 {
673 return insert(pos, 1, value);
674 }
675
694 constexpr iterator insert(const_iterator pos, size_type const count, value_type const value) noexcept(is_noexcept)
695 {
696 auto tmp = views::repeat_n(value, count);
697 return insert(pos, std::ranges::begin(tmp), std::ranges::end(tmp));
698 }
699
722 template <std::forward_iterator begin_it_type, typename end_it_type>
723 requires std::sentinel_for<end_it_type, begin_it_type>
724 && std::constructible_from<value_type, std::iter_reference_t<begin_it_type>>
725 constexpr iterator insert(const_iterator pos, begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept)
726 {
727 auto const pos_as_num = std::ranges::distance(cbegin(), pos);
728 auto const length = std::ranges::distance(begin_it, end_it);
729
730 assert(pos_as_num + length <= capacity());
731
732 if (length == 0)
733 return begin(); // nothing to insert
734
735 for (size_type i = sz + length - 1; i > pos_as_num + length - 1; --i)
736 data_[i] = data_[i - length];
737
738#if SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY
739# pragma GCC diagnostic push
740# pragma GCC diagnostic ignored "-Wstringop-overflow"
741#endif // SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY
742 std::ranges::copy(begin_it, end_it, &data_[pos_as_num]);
743#if SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY
744# pragma GCC diagnostic pop
745#endif // SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY
746 sz += length;
747 return begin() + pos_as_num;
748 }
749
767 constexpr iterator insert(const_iterator pos, std::initializer_list<value_type> const & ilist) noexcept(is_noexcept)
768 {
769 return insert(pos, ilist.begin(), ilist.end());
770 }
771
792 constexpr iterator erase(const_iterator begin_it, const_iterator end_it) noexcept
793 {
794 if (begin_it >= end_it) // [[unlikely]]
795 return begin() + std::ranges::distance(cbegin(), end_it);
796
797 size_type const length = std::ranges::distance(begin_it, end_it);
798 auto out_it = begin() + std::ranges::distance(cbegin(), begin_it);
799
800 while (end_it != cend())
801 *(out_it++) = *(end_it++);
802
803 sz -= length;
804 return begin() + std::ranges::distance(cbegin(), begin_it);
805 }
806
827 constexpr iterator erase(const_iterator pos) noexcept
828 {
829 return erase(pos, pos + 1);
830 }
831
847 constexpr void push_back(value_type const value) noexcept
848 {
849 assert(sz < capacity_);
850 data_[sz] = value;
851 ++sz;
852 }
853
870 constexpr void pop_back() noexcept
871 {
872 assert(sz > 0);
873 --sz;
874 }
875
891 constexpr void resize(size_type const count) noexcept
892 {
893 assert(count <= capacity_);
894 sz = count;
895 }
896
901 constexpr void resize(size_type const count, value_type const value) noexcept
902 {
903 assert(count <= capacity_);
904 for (size_t i = sz; i < count; ++i)
905 data_[i] = value;
906 sz = count;
907 }
908
922 constexpr void swap(small_vector & rhs) noexcept(is_noexcept)
923 {
924 auto tmp = *this;
925
926 data_ = rhs.data_;
927 sz = rhs.sz;
928
929 rhs.data_ = tmp.data_;
930 rhs.sz = tmp.sz;
931 }
932
934 constexpr void swap(small_vector && rhs) noexcept(is_noexcept)
935 {
936 data_ = rhs.data_;
937 sz = rhs.sz;
938 }
940
955 friend constexpr void swap(small_vector & lhs, small_vector & rhs) noexcept(is_noexcept)
956 {
957 lhs.swap(rhs);
958 }
959
961 friend constexpr void swap(small_vector && lhs, small_vector && rhs) noexcept(is_noexcept)
962 {
963 lhs.swap(rhs);
964 }
965
973 template <size_t cap2>
974 friend constexpr bool operator==(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
975 {
976 return std::ranges::equal(lhs, rhs);
977 }
978
983 template <size_t cap2>
984 friend constexpr bool operator!=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
985 {
986 return !(lhs == rhs);
987 }
988
993 template <size_t cap2>
994 friend constexpr bool operator<(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
995 {
996 for (size_t i = 0; i < std::min(lhs.size(), rhs.size()); ++i)
997 if (lhs[i] > rhs[i])
998 return false;
999 else if (lhs[i] < rhs[i])
1000 return true;
1001 return lhs.size() < rhs.size();
1002 }
1003
1008 template <size_t cap2>
1009 friend constexpr bool operator>(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
1010 {
1011 for (size_t i = 0; i < std::min(lhs.size(), rhs.size()); ++i)
1012 if (lhs[i] < rhs[i])
1013 return false;
1014 else if (lhs[i] > rhs[i])
1015 return true;
1016 return lhs.size() > rhs.size();
1017 }
1018
1023 template <size_t cap2>
1024 friend constexpr bool operator<=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
1025 {
1026 return !(lhs > rhs);
1027 }
1028
1033 template <size_t cap2>
1034 friend constexpr bool operator>=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
1035 {
1036 return !(lhs < rhs);
1037 }
1039
1040public:
1042
1046 size_type sz{0};
1047
1049
1055 template <cereal_archive archive_t>
1056 void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
1057 {
1058 archive(data_);
1059 archive(sz);
1060 }
1062};
1063
1072template <size_t capacity2, typename value_type>
1075
1076} // namespace seqan3
T begin(T... args)
Adaptions of concepts from the Cereal library.
A "pretty printer" for most SeqAn data structures and related types.
Definition debug_stream_type.hpp:79
A constexpr vector implementation with dynamic size at compile time.
Definition small_vector.hpp:44
constexpr void swap(small_vector &rhs) noexcept(is_noexcept)
Swap contents with another instance.
Definition small_vector.hpp:922
constexpr small_vector(other_value_type... args) noexcept(is_noexcept)
Construct from a list of values of value_type.
Definition small_vector.hpp:170
constexpr reference operator[](size_type const i) noexcept
Return the i-th element.
Definition small_vector.hpp:452
constexpr bool empty() const noexcept
Checks whether the container is empty.
Definition small_vector.hpp:553
friend constexpr void swap(small_vector &lhs, small_vector &rhs) noexcept(is_noexcept)
Swap contents with another instance.
Definition small_vector.hpp:955
constexpr reference front() noexcept
Return the first element. Calling front on an empty container is undefined.
Definition small_vector.hpp:480
constexpr void shrink_to_fit() const noexcept
Since the capacity is fixed on compile time, this is a no-op.
Definition small_vector.hpp:628
constexpr const_iterator cbegin() const noexcept
Returns the begin to the string.
Definition small_vector.hpp:369
constexpr iterator insert(const_iterator pos, size_type const count, value_type const value) noexcept(is_noexcept)
Inserts count copies of value before position in the container.
Definition small_vector.hpp:694
constexpr void resize(size_type const count) noexcept
Resizes the container to contain count elements.
Definition small_vector.hpp:891
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:610
constexpr small_vector() noexcept=default
Defaulted.
constexpr void assign(size_type const count, value_type const value) noexcept(is_noexcept)
Assign with count times value.
Definition small_vector.hpp:294
constexpr void swap(small_vector &&rhs) noexcept(is_noexcept)
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition small_vector.hpp:934
constexpr const_reference operator[](size_type const i) const noexcept
Return the i-th element.
Definition small_vector.hpp:459
constexpr void push_back(value_type const value) noexcept
Appends the given element value to the end of the container.
Definition small_vector.hpp:847
constexpr void pop_back() noexcept
Removes the last element of the container.
Definition small_vector.hpp:870
constexpr void assign(std::initializer_list< value_type > ilist) noexcept(is_noexcept)
Assign from std::initializer_list.
Definition small_vector.hpp:275
constexpr small_vector & operator=(std::initializer_list< value_type > ilist) noexcept(is_noexcept)
Assign from std::initializer_list.
Definition small_vector.hpp:256
constexpr small_vector(size_type n, value_type value) noexcept(is_noexcept)
Construct with n times value.
Definition small_vector.hpp:238
friend constexpr void swap(small_vector &&lhs, small_vector &&rhs) noexcept(is_noexcept)
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition small_vector.hpp:961
friend constexpr bool operator>(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition small_vector.hpp:1009
constexpr iterator erase(const_iterator pos) noexcept
Removes specified elements from the container.
Definition small_vector.hpp:827
constexpr small_vector(other_range_t &&range) noexcept(is_noexcept)
Construct from a different range.
Definition small_vector.hpp:220
constexpr iterator erase(const_iterator begin_it, const_iterator end_it) noexcept
Removes specified elements from the container.
Definition small_vector.hpp:792
constexpr iterator insert(const_iterator pos, value_type const value) noexcept(is_noexcept)
Inserts value before position in the container.
Definition small_vector.hpp:671
constexpr void resize(size_type const count, value_type const value) noexcept
Resizes the container to contain count elements.
Definition small_vector.hpp:901
value_type_ value_type
The value_type type.
Definition small_vector.hpp:57
constexpr const_iterator begin() const noexcept
Returns the begin to the string.
Definition small_vector.hpp:363
detail::min_viable_uint_t< capacity_ > size_type
The size_type type.
Definition small_vector.hpp:93
friend constexpr bool operator==(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition small_vector.hpp:974
constexpr size_type size() const noexcept
Returns the number of elements in the container, i.e. std::distance(begin(), end()).
Definition small_vector.hpp:571
constexpr const_iterator cend() const noexcept
Returns iterator past the end of the vector.
Definition small_vector.hpp:390
constexpr reference back() noexcept
Return the last element.
Definition small_vector.hpp:508
constexpr value_type const * data() const noexcept
Direct access to the underlying array.
Definition small_vector.hpp:531
constexpr void assign(other_range_t &&range) noexcept(is_noexcept)
Assign from a different range.
Definition small_vector.hpp:318
const_reference at(size_type const i) const
Return the i-th element.
Definition small_vector.hpp:426
constexpr iterator begin() noexcept
Returns the begin to the string.
Definition small_vector.hpp:357
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:149
constexpr void clear() noexcept
Removes all elements from the container.
Definition small_vector.hpp:649
ptrdiff_t difference_type
The difference_type type.
Definition small_vector.hpp:87
constexpr small_vector(begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept)
Construct from two iterators.
Definition small_vector.hpp:197
constexpr iterator end() noexcept
Returns iterator past the end of the vector.
Definition small_vector.hpp:378
constexpr value_type * data() noexcept
Direct access to the underlying array.
Definition small_vector.hpp:525
friend constexpr bool operator!=(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition small_vector.hpp:984
friend constexpr bool operator<(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition small_vector.hpp:994
friend constexpr bool operator<=(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition small_vector.hpp:1024
friend constexpr bool operator>=(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition small_vector.hpp:1034
constexpr iterator insert(const_iterator pos, begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept)
Inserts elements from range [begin_it, end_it) before position in the container.
Definition small_vector.hpp:725
constexpr const_reference front() const noexcept
Return the first element. Calling front on an empty container is undefined.
Definition small_vector.hpp:487
constexpr void assign(begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept)
Assign from pair of iterators.
Definition small_vector.hpp:343
reference at(size_type const i)
Return the i-th element.
Definition small_vector.hpp:416
constexpr void reserve(size_type) const noexcept
Since the capacity is fixed on compile time, this is a no-op.
Definition small_vector.hpp:619
constexpr const_reference back() const noexcept
Return the last element.
Definition small_vector.hpp:515
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:592
constexpr const_iterator end() const noexcept
Returns iterator past the end of the vector.
Definition small_vector.hpp:384
constexpr iterator insert(const_iterator pos, std::initializer_list< value_type > const &ilist) noexcept(is_noexcept)
Inserts elements from initializer list before position in the container.
Definition small_vector.hpp:767
T copy(T... args)
T data(T... args)
T equal(T... args)
constexpr auto repeat_n
A view factory that repeats a given value n times.
Definition repeat_n.hpp:88
Provides metaprogramming utilities for integer types.
T min(T... args)
The main SeqAn3 namespace.
Definition aligned_sequence_concept.hpp:26
SeqAn specific customisations in the standard namespace.
Provides seqan3::views::repeat_n.
Provides type traits for working with templates.
Hide me