Concatenate two containers, e.g. vector or strings I'd like to create a function that can concatenate vectors or strings. It must


Keep correct order
Be optimal


This is the solution I came up with:

template&lt;typename V&gt;
V concatenate( V&amp;&amp; v )
{
  return v;
}

template&lt;typename V1, typename V2, typename... Rest&gt;
V1 concatenate( V1 v1, V2&amp;&amp; v2, Rest&amp;&amp;... rest)
{
  v1.insert( v1.end(), v2.begin(), v2.end() );
  return concatenate( std::move(v1), std::forward&lt;Rest&gt;(rest)... );
}

// usage:
std::vector&lt;int&gt; v1 = { 1, 2, 3 };
std::vector&lt;int&gt; v2 = { 4, 5, 6 };
std::vector&lt;int&gt; v3 = { 7, 8, 9 };
std::vector&lt;int&gt; v12 = concatenate( v1, v2 );
std::vector&lt;int&gt; v123 = concatenate( v1, v2, v3 );
std::vector&lt;int&gt; vm12 = concatenate( std::move(v1), v2 );
std::vector&lt;int&gt; vm23 = concatenate( v2, std::move(v3) );


Is my argument forwarding correct here? Is this the simplest solution?
Your current strategy will cause more reallocations than you need to, which is not efficient. You already have all of your vector parameters, so you simply need to get their size, and reserve that amount for the output vector.

template&lt;typename V1, typename V2, typename... Rest&gt;
std::size_t get_reserve_amount( V1 const&amp; v1, V2 const&amp; v2, Rest const&amp;... rest ) noexcept
{
    using exp = int[];

    std::size_t size_sum{ v1.size() + v2.size() };
    (void)exp{ 0, ( ( size_sum += rest.size() ), void(), 0 )... };

    return size_sum;
}





Create an output vector, call reserve with the result from get_reserve_amount().
Use the same technique from above to insert elements into the vector.
We also remove the single element concatenate() overload.


Using those suggestions, we get rid of recursion completely in the concatenate function.

template&lt;typename V1, typename V2, typename... Rest&gt;
std::decay_t&lt;V1&gt; concatenate( V1&amp;&amp; v1, V2&amp;&amp; v2, Rest&amp;&amp;... rest )
{
    using exp = int[];

    std::decay_t&lt;V1&gt; v;
    v.reserve( get_reserve_amount( v1, v2, rest... ) );

    v.insert( v.cend(), v1.cbegin(), v1.cend() );
    v.insert( v.cend(), v2.cbegin(), v2.cend() );

    (void) exp
    { 0, ( ( v.insert( v.cend(), rest.cbegin(), rest.cend() ) ), void(), 0 )... };

    return v;
}


Usage remains the same.



Here's a couple of timing (in milliseconds) tests to show you how big of a difference this makes.

Before reserve: 1061, 1062, 1058

After reserve: 332, 331, 330

Here is my timing test code:

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;chrono&gt;

template &lt;class TimeUnit, class Clock, class F, class... FArgs&gt;
TimeUnit measure( F&amp;&amp; f, FArgs&amp;&amp;... f_args )
{
    auto t0{ Clock::now() };
    std::forward&lt;F&gt;( f )( std::forward&lt;FArgs&gt;( f_args )... );
    return std::chrono::duration_cast&lt;TimeUnit&gt;( Clock::now() - t0 );
}

int main()
{
    std::vector&lt;int&gt; v0( 11'000, 1 );
    std::vector&lt;int&gt; v1( 33'000, 3 );
    std::vector&lt;int&gt; v2( 55'000, 5 );
    std::vector&lt;int&gt; v3( 77'000, 7 );
    std::vector&lt;int&gt; v4( 99'000, 9 );

    std::size_t loop_count{ 1'000 };

    auto test = [ &amp;, lc = loop_count ]
    {
        std::vector&lt;int&gt; v;
        for ( std::size_t i{ 0 }; i != lc; ++i )
        {
            v = concatenate( v0, v1, v2, v3, v4 );
        }
    };

    using ms = std::chrono::milliseconds;
    using hrc = std::chrono::high_resolution_clock;

    std::cout &lt;&lt; measure&lt;ms, hrc&gt;( test ).count() &lt;&lt; '\n';
}


You can most likely optimize this further by using move operations when concatenating.

The expanding pattern is explained very well here:

https://stackoverflow.com/a/25683817/2296177