Export of internal Abseil changes.

--
635146be541d732fbf2e9c93c6bec89035552484 by Gennadiy Rozental <rogeeff@google.com>:

Merge external PR #324

PiperOrigin-RevId: 253849839

--
7a37f87f0f419ab535e59c7dae7961546586671a by Gennadiy Rozental <rogeeff@google.com>:

Merge external PR #323

PiperOrigin-RevId: 253849558

--
75455e93e1f3987c926f35fbe80a0ea84e4ba35b by CJ Johnson <johnsoncj@google.com>:

Removes `ivi` namespace typedef to reduce reader confusion

PiperOrigin-RevId: 253789534

--
2f99d27194468129767c48ab621b952660427493 by CJ Johnson <johnsoncj@google.com>:

New benchmarks the various overloads of InlinedVector::assign(...)/InlinedVector::operator=(...)

PiperOrigin-RevId: 253787316

--
a0949eb100b93aae22b85b4a4820e4bf9a5a2dbb by CJ Johnson <johnsoncj@google.com>:

Updates the definition of `InlinedVector::pop_back(...)` to be cleaner and more direct (hiding the is_allocated branch behind a single call to `data()`)

Adds exception safety test for `InlinedVector::pop_back(...)`

PiperOrigin-RevId: 253607385

--
2dbc728ddf84835dcb6341f9a166f1c9bde103b9 by CJ Johnson <johnsoncj@google.com>:

Adds the remaining constructor exception safety tests for InlinedVector

PiperOrigin-RevId: 253592324

--
40d88e0d6232c93af5e008088f69ad41cb44e4ce by CJ Johnson <johnsoncj@google.com>:

Updates the constructors of InlinedVector to new, exception-safe and more-performant implementations.

PiperOrigin-RevId: 253294508
GitOrigin-RevId: 635146be541d732fbf2e9c93c6bec89035552484
Change-Id: I7d37a749632084f5d7fa56d42392e622a9d0180d

6 files changed, 351 insertions, 83 deletions

diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index 331030ac..998294c0 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -124,6 +124,7 @@ cc_library(
     linkopts = ABSL_DEFAULT_LINKOPTS,
     deps = [
         ":compressed_tuple",
+        "//absl/base:core_headers",
         "//absl/memory",
         "//absl/meta:type_traits",
     ],
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index c75b0a2b..5196e503 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -124,6 +124,7 @@ absl_cc_library(
     ${ABSL_DEFAULT_COPTS}
   DEPS
     absl::compressed_tuple
+    absl::core_headers
     absl::memory
     absl::type_traits
   PUBLIC
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 046182dd..2c96cc37 100644
--- a/absl/container/inlined_vector.h
+++ b/absl/container/inlined_vector.h
@@ -70,7 +70,16 @@ class InlinedVector {
       N > 0, "InlinedVector cannot be instantiated with `0` inlined elements.");
 
   using Storage = inlined_vector_internal::Storage<T, N, A>;
+  using rvalue_reference = typename Storage::rvalue_reference;
+  using MoveIterator = typename Storage::MoveIterator;
   using AllocatorTraits = typename Storage::AllocatorTraits;
+  using IsMemcpyOk = typename Storage::IsMemcpyOk;
+
+  template <typename Iterator>
+  using IteratorValueAdapter =
+      typename Storage::template IteratorValueAdapter<Iterator>;
+  using CopyValueAdapter = typename Storage::CopyValueAdapter;
+  using DefaultValueAdapter = typename Storage::DefaultValueAdapter;
 
   template <typename Iterator>
   using EnableIfAtLeastForwardIterator = absl::enable_if_t<
@@ -80,8 +89,6 @@ class InlinedVector {
   using DisableIfAtLeastForwardIterator = absl::enable_if_t<
       !inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value>;
 
-  using rvalue_reference = typename Storage::rvalue_reference;
-
  public:
   using allocator_type = typename Storage::allocator_type;
   using value_type = typename Storage::value_type;
@@ -111,34 +118,14 @@ class InlinedVector {
   explicit InlinedVector(size_type n,
                          const allocator_type& alloc = allocator_type())
       : storage_(alloc) {
-    if (n > static_cast<size_type>(N)) {
-      pointer new_data = AllocatorTraits::allocate(*storage_.GetAllocPtr(), n);
-      storage_.SetAllocatedData(new_data, n);
-      UninitializedFill(storage_.GetAllocatedData(),
-                        storage_.GetAllocatedData() + n);
-      storage_.SetAllocatedSize(n);
-    } else {
-      UninitializedFill(storage_.GetInlinedData(),
-                        storage_.GetInlinedData() + n);
-      storage_.SetInlinedSize(n);
-    }
+    storage_.Initialize(DefaultValueAdapter(), n);
   }
 
   // Creates an inlined vector with `n` copies of `v`.
   InlinedVector(size_type n, const_reference v,
                 const allocator_type& alloc = allocator_type())
       : storage_(alloc) {
-    if (n > static_cast<size_type>(N)) {
-      pointer new_data = AllocatorTraits::allocate(*storage_.GetAllocPtr(), n);
-      storage_.SetAllocatedData(new_data, n);
-      UninitializedFill(storage_.GetAllocatedData(),
-                        storage_.GetAllocatedData() + n, v);
-      storage_.SetAllocatedSize(n);
-    } else {
-      UninitializedFill(storage_.GetInlinedData(),
-                        storage_.GetInlinedData() + n, v);
-      storage_.SetInlinedSize(n);
-    }
+    storage_.Initialize(CopyValueAdapter(v), n);
   }
 
   // Creates an inlined vector of copies of the values in `list`.
@@ -157,15 +144,8 @@ class InlinedVector {
   InlinedVector(ForwardIterator first, ForwardIterator last,
                 const allocator_type& alloc = allocator_type())
       : storage_(alloc) {
-    auto length = std::distance(first, last);
-    reserve(size() + length);
-    if (storage_.GetIsAllocated()) {
-      UninitializedCopy(first, last, storage_.GetAllocatedData() + size());
-      storage_.SetAllocatedSize(size() + length);
-    } else {
-      UninitializedCopy(first, last, storage_.GetInlinedData() + size());
-      storage_.SetInlinedSize(size() + length);
-    }
+    storage_.Initialize(IteratorValueAdapter<ForwardIterator>(first),
+                        std::distance(first, last));
   }
 
   // Creates an inlined vector with elements constructed from the provided input
@@ -185,14 +165,11 @@ class InlinedVector {
   // Creates a copy of an `other` inlined vector using a specified allocator.
   InlinedVector(const InlinedVector& other, const allocator_type& alloc)
       : storage_(alloc) {
-    reserve(other.size());
-    if (storage_.GetIsAllocated()) {
-      UninitializedCopy(other.begin(), other.end(),
-                        storage_.GetAllocatedData());
-      storage_.SetAllocatedSize(other.size());
+    if (IsMemcpyOk::value && !other.storage_.GetIsAllocated()) {
+      storage_.MemcpyContents(other.storage_);
     } else {
-      UninitializedCopy(other.begin(), other.end(), storage_.GetInlinedData());
-      storage_.SetInlinedSize(other.size());
+      storage_.Initialize(IteratorValueAdapter<const_pointer>(other.data()),
+                          other.size());
     }
   }
 
@@ -215,20 +192,21 @@ class InlinedVector {
       absl::allocator_is_nothrow<allocator_type>::value ||
       std::is_nothrow_move_constructible<value_type>::value)
       : storage_(*other.storage_.GetAllocPtr()) {
-    if (other.storage_.GetIsAllocated()) {
-      // We can just steal the underlying buffer from the source.
-      // That leaves the source empty, so we clear its size.
+    if (IsMemcpyOk::value) {
+      storage_.MemcpyContents(other.storage_);
+      other.storage_.SetInlinedSize(0);
+    } else if (other.storage_.GetIsAllocated()) {
       storage_.SetAllocatedData(other.storage_.GetAllocatedData(),
                                 other.storage_.GetAllocatedCapacity());
-      storage_.SetAllocatedSize(other.size());
+      storage_.SetAllocatedSize(other.storage_.GetSize());
       other.storage_.SetInlinedSize(0);
     } else {
-      UninitializedCopy(
-          std::make_move_iterator(other.storage_.GetInlinedData()),
-          std::make_move_iterator(other.storage_.GetInlinedData() +
-                                  other.size()),
-          storage_.GetInlinedData());
-      storage_.SetInlinedSize(other.size());
+      IteratorValueAdapter<MoveIterator> other_values(
+          MoveIterator(other.storage_.GetInlinedData()));
+      inlined_vector_internal::ConstructElements(
+          storage_.GetAllocPtr(), storage_.GetInlinedData(), &other_values,
+          other.storage_.GetSize());
+      storage_.SetInlinedSize(other.storage_.GetSize());
     }
   }
 
@@ -248,28 +226,19 @@ class InlinedVector {
   InlinedVector(InlinedVector&& other, const allocator_type& alloc) noexcept(
       absl::allocator_is_nothrow<allocator_type>::value)
       : storage_(alloc) {
-    if (other.storage_.GetIsAllocated()) {
-      if (*storage_.GetAllocPtr() == *other.storage_.GetAllocPtr()) {
-        // We can just steal the allocation from the source.
-        storage_.SetAllocatedSize(other.size());
-        storage_.SetAllocatedData(other.storage_.GetAllocatedData(),
-                                  other.storage_.GetAllocatedCapacity());
-        other.storage_.SetInlinedSize(0);
-      } else {
-        // We need to use our own allocator
-        reserve(other.size());
-        UninitializedCopy(std::make_move_iterator(other.begin()),
-                          std::make_move_iterator(other.end()),
-                          storage_.GetAllocatedData());
-        storage_.SetAllocatedSize(other.size());
-      }
+    if (IsMemcpyOk::value) {
+      storage_.MemcpyContents(other.storage_);
+      other.storage_.SetInlinedSize(0);
+    } else if ((*storage_.GetAllocPtr() == *other.storage_.GetAllocPtr()) &&
+               other.storage_.GetIsAllocated()) {
+      storage_.SetAllocatedData(other.storage_.GetAllocatedData(),
+                                other.storage_.GetAllocatedCapacity());
+      storage_.SetAllocatedSize(other.storage_.GetSize());
+      other.storage_.SetInlinedSize(0);
     } else {
-      UninitializedCopy(
-          std::make_move_iterator(other.storage_.GetInlinedData()),
-          std::make_move_iterator(other.storage_.GetInlinedData() +
-                                  other.size()),
-          storage_.GetInlinedData());
-      storage_.SetInlinedSize(other.size());
+      storage_.Initialize(
+          IteratorValueAdapter<MoveIterator>(MoveIterator(other.data())),
+          other.size());
     }
   }
 
@@ -757,15 +726,8 @@ class InlinedVector {
   // by `1` (unless the inlined vector is empty, in which case this is a no-op).
   void pop_back() noexcept {
     assert(!empty());
-    size_type s = size();
-    if (storage_.GetIsAllocated()) {
-      Destroy(storage_.GetAllocatedData() + s - 1,
-              storage_.GetAllocatedData() + s);
-      storage_.SetAllocatedSize(s - 1);
-    } else {
-      Destroy(storage_.GetInlinedData() + s - 1, storage_.GetInlinedData() + s);
-      storage_.SetInlinedSize(s - 1);
-    }
+    AllocatorTraits::destroy(*storage_.GetAllocPtr(), data() + (size() - 1));
+    storage_.AddSize(-1);
   }
 
   // `InlinedVector::erase()`
diff --git a/absl/container/inlined_vector_benchmark.cc b/absl/container/inlined_vector_benchmark.cc
index a8368d41..df4d3ce5 100644
--- a/absl/container/inlined_vector_benchmark.cc
+++ b/absl/container/inlined_vector_benchmark.cc
@@ -383,6 +383,12 @@ constexpr size_t kBatchSize = 100;
   BENCHMARK_TEMPLATE(BM_FunctionTemplate, T, kLargeSize);        \
   BENCHMARK_TEMPLATE(BM_FunctionTemplate, T, kSmallSize)
 
+#define ABSL_INTERNAL_BENCHMARK_TWO_SIZE(BM_FunctionTemplate, T)      \
+  BENCHMARK_TEMPLATE(BM_FunctionTemplate, T, kLargeSize, kLargeSize); \
+  BENCHMARK_TEMPLATE(BM_FunctionTemplate, T, kLargeSize, kSmallSize); \
+  BENCHMARK_TEMPLATE(BM_FunctionTemplate, T, kSmallSize, kLargeSize); \
+  BENCHMARK_TEMPLATE(BM_FunctionTemplate, T, kSmallSize, kSmallSize)
+
 template <typename T>
 using InlVec = absl::InlinedVector<T, kInlinedCapacity>;
 
@@ -525,6 +531,74 @@ void BM_ConstructFromMove(benchmark::State& state) {
 ABSL_INTERNAL_BENCHMARK_ONE_SIZE(BM_ConstructFromMove, TrivialType);
 ABSL_INTERNAL_BENCHMARK_ONE_SIZE(BM_ConstructFromMove, NontrivialType);
 
+template <typename T, size_t FromSize, size_t ToSize>
+void BM_AssignSizeRef(benchmark::State& state) {
+  auto size = ToSize;
+  auto ref = T();
+  BatchedBenchmark<T>(
+      state,
+      /* prepare_vec = */ [](InlVec<T>* vec, size_t) { vec->resize(FromSize); },
+      /* test_vec = */
+      [&](InlVec<T>* vec, size_t) {
+        benchmark::DoNotOptimize(size);
+        benchmark::DoNotOptimize(ref);
+        vec->assign(size, ref);
+      });
+}
+ABSL_INTERNAL_BENCHMARK_TWO_SIZE(BM_AssignSizeRef, TrivialType);
+ABSL_INTERNAL_BENCHMARK_TWO_SIZE(BM_AssignSizeRef, NontrivialType);
+
+template <typename T, size_t FromSize, size_t ToSize>
+void BM_AssignRange(benchmark::State& state) {
+  std::array<T, ToSize> arr{};
+  BatchedBenchmark<T>(
+      state,
+      /* prepare_vec = */ [](InlVec<T>* vec, size_t) { vec->resize(FromSize); },
+      /* test_vec = */
+      [&](InlVec<T>* vec, size_t) {
+        benchmark::DoNotOptimize(arr);
+        vec->assign(arr.begin(), arr.end());
+      });
+}
+ABSL_INTERNAL_BENCHMARK_TWO_SIZE(BM_AssignRange, TrivialType);
+ABSL_INTERNAL_BENCHMARK_TWO_SIZE(BM_AssignRange, NontrivialType);
+
+template <typename T, size_t FromSize, size_t ToSize>
+void BM_AssignFromCopy(benchmark::State& state) {
+  InlVec<T> other_vec(ToSize);
+  BatchedBenchmark<T>(
+      state,
+      /* prepare_vec = */ [](InlVec<T>* vec, size_t) { vec->resize(FromSize); },
+      /* test_vec = */
+      [&](InlVec<T>* vec, size_t) {
+        benchmark::DoNotOptimize(other_vec);
+        *vec = other_vec;
+      });
+}
+ABSL_INTERNAL_BENCHMARK_TWO_SIZE(BM_AssignFromCopy, TrivialType);
+ABSL_INTERNAL_BENCHMARK_TWO_SIZE(BM_AssignFromCopy, NontrivialType);
+
+template <typename T, size_t FromSize, size_t ToSize>
+void BM_AssignFromMove(benchmark::State& state) {
+  using VecT = InlVec<T>;
+  std::array<VecT, kBatchSize> vector_batch{};
+  BatchedBenchmark<T>(
+      state,
+      /* prepare_vec = */
+      [&](InlVec<T>* vec, size_t i) {
+        vector_batch[i].clear();
+        vector_batch[i].resize(ToSize);
+        vec->resize(FromSize);
+      },
+      /* test_vec = */
+      [&](InlVec<T>* vec, size_t i) {
+        benchmark::DoNotOptimize(vector_batch[i]);
+        *vec = std::move(vector_batch[i]);
+      });
+}
+ABSL_INTERNAL_BENCHMARK_TWO_SIZE(BM_AssignFromMove, TrivialType);
+ABSL_INTERNAL_BENCHMARK_TWO_SIZE(BM_AssignFromMove, NontrivialType);
+
 template <typename T, size_t FromSize>
 void BM_Clear(benchmark::State& state) {
   BatchedBenchmark<T>(
diff --git a/absl/container/inlined_vector_exception_safety_test.cc b/absl/container/inlined_vector_exception_safety_test.cc
index 1aae0b04..0a964925 100644
--- a/absl/container/inlined_vector_exception_safety_test.cc
+++ b/absl/container/inlined_vector_exception_safety_test.cc
@@ -36,6 +36,26 @@ using ThrowAllocThrowerVec =
 using ThrowAllocMovableThrowerVec =
     absl::InlinedVector<MovableThrower, kInlinedCapacity, ThrowAlloc>;
 
+// In GCC, if an element of a `std::initializer_list` throws during construction
+// the elements that were constructed before it are not destroyed. This causes
+// incorrect exception safety test failures. Thus, `testing::nothrow_ctor` is
+// required. See: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66139
+#define ABSL_INTERNAL_MAKE_INIT_LIST(T, N)                     \
+  (N > kInlinedCapacity                                        \
+       ? std::initializer_list<T>{T(0, testing::nothrow_ctor), \
+                                  T(1, testing::nothrow_ctor), \
+                                  T(2, testing::nothrow_ctor), \
+                                  T(3, testing::nothrow_ctor), \
+                                  T(4, testing::nothrow_ctor), \
+                                  T(5, testing::nothrow_ctor), \
+                                  T(6, testing::nothrow_ctor), \
+                                  T(7, testing::nothrow_ctor)} \
+                                                               \
+       : std::initializer_list<T>{T(0, testing::nothrow_ctor), \
+                                  T(1, testing::nothrow_ctor)})
+static_assert((kLargeSize == 8 || kSmallSize == 2),
+              "Must update ABSL_INTERNAL_MAKE_INIT_LIST(...).");
+
 template <typename TheVecT, size_t... TheSizes>
 class TestParams {
  public:
@@ -88,6 +108,90 @@ TYPED_TEST(NoSizeTest, DefaultConstructor) {
   testing::TestThrowingCtor<VecT>(allocator_type{});
 }
 
+TYPED_TEST(OneSizeTest, SizeConstructor) {
+  using VecT = typename TypeParam::VecT;
+  using allocator_type = typename VecT::allocator_type;
+  constexpr static auto size = TypeParam::GetSizeAt(0);
+
+  testing::TestThrowingCtor<VecT>(size);
+
+  testing::TestThrowingCtor<VecT>(size, allocator_type{});
+}
+
+TYPED_TEST(OneSizeTest, SizeRefConstructor) {
+  using VecT = typename TypeParam::VecT;
+  using value_type = typename VecT::value_type;
+  using allocator_type = typename VecT::allocator_type;
+  constexpr static auto size = TypeParam::GetSizeAt(0);
+
+  testing::TestThrowingCtor<VecT>(size, value_type{});
+
+  testing::TestThrowingCtor<VecT>(size, value_type{}, allocator_type{});
+}
+
+TYPED_TEST(OneSizeTest, InitializerListConstructor) {
+  using VecT = typename TypeParam::VecT;
+  using value_type = typename VecT::value_type;
+  using allocator_type = typename VecT::allocator_type;
+  constexpr static auto size = TypeParam::GetSizeAt(0);
+
+  testing::TestThrowingCtor<VecT>(
+      ABSL_INTERNAL_MAKE_INIT_LIST(value_type, size));
+
+  testing::TestThrowingCtor<VecT>(
+      ABSL_INTERNAL_MAKE_INIT_LIST(value_type, size), allocator_type{});
+}
+
+TYPED_TEST(OneSizeTest, RangeConstructor) {
+  using VecT = typename TypeParam::VecT;
+  using value_type = typename VecT::value_type;
+  using allocator_type = typename VecT::allocator_type;
+  constexpr static auto size = TypeParam::GetSizeAt(0);
+
+  std::array<value_type, size> arr{};
+
+  testing::TestThrowingCtor<VecT>(arr.begin(), arr.end());
+
+  testing::TestThrowingCtor<VecT>(arr.begin(), arr.end(), allocator_type{});
+}
+
+TYPED_TEST(OneSizeTest, CopyConstructor) {
+  using VecT = typename TypeParam::VecT;
+  using allocator_type = typename VecT::allocator_type;
+  constexpr static auto size = TypeParam::GetSizeAt(0);
+
+  VecT other_vec{size};
+
+  testing::TestThrowingCtor<VecT>(other_vec);
+
+  testing::TestThrowingCtor<VecT>(other_vec, allocator_type{});
+}
+
+TYPED_TEST(OneSizeTest, MoveConstructor) {
+  using VecT = typename TypeParam::VecT;
+  using allocator_type = typename VecT::allocator_type;
+  constexpr static auto size = TypeParam::GetSizeAt(0);
+
+  if (!absl::allocator_is_nothrow<allocator_type>::value) {
+    testing::TestThrowingCtor<VecT>(VecT{size});
+
+    testing::TestThrowingCtor<VecT>(VecT{size}, allocator_type{});
+  }
+}
+
+TYPED_TEST(OneSizeTest, PopBack) {
+  using VecT = typename TypeParam::VecT;
+  constexpr static auto size = TypeParam::GetSizeAt(0);
+
+  auto tester = testing::MakeExceptionSafetyTester()
+                    .WithInitialValue(VecT(size))
+                    .WithContracts(NoThrowGuarantee<VecT>);
+
+  EXPECT_TRUE(tester.Test([](VecT* vec) {
+    vec->pop_back();  //
+  }));
+}
+
 TYPED_TEST(OneSizeTest, Clear) {
   using VecT = typename TypeParam::VecT;
   constexpr static auto size = TypeParam::GetSizeAt(0);
diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h
index f4eb92ec..92c21ab9 100644
--- a/absl/container/internal/inlined_vector.h
+++ b/absl/container/internal/inlined_vector.h
@@ -21,6 +21,7 @@
 #include <memory>
 #include <utility>
 
+#include "absl/base/macros.h"
 #include "absl/container/internal/compressed_tuple.h"
 #include "absl/memory/memory.h"
 #include "absl/meta/type_traits.h"
@@ -33,6 +34,14 @@ using IsAtLeastForwardIterator = std::is_convertible<
     typename std::iterator_traits<Iterator>::iterator_category,
     std::forward_iterator_tag>;
 
+template <typename AllocatorType>
+using IsMemcpyOk = absl::conjunction<
+    std::is_same<std::allocator<typename AllocatorType::value_type>,
+                 AllocatorType>,
+    absl::is_trivially_copy_constructible<typename AllocatorType::value_type>,
+    absl::is_trivially_copy_assignable<typename AllocatorType::value_type>,
+    absl::is_trivially_destructible<typename AllocatorType::value_type>>;
+
 template <typename AllocatorType, typename ValueType, typename SizeType>
 void DestroyElements(AllocatorType* alloc_ptr, ValueType* destroy_first,
                      SizeType destroy_size) {
@@ -52,6 +61,23 @@ void DestroyElements(AllocatorType* alloc_ptr, ValueType* destroy_first,
 #endif  // NDEBUG
 }
 
+template <typename AllocatorType, typename ValueType, typename ValueAdapter,
+          typename SizeType>
+void ConstructElements(AllocatorType* alloc_ptr, ValueType* construct_first,
+                       ValueAdapter* values_ptr, SizeType construct_size) {
+  // If any construction fails, all completed constructions are rolled back.
+  for (SizeType i = 0; i < construct_size; ++i) {
+    ABSL_INTERNAL_TRY {
+      values_ptr->ConstructNext(alloc_ptr, construct_first + i);
+    }
+    ABSL_INTERNAL_CATCH_ANY {
+      inlined_vector_internal::DestroyElements(alloc_ptr, construct_first, i);
+
+      ABSL_INTERNAL_RETHROW;
+    }
+  }
+}
+
 template <typename AllocatorType>
 struct StorageView {
   using pointer = typename AllocatorType::pointer;
@@ -62,6 +88,55 @@ struct StorageView {
   size_type capacity;
 };
 
+template <typename AllocatorType, typename Iterator>
+class IteratorValueAdapter {
+  using pointer = typename AllocatorType::pointer;
+  using AllocatorTraits = absl::allocator_traits<AllocatorType>;
+
+ public:
+  explicit IteratorValueAdapter(const Iterator& it) : it_(it) {}
+
+  void ConstructNext(AllocatorType* alloc_ptr, pointer construct_at) {
+    AllocatorTraits::construct(*alloc_ptr, construct_at, *it_);
+    ++it_;
+  }
+
+ private:
+  Iterator it_;
+};
+
+template <typename AllocatorType>
+class CopyValueAdapter {
+  using pointer = typename AllocatorType::pointer;
+  using const_pointer = typename AllocatorType::const_pointer;
+  using const_reference = typename AllocatorType::const_reference;
+  using AllocatorTraits = absl::allocator_traits<AllocatorType>;
+
+ public:
+  explicit CopyValueAdapter(const_reference v) : ptr_(std::addressof(v)) {}
+
+  void ConstructNext(AllocatorType* alloc_ptr, pointer construct_at) {
+    AllocatorTraits::construct(*alloc_ptr, construct_at, *ptr_);
+  }
+
+ private:
+  const_pointer ptr_;
+};
+
+template <typename AllocatorType>
+class DefaultValueAdapter {
+  using pointer = typename AllocatorType::pointer;
+  using value_type = typename AllocatorType::value_type;
+  using AllocatorTraits = absl::allocator_traits<AllocatorType>;
+
+ public:
+  explicit DefaultValueAdapter() {}
+
+  void ConstructNext(AllocatorType* alloc_ptr, pointer construct_at) {
+    AllocatorTraits::construct(*alloc_ptr, construct_at);
+  }
+};
+
 template <typename T, size_t N, typename A>
 class Storage {
  public:
@@ -78,10 +153,20 @@ class Storage {
   using const_iterator = const_pointer;
   using reverse_iterator = std::reverse_iterator<iterator>;
   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+  using MoveIterator = std::move_iterator<iterator>;
   using AllocatorTraits = absl::allocator_traits<allocator_type>;
+  using IsMemcpyOk = inlined_vector_internal::IsMemcpyOk<allocator_type>;
 
   using StorageView = inlined_vector_internal::StorageView<allocator_type>;
 
+  template <typename Iterator>
+  using IteratorValueAdapter =
+      inlined_vector_internal::IteratorValueAdapter<allocator_type, Iterator>;
+  using CopyValueAdapter =
+      inlined_vector_internal::CopyValueAdapter<allocator_type>;
+  using DefaultValueAdapter =
+      inlined_vector_internal::DefaultValueAdapter<allocator_type>;
+
   Storage() : metadata_() {}
 
   explicit Storage(const allocator_type& alloc)
@@ -128,6 +213,8 @@ class Storage {
     return std::addressof(metadata_.template get<0>());
   }
 
+  void SetIsAllocated() { GetSizeAndIsAllocated() |= 1; }
+
   void SetAllocatedSize(size_type size) {
     GetSizeAndIsAllocated() = (size << 1) | static_cast<size_type>(1);
   }
@@ -151,8 +238,18 @@ class Storage {
     swap(data_.allocated, other->data_.allocated);
   }
 
+  void MemcpyContents(const Storage& other) {
+    assert(IsMemcpyOk::value);
+
+    GetSizeAndIsAllocated() = other.GetSizeAndIsAllocated();
+    data_ = other.data_;
+  }
+
   void DestroyAndDeallocate();
 
+  template <typename ValueAdapter>
+  void Initialize(ValueAdapter values, size_type new_size);
+
  private:
   size_type& GetSizeAndIsAllocated() { return metadata_.template get<1>(); }
 
@@ -185,11 +282,10 @@ class Storage {
 
 template <typename T, size_t N, typename A>
 void Storage<T, N, A>::DestroyAndDeallocate() {
-  namespace ivi = inlined_vector_internal;
-
   StorageView storage_view = MakeStorageView();
 
-  ivi::DestroyElements(GetAllocPtr(), storage_view.data, storage_view.size);
+  inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data,
+                                           storage_view.size);
 
   if (GetIsAllocated()) {
     AllocatorTraits::deallocate(*GetAllocPtr(), storage_view.data,
@@ -197,6 +293,36 @@ void Storage<T, N, A>::DestroyAndDeallocate() {
   }
 }
 
+template <typename T, size_t N, typename A>
+template <typename ValueAdapter>
+auto Storage<T, N, A>::Initialize(ValueAdapter values, size_type new_size)
+    -> void {
+  // Only callable from constructors!
+  assert(!GetIsAllocated());
+  assert(GetSize() == 0);
+
+  pointer construct_data;
+
+  if (new_size > static_cast<size_type>(N)) {
+    // Because this is only called from the `InlinedVector` constructors, it's
+    // safe to take on the allocation with size `0`. If `ConstructElements(...)`
+    // throws, deallocation will be automatically handled by `~Storage()`.
+    construct_data = AllocatorTraits::allocate(*GetAllocPtr(), new_size);
+    SetAllocatedData(construct_data, new_size);
+    SetIsAllocated();
+  } else {
+    construct_data = GetInlinedData();
+  }
+
+  inlined_vector_internal::ConstructElements(GetAllocPtr(), construct_data,
+                                             &values, new_size);
+
+  // Since the initial size was guaranteed to be `0` and the allocated bit is
+  // already correct for either case, *adding* `new_size` gives us the correct
+  // result faster than setting it directly.
+  AddSize(new_size);
+}
+
 }  // namespace inlined_vector_internal
 }  // namespace absl