BLI: add reverse iterators, iterator constructor and Vector.insert/prepend

The new reverse iterators behave as the reverse iterators for contains from
the standard library. Have a look at the tests to see how to use them.
Using them will hopefully become easier with ranges in C++20.

A Vector can now be constructed from two iterators, which is very common
in the standard library.

New Vector.insert methods allow adding elements in the middle of a vector.
These methods should not be used often in practice, because they has a linear running time.

New Vector.prepend methods allow adding elements to the beginning of a vector.
These methods are O(n) as well.

1 files changed, 28 insertions, 0 deletions

diff --git a/source/blender/blenlib/tests/BLI_span_test.cc b/source/blender/blenlib/tests/BLI_span_test.cc
index 6ad2a5633ad..82d21e53084 100644
--- a/source/blender/blenlib/tests/BLI_span_test.cc
+++ b/source/blender/blenlib/tests/BLI_span_test.cc
@@ -308,4 +308,32 @@ TEST(span, CopyFrom)
   EXPECT_EQ(dst[3], 8);
 }
 
+TEST(span, ReverseIterator)
+{
+  std::array<int, 4> src = {4, 5, 6, 7};
+  Span<int> span = src;
+  Vector<int> reversed_vec;
+
+  for (auto it = span.rbegin(); it != span.rend(); ++it) {
+    reversed_vec.append(*it);
+  }
+  EXPECT_EQ(reversed_vec.size(), 4);
+  EXPECT_EQ_ARRAY(reversed_vec.data(), Span({7, 6, 5, 4}).data(), 4);
+}
+
+TEST(span, MutableReverseIterator)
+{
+  std::array<int, 4> src = {4, 5, 6, 7};
+  MutableSpan<int> span = src;
+  Vector<int> reversed_vec;
+
+  for (auto it = span.rbegin(); it != span.rend(); ++it) {
+    reversed_vec.append(*it);
+    *it += 10;
+  }
+  EXPECT_EQ(reversed_vec.size(), 4);
+  EXPECT_EQ_ARRAY(reversed_vec.data(), Span({7, 6, 5, 4}).data(), 4);
+  EXPECT_EQ_ARRAY(src.data(), Span({14, 15, 16, 17}).data(), 4);
+}
+
 }  // namespace blender::tests