[PATCH] Optimize seed_seq construction

[Antony Polukhin <antoshkka@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 322 bytes --]

When std::seed_seq is constructed from random access iterators we can
detect the internal vector size in O(1). Reserving memory for elements
in such cases may avoid multiple memory allocations.

libstdc++-v3/ChangeLog:

        * include/bits/random.tcc: Optimize seed_seq construction.

-- 
Best regards,
Antony Polukhin

[-- Attachment #2: seed_seq_optimize_construction.txt --]
[-- Type: text/plain, Size: 1503 bytes --]

diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc
index bf43970..816bfc1 100644
--- a/libstdc++-v3/include/bits/random.tcc
+++ b/libstdc++-v3/include/bits/random.tcc
@@ -3234,14 +3234,31 @@ namespace __detail
   template<typename _IntType>
     seed_seq::seed_seq(std::initializer_list<_IntType> __il)
     {
+      _M_v.reserve(__il.size());
       for (auto __iter = __il.begin(); __iter != __il.end(); ++__iter)
 	_M_v.push_back(__detail::__mod<result_type,
 		       __detail::_Shift<result_type, 32>::__value>(*__iter));
     }
 
+  template<typename _Vector, typename _InputIterator>
+    void __reserve_if_distance_cheap(_Vector& __vec, _InputIterator __begin,
+      _InputIterator __end, random_access_iterator_tag)
+    {
+      __vec.reserve(__end - __begin);
+    }
+
+  template<typename _Vector, typename _InputIterator, typename _Tag>
+    void __reserve_if_distance_cheap(_Vector&, _InputIterator,
+      _InputIterator, _Tag)
+    {
+      // computing the distance between __begin and __end is not O(1)
+    }
+
   template<typename _InputIterator>
     seed_seq::seed_seq(_InputIterator __begin, _InputIterator __end)
     {
+      std::__reserve_if_distance_cheap(_M_v, __begin, __end,
+          typename iterator_traits<_InputIterator>::iterator_category());
       for (_InputIterator __iter = __begin; __iter != __end; ++__iter)
 	_M_v.push_back(__detail::__mod<result_type,
 		       __detail::_Shift<result_type, 32>::__value>(*__iter));