7 files changed, 603 insertions, 24 deletions

diff --git a/pw_containers/public/pw_containers/algorithm.h b/pw_containers/public/pw_containers/algorithm.h
new file mode 100644
index 000000000..e8e81efcf
--- /dev/null
+++ b/pw_containers/public/pw_containers/algorithm.h
@@ -0,0 +1,366 @@
+// Copyright 2022 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+//
+// -----------------------------------------------------------------------------
+// File: algorithm.h
+// -----------------------------------------------------------------------------
+//
+// This header file provides Container-based versions of algorithmic functions
+// within the C++ standard library, based on a subset of
+// absl/algorithm/container.h. The following standard library sets of functions
+// are covered within this file:
+//
+//   * <algorithm> functions
+//
+// The standard library functions operate on iterator ranges; the functions
+// within this API operate on containers, though many return iterator ranges.
+//
+// All functions within this API are CamelCase instead of their std::
+// snake_case counterparts. Calls such as `pw::containers::Foo(container, ...)
+// are equivalent to std:: functions such as
+// `std::foo(std::begin(cont), std::end(cont), ...)`. Functions that act on
+// iterators but not conceptually on iterator ranges (e.g. `std::iter_swap`)
+// have no equivalent here.
+//
+// For template parameter and variable naming, `C` indicates the container type
+// to which the function is applied, `Pred` indicates the predicate object type
+// to be used by the function and `T` indicates the applicable element type.
+//
+// This was forked from
+// https://cs.opensource.google/abseil/abseil-cpp/+/main:absl/algorithm/algorithm.h;drc=12bc53e0318d80569270a5b26ccbc62b52022b89
+#pragma once
+
+#include <algorithm>
+#include <utility>
+
+#include "pw_containers/internal/algorithm_internal.h"
+
+namespace pw::containers {
+
+//------------------------------------------------------------------------------
+// <algorithm> Non-modifying sequence operations
+//------------------------------------------------------------------------------
+
+// AllOf()
+//
+// Container-based version of the <algorithm> `std::all_of()` function to
+// test if all elements within a container satisfy a condition.
+template <typename C, typename Pred>
+bool AllOf(const C& c, Pred&& pred) {
+  return std::all_of(std::begin(c), std::end(c), std::forward<Pred>(pred));
+}
+
+// AnyOf()
+//
+// Container-based version of the <algorithm> `std::any_of()` function to
+// test if any element in a container fulfills a condition.
+template <typename C, typename Pred>
+bool AnyOf(const C& c, Pred&& pred) {
+  return std::any_of(std::begin(c), std::end(c), std::forward<Pred>(pred));
+}
+
+// NoneOf()
+//
+// Container-based version of the <algorithm> `std::none_of()` function to
+// test if no elements in a container fulfill a condition.
+template <typename C, typename Pred>
+bool NoneOf(const C& c, Pred&& pred) {
+  return std::none_of(std::begin(c), std::end(c), std::forward<Pred>(pred));
+}
+
+// ForEach()
+//
+// Container-based version of the <algorithm> `std::for_each()` function to
+// apply a function to a container's elements.
+template <typename C, typename Function>
+std::decay_t<Function> ForEach(C&& c, Function&& f) {
+  return std::for_each(std::begin(c), std::end(c), std::forward<Function>(f));
+}
+
+// Find()
+//
+// Container-based version of the <algorithm> `std::find()` function to find
+// the first element containing the passed value within a container value.
+template <typename C, typename T>
+internal_algorithm::ContainerIter<C> Find(C& c, T&& value) {
+  return std::find(std::begin(c), std::end(c), std::forward<T>(value));
+}
+
+// FindIf()
+//
+// Container-based version of the <algorithm> `std::find_if()` function to find
+// the first element in a container matching the given condition.
+template <typename C, typename Pred>
+internal_algorithm::ContainerIter<C> FindIf(C& c, Pred&& pred) {
+  return std::find_if(std::begin(c), std::end(c), std::forward<Pred>(pred));
+}
+
+// FindIfNot()
+//
+// Container-based version of the <algorithm> `std::find_if_not()` function to
+// find the first element in a container not matching the given condition.
+template <typename C, typename Pred>
+internal_algorithm::ContainerIter<C> FindIfNot(C& c, Pred&& pred) {
+  return std::find_if_not(std::begin(c), std::end(c), std::forward<Pred>(pred));
+}
+
+// FindEnd()
+//
+// Container-based version of the <algorithm> `std::find_end()` function to
+// find the last subsequence within a container.
+template <typename Sequence1, typename Sequence2>
+internal_algorithm::ContainerIter<Sequence1> FindEnd(Sequence1& sequence,
+                                                     Sequence2& subsequence) {
+  return std::find_end(std::begin(sequence),
+                       std::end(sequence),
+                       std::begin(subsequence),
+                       std::end(subsequence));
+}
+
+// Overload of FindEnd() for using a predicate evaluation other than `==` as
+// the function's test condition.
+template <typename Sequence1, typename Sequence2, typename BinaryPredicate>
+internal_algorithm::ContainerIter<Sequence1> FindEnd(Sequence1& sequence,
+                                                     Sequence2& subsequence,
+                                                     BinaryPredicate&& pred) {
+  return std::find_end(std::begin(sequence),
+                       std::end(sequence),
+                       std::begin(subsequence),
+                       std::end(subsequence),
+                       std::forward<BinaryPredicate>(pred));
+}
+
+// FindFirstOf()
+//
+// Container-based version of the <algorithm> `std::find_first_of()` function to
+// find the first element within the container that is also within the options
+// container.
+template <typename C1, typename C2>
+internal_algorithm::ContainerIter<C1> FindFirstOf(C1& container, C2& options) {
+  return std::find_first_of(std::begin(container),
+                            std::end(container),
+                            std::begin(options),
+                            std::end(options));
+}
+
+// Overload of FindFirstOf() for using a predicate evaluation other than
+// `==` as the function's test condition.
+template <typename C1, typename C2, typename BinaryPredicate>
+internal_algorithm::ContainerIter<C1> FindFirstOf(C1& container,
+                                                  C2& options,
+                                                  BinaryPredicate&& pred) {
+  return std::find_first_of(std::begin(container),
+                            std::end(container),
+                            std::begin(options),
+                            std::end(options),
+                            std::forward<BinaryPredicate>(pred));
+}
+
+// AdjacentFind()
+//
+// Container-based version of the <algorithm> `std::adjacent_find()` function to
+// find equal adjacent elements within a container.
+template <typename Sequence>
+internal_algorithm::ContainerIter<Sequence> AdjacentFind(Sequence& sequence) {
+  return std::adjacent_find(std::begin(sequence), std::end(sequence));
+}
+
+// Overload of AdjacentFind() for using a predicate evaluation other than
+// `==` as the function's test condition.
+template <typename Sequence, typename BinaryPredicate>
+internal_algorithm::ContainerIter<Sequence> AdjacentFind(
+    Sequence& sequence, BinaryPredicate&& pred) {
+  return std::adjacent_find(std::begin(sequence),
+                            std::end(sequence),
+                            std::forward<BinaryPredicate>(pred));
+}
+
+// Count()
+//
+// Container-based version of the <algorithm> `std::count()` function to count
+// values that match within a container.
+template <typename C, typename T>
+internal_algorithm::ContainerDifferenceType<const C> Count(const C& c,
+                                                           T&& value) {
+  return std::count(std::begin(c), std::end(c), std::forward<T>(value));
+}
+
+// CountIOf()
+//
+// Container-based version of the <algorithm> `std::count_if()` function to
+// count values matching a condition within a container.
+template <typename C, typename Pred>
+internal_algorithm::ContainerDifferenceType<const C> CountIf(const C& c,
+                                                             Pred&& pred) {
+  return std::count_if(std::begin(c), std::end(c), std::forward<Pred>(pred));
+}
+
+// Mismatch()
+//
+// Container-based version of the <algorithm> `std::mismatch()` function to
+// return the first element where two ordered containers differ. Applies `==` to
+// the first N elements of `c1` and `c2`, where N = min(size(c1), size(c2)).
+template <typename C1, typename C2>
+internal_algorithm::ContainerIterPairType<C1, C2> Mismatch(C1& c1, C2& c2) {
+  auto first1 = std::begin(c1);
+  auto last1 = std::end(c1);
+  auto first2 = std::begin(c2);
+  auto last2 = std::end(c2);
+
+  for (; first1 != last1 && first2 != last2; ++first1, (void)++first2) {
+    // Negates equality because Cpp17EqualityComparable doesn't require clients
+    // to overload both `operator==` and `operator!=`.
+    if (!(*first1 == *first2)) {
+      break;
+    }
+  }
+
+  return std::make_pair(first1, first2);
+}
+
+// Overload of Mismatch() for using a predicate evaluation other than `==` as
+// the function's test condition. Applies `pred`to the first N elements of `c1`
+// and `c2`, where N = min(size(c1), size(c2)).
+template <typename C1, typename C2, typename BinaryPredicate>
+internal_algorithm::ContainerIterPairType<C1, C2> Mismatch(
+    C1& c1, C2& c2, BinaryPredicate pred) {
+  auto first1 = std::begin(c1);
+  auto last1 = std::end(c1);
+  auto first2 = std::begin(c2);
+  auto last2 = std::end(c2);
+
+  for (; first1 != last1 && first2 != last2; ++first1, (void)++first2) {
+    if (!pred(*first1, *first2)) {
+      break;
+    }
+  }
+
+  return std::make_pair(first1, first2);
+}
+
+// Equal()
+//
+// Container-based version of the <algorithm> `std::equal()` function to
+// test whether two containers are equal.
+//
+// NOTE: the semantics of Equal() are slightly different than those of
+// equal(): while the latter iterates over the second container only up to the
+// size of the first container, Equal() also checks whether the container
+// sizes are equal.  This better matches expectations about Equal() based on
+// its signature.
+//
+// Example:
+//   vector v1 = <1, 2, 3>;
+//   vector v2 = <1, 2, 3, 4>;
+//   equal(std::begin(v1), std::end(v1), std::begin(v2)) returns true
+//   Equal(v1, v2) returns false
+
+template <typename C1, typename C2>
+bool Equal(const C1& c1, const C2& c2) {
+  return ((std::size(c1) == std::size(c2)) &&
+          std::equal(std::begin(c1), std::end(c1), std::begin(c2)));
+}
+
+// Overload of Equal() for using a predicate evaluation other than `==` as
+// the function's test condition.
+template <typename C1, typename C2, typename BinaryPredicate>
+bool Equal(const C1& c1, const C2& c2, BinaryPredicate&& pred) {
+  return ((std::size(c1) == std::size(c2)) &&
+          std::equal(std::begin(c1),
+                     std::end(c1),
+                     std::begin(c2),
+                     std::forward<BinaryPredicate>(pred)));
+}
+
+// IsPermutation()
+//
+// Container-based version of the <algorithm> `std::is_permutation()` function
+// to test whether a container is a permutation of another.
+template <typename C1, typename C2>
+bool IsPermutation(const C1& c1, const C2& c2) {
+  using std::begin;
+  using std::end;
+  return c1.size() == c2.size() &&
+         std::is_permutation(begin(c1), end(c1), begin(c2));
+}
+
+// Overload of IsPermutation() for using a predicate evaluation other than
+// `==` as the function's test condition.
+template <typename C1, typename C2, typename BinaryPredicate>
+bool IsPermutation(const C1& c1, const C2& c2, BinaryPredicate&& pred) {
+  using std::begin;
+  using std::end;
+  return c1.size() == c2.size() &&
+         std::is_permutation(begin(c1),
+                             end(c1),
+                             begin(c2),
+                             std::forward<BinaryPredicate>(pred));
+}
+
+// Search()
+//
+// Container-based version of the <algorithm> `std::search()` function to search
+// a container for a subsequence.
+template <typename Sequence1, typename Sequence2>
+internal_algorithm::ContainerIter<Sequence1> Search(Sequence1& sequence,
+                                                    Sequence2& subsequence) {
+  return std::search(std::begin(sequence),
+                     std::end(sequence),
+                     std::begin(subsequence),
+                     std::end(subsequence));
+}
+
+// Overload of Search() for using a predicate evaluation other than
+// `==` as the function's test condition.
+template <typename Sequence1, typename Sequence2, typename BinaryPredicate>
+internal_algorithm::ContainerIter<Sequence1> Search(Sequence1& sequence,
+                                                    Sequence2& subsequence,
+                                                    BinaryPredicate&& pred) {
+  return std::search(std::begin(sequence),
+                     std::end(sequence),
+                     std::begin(subsequence),
+                     std::end(subsequence),
+                     std::forward<BinaryPredicate>(pred));
+}
+
+// SearchN()
+//
+// Container-based version of the <algorithm> `std::search_n()` function to
+// search a container for the first sequence of N elements.
+template <typename Sequence, typename Size, typename T>
+internal_algorithm::ContainerIter<Sequence> SearchN(Sequence& sequence,
+                                                    Size count,
+                                                    T&& value) {
+  return std::search_n(
+      std::begin(sequence), std::end(sequence), count, std::forward<T>(value));
+}
+
+// Overload of SearchN() for using a predicate evaluation other than
+// `==` as the function's test condition.
+template <typename Sequence,
+          typename Size,
+          typename T,
+          typename BinaryPredicate>
+internal_algorithm::ContainerIter<Sequence> SearchN(Sequence& sequence,
+                                                    Size count,
+                                                    T&& value,
+                                                    BinaryPredicate&& pred) {
+  return std::search_n(std::begin(sequence),
+                       std::end(sequence),
+                       count,
+                       std::forward<T>(value),
+                       std::forward<BinaryPredicate>(pred));
+}
+
+}  // namespace pw::containers
diff --git a/pw_containers/public/pw_containers/filtered_view.h b/pw_containers/public/pw_containers/filtered_view.h
index 7daf821f2..b1b499176 100644
--- a/pw_containers/public/pw_containers/filtered_view.h
+++ b/pw_containers/public/pw_containers/filtered_view.h
@@ -17,6 +17,7 @@
 #include <iterator>
 
 #include "pw_assert/assert.h"
