Utilities/Containers: New RandomResize implementation with guaranteed asymptotic linear time for all container types (#19974)

(cherry picked from commit ac50034df7fa6cf67b95e0920ca8fbbe8001a510)

1 files changed, 18 insertions, 6 deletions

diff --git a/src/common/Utilities/Containers.h b/src/common/Utilities/Containers.h
index e9bc46d1306..c34761941a6 100644
--- a/src/common/Utilities/Containers.h
+++ b/src/common/Utilities/Containers.h
@@ -53,17 +53,29 @@ namespace Trinity
             return size;
         }
 
+        // resizes <container> to have at most <requestedSize> elements
+        // if it has more than <requestedSize> elements, the elements to keep are selected randomly
         template<class C>
         void RandomResize(C& container, std::size_t requestedSize)
         {
-            uint32 currentSize = uint32(Size(container));
-            while (currentSize > requestedSize)
+            static_assert(std::is_base_of<std::forward_iterator_tag, typename std::iterator_traits<typename C::iterator>::iterator_category>::value, "Invalid container passed to Trinity::Containers::RandomResize");
+            if (Size(container) <= requestedSize)
+                return;
+            auto keepIt = std::begin(container), curIt = std::begin(container);
+            uint32 elementsToKeep = requestedSize, elementsToProcess = Size(container);
+            while (elementsToProcess)
             {
-                auto itr = std::begin(container);
-                std::advance(itr, urand(0, currentSize - 1));
-                container.erase(itr);
-                --currentSize;
+                // this element has chance (elementsToKeep / elementsToProcess) of being kept
+                if (urand(1, elementsToProcess) <= elementsToKeep)
+                {
+                    *keepIt = std::move(*curIt);
+                    ++keepIt;
+                    --elementsToKeep;
+                }
+                ++curIt;
+                --elementsToProcess;
             }
+            container.erase(keepIt, std::end(container));
         }
 
         template<class C, class Predicate>