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
V concatenate( V&& v )
{
  return v;
}

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

// usage:
std::vector v1 = { 1, 2, 3 };
std::vector v2 = { 4, 5, 6 };
std::vector v3 = { 7, 8, 9 };
std::vector v12 = concatenate( v1, v2 );
std::vector v123 = concatenate( v1, v2, v3 );
std::vector vm12 = concatenate( std::move(v1), v2 );
std::vector 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
std::size_t get_reserve_amount( V1 const& v1, V2 const& v2, Rest const&... 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
std::decay_t concatenate( V1&& v1, V2&& v2, Rest&&... rest )
{
    using exp = int[];

    std::decay_t 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 
#include 
#include 

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

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

    std::size_t loop_count{ 1'000 };

    auto test = [ &, lc = loop_count ]
    {
        std::vector 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 ( test ).count() << '\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

StackExchange Code Review Q#141433, answer score: 8