helly25 · helly25 · Jul 13, 2024 · Jul 13, 2024
diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -1,5 +1,6 @@
 # 0.2.27
 
+* Implemented `LimitedVector::insert`.
 * Fixed a bug in `LimitedVector::assign`.
 * Updated https://github.com/bazel-contrib/toolchains_llvm past version 1.0.0.
 * Changed `LimitedMap` and `LimitedSet` to not verify whether input is sorted, if they use `kRequireSortedInput` and `NDEBUG` is defined.

diff --git a/mbo/container/limited_vector.h b/mbo/container/limited_vector.h
@@ -236,7 +236,7 @@ class LimitedVector final {
     return *this;
   }
 
-  // Mofification: clear, resize, reserve, explace_back, push_back, pop_back, assign
+  // Mofification: clear, resize, reserve, explace_back, push_back, pop_back, assign, insert
 
   constexpr void clear() noexcept {
     while (!empty()) {
@@ -376,6 +376,59 @@ class LimitedVector final {
     }
   }
 
+  constexpr iterator insert(const_iterator pos, T&& value) {
+    LV_REQUIRE(FATAL, size_ < Capacity) << "Called `insert` at capacity.";
+    LV_REQUIRE(FATAL, begin() <= pos && pos <= end()) << "Invalid `pos`.";
+    // Clang does not like `std::distance`. The issue is that the iterators point into the union.
+    // That makes them technically not point into an array AND that is indeed not allowed by C++.
+    const iterator dst = const_cast<iterator>(pos);
+    move_backward(dst, 1);
+    std::construct_at(&*dst, value);
+    return dst;
+  }
+
+  constexpr iterator insert(const_iterator pos, size_type count, const T& value) {
+    LV_REQUIRE(FATAL, size_ + count <= Capacity) << "Called `insert` at capacity.";
+    LV_REQUIRE(FATAL, begin() <= pos && pos <= end()) << "Invalid `pos`.";
+    const iterator dst = const_cast<iterator>(pos);
+    if (count == 0) {
+      return dst;
+    }
+    std::size_t index = move_backward(dst, count);
+    while (count) {
+      std::construct_at(&values_[index].data, value);
+      ++index;
+      --count;
+    }
+    return dst;
+  }
+
+  constexpr iterator insert(const_iterator pos, const T& value) { return insert(pos, 1, value); }
+
+  template<std::convertible_to<const_iterator> InputIt>
+  constexpr iterator insert(const_iterator pos, InputIt first, InputIt last) {
+    LV_REQUIRE(FATAL, begin() <= pos && pos <= end()) << "Invalid `pos`.";
+    LV_REQUIRE(FATAL, first <= last) << "First > Last.";
+    std::size_t count = std::distance(first, last);
+    LV_REQUIRE(FATAL, size_ + count <= Capacity) << "Called `insert` at capacity.";
+    const iterator dst = const_cast<iterator>(pos);
+    if (count == 0) {
+      return dst;
+    }
+    std::size_t index = move_backward(dst, count);
+    while (count) {
+      std::construct_at(&values_[index].data, *first);
+      ++index;
+      --count;
+      ++first;
+    }
+    return dst;
+  }
+
+  constexpr iterator insert(const_iterator pos, std::initializer_list<T> list) {
+    return insert(pos, list.begin(), list.end());
+  }
+
   // Read/write access
 
   constexpr std::size_t size() const noexcept { return size_; }
@@ -441,6 +494,16 @@ class LimitedVector final {
   constexpr const_pointer data() const noexcept { return &values_[0].data; }
 
  private:
+  constexpr std::size_t move_backward(iterator dst, std::size_t count) {
+    std::size_t pos = size_;
+    while (dst < &values_[pos].data) {
+      --pos;
+      std::construct_at(&values_[pos + count].data, std::move(values_[pos].data));
+    }
+    size_ += count;
+    return pos;
+  }
+
   std::size_t size_{0};
   // Array would be better but that does not work with ASAN builds.
   // std::array<Data, Capacity == 0 ? 1 : Capacity> values_;

diff --git a/mbo/container/limited_vector_test.cc b/mbo/container/limited_vector_test.cc
@@ -515,6 +515,122 @@ TEST_F(LimitedVectorTest, Assign3) {
   EXPECT_THAT(kData, ElementsAre(5, 6));
 }
 
+TEST_F(LimitedVectorTest, Insert1WithoutMoving) {
+  {
+    static constexpr auto kData = [] {
+      LimitedVector<int, 5> result{};
+      result.insert(result.begin(), 1);
+      return result;
+    }();
+    EXPECT_THAT(kData, ElementsAre(1));
+  }
+  {
+    static constexpr auto kData = [] {
+      LimitedVector<int, 5> result{};
+      result.insert(result.end(), 1);
+      result.insert(result.end(), 2);
+      result.insert(result.end(), 3);
+      return result;
+    }();
+    EXPECT_THAT(kData, ElementsAre(1, 2, 3));
+  }
+}
+
+TEST_F(LimitedVectorTest, Insert1WithMoving) {
+  {
+    static constexpr auto kData = [] {
+      LimitedVector<int, 5> result{};
+      result.insert(result.begin(), 1);
+      result.insert(result.begin(), 2);
+      result.insert(result.begin(), 3);
+      return result;
+    }();
+    EXPECT_THAT(kData, ElementsAre(3, 2, 1));
+  }
+  {
+    static constexpr auto kData = [] {
+      LimitedVector<int, 5> result({1, 2});
+      result.insert(result.begin(), 25);
+      result.insert(&result[2], 33);
+      result.insert(result.end(), 42);
+      return result;
+    }();
+    EXPECT_THAT(kData, ElementsAre(25, 1, 33, 2, 42));
+  }
+}
+
+TEST_F(LimitedVectorTest, Insert2) {
+  {
+    static constexpr auto kData = [] {
+      LimitedVector<int, 10> result{};
+      result.insert(result.begin(), 1, 0);
+      result.insert(result.begin(), 2, 1);
+      result.insert(result.begin(), 3, 2);
+      result.insert(result.begin(), 4, 3);
+      result.insert(result.begin(), 0, 4);
+      return result;
+    }();
+    EXPECT_THAT(kData, ElementsAre(3, 3, 3, 3, 2, 2, 2, 1, 1, 0));
+  }
+  {
+    static constexpr auto kData = [] {
+      LimitedVector<int, 10> result{};
+      result.insert(result.end(), 1, 0);
+      result.insert(result.end(), 2, 1);
+      result.insert(result.end(), 3, 2);
+      result.insert(result.end(), 4, 3);
+      result.insert(result.end(), 0, 4);
+      return result;
+    }();
+    EXPECT_THAT(kData, ElementsAre(0, 1, 1, 2, 2, 2, 3, 3, 3, 3));
+  }
+  {
+    static constexpr auto kData = [] {
+      LimitedVector<int, 10> result({1, 2});
+      result.insert(result.begin(), 2, 25);
+      result.insert(&result[3], 3, 33);
+      result.insert(result.end(), 3, 42);
+      return result;
+    }();
+    EXPECT_THAT(kData, ElementsAre(25, 25, 1, 33, 33, 33, 2, 42, 42, 42));
+  }
+}
+
+TEST_F(LimitedVectorTest, Insert3) {
+  {
+    static constexpr auto kData = [] {
+      LimitedVector<int, 6> result{};
+      result.insert(result.begin(), {11});
+      result.insert(result.begin(), {21, 22});
+      result.insert(result.begin(), {31, 32, 33});
+      result.insert(result.begin(), {});
+      return result;
+    }();
+    EXPECT_THAT(kData, ElementsAre(31, 32, 33, 21, 22, 11));
+  }
+  {
+    static constexpr auto kData = [] {
+      LimitedVector<int, 6> result{};
+      result.insert(result.end(), {11});
+      result.insert(result.end(), {21, 22});
+      result.insert(result.end(), {31, 32, 33});
+      result.insert(result.end(), {});
+      return result;
+    }();
+    EXPECT_THAT(kData, ElementsAre(11, 21, 22, 31, 32, 33));
+  }
+  {
+    static constexpr auto kData = [] {
+      LimitedVector<int, 8> result({1, 2});
+      result.insert(result.begin(), {21, 22});
+      result.insert(&result[3], {31, 32});
+      result.insert(result.end(), {41, 42});
+      return result;
+    }();
+    EXPECT_THAT(kData, ElementsAre(21, 22, 1, 31, 32, 2, 41, 42));
+  }
+}
+
 // NOLINTEND(*-magic-numbers)
 
 }  // namespace