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, 18 insertions, 2 deletions

diff --git a/source/blender/blenlib/BLI_span.hh b/source/blender/blenlib/BLI_span.hh
index 165814cf23c..5b4d2769f57 100644
--- a/source/blender/blenlib/BLI_span.hh
+++ b/source/blender/blenlib/BLI_span.hh
@@ -213,12 +213,20 @@ template<typename T> class Span {
   {
     return data_;
   }
-
   const T *end() const
   {
     return data_ + size_;
   }
 
+  std::reverse_iterator<const T *> rbegin() const
+  {
+    return std::reverse_iterator<const T *>(this->end());
+  }
+  std::reverse_iterator<const T *> rend() const
+  {
+    return std::reverse_iterator<const T *>(this->begin());
+  }
+
   /**
    * Access an element in the array. This invokes undefined behavior when the index is out of
    * bounds.
@@ -502,12 +510,20 @@ template<typename T> class MutableSpan {
   {
     return data_;
   }
-
   T *end() const
   {
     return data_ + size_;
   }
 
+  std::reverse_iterator<T *> rbegin() const
+  {
+    return std::reverse_iterator<T *>(this->end());
+  }
+  std::reverse_iterator<T *> rend() const
+  {
+    return std::reverse_iterator<T *>(this->begin());
+  }
+
   T &operator[](const int64_t index) const
   {
     BLI_assert(index < this->size());