+#include "pw_preprocessor/compiler.h"
 
 namespace pw::containers {
 
@@ -160,6 +161,7 @@ FilteredView<Container, Filter>::iterator::operator--() {
   }
 
   PW_ASSERT(false);
+  PW_UNREACHABLE;
 }
 
 }  // namespace pw::containers
diff --git a/pw_containers/public/pw_containers/flat_map.h b/pw_containers/public/pw_containers/flat_map.h
index b4c2ab537..7ce97cab0 100644
--- a/pw_containers/public/pw_containers/flat_map.h
+++ b/pw_containers/public/pw_containers/flat_map.h
@@ -21,9 +21,21 @@
 
 namespace pw::containers {
 
+// Define and use a custom Pair object. This is because std::pair does not
+// support constexpr assignment until C++20. The assignment is needed since
+// the array of pairs will be sorted in the constructor (if not already).
+template <typename First, typename Second>
+struct Pair {
+  First first;
+  Second second;
+};
+
+template <typename T1, typename T2>
+Pair(T1, T2) -> Pair<T1, T2>;
+
 // A simple, fixed-size associative array with lookup by key or value.
 //
-// FlatMaps are initialized with a std::array of FlatMap::Pair objects:
+// FlatMaps are initialized with a std::array of Pair<K, V> objects:
 //   FlatMap<int, int> map({{{1, 2}, {3, 4}}});
 //
 // The keys do not need to be sorted as the constructor will sort the items
@@ -31,15 +43,6 @@ namespace pw::containers {
 template <typename Key, typename Value, size_t kArraySize>
 class FlatMap {
  public:
-  // Define and use a custom Pair object. This is because std::pair does not
-  // support constexpr assignment until C++20. The assignment is needed since
-  // the array of pairs will be sorted in the constructor (if not already).
-  template <typename First, typename Second>
-  struct Pair {
-    First first;
-    Second second;
-  };
-
   using key_type = Key;
   using mapped_type = Value;
   using value_type = Pair<key_type, mapped_type>;
@@ -73,7 +76,10 @@ class FlatMap {
     }
 
     const_iterator it = lower_bound(key);
-    return key == it->first ? it : end();
+    if (it == end() || it->first != key) {
+      return end();
+    }
+    return it;
   }
 
   constexpr const_iterator lower_bound(const key_type& key) const {
diff --git a/pw_containers/public/pw_containers/internal/algorithm_internal.h b/pw_containers/public/pw_containers/internal/algorithm_internal.h
new file mode 100644
index 000000000..9d376e09a
--- /dev/null
+++ b/pw_containers/public/pw_containers/internal/algorithm_internal.h
@@ -0,0 +1,38 @@
+// Copyright 2022 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+#pragma once
+
+#include <cstddef>
+#include <iterator>
+#include <utility>
+
+namespace pw::containers::internal_algorithm {
+
+// The type of the iterator given by begin(c) (possibly std::begin(c)).
+// ContainerIter<const vector<T>> gives vector<T>::const_iterator,
+// while ContainerIter<vector<T>> gives vector<T>::iterator.
+template <typename C>
+using ContainerIter = decltype(std::begin(std::declval<C&>()));
+
+// An MSVC bug involving template parameter substitution requires us to use
+// decltype() here instead of just std::pair.
+template <typename C1, typename C2>
+using ContainerIterPairType =
+    decltype(std::make_pair(ContainerIter<C1>(), ContainerIter<C2>()));
+
+template <typename C>
+using ContainerDifferenceType = decltype(std::distance(
+    std::declval<ContainerIter<C>>(), std::declval<ContainerIter<C>>()));
+
+}  // namespace pw::containers::internal_algorithm
diff --git a/pw_containers/public/pw_containers/iterator.h b/pw_containers/public/pw_containers/iterator.h
new file mode 100644
index 000000000..d9a8f7296
--- /dev/null
+++ b/pw_containers/public/pw_containers/iterator.h
@@ -0,0 +1,34 @@
+// Copyright 2022 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+#pragma once
+
+#include <iterator>
+
+#include "pw_polyfill/standard.h"
+
+namespace pw::containers {
+
+#if PW_CXX_STANDARD_IS_SUPPORTED(20)
+
+// If std::contiguous_iterator_tag exists, use it directly.
+using std::contiguous_iterator_tag;
+
+#else
+
+// If std::contiguous_iterator_tag does not exist, define a stand-in type.
+struct contiguous_iterator_tag : public std::random_access_iterator_tag {};
+
+#endif  // PW_CXX_STANDARD_IS_SUPPORTED(20)
+
+}  // namespace pw::containers
diff --git a/pw_containers/public/pw_containers/to_array.h b/pw_containers/public/pw_containers/to_array.h
index 63a107fd6..fa02c274b 100644
--- a/pw_containers/public/pw_containers/to_array.h
+++ b/pw_containers/public/pw_containers/to_array.h
@@ -20,6 +20,14 @@
 
 namespace pw {
 namespace containers {
+
+// If std::to_array is available, use it as pw::containers::to_array.
+#ifdef __cpp_lib_to_array
+
+using std::to_array;
+
+#else
+
 namespace impl {
 
 template <typename T, size_t kSize, size_t... kIndices>
@@ -36,8 +44,8 @@ constexpr std::array<std::remove_cv_t<T>, kSize> MoveArray(
 
 }  // namespace impl
 
-// pw::containers::to_array is C++14-compatible implementation of C++20's
-// std::to_array.
+// If C++20's std::to_array is not available, implement pw::containers::to_array
+// in a C++14-compatible way.
 template <typename T, size_t kSize>
 constexpr std::array<std::remove_cv_t<T>, kSize> to_array(T (&values)[kSize]) {
   return impl::CopyArray(values, std::make_index_sequence<kSize>{});
@@ -48,5 +56,7 @@ constexpr std::array<std::remove_cv_t<T>, kSize> to_array(T (&&values)[kSize]) {
   return impl::MoveArray(std::move(values), std::make_index_sequence<kSize>{});
 }
 
+#endif  // __cpp_lib_to_array
+
 }  // namespace containers
 }  // namespace pw
diff --git a/pw_containers/public/pw_containers/vector.h b/pw_containers/public/pw_containers/vector.h
index 34380749e..62ebc8aa1 100644
--- a/pw_containers/public/pw_containers/vector.h
+++ b/pw_containers/public/pw_containers/vector.h
@@ -20,6 +20,7 @@
 #include <iterator>
 #include <limits>
 #include <new>
+#include <string_view>
 #include <type_traits>
 #include <utility>
 
@@ -113,6 +114,18 @@ class Vector : public Vector<T, vector_impl::kGeneric> {
   Vector(std::initializer_list<T> list)
       : Vector<T, vector_impl::kGeneric>(kMaxSize, list) {}
 
+  static constexpr size_t max_size() { return kMaxSize; }
+
+  // Construct from std::string_view when T is char.
+  template <typename U = T,
+            typename = std::enable_if_t<std::is_same_v<U, char>>>
+  Vector(std::string_view source) : Vector(source.begin(), source.end()) {}
+
+  // Construct from const char* when T is char.
+  template <typename U = T,
+            typename = std::enable_if_t<std::is_same_v<U, char>>>
+  Vector(const char* source) : Vector(std::string_view(source)) {}
+
   Vector& operator=(const Vector& other) {
     Vector<T>::assign(other.begin(), other.end());
     return *this;
@@ -314,26 +327,28 @@ class Vector<T, vector_impl::kGeneric>
 
   void clear() noexcept;
 
-  // TODO(hepler): insert, emplace, and erase are not yet implemented.
-  //    Currently, items can only be added to or removed from the end.
-  iterator insert(const_iterator index, const T& value);
+  iterator insert(const_iterator index, size_type count, const T& value);
 
-  iterator insert(const_iterator index, T&& value);
+  iterator insert(const_iterator index, const T& value) {
+    return insert(index, 1, value);
+  }
 
-  iterator insert(const_iterator index, size_type count, const T& value);
+  iterator insert(const_iterator index, T&& value);
 
   template <typename Iterator>
   iterator insert(const_iterator index, Iterator first, Iterator last);
 
-  iterator insert(const_iterator index, std::initializer_list<T> list);
+  iterator insert(const_iterator index, std::initializer_list<T> list) {
+    return insert(index, list.begin(), list.end());
+  }
 
   template <typename... Args>
   iterator emplace(const_iterator index, Args&&... args);
 
-  iterator erase(const_iterator index);
-
   iterator erase(const_iterator first, const_iterator last);
 
+  iterator erase(const_iterator index) { return erase(index, index + 1); }
+
   void push_back(const T& value) { emplace_back(value); }
 
   void push_back(T&& value) { emplace_back(std::move(value)); }
@@ -433,8 +448,10 @@ bool operator>=(const Vector<T, kLhsSize>& lhs,
 
 template <typename T>
 void Vector<T, vector_impl::kGeneric>::clear() noexcept {
-  for (auto& item : *this) {
-    item.~T();
+  if constexpr (!std::is_trivially_destructible_v<value_type>) {
+    for (auto& item : *this) {
+      item.~T();
+    }
   }
   size_ = 0;
 }
@@ -451,7 +468,9 @@ void Vector<T, vector_impl::kGeneric>::emplace_back(Args&&... args) {
 template <typename T>
 void Vector<T, vector_impl::kGeneric>::pop_back() {
   if (!empty()) {
-    back().~T();
+    if constexpr (!std::is_trivially_destructible_v<value_type>) {
+      back().~T();
+    }
     size_ -= 1;
   }
 }
@@ -469,6 +488,110 @@ void Vector<T, vector_impl::kGeneric>::resize(size_type new_size,
 }
 
 template <typename T>
+typename Vector<T>::iterator Vector<T>::insert(Vector<T>::const_iterator index,
+                                               T&& value) {
+  PW_DASSERT(index >= cbegin());
+  PW_DASSERT(index <= cend());
+  PW_DASSERT(!full());
+
+  iterator insertion_point = begin() + std::distance(cbegin(), index);
+  if (insertion_point == end()) {
+    emplace_back(std::move(value));
+    return insertion_point;
+  }
+
+  std::move_backward(insertion_point, end(), end() + 1);
+  *insertion_point = std::move(value);
+  ++size_;
+
+  // Return an iterator pointing to the inserted value.
+  return insertion_point;
+}
+
+template <typename T>
+template <typename Iterator>
+typename Vector<T>::iterator Vector<T>::insert(Vector<T>::const_iterator index,
+                                               Iterator first,
+                                               Iterator last) {
+  PW_DASSERT(index >= cbegin());
+  PW_DASSERT(index <= cend());
+  PW_DASSERT(!full());
+
+  iterator insertion_point = begin() + std::distance(cbegin(), index);
+
+  const size_t insertion_count = std::distance(first, last);
+  if (insertion_count == 0) {
+    return insertion_point;
+  }
+  PW_DASSERT(size() + insertion_count <= max_size());
+
+  iterator return_value = insertion_point;
+
+  if (insertion_point != end()) {
+    std::move_backward(insertion_point, end(), end() + insertion_count);
+  }
+
+  while (first != last) {
+    *insertion_point = *first;
+    ++first;
+    ++insertion_point;
+  }
+  size_ += insertion_count;
+
+  // Return an iterator pointing to the first element inserted.
+  return return_value;
+}
+
+template <typename T>
+typename Vector<T>::iterator Vector<T>::insert(Vector<T>::const_iterator index,
+                                               size_type count,
+                                               const T& value) {
+  PW_DASSERT(index >= cbegin());
+  PW_DASSERT(index <= cend());
+  PW_DASSERT(size() + count <= max_size());
+
+  iterator insertion_point = begin() + std::distance(cbegin(), index);
+  if (count == size_type{}) {
+    return insertion_point;
+  }
+
+  if (insertion_point != end()) {
+    std::move_backward(insertion_point, end(), end() + count);
+  }
+
+  iterator return_value = insertion_point;
+
+  for (size_type final_count = size_ + count; size_ != final_count; ++size_) {
+    *insertion_point = value;
+    ++insertion_point;
+  }
+
+  // Return an iterator pointing to the first element inserted.
+  return return_value;
+}
+
+template <typename T>
+typename Vector<T>::iterator Vector<T>::erase(Vector<T>::const_iterator first,
+                                              Vector<T>::const_iterator last) {
+  iterator source = begin() + std::distance(cbegin(), last);
+  if (first == last) {
+    return source;
+  }
+
+  if constexpr (!std::is_trivially_destructible_v<T>) {
+    std::destroy(first, last);
+  }
+
+  iterator destination = begin() + std::distance(cbegin(), first);
+  iterator new_end = std::move(source, end(), destination);
+
+  size_ = std::distance(begin(), new_end);
+
+  // Return an iterator following the last removed element.
+  return new_end;
+}
+
+template <typename T>
 template <typename Iterator>
 void Vector<T, vector_impl::kGeneric>::CopyFrom(Iterator first, Iterator last) {
   while (first != last) {