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
739 std::ranges::copy(begin_it, end_it, &data_[pos_as_num]);
741 sz += length;
742 return begin() + pos_as_num;
743 }
744
762 constexpr iterator insert(const_iterator pos, std::initializer_list<value_type> const & ilist) noexcept(is_noexcept)
763 {
764 return insert(pos, ilist.begin(), ilist.end());
765 }
766
787 constexpr iterator erase(const_iterator begin_it, const_iterator end_it) noexcept
788 {
789 if (begin_it >= end_it) // [[unlikely]]
790 return begin() + std::ranges::distance(cbegin(), end_it);
791
792 size_type const length = std::ranges::distance(begin_it, end_it);
793 auto out_it = begin() + std::ranges::distance(cbegin(), begin_it);
794
795 while (end_it != cend())
796 *(out_it++) = *(end_it++);
797
798 sz -= length;
799 return begin() + std::ranges::distance(cbegin(), begin_it);
800 }
801
822 constexpr iterator erase(const_iterator pos) noexcept
823 {
824 return erase(pos, pos + 1);
825 }
826
842 constexpr void push_back(value_type const value) noexcept
843 {
844 assert(sz < capacity_);
845 data_[sz] = value;
846 ++sz;
847 }
848
865 constexpr void pop_back() noexcept
866 {
867 assert(sz > 0);
868 --sz;
869 }
870
886 constexpr void resize(size_type const count) noexcept
887 {
888 assert(count <= capacity_);
889 sz = count;
890 }
891
896 constexpr void resize(size_type const count, value_type const value) noexcept
897 {
898 assert(count <= capacity_);
899 for (size_t i = sz; i < count; ++i)
900 data_[i] = value;
901 sz = count;
902 }
903
917 constexpr void swap(small_vector & rhs) noexcept(is_noexcept)
918 {
919 auto tmp = *this;
920
921 data_ = rhs.data_;
922 sz = rhs.sz;
923
924 rhs.data_ = tmp.data_;
925 rhs.sz = tmp.sz;
926 }
927
929 constexpr void swap(small_vector && rhs) noexcept(is_noexcept)
930 {
931 data_ = rhs.data_;
932 sz = rhs.sz;
933 }
935
950 friend constexpr void swap(small_vector & lhs, small_vector & rhs) noexcept(is_noexcept)
951 {
952 lhs.swap(rhs);
953 }
954
956 friend constexpr void swap(small_vector && lhs, small_vector && rhs) noexcept(is_noexcept)
957 {
958 lhs.swap(rhs);
959 }
960
968 template <size_t cap2>
969 friend constexpr bool operator==(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
970 {
971 return std::ranges::equal(lhs, rhs);
972 }
973
978 template <size_t cap2>
979 friend constexpr bool operator!=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
980 {
981 return !(lhs == rhs);
982 }
983
988 template <size_t cap2>
989 friend constexpr bool operator<(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
990 {
991 for (size_t i = 0; i < std::min(lhs.size(), rhs.size()); ++i)
992 if (lhs[i] > rhs[i])
993 return false;
994 else if (lhs[i] < rhs[i])
995 return true;
996 return lhs.size() < rhs.size();
997 }
998
1003 template <size_t cap2>
1004 friend constexpr bool operator>(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
1005 {
1006 for (size_t i = 0; i < std::min(lhs.size(), rhs.size()); ++i)
1007 if (lhs[i] < rhs[i])
1008 return false;
1009 else if (lhs[i] > rhs[i])
1010 return true;
1011 return lhs.size() > rhs.size();
1012 }
1013
1018 template <size_t cap2>
1019 friend constexpr bool operator<=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
1020 {
1021 return !(lhs > rhs);
1022 }
1023
1028 template <size_t cap2>
1029 friend constexpr bool operator>=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
1030 {
1031 return !(lhs < rhs);
1032 }
1034
1035public:
1037
1041 size_type sz{0};
1042
1044
1050 template <cereal_archive archive_t>
1051 void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
1052 {
1053 archive(data_);
1054 archive(sz);
1055 }
1057};
1058
1067template <size_t capacity2, typename value_type>
1070
1071} // 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:917
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:950
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:886
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:929
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:842
constexpr void pop_back() noexcept
Removes the last element of the container.
Definition small_vector.hpp:865
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:956
friend constexpr bool operator>(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition small_vector.hpp:1004
constexpr iterator erase(const_iterator pos) noexcept
Removes specified elements from the container.
Definition small_vector.hpp:822
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:787
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:896
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:969
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:979
friend constexpr bool operator<(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition small_vector.hpp:989
friend constexpr bool operator<=(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition small_vector.hpp:1019
friend constexpr bool operator>=(small_vector const &lhs, small_vector< value_type, cap2 > const &rhs) noexcept
Performs element-wise comparison.
Definition small_vector.hpp:1029
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:762
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.
#define SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY_START(...)
Denotes the start of a block where diagnostics are ignored.
Definition platform.hpp:275
#define SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY_STOP
Denotes the end of a block where diagnostics are ignored.
Definition platform.hpp:284
Provides seqan3::views::repeat_n.
Provides type traits for working with templates.
Hide me