pw_minimal_cpp_stdlib: Various additions

- Implement a few library features: std::equal and
  std::lexicographical_compare, std::launder, std::add_rvalue_reference,
  std::add_lvalue_reference, std::negation.
- Conditionally include <vector> on key_value_store_test.cc.

Change-Id: I9efb16c385b4ff2005cfd737da1efe9d95fe1bdd

6 files changed, 88 insertions, 5 deletions

diff --git a/pw_kvs/key_value_store_test.cc b/pw_kvs/key_value_store_test.cc
index c54d6e773..401ef8e15 100644
--- a/pw_kvs/key_value_store_test.cc
+++ b/pw_kvs/key_value_store_test.cc
@@ -21,7 +21,10 @@
 #include <array>
 #include <cstdio>
 #include <cstring>
+
+#if DUMP_KVS_STATE_TO_FILE
 #include <vector>
+#endif  // DUMP_KVS_STATE_TO_FILE
 
 #include "gtest/gtest.h"
 #include "pw_checksum/ccitt_crc16.h"
diff --git a/pw_minimal_cpp_stdlib/public/internal/algorithm.h b/pw_minimal_cpp_stdlib/public/internal/algorithm.h
index 2556702de..f905e11a5 100644
--- a/pw_minimal_cpp_stdlib/public/internal/algorithm.h
+++ b/pw_minimal_cpp_stdlib/public/internal/algorithm.h
@@ -37,4 +37,38 @@ constexpr T&& forward(remove_reference_t<T>&& value) {
   return static_cast<T&&>(value);
 }
 
+template <class LhsIterator, class RhsIterator>
+constexpr bool equal(LhsIterator first_l,
+                     LhsIterator last_l,
+                     RhsIterator first_r,
+                     RhsIterator last_r) {
+  while (first_l != last_l && first_r != last_r) {
+    if (*first_l != *first_r) {
+      return false;
+    }
+    ++first_l;
+    ++first_r;
+  }
+  return first_l == last_l && first_r == last_r;
+}
+
+template <class LhsIterator, class RhsIterator>
+constexpr bool lexicographical_compare(LhsIterator first_l,
+                                       LhsIterator last_l,
+                                       RhsIterator first_r,
+                                       RhsIterator last_r) {
+  while (first_l != last_l && first_r != last_r) {
+    if (*first_l < *first_r) {
+      return true;
+    }
+    if (*first_r < *first_l) {
+      return false;
+    }
+
+    ++first_l;
+    ++first_r;
+  }
+  return (first_l == last_l) && (first_r != last_r);
+}
+
 }  // namespace std
diff --git a/pw_minimal_cpp_stdlib/public/internal/iterator.h b/pw_minimal_cpp_stdlib/public/internal/iterator.h
index 9c5e9ad66..447073185 100644
--- a/pw_minimal_cpp_stdlib/public/internal/iterator.h
+++ b/pw_minimal_cpp_stdlib/public/internal/iterator.h
@@ -44,6 +44,10 @@ constexpr decltype(sizeof(int)) size(const T (&)[kSize]) noexcept {
   return kSize;
 }
 
+// NOT IMPLEMENTED: iterator_traits does not work
+template <typename>
+struct iterator_traits {};
+
 // NOT IMPLEMENTED: Reverse iterators are not implemented.
 template <typename>
 struct reverse_iterator;
diff --git a/pw_minimal_cpp_stdlib/public/internal/new.h b/pw_minimal_cpp_stdlib/public/internal/new.h
index d21d991b3..b7a583c5a 100644
--- a/pw_minimal_cpp_stdlib/public/internal/new.h
+++ b/pw_minimal_cpp_stdlib/public/internal/new.h
@@ -15,3 +15,14 @@
 
 // Placement new
 inline void* operator new(decltype(sizeof(0)), void* ptr) { return ptr; }
+
+#define __cpp_lib_launder 201606L
+
+namespace std {
+
+template <typename T>
+[[nodiscard]] constexpr T* launder(T* pointer) noexcept {
+  return __builtin_launder(pointer);
+}
+
+}  // namespace std
diff --git a/pw_minimal_cpp_stdlib/public/internal/type_traits.h b/pw_minimal_cpp_stdlib/public/internal/type_traits.h
index 422b2df0e..366f56802 100644
--- a/pw_minimal_cpp_stdlib/public/internal/type_traits.h
+++ b/pw_minimal_cpp_stdlib/public/internal/type_traits.h
@@ -206,6 +206,12 @@ struct is_void : is_same<void, typename remove_cv<T>::type> {};
 template <typename T>
 inline constexpr bool is_void_v = is_void<T>::value;
 
+template <typename T>
+struct negation : bool_constant<!bool(T::value)> {};
+
+template <typename T>
+inline constexpr bool negation_v = negation<T>::value;
+
 template <bool kBool, typename TrueType, typename FalseType>
 struct conditional {
   using type = TrueType;
@@ -358,11 +364,30 @@ using type_identity_t = typename type_identity<T>::type;
 template <typename...>
 using void_t = void;
 
-// NOT IMPLEMENTED: add_rvalue_refernce does work with reference types.
+namespace impl {
+
 template <typename T>
-struct add_rvalue_reference {
-  using type = T&&;
-};
+type_identity<T&> AddLValueReference(int);
+
+template <typename T>
+type_identity<T> AddLValueReference(...);
+
+template <typename T>
+type_identity<T&&> AddRValueReference(int);
+
+template <typename T>
+type_identity<T> AddRValueReference(...);
+
+}  // namespace impl
+
+template <class T>
+struct add_lvalue_reference : decltype(impl::AddLValueReference<T>(0)) {};
+
+template <typename T>
+using add_lvalue_reference_t = typename add_lvalue_reference<T>::type;
+
+template <class T>
+struct add_rvalue_reference : decltype(impl::AddRValueReference<T>(0)) {};
 
 template <typename T>
 using add_rvalue_reference_t = typename add_rvalue_reference<T>::type;
diff --git a/pw_minimal_cpp_stdlib/test.cc b/pw_minimal_cpp_stdlib/test.cc
index 3b1d42af6..a29f64903 100644
--- a/pw_minimal_cpp_stdlib/test.cc
+++ b/pw_minimal_cpp_stdlib/test.cc
@@ -134,7 +134,7 @@ TEST(Limits, Basic) {
                 18446744073709551615ull);
 }
 
-TEST(New, Basic) {
+TEST(New, PlacementNew) {
   unsigned char value[4];
   new (value) int(1234);
 
@@ -143,6 +143,12 @@ TEST(New, Basic) {
   EXPECT_EQ(1234, int_value);
 }
 
+TEST(New, Launder) {
+  unsigned char value[4];
+  int* int_ptr = std::launder(reinterpret_cast<int*>(value));
+  EXPECT_EQ(static_cast<void*>(int_ptr), static_cast<void*>(value));
+}
+
 TEST(StringView, Basic) {
   constexpr std::string_view value("1234567890");
   static_assert(value.size() == 10);