initial vector list

3 files changed, 46 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_vector_list.hh b/source/blender/blenlib/BLI_vector_list.hh
new file mode 100644
index 00000000000..cefd60b88bd
--- /dev/null
+++ b/source/blender/blenlib/BLI_vector_list.hh
@@ -0,0 +1,37 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#pragma once
+
+/** \file
+ * \ingroup bli
+ *
+ * A `blender::VectorList` is a dynamically growing ordered container for values of type T.
+ * It is *not* guaranteed that all values will be stored in one contiguous array. Instead, multiple
+ * arrays may be used.
+ *
+ * Comparison to `blender::Vector`:
+ * - `VectorList` has better performance when appending many elements, because it does not have to
+ *   move existing values.
+ * - This also means that `VectorList` can be used with types that cannot be moved.
+ * - A `VectorList` can not be indexed efficiently. So while the container is ordered, one can not
+ *   efficiently get the value at a specific index.
+ * - Iterating over a `VectorList` is a little bit slower, because it may have to iterate over
+ *   multiple arrays. That is likely negligible in most cases.
+ *
+ * `VectorList` should be used instead of `Vector` when the following two statements are true:
+ * - The elements do not have to be in a contiguous array.
+ * - The elements do not have to be accessed with an index.
+ */
+
+#include "BLI_allocator.hh"
+#include "BLI_memory_utils.hh"
+
+namespace blender {
+
+template<typename T,
+         int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(T)),
+         typename Allocator = GuardedAllocator>
+class VectorList {
+};
+
+}  // namespace blender
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index d87c60e6099..dddb073fe76 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -330,6 +330,7 @@ set(SRC
   BLI_uvproject.h
   BLI_vector.hh
   BLI_vector_adaptor.hh
+  BLI_vector_list.hh
   BLI_vector_set.hh
   BLI_vector_set_slots.hh
   BLI_virtual_array.hh
@@ -494,6 +495,7 @@ if(WITH_GTESTS)
     tests/BLI_uuid_test.cc
     tests/BLI_vector_set_test.cc
     tests/BLI_vector_test.cc
+    tests/BLI_vector_list_test.cc
     tests/BLI_virtual_array_test.cc
 
     tests/BLI_exception_safety_test_utils.hh
diff --git a/source/blender/blenlib/tests/BLI_vector_list_test.cc b/source/blender/blenlib/tests/BLI_vector_list_test.cc
new file mode 100644
index 00000000000..3219c573956
--- /dev/null
+++ b/source/blender/blenlib/tests/BLI_vector_list_test.cc
@@ -0,0 +1,7 @@
+/* SPDX-License-Identifier: Apache-2.0 */
+
+#include "BLI_vector_list.hh"
+#include "testing/testing.h"
+
+namespace blender::tests {
+}