5
\$\begingroup\$

I'd like to create a function that can concatenate vectors or strings. It must

  1. Keep correct order
  2. Be optimal

This is the solution I came up with:

template<typename V>
V concatenate( V&& v )
{
  return v;
}

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

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

Is my argument forwarding correct here? Is this the simplest solution?

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Vogel612 Sep 16 '16 at 11:42
7
\$\begingroup\$

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<typename V1, typename V2, typename... Rest>
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<typename V1, typename V2, typename... Rest>
std::decay_t<V1> concatenate( V1&& v1, V2&& v2, Rest&&... rest )
{
    using exp = int[];

    std::decay_t<V1> 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 <iostream>
#include <vector>
#include <chrono>

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

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

    std::size_t loop_count{ 1'000 };

    auto test = [ &, lc = loop_count ]
    {
        std::vector<int> 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 << measure<ms, hrc>( 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

\$\endgroup\$
  • \$\begingroup\$ What's the name for the pattern that describes this: (void)exp{ 0, ( ( size_sum += rest.size() ), void(), 0 )... }; ? \$\endgroup\$ – cloakedlearning Sep 15 '16 at 20:15
  • \$\begingroup\$ @cloakedlearning I added a link at the end of the answer. \$\endgroup\$ – user2296177 Sep 15 '16 at 20:20
  • \$\begingroup\$ Excellent ideas. I didn't know about std::decay_t, that's really useful. Also I agree that using reserve makes a big improvement to the performance. The use of move operations is actually not that useful I found out, because it is very likely that all items have to be copied once anyway. \$\endgroup\$ – Mathijs Sep 16 '16 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.