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/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>