Loading...
Searching...
No Matches
small_vector.hpp
Go to the documentation of this file.
// SPDX-FileCopyrightText: 2006-2025 Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2025 Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: BSD-3-Clause
#pragma once
#include <array>
#include <type_traits>
#if SEQAN3_HAS_CEREAL
# include <cereal/types/array.hpp>
#endif // SEQAN3_HAS_CEREAL
#include <seqan3/core/concept/cereal.hpp>
#include <seqan3/core/detail/template_inspection.hpp>
#include <seqan3/utility/detail/integer_traits.hpp>
#include <seqan3/utility/views/repeat_n.hpp>
namespace seqan3
{
template <typename value_type_, size_t capacity_>
class small_vector
{
private:
static constexpr bool is_noexcept = std::is_nothrow_copy_constructible_v<value_type_>;
public:
using value_type = value_type_;
using reference = value_type &;
using const_reference = value_type const &;
using iterator = value_type *;
using const_iterator = value_type const *;
using difference_type = ptrdiff_t;
using size_type = detail::min_viable_uint_t<capacity_>;
constexpr small_vector() noexcept = default;
constexpr small_vector(small_vector const &) noexcept = default;
constexpr small_vector(small_vector &&) noexcept = default;
constexpr small_vector & operator=(small_vector const &) noexcept = default;
constexpr small_vector & operator=(small_vector &&) noexcept = default;
~small_vector() noexcept = default;
explicit constexpr small_vector(std::array<value_type, capacity_> const & array) noexcept(is_noexcept) :
data_{array},
sz{capacity_}
{}
template <size_t capacity2>
explicit constexpr small_vector(std::array<value_type, capacity2> const & array) noexcept(is_noexcept) :
sz{capacity2}
{
static_assert(capacity2 <= capacity_, "You can only initialize from array that has smaller or equal capacity.");
std::ranges::copy(array, data_.begin());
}
template <size_t capacity2>
explicit constexpr small_vector(value_type const (&array)[capacity2]) noexcept(is_noexcept) : sz{capacity2}
{
static_assert(capacity2 <= capacity_, "You can only initialize from array that has smaller or equal capacity.");
std::ranges::copy(array, data_.begin());
}
template <typename... other_value_type>
requires (std::same_as<value_type, other_value_type> && ...)
constexpr small_vector(other_value_type... args) noexcept(is_noexcept) :
data_{args...},
sz{sizeof...(other_value_type)}
{
static_assert(sizeof...(other_value_type) <= capacity_, "Value list must not exceed the capacity.");
}
template <std::forward_iterator begin_it_type, typename end_it_type>
requires std::sentinel_for<end_it_type, begin_it_type>
&& std::constructible_from<value_type, std::iter_reference_t<begin_it_type>>
constexpr small_vector(begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept) : small_vector{}
{
assign(begin_it, end_it);
}
template <std::ranges::input_range other_range_t>
requires (!std::is_same_v<std::remove_cvref_t<other_range_t>, small_vector>)
&& std::constructible_from<value_type, std::ranges::range_reference_t<other_range_t>>
explicit constexpr small_vector(other_range_t && range) noexcept(is_noexcept) :
small_vector{std::ranges::begin(range), std::ranges::end(range)}
{}
constexpr small_vector(size_type n, value_type value) noexcept(is_noexcept) : small_vector{}
{
assign(n, value);
}
constexpr small_vector & operator=(std::initializer_list<value_type> ilist) noexcept(is_noexcept)
{
assign(std::ranges::begin(ilist), std::ranges::end(ilist));
return *this;
}
constexpr void assign(std::initializer_list<value_type> ilist) noexcept(is_noexcept)
{
assign(std::ranges::begin(ilist), std::ranges::end(ilist));
}
constexpr void assign(size_type const count, value_type const value) noexcept(is_noexcept)
{
clear();
auto tmp = views::repeat_n(value, count);
assign(std::ranges::begin(tmp), std::ranges::end(tmp));
}
template <std::ranges::input_range other_range_t>
requires std::constructible_from<value_type, std::ranges::range_reference_t<other_range_t>>
constexpr void assign(other_range_t && range) noexcept(is_noexcept)
{
assign(std::ranges::begin(range), std::ranges::end(range));
}
template <std::forward_iterator begin_it_type, typename end_it_type>
requires std::sentinel_for<end_it_type, begin_it_type>
&& std::constructible_from<value_type, std::iter_reference_t<begin_it_type>>
constexpr void assign(begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept)
{
clear();
insert(cbegin(), begin_it, end_it);
}
constexpr iterator begin() noexcept
{
return data_.data();
}
constexpr const_iterator begin() const noexcept
{
return data_.data();
}
constexpr const_iterator cbegin() const noexcept
{
return data_.data();
}
constexpr iterator end() noexcept
{
return data_.data() + sz;
}
constexpr const_iterator end() const noexcept
{
return data_.data() + sz;
}
constexpr const_iterator cend() const noexcept
{
return data_.data() + sz;
}
reference at(size_type const i)
{
if (i >= size()) // [[unlikely]]
{
throw std::out_of_range{"Trying to access element behind the last in small_vector."};
}
return (*this)[i];
}
const_reference at(size_type const i) const
{
if (i >= size()) // [[unlikely]]
{
throw std::out_of_range{"Trying to access element behind the last in small_vector."};
}
return (*this)[i];
}
constexpr reference operator[](size_type const i) noexcept
{
assert(i < size());
return data_[i];
}
constexpr const_reference operator[](size_type const i) const noexcept
{
assert(i < size());
return data_[i];
}
constexpr reference front() noexcept
{
assert(size() > 0);
return (*this)[0];
}
constexpr const_reference front() const noexcept
{
assert(size() > 0);
return (*this)[0];
}
constexpr reference back() noexcept
{
assert(size() > 0);
return (*this)[size() - 1];
}
constexpr const_reference back() const noexcept
{
assert(size() > 0);
return (*this)[size() - 1];
}
constexpr value_type * data() noexcept
{
return data_.data();
}
constexpr value_type const * data() const noexcept
{
return data_.data();
}
constexpr bool empty() const noexcept
{
return size() == 0;
}
constexpr size_type size() const noexcept
{
return sz;
}
constexpr size_type max_size() const noexcept
{
return capacity_;
}
constexpr size_type capacity() const noexcept
{
return capacity_;
}
constexpr void reserve(size_type) const noexcept
{
// no-op
}
constexpr void shrink_to_fit() const noexcept
{
// no-op
}
constexpr void clear() noexcept
{
sz = 0;
}
constexpr iterator insert(const_iterator pos, value_type const value) noexcept(is_noexcept)
{
return insert(pos, 1, value);
}
constexpr iterator insert(const_iterator pos, size_type const count, value_type const value) noexcept(is_noexcept)
{
auto tmp = views::repeat_n(value, count);
return insert(pos, std::ranges::begin(tmp), std::ranges::end(tmp));
}
template <std::forward_iterator begin_it_type, typename end_it_type>
requires std::sentinel_for<end_it_type, begin_it_type>
&& std::constructible_from<value_type, std::iter_reference_t<begin_it_type>>
constexpr iterator insert(const_iterator pos, begin_it_type begin_it, end_it_type end_it) noexcept(is_noexcept)
{
auto const pos_as_num = std::ranges::distance(cbegin(), pos);
auto const length = std::ranges::distance(begin_it, end_it);
assert(pos_as_num + length <= capacity());
if (length == 0)
return begin(); // nothing to insert
for (size_type i = sz + length - 1; i > pos_as_num + length - 1; --i)
data_[i] = data_[i - length];
SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY_START(-Wstringop-overflow)
std::ranges::copy(begin_it, end_it, &data_[pos_as_num]);
SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY_STOP
sz += length;
return begin() + pos_as_num;
}
constexpr iterator insert(const_iterator pos, std::initializer_list<value_type> const & ilist) noexcept(is_noexcept)
{
return insert(pos, ilist.begin(), ilist.end());
}
constexpr iterator erase(const_iterator begin_it, const_iterator end_it) noexcept
{
if (begin_it >= end_it) // [[unlikely]]
return begin() + std::ranges::distance(cbegin(), end_it);
size_type const length = std::ranges::distance(begin_it, end_it);
auto out_it = begin() + std::ranges::distance(cbegin(), begin_it);
while (end_it != cend())
*(out_it++) = *(end_it++);
sz -= length;
return begin() + std::ranges::distance(cbegin(), begin_it);
}
constexpr iterator erase(const_iterator pos) noexcept
{
return erase(pos, pos + 1);
}
constexpr void push_back(value_type const value) noexcept
{
assert(sz < capacity_);
data_[sz] = value;
++sz;
}
constexpr void pop_back() noexcept
{
assert(sz > 0);
--sz;
}
constexpr void resize(size_type const count) noexcept
{
assert(count <= capacity_);
sz = count;
}
constexpr void resize(size_type const count, value_type const value) noexcept
{
assert(count <= capacity_);
for (size_t i = sz; i < count; ++i)
data_[i] = value;
sz = count;
}
constexpr void swap(small_vector & rhs) noexcept(is_noexcept)
{
auto tmp = *this;
data_ = rhs.data_;
sz = rhs.sz;
rhs.data_ = tmp.data_;
rhs.sz = tmp.sz;
}
constexpr void swap(small_vector && rhs) noexcept(is_noexcept)
{
data_ = rhs.data_;
sz = rhs.sz;
}
friend constexpr void swap(small_vector & lhs, small_vector & rhs) noexcept(is_noexcept)
{
lhs.swap(rhs);
}
friend constexpr void swap(small_vector && lhs, small_vector && rhs) noexcept(is_noexcept)
{
lhs.swap(rhs);
}
template <size_t cap2>
friend constexpr bool operator==(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
{
return std::ranges::equal(lhs, rhs);
}
template <size_t cap2>
friend constexpr bool operator!=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
{
return !(lhs == rhs);
}
template <size_t cap2>
friend constexpr bool operator<(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
{
for (size_t i = 0; i < std::min(lhs.size(), rhs.size()); ++i)
if (lhs[i] > rhs[i])
return false;
else if (lhs[i] < rhs[i])
return true;
return lhs.size() < rhs.size();
}
template <size_t cap2>
friend constexpr bool operator>(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
{
for (size_t i = 0; i < std::min(lhs.size(), rhs.size()); ++i)
if (lhs[i] < rhs[i])
return false;
else if (lhs[i] > rhs[i])
return true;
return lhs.size() > rhs.size();
}
template <size_t cap2>
friend constexpr bool operator<=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
{
return !(lhs > rhs);
}
template <size_t cap2>
friend constexpr bool operator>=(small_vector const & lhs, small_vector<value_type, cap2> const & rhs) noexcept
{
return !(lhs < rhs);
}
public:
std::array<value_type, capacity_> data_{};
size_type sz{0};
template <cereal_archive archive_t>
void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
{
archive(data_);
archive(sz);
}
};
template <size_t capacity2, typename value_type>
small_vector(value_type const (&array)[capacity2]) -> small_vector<value_type, capacity2>;
} // namespace seqan3
array
cereal.hpp
Adaptions of concepts from the Cereal library.
seqan3::small_vector
A constexpr vector implementation with dynamic size at compile time.
Definition small_vector.hpp:44
seqan3::small_vector::swap
constexpr void swap(small_vector &rhs) noexcept(is_noexcept)
Swap contents with another instance.
Definition small_vector.hpp:917
seqan3::small_vector::small_vector
constexpr small_vector(other_value_type... args) noexcept(is_noexcept)
Construct from a list of values of value_type.
Definition small_vector.hpp:170
seqan3::small_vector::operator[]
constexpr reference operator[](size_type const i) noexcept
Return the i-th element.
Definition small_vector.hpp:452
seqan3::small_vector::empty
constexpr bool empty() const noexcept
Checks whether the container is empty.
Definition small_vector.hpp:553
seqan3::small_vector::swap
friend constexpr void swap(small_vector &lhs, small_vector &rhs) noexcept(is_noexcept)
Swap contents with another instance.
Definition small_vector.hpp:950
seqan3::small_vector::front
constexpr reference front() noexcept
Return the first element. Calling front on an empty container is undefined.
Definition small_vector.hpp:480
seqan3::small_vector::shrink_to_fit
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
seqan3::small_vector::cbegin
constexpr const_iterator cbegin() const noexcept
Returns the begin to the string.
Definition small_vector.hpp:369
seqan3::small_vector::insert
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
seqan3::small_vector::resize
constexpr void resize(size_type const count) noexcept
Resizes the container to contain count elements.
Definition small_vector.hpp:886
seqan3::small_vector::capacity
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
seqan3::small_vector::small_vector
constexpr small_vector() noexcept=default
Defaulted.
seqan3::small_vector::assign
constexpr void assign(size_type const count, value_type const value) noexcept(is_noexcept)
Assign with count times value.
Definition small_vector.hpp:294
seqan3::small_vector::swap
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
seqan3::small_vector::operator[]
constexpr const_reference operator[](size_type const i) const noexcept
Return the i-th element.
Definition small_vector.hpp:459
seqan3::small_vector::push_back
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
seqan3::small_vector::pop_back
constexpr void pop_back() noexcept
Removes the last element of the container.
Definition small_vector.hpp:865
seqan3::small_vector::assign
constexpr void assign(std::initializer_list< value_type > ilist) noexcept(is_noexcept)
Assign from std::initializer_list.
Definition small_vector.hpp:275
seqan3::small_vector< char, capacity_+1 >::iterator
value_type * iterator
Definition small_vector.hpp:75
seqan3::small_vector::operator=
constexpr small_vector & operator=(std::initializer_list< value_type > ilist) noexcept(is_noexcept)
Assign from std::initializer_list.
Definition small_vector.hpp:256
seqan3::small_vector::small_vector
constexpr small_vector(size_type n, value_type value) noexcept(is_noexcept)
Construct with n times value.
Definition small_vector.hpp:238
seqan3::small_vector::swap
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
seqan3::small_vector::operator>
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
seqan3::small_vector::erase
constexpr iterator erase(const_iterator pos) noexcept
Removes specified elements from the container.
Definition small_vector.hpp:822
seqan3::small_vector< char, capacity_+1 >::const_iterator
value_type const * const_iterator
Definition small_vector.hpp:81
seqan3::small_vector::small_vector
constexpr small_vector(other_range_t &&range) noexcept(is_noexcept)
Construct from a different range.
Definition small_vector.hpp:220
seqan3::small_vector::erase
constexpr iterator erase(const_iterator begin_it, const_iterator end_it) noexcept
Removes specified elements from the container.
Definition small_vector.hpp:787
seqan3::small_vector::insert
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
seqan3::small_vector::resize
constexpr void resize(size_type const count, value_type const value) noexcept
Resizes the container to contain count elements.
Definition small_vector.hpp:896
seqan3::small_vector< char, capacity_+1 >::value_type
char value_type
Definition small_vector.hpp:57
seqan3::small_vector::begin
constexpr const_iterator begin() const noexcept
Returns the begin to the string.
Definition small_vector.hpp:363
seqan3::small_vector< char, capacity_+1 >::size_type
detail::min_viable_uint_t< capacity_ > size_type
Definition small_vector.hpp:93
seqan3::small_vector< char, capacity_+1 >::const_reference
value_type const & const_reference
Definition small_vector.hpp:69
seqan3::small_vector::operator==
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
seqan3::small_vector::size
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
seqan3::small_vector::cend
constexpr const_iterator cend() const noexcept
Returns iterator past the end of the vector.
Definition small_vector.hpp:390
seqan3::small_vector::back
constexpr reference back() noexcept
Return the last element.
Definition small_vector.hpp:508
seqan3::small_vector::data
constexpr value_type const * data() const noexcept
Direct access to the underlying array.
Definition small_vector.hpp:531
seqan3::small_vector::assign
constexpr void assign(other_range_t &&range) noexcept(is_noexcept)
Assign from a different range.
Definition small_vector.hpp:318
seqan3::small_vector::at
const_reference at(size_type const i) const
Return the i-th element.
Definition small_vector.hpp:426
seqan3::small_vector< char, capacity_+1 >::begin
constexpr iterator begin() noexcept
Definition small_vector.hpp:357
seqan3::small_vector::small_vector
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
seqan3::small_vector::clear
constexpr void clear() noexcept
Removes all elements from the container.
Definition small_vector.hpp:649
seqan3::small_vector< char, capacity_+1 >::difference_type
ptrdiff_t difference_type
Definition small_vector.hpp:87
seqan3::small_vector::small_vector
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
seqan3::small_vector< char, capacity_+1 >::end
constexpr iterator end() noexcept
Definition small_vector.hpp:378
seqan3::small_vector::data
constexpr value_type * data() noexcept
Direct access to the underlying array.
Definition small_vector.hpp:525
seqan3::small_vector::operator!=
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
seqan3::small_vector< char, capacity_+1 >::reference
value_type & reference
Definition small_vector.hpp:63
seqan3::small_vector::operator<
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
seqan3::small_vector::operator<=
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
seqan3::small_vector::operator>=
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
seqan3::small_vector::insert
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
seqan3::small_vector::front
constexpr const_reference front() const noexcept
Return the first element. Calling front on an empty container is undefined.
Definition small_vector.hpp:487
seqan3::small_vector::assign
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
seqan3::small_vector::at
reference at(size_type const i)
Return the i-th element.
Definition small_vector.hpp:416
seqan3::small_vector::reserve
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
seqan3::small_vector::back
constexpr const_reference back() const noexcept
Return the last element.
Definition small_vector.hpp:515
seqan3::small_vector::max_size
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
seqan3::small_vector::end
constexpr const_iterator end() const noexcept
Returns iterator past the end of the vector.
Definition small_vector.hpp:384
seqan3::small_vector::insert
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
seqan3::views::repeat_n
constexpr auto repeat_n
A view factory that repeats a given value n times.
Definition repeat_n.hpp:88
std::initializer_list
integer_traits.hpp
Provides metaprogramming utilities for integer types.
std::is_nothrow_copy_constructible_v
T is_nothrow_copy_constructible_v
std::is_same_v
T is_same_v
std::min
T min(T... args)
seqan3
The main SeqAn3 namespace.
Definition aligned_sequence_concept.hpp:26
seqan3::small_vector
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.
std
SeqAn specific customisations in the standard namespace.
std::out_of_range
SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY_START
#define SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY_START(...)
Denotes the start of a block where diagnostics are ignored.
Definition platform.hpp:268
SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY_STOP
#define SEQAN3_WORKAROUND_GCC_BOGUS_MEMCPY_STOP
Denotes the end of a block where diagnostics are ignored.
Definition platform.hpp:277
repeat_n.hpp
Provides seqan3::views::repeat_n.
template_inspection.hpp
Provides type traits for working with templates.
type_traits
Hide me