FTL: Refine container semantics
Allow constructing StaticVector and SmallVector by moving smaller
convertible vectors, which so far incurred a copy. Allow the same
copy/move conversion for SmallMap.
Consistently with StaticVector, do not require assignable elements for
the SmallVector to be assignable, which notably enables SmallMap to be
assignable despite its const keys.
Allow comparison of convertible containers.
Bug: 185536303
Test: ftl_test
Change-Id: I35923e794ef26178dc3072f514dea7ad5600bc15
diff --git a/include/ftl/details/array_traits.h b/include/ftl/details/array_traits.h
index 16e63ec..5234c38 100644
--- a/include/ftl/details/array_traits.h
+++ b/include/ftl/details/array_traits.h
@@ -42,7 +42,7 @@
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
template <typename... Args>
- static pointer construct_at(const_iterator it, Args&&... args) {
+ static constexpr pointer construct_at(const_iterator it, Args&&... args) {
void* const ptr = const_cast<void*>(static_cast<const void*>(it));
if constexpr (std::is_constructible_v<value_type, Args...>) {
// TODO: Replace with std::construct_at in C++20.
@@ -52,6 +52,42 @@
return new (ptr) value_type{std::forward<Args>(args)...};
}
}
+
+ // TODO: Make constexpr in C++20.
+ template <typename... Args>
+ static reference replace_at(const_iterator it, Args&&... args) {
+ value_type element{std::forward<Args>(args)...};
+ return replace_at(it, std::move(element));
+ }
+
+ // TODO: Make constexpr in C++20.
+ static reference replace_at(const_iterator it, value_type&& value) {
+ std::destroy_at(it);
+ // This is only safe because exceptions are disabled.
+ return *construct_at(it, std::move(value));
+ }
+
+ // TODO: Make constexpr in C++20.
+ static void in_place_swap(reference a, reference b) {
+ value_type c{std::move(a)};
+ replace_at(&a, std::move(b));
+ replace_at(&b, std::move(c));
+ }
+
+ // TODO: Make constexpr in C++20.
+ static void in_place_swap_ranges(iterator first1, iterator last1, iterator first2) {
+ while (first1 != last1) {
+ in_place_swap(*first1++, *first2++);
+ }
+ }
+
+ // TODO: Replace with std::uninitialized_copy in C++20.
+ template <typename Iterator>
+ static void uninitialized_copy(Iterator first, Iterator last, const_iterator out) {
+ while (first != last) {
+ construct_at(out++, *first++);
+ }
+ }
};
// CRTP mixin to define iterator functions in terms of non-const Self::begin and Self::end.
@@ -101,33 +137,33 @@
// TODO: Replace with operator<=> in C++20.
template <template <typename, std::size_t> class Array>
struct ArrayComparators {
- template <typename T, std::size_t N, std::size_t M>
- friend bool operator==(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ template <typename T, typename U, std::size_t N, std::size_t M>
+ friend bool operator==(const Array<T, N>& lhs, const Array<U, M>& rhs) {
return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
}
- template <typename T, std::size_t N, std::size_t M>
- friend bool operator<(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ template <typename T, typename U, std::size_t N, std::size_t M>
+ friend bool operator<(const Array<T, N>& lhs, const Array<U, M>& rhs) {
return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}
- template <typename T, std::size_t N, std::size_t M>
- friend bool operator>(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ template <typename T, typename U, std::size_t N, std::size_t M>
+ friend bool operator>(const Array<T, N>& lhs, const Array<U, M>& rhs) {
return rhs < lhs;
}
- template <typename T, std::size_t N, std::size_t M>
- friend bool operator!=(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ template <typename T, typename U, std::size_t N, std::size_t M>
+ friend bool operator!=(const Array<T, N>& lhs, const Array<U, M>& rhs) {
return !(lhs == rhs);
}
- template <typename T, std::size_t N, std::size_t M>
- friend bool operator>=(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ template <typename T, typename U, std::size_t N, std::size_t M>
+ friend bool operator>=(const Array<T, N>& lhs, const Array<U, M>& rhs) {
return !(lhs < rhs);
}
- template <typename T, std::size_t N, std::size_t M>
- friend bool operator<=(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ template <typename T, typename U, std::size_t N, std::size_t M>
+ friend bool operator<=(const Array<T, N>& lhs, const Array<U, M>& rhs) {
return !(lhs > rhs);
}
};
diff --git a/include/ftl/small_map.h b/include/ftl/small_map.h
index 2effaa4..5217e76 100644
--- a/include/ftl/small_map.h
+++ b/include/ftl/small_map.h
@@ -65,6 +65,9 @@
class SmallMap final {
using Map = SmallVector<std::pair<const K, V>, N>;
+ template <typename, typename, std::size_t, typename>
+ friend class SmallMap;
+
public:
using key_type = K;
using mapped_type = V;
@@ -100,6 +103,10 @@
deduplicate();
}
+ // Copies or moves key-value pairs from a convertible map.
+ template <typename Q, typename W, std::size_t M, typename E>
+ SmallMap(SmallMap<Q, W, M, E> other) : map_(std::move(other.map_)) {}
+
size_type max_size() const { return map_.max_size(); }
size_type size() const { return map_.size(); }
bool empty() const { return map_.empty(); }
diff --git a/include/ftl/small_vector.h b/include/ftl/small_vector.h
index 03587e3..339726e 100644
--- a/include/ftl/small_vector.h
+++ b/include/ftl/small_vector.h
@@ -37,6 +37,9 @@
// augmented by an unstable_erase operation that does not preserve order, and a replace operation
// that destructively emplaces.
//
+// Unlike std::vector, T does not require copy/move assignment, so may be an object with const data
+// members, or be const itself.
+//
// SmallVector<T, 0> is a specialization that thinly wraps std::vector.
//
// Example usage:
@@ -105,10 +108,9 @@
SmallVector(Arg&& arg, Args&&... args)
: vector_(std::in_place_type<Static>, std::forward<Arg>(arg), std::forward<Args>(args)...) {}
- // Copies at most N elements from a smaller convertible vector.
- template <typename U, std::size_t M, typename = std::enable_if_t<M <= N>>
- SmallVector(const SmallVector<U, M>& other)
- : SmallVector(kIteratorRange, other.begin(), other.end()) {}
+ // Copies or moves elements from a smaller convertible vector.
+ template <typename U, std::size_t M, typename = std::enable_if_t<(M > 0)>>
+ SmallVector(SmallVector<U, M> other) : vector_(convert(std::move(other))) {}
void swap(SmallVector& other) { vector_.swap(other.vector_); }
@@ -235,7 +237,30 @@
}
}
+ // Extracts the elements as std::vector.
+ std::vector<T> promote() && {
+ if (dynamic()) {
+ return std::get<Dynamic>(std::move(vector_)).promote();
+ } else {
+ return {std::make_move_iterator(begin()), std::make_move_iterator(end())};
+ }
+ }
+
private:
+ template <typename, std::size_t>
+ friend class SmallVector;
+
+ template <typename U, std::size_t M>
+ static std::variant<Static, Dynamic> convert(SmallVector<U, M>&& other) {
+ using Other = SmallVector<U, M>;
+
+ if (other.dynamic()) {
+ return std::get<typename Other::Dynamic>(std::move(other.vector_));
+ } else {
+ return std::get<typename Other::Static>(std::move(other.vector_));
+ }
+ }
+
template <auto InsertStatic, auto InsertDynamic, typename... Args>
auto insert(Args&&... args) {
if (Dynamic* const vector = std::get_if<Dynamic>(&vector_)) {
@@ -267,9 +292,10 @@
// Partial specialization without static storage.
template <typename T>
class SmallVector<T, 0> final : details::ArrayTraits<T>,
+ details::ArrayComparators<SmallVector>,
details::ArrayIterators<SmallVector<T, 0>, T>,
std::vector<T> {
- using details::ArrayTraits<T>::construct_at;
+ using details::ArrayTraits<T>::replace_at;
using Iter = details::ArrayIterators<SmallVector, T>;
using Impl = std::vector<T>;
@@ -291,8 +317,30 @@
FTL_ARRAY_TRAIT(T, const_iterator);
FTL_ARRAY_TRAIT(T, const_reverse_iterator);
+ // See std::vector for underlying constructors.
using Impl::Impl;
+ // Copies and moves a vector, respectively.
+ SmallVector(const SmallVector&) = default;
+ SmallVector(SmallVector&&) = default;
+
+ // Constructs elements in place. See StaticVector for underlying constructor.
+ template <typename U, std::size_t... Sizes, typename... Types>
+ SmallVector(InitializerList<U, std::index_sequence<Sizes...>, Types...>&& list)
+ : SmallVector(SmallVector<T, sizeof...(Sizes)>(std::move(list))) {}
+
+ // Copies or moves elements from a convertible vector.
+ template <typename U, std::size_t M>
+ SmallVector(SmallVector<U, M> other) : Impl(convert(std::move(other))) {}
+
+ SmallVector& operator=(SmallVector other) {
+ // Define copy/move assignment in terms of copy/move construction.
+ swap(other);
+ return *this;
+ }
+
+ void swap(SmallVector& other) { Impl::swap(other); }
+
using Impl::empty;
using Impl::max_size;
using Impl::size;
@@ -324,10 +372,7 @@
template <typename... Args>
reference replace(const_iterator it, Args&&... args) {
- value_type element{std::forward<Args>(args)...};
- std::destroy_at(it);
- // This is only safe because exceptions are disabled.
- return *construct_at(it, std::move(element));
+ return replace_at(it, std::forward<Args>(args)...);
}
template <typename... Args>
@@ -353,7 +398,26 @@
pop_back();
}
- void swap(SmallVector& other) { Impl::swap(other); }
+ std::vector<T> promote() && { return std::move(*this); }
+
+ private:
+ template <typename U, std::size_t M>
+ static Impl convert(SmallVector<U, M>&& other) {
+ if constexpr (std::is_constructible_v<Impl, std::vector<U>&&>) {
+ return std::move(other).promote();
+ } else {
+ SmallVector vector(other.size());
+
+ // Consistently with StaticVector, T only requires copy/move construction from U, rather than
+ // copy/move assignment.
+ auto it = vector.begin();
+ for (auto& element : other) {
+ vector.replace(it++, std::move(element));
+ }
+
+ return vector;
+ }
+ }
};
template <typename>
diff --git a/include/ftl/static_vector.h b/include/ftl/static_vector.h
index 70f1721..eb83b85 100644
--- a/include/ftl/static_vector.h
+++ b/include/ftl/static_vector.h
@@ -39,6 +39,9 @@
// adheres to standard containers, except the unstable_erase operation that does not preserve order,
// and the replace operation that destructively emplaces.
//
+// Unlike std::vector, T does not require copy/move assignment, so may be an object with const data
+// members, or be const itself.
+//
// StaticVector<T, 1> is analogous to an iterable std::optional.
// StaticVector<T, 0> is an error.
//
@@ -78,7 +81,14 @@
details::ArrayComparators<StaticVector> {
static_assert(N > 0);
+ // For constructor that moves from a smaller convertible vector.
+ template <typename, std::size_t>
+ friend class StaticVector;
+
using details::ArrayTraits<T>::construct_at;
+ using details::ArrayTraits<T>::replace_at;
+ using details::ArrayTraits<T>::in_place_swap_ranges;
+ using details::ArrayTraits<T>::uninitialized_copy;
using Iter = details::ArrayIterators<StaticVector, T>;
friend Iter;
@@ -117,14 +127,18 @@
StaticVector(StaticVector&& other) { swap<true>(other); }
// Copies at most N elements from a smaller convertible vector.
- template <typename U, std::size_t M, typename = std::enable_if_t<M <= N>>
+ template <typename U, std::size_t M>
StaticVector(const StaticVector<U, M>& other)
- : StaticVector(kIteratorRange, other.begin(), other.end()) {}
+ : StaticVector(kIteratorRange, other.begin(), other.end()) {
+ static_assert(N >= M, "Insufficient capacity");
+ }
- // Copies at most N elements from an array.
+ // Copies at most N elements from a smaller convertible array.
template <typename U, std::size_t M>
explicit StaticVector(U (&array)[M])
- : StaticVector(kIteratorRange, std::begin(array), std::end(array)) {}
+ : StaticVector(kIteratorRange, std::begin(array), std::end(array)) {
+ static_assert(N >= M, "Insufficient capacity");
+ }
// Copies at most N elements from the range [first, last).
//
@@ -139,7 +153,18 @@
template <typename Iterator>
StaticVector(IteratorRangeTag, Iterator first, Iterator last)
: size_(std::min(max_size(), static_cast<size_type>(std::distance(first, last)))) {
- std::uninitialized_copy(first, first + size_, begin());
+ uninitialized_copy(first, first + size_, begin());
+ }
+
+ // Moves at most N elements from a smaller convertible vector.
+ template <typename U, std::size_t M>
+ StaticVector(StaticVector<U, M>&& other) {
+ static_assert(N >= M, "Insufficient capacity");
+
+ // Same logic as swap<true>, though M need not be equal to N.
+ std::uninitialized_move(other.begin(), other.end(), begin());
+ std::destroy(other.begin(), other.end());
+ std::swap(size_, other.size_);
}
// Constructs at most N elements. The template arguments T and N are inferred using the
@@ -240,10 +265,7 @@
//
template <typename... Args>
reference replace(const_iterator it, Args&&... args) {
- value_type element{std::forward<Args>(args)...};
- std::destroy_at(it);
- // This is only safe because exceptions are disabled.
- return *construct_at(it, std::move(element));
+ return replace_at(it, std::forward<Args>(args)...);
}
// Appends an element, and returns an iterator to it. If the vector is full, the element is not
@@ -382,7 +404,7 @@
}
// Swap elements [0, min).
- std::swap_ranges(begin(), begin() + min, other.begin());
+ in_place_swap_ranges(begin(), begin() + min, other.begin());
// No elements to move if sizes are equal.
if (min == max) return;