https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81476
--- Comment #12 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #10)
> Inserting an InputRange (not even Forward) at the beginning of a vector is
> really a misuse of vector. It is true that we can do better than what
> libstdc++ currently does, though we shouldn't encourage the practice.
Completely agreed.
> Trivial idea would be first to copy the InputRange to some array (either
> something dynamic like a vector, or by block to a fixed size buffer), then
> insert that. Variants include tricks like inserting the InputRange at the
> end of the vector, then calling std::rotate to move it to the right position.
Right, with this patch:
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -617,11 +617,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
_M_range_insert(iterator __pos, _InputIterator __first,
_InputIterator __last, std::input_iterator_tag)
{
- for (; __first != __last; ++__first)
- {
- __pos = insert(__pos, *__first);
- ++__pos;
- }
+ vector __tmp(__first, __last, get_allocator());
+ insert(__pos, __tmp.begin(), __tmp.end());
}
template<typename _Tp, typename _Alloc>
I get these times for -O2:
Insert directly: 11593
1000000
Insert from range: 14070
1000000
Rather than:
Insert directly: 11976
1000000
Insert from range: 11383109
1000000
Or using clang and libc++ with -O2:
Insert directly: 13327
1000000
Insert from range: 674060
1000000
