Optimize array::insert

foonathan · foonathan · commit 427bf803a59f · 2018-05-23T18:35:54.000+02:00
diff --git a/include/foonathan/array/array.hpp b/include/foonathan/array/array.hpp
@@ -269,8 +269,8 @@ namespace foonathan
             template <typename... Args>
             iterator emplace(const_iterator pos, Args&&... args)
             {
-                // note: we emplace at a given position by creating the objects at the back,
-                // then rotating it to the correct position
+                // note: we emplace at a given position by moving elements to create the space
+                // then assigning it at the position
                 //
                 // when the capacity is sufficient, this is almost as efficient as possible,
                 // just one extra swap or so
@@ -279,9 +279,23 @@ namespace foonathan
                 // however this would vastly complicate the interface and just isn't worth it,
                 // as it is the slow path anyway
 
-                auto index = pos - begin();
-                emplace_back(std::forward<Args>(args)...);
-                std::rotate(begin() + index, std::prev(end()), end());
+                auto index = size_type(pos - cbegin());
+                if (index == size())
+                    // just do an emplace back
+                    emplace_back(std::forward<Args>(args)...);
+                else
+                {
+                    // reserve for one more element
+                    reserve(size() + 1u);
+                    auto ptr = view().data() + index;
+
+                    // move all elements following it one over
+                    move_range(ptr, view().data_end(), ptr + 1);
+
+                    // create the element at the now empty position
+                    emplace_impl(ptr, std::forward<Args>(args)...);
+                }
+
                 return begin() + index;
             }
 
@@ -403,6 +417,36 @@ namespace foonathan
                 return array_view<T>(to_pointer<T>(storage_.block().begin()), to_pointer<T>(end_));
             }
 
+            void move_range(T* from_begin, T* from_end, T* to)
+            {
+                // [from_begin, assign_end) can be assigned to [from_begin + assign_range_size, cur_end)
+                // [assign_end, from_end) must be constructed at the back
+                auto cur_end           = to_pointer<T>(end_);
+                auto assign_range_size = cur_end - to;
+                auto assign_end        = from_begin + assign_range_size;
+
+                // do the construction
+                for (auto cur = assign_end; cur != from_end; ++cur)
+                {
+                    construct_object<T>(end_, std::move(*cur));
+                    end_ += sizeof(T);
+                }
+
+                // do the assignment
+                std::move_backward(from_begin, assign_end, cur_end);
+            }
+
+            template <typename Arg>
+            static auto emplace_impl(T* ptr, Arg&& arg) -> decltype(*ptr = std::forward<Arg>(arg))
+            {
+                return *ptr = std::forward<Arg>(arg);
+            }
+            template <typename... Args>
+            static void emplace_impl(T* ptr, Args&&... args)
+            {
+                *ptr = T(std::forward<Args>(args)...);
+            }
+
             template <typename InputIt>
             iterator append_range_impl(std::input_iterator_tag, InputIt begin, InputIt end)
             {
@@ -448,7 +492,7 @@ namespace foonathan
             {
                 auto index = pos - this->begin();
 
-                // again, like with insert, do an append, plus rotate
+                // just do an append plus rotate
                 auto new_begin = append_range(begin, end);
                 std::rotate(this->begin() + index, new_begin, this->end());
 
diff --git a/include/foonathan/array/flat_map.hpp b/include/foonathan/array/flat_map.hpp
@@ -887,16 +887,17 @@ namespace foonathan
                 return size_type(key - iterator_to_pointer(keys_.begin()));
             }
 
+            template <typename Arg>
+            auto assign_value(value_iterator iter, Arg&& arg) noexcept
+                -> decltype(*iter = std::forward<Arg>(arg))
+            {
+                return *iter = std::forward<Arg>(arg);
+            }
             template <typename... Args>
             void assign_value(value_iterator iter, Args&&... args) const
             {
                 *iter = Value(std::forward<Args>(args)...);
             }
-            template <typename Arg>
-            void assign_value(value_iterator iter, Arg&& arg) noexcept
-            {
-                *iter = std::forward<Arg>(arg);
-            }
 
             template <typename InputIt>
             static size_type range_size(std::input_iterator_tag, InputIt, InputIt)
diff --git a/main.cpp b/main.cpp
@@ -4,6 +4,7 @@
 
 #include <algorithm>
 #include <iostream>
+#include <vector>
 
 #include <foonathan/array/bag.hpp>
 #include <foonathan/array/block_storage_new.hpp>
@@ -12,28 +13,6 @@ namespace array = foonathan::array;
 
 int main()
 {
-    using bag = array::bag<int, array::block_storage_new<int, array::default_growth>>;
-
-    bag b;
-    b.insert(1);
-    b.insert(2);
-    b.insert(3);
-    b.insert(4);
-
-    for (auto el : b)
-        std::cout << el << ' ';
-    std::cout << '\n';
-
-    auto iter = std::find(b.begin(), b.end(), 2);
-    b.erase(iter);
-
-    for (auto el : b)
-        std::cout << el << ' ';
-    std::cout << '\n';
-
-    b.insert(5);
-
-    for (auto el : b)
-        std::cout << el << ' ';
-    std::cout << '\n';
+    std::vector<int> vec(7);
+    std::cout << vec.size() << ' ' << vec.capacity() << '\n';
 }
