add move operations, more constructors, fit memory blocks to power-of-two size

2 files changed, 107 insertions, 5 deletions

diff --git a/library/cpp/containers/compact_vector/compact_vector.h b/library/cpp/containers/compact_vector/compact_vector.h
index dbe7473f0c..b3795708a5 100644
--- a/library/cpp/containers/compact_vector/compact_vector.h
+++ b/library/cpp/containers/compact_vector/compact_vector.h
@@ -52,6 +52,32 @@ public:
         }
     }
 
+    TCompactVector(TThis&& that) noexcept
+        : Ptr(nullptr)
+    {
+        Swap(that);
+    }
+
+    TCompactVector(std::initializer_list<T> init)
+        : Ptr(nullptr)
+    {
+        Reserve(init.size());
+        for (const T& val : init) {
+            PushBack(val);
+        }
+    }
+
+    template <class InputIterator>
+    TCompactVector(InputIterator begin, InputIterator end)
+        : Ptr(nullptr)
+    {
+        Reserve(std::distance(begin, end));
+
+        for (auto it = begin; it != end; ++it) {
+            push_back(*it);
+        }
+    }
+
     ~TCompactVector() {
         for (size_t i = 0; i < Size(); ++i) {
             try {
@@ -63,6 +89,17 @@ public:
             free(Header());
     }
 
+    TThis& operator = (TThis&& that) noexcept {
+        Swap(that);
+        return *this;
+    }
+
+    TThis& operator = (std::initializer_list<T> init) {
+        TThis data(init);
+        Swap(data);
+        return *this;
+    }
+
     TIterator Begin() {
         return Ptr;
     }
@@ -95,23 +132,33 @@ public:
         return End();
     }
 
-    void Swap(TThis& that) {
+    void Swap(TThis& that) noexcept {
         DoSwap(Ptr, that.Ptr);
     }
 
     void Reserve(size_t newCapacity) {
         if (newCapacity <= Capacity()) {
         } else if (Ptr == nullptr) {
-            void* mem = ::malloc(sizeof(THeader) + newCapacity * sizeof(T));
+            constexpr size_t maxBlockSize = static_cast<size_t>(1) << (sizeof(size_t) * 8 - 1);
+            constexpr size_t maxCapacity = (maxBlockSize - sizeof(THeader)) / sizeof(T);
+            Y_ENSURE(newCapacity <= maxCapacity);
+
+            const size_t requiredMemSize = sizeof(THeader) + newCapacity * sizeof(T);
+            // most allocators operates pow-of-two memory blocks,
+            // so we try to allocate such memory block to fully utilize its capacity
+            const size_t memSizePowOf2 = FastClp2(requiredMemSize);
+            const size_t realNewCapacity = (memSizePowOf2 - sizeof(THeader)) / sizeof(T);
+            Y_ASSERT(realNewCapacity >= newCapacity);
+
+            void* mem = ::malloc(memSizePowOf2);
             if (mem == nullptr)
                 ythrow yexception() << "out of memory";
             Ptr = (T*)(((THeader*)mem) + 1);
             Header()->Size = 0;
-            Header()->Capacity = newCapacity;
+            Header()->Capacity = realNewCapacity;
         } else {
             TThis copy;
-            size_t realNewCapacity = Max(Capacity() * 2, newCapacity);
-            copy.Reserve(realNewCapacity);
+            copy.Reserve(newCapacity);
             for (TConstIterator it = Begin(); it != End(); ++it) {
                 copy.PushBack(*it);
             }
@@ -145,6 +192,10 @@ public:
         ++(Header()->Size);
     }
 
+    void push_back(const T& elem) {
+        PushBack(elem);
+    }
+
     T& Back() {
         return *(End() - 1);
     }
diff --git a/library/cpp/containers/compact_vector/compact_vector_ut.cpp b/library/cpp/containers/compact_vector/compact_vector_ut.cpp
index 7d413d6575..84cb7b645a 100644
--- a/library/cpp/containers/compact_vector/compact_vector_ut.cpp
+++ b/library/cpp/containers/compact_vector/compact_vector_ut.cpp
@@ -43,4 +43,55 @@ Y_UNIT_TEST_SUITE(TCompactVectorTest) {
         UNIT_ASSERT_VALUES_EQUAL(5u, vector[5]);
         UNIT_ASSERT_VALUES_EQUAL(11u, vector[11]);
     }
+
+    Y_UNIT_TEST(TestInitializerListConstructor) {
+        TCompactVector<ui32> vector = { 4, 8, 10, 3, 5};
+        UNIT_ASSERT_VALUES_EQUAL(5u, vector.Size());
+
+        UNIT_ASSERT_VALUES_EQUAL(4u, vector[0]);
+        UNIT_ASSERT_VALUES_EQUAL(8u, vector[1]);
+        UNIT_ASSERT_VALUES_EQUAL(10u, vector[2]);
+        UNIT_ASSERT_VALUES_EQUAL(3u, vector[3]);
+        UNIT_ASSERT_VALUES_EQUAL(5u, vector[4]);
+    }
+
+    Y_UNIT_TEST(TestIteratorConstructor) {
+        TVector<ui32> origVector = { 4, 8, 10, 3, 5};
+        TCompactVector<ui32> vector(origVector.begin(), origVector.end());
+        UNIT_ASSERT_VALUES_EQUAL(5u, vector.Size());
+
+        UNIT_ASSERT_VALUES_EQUAL(4u, vector[0]);
+        UNIT_ASSERT_VALUES_EQUAL(8u, vector[1]);
+        UNIT_ASSERT_VALUES_EQUAL(10u, vector[2]);
+        UNIT_ASSERT_VALUES_EQUAL(3u, vector[3]);
+        UNIT_ASSERT_VALUES_EQUAL(5u, vector[4]);
+    }
+
+    Y_UNIT_TEST(TestInitializerListCopyOperator) {
+        TCompactVector<double> vector = { 4, 8, 10, 3, 5};
+        UNIT_ASSERT_VALUES_EQUAL(5u, vector.Size());
+
+        vector = { 11, 17, 23 };
+        UNIT_ASSERT_VALUES_EQUAL(3u, vector.Size());
+
+        UNIT_ASSERT_VALUES_EQUAL(11.0, vector[0]);
+        UNIT_ASSERT_VALUES_EQUAL(17.0, vector[1]);
+        UNIT_ASSERT_VALUES_EQUAL(23.0, vector[2]);
+    }
+
+    Y_UNIT_TEST(TestMoveConstructor) {
+        TCompactVector<ui32> vector = { 4, 8, 10, 3, 5};
+        auto it = vector.Begin();
+
+        TCompactVector<ui32> vector2(std::move(vector));
+        UNIT_ASSERT_VALUES_EQUAL(it, vector2.begin());
+
+        UNIT_ASSERT_VALUES_EQUAL(5u, vector2.Size());
+
+        UNIT_ASSERT_VALUES_EQUAL(4u, vector2[0]);
+        UNIT_ASSERT_VALUES_EQUAL(8u, vector2[1]);
+        UNIT_ASSERT_VALUES_EQUAL(10u, vector2[2]);
+        UNIT_ASSERT_VALUES_EQUAL(3u, vector2[3]);
+        UNIT_ASSERT_VALUES_EQUAL(5u, vector2[4]);
+    }
 }