2

While learning about template parameter packs, I'm trying to write a clever, simple function to efficiently append two or more std::vector containers together.

Below are two initial solutions.

Version 1 is elegant but buggy, as it relies on side-effects during the expansion of the parameter pack, and the order of evaluation is undefined.

Version 2 works, but relies on a helper function that requires two cases. Yuck.

Can you see if you can come up with a simpler solution? (For efficiency, the vector data should not be copied more than once.)

#include <vector>
#include <iostream>

// Append all elements of v2 to the end of v1.
template<typename T>
void append_to_vector(std::vector<T>& v1, const std::vector<T>& v2) {
    for (auto& e : v2) v1.push_back(e);
}

// Expand a template parameter pack for side effects.
template<typename... A> void ignore_all(const A&...) { }

// Version 1: Concatenate two or more std::vector<> containers into one.
// Nicely simple, but buggy as the order of evaluation is undefined.
template<typename T, typename... A>
std::vector<T> concat1(std::vector<T> v1, const A&... vr) {
    // Function append_to_vector() returns void, so I enclose it in (..., 1).
    ignore_all((append_to_vector(v1, vr), 1)...);
    // In fact, the evaluation order is right-to-left in gcc and MSVC.
    return v1;
}

// Version 2:
// It works but looks ugly.
template<typename T, typename... A>
void concat2_aux(std::vector<T>& v1, const std::vector<T>& v2) {
    append_to_vector(v1, v2);
}

template<typename T, typename... A>
void concat2_aux(std::vector<T>& v1, const std::vector<T>& v2, const A&... vr) {
    append_to_vector(v1, v2);
    concat2_aux(v1, vr...);
}

template<typename T, typename... A>
std::vector<T> concat2(std::vector<T> v1, const A&... vr) {
    concat2_aux(v1, vr...);
    return v1;
}

int main() {
    const std::vector<int> v1 { 1, 2, 3 };
    const std::vector<int> v2 { 4 };
    const std::vector<int> v3 { 5, 6 };
    for (int i : concat1(v1, v2, v3)) std::cerr << " " << i;
    std::cerr << "\n";          // gcc output is:  1 2 3 5 6 4
    for (int i : concat2(v1, v2, v3)) std::cerr << " " << i;
    std::cerr << "\n";          // gcc output is:  1 2 3 4 5 6
}
Xeo
  • 129,499
  • 52
  • 291
  • 397
Hugues
  • 2,865
  • 1
  • 27
  • 39
  • concat2() looks nice to me. Having 2 overloaded functions to handle the separate cases isn't ugly at all IMHO; it mirrors the way pattern-matching cases are declared for recursive functions in functional languages like Haskell. Also it's easy to understand. – j_random_hacker May 03 '14 at 01:49

3 Answers3

6

A helper type: I dislike using intfor it.

struct do_in_order { template<class T>do_in_order(T&&){}};

Add up sizes:'

template<class V>
std::size_t sum_size( std::size_t& s, V&& v ) {return s+= v.size(); }

Concat. Returns type to be ignored:

template<class V>
do_in_order concat_helper( V& lhs, V const& rhs ) { lhs.insert( lhs.end(), rhs.begin(), rhs.end() ); return {}; }

Micro optimization, and lets you concat vectors of move only types:

template<class V>
do_in_order concat_helper( V& lhs, V && rhs ) { lhs.insert( lhs.end(), std::make_move_iterator(rhs.begin()), std::make_move_iterator(rhs.end()) ); return{}; }

actual function. Above stuff should be in a details namespace:

template< typename T, typename A, typename... Vs >
std::vector<T,A> concat( std::vector<T,A> lhs, Vs&&...vs ){
  std::size s=lhs.size();
  do_in_order _0[]={ sum_size(s,vs)..., 0 };
  lhs.reserve(s);
  do_in_order _1[]={ concat_helper( lhs, std::forward<Vs>(vs) )..., 0 };
  return std::move(lhs); // rvo blocked
}

apologies for any typos.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
  • Thanks for the new perspective; I'll give it a try. Perhaps it's possible to omit `_0[]=` and `_1[]=` so that it creates temporary objects (that transparently get cast to `void`). – Hugues May 03 '14 at 02:38
  • Oops -- in my suggestion the constructor could expand the parameter pack out-of-order. However, it will do the right thing if initialized with an initializer list: `struct do_in_order { template do_in_order(std::initializer_list){} };` – Hugues May 03 '14 at 02:52
  • "// rvo blocked" -- doesn't mean you need to manually move. The language demands a move of the return value here. – Xeo May 03 '14 at 11:54
4

There is a related answer on concatenation of strings: https://stackoverflow.com/a/21806609/1190077 . Adapted here, it looks like:

template<typename T, typename... A>
std::vector<T> concat_version3(std::vector<T> v1, const A&... vr) {
    int unpack[] { (append_to_vector(v1, vr), 0)... };
    (void(unpack));
    return v1;
}

This seems to work!

However, is the evaluation order of the template parameter pack now well-defined, or is it by accident that the compiler did the right thing?

Community
  • 1
  • 1
Hugues
  • 2,865
  • 1
  • 27
  • 39
  • 1
    Yes, expressions in an initializer-list are sequenced left-to-right. – aschepler May 03 '14 at 01:48
  • Does the `...` pack-expansion operator work with the plain old comma operator? If so then couldn't you just write `(append_to_vector(v1, vr)...);` and get rid of the `unpack[]` array altogether? – j_random_hacker May 03 '14 at 01:54
  • @j_random_hacker I think that the pack-expansion must occur within some list context (like argument list or initializer list). Can you please be more specific with your suggestion? thx. – Hugues May 03 '14 at 02:00
  • @Hugues: What I mean is that something like `(123, "Blah", f(42), 456);` is a valid statement in C++ (and even in C), consisting of an expression with 3 calls to the comma operator. The comma operator evaluates its LHS and throws away the result, then evaluates its RHS and returns the value of that. – j_random_hacker May 03 '14 at 02:07
  • You should add a 'sum up `.size()` then `.reserve` pass: no need to waste time reallocating. – Yakk - Adam Nevraumont May 03 '14 at 02:08
  • @Hugues: In fact the parens in the above statement aren't even necessary; they're only needed for disambiguation in the case where it would otherwise look like a multi-argument function call. So e.g. `foo(123, "Blah");` calls `foo()` with 2 args, but `foo((123, "Blah"));` calls `foo()` with just 1 arg, `"Blah"`, which is the result of applying the comma operator to the expressions `123` and `"Blah"`. – j_random_hacker May 03 '14 at 02:10
  • @j_random_hacker `...` does not chain comma operators. It only works in a 'list' like context, such as function parameters **or** an initializer. In the case of an initializer list, order is guaranteed. – Yakk - Adam Nevraumont May 03 '14 at 02:10
  • @Yakk: OK, good to know, but it's a shame -- I can't see what would be lost by allowing `...` to work with comma operators, and obviously this would allow writing code that is both more concise and more transparent, for what is surely a fairly common case (wanting to process a bunch of arguments in left-to-right order). – j_random_hacker May 03 '14 at 02:16
  • @ j_random_hacker I agree this would be a nice feature to add to the language. – Hugues May 03 '14 at 02:19
2

The answer by Yakk (https://stackoverflow.com/a/23439527/1190077) works well.

Here is a polished version, incorporating my improvement to do_in_order and removing the sum_size external function:

// Nice syntax to allow in-order expansion of parameter packs.
struct do_in_order {
    template<typename T> do_in_order(std::initializer_list<T>&&) { }
};

namespace details {
template<typename V> void concat_helper(V& l, const V& r) {
    l.insert(l.end(), r.begin(), r.end());
}
template<class V> void concat_helper(V& l, V&& r) {
    l.insert(l.end(), std::make_move_iterator(r.begin()),
             std::make_move_iterator(r.end()));
}
} // namespace details

template<typename T, typename... A>
std::vector<T> concat(std::vector<T> v1, A&&... vr) {
    std::size_t s = v1.size();
    do_in_order { s += vr.size() ... };
    v1.reserve(s);
    do_in_order { (details::concat_helper(v1, std::forward<A>(vr)), 0)... };
    return std::move(v1);   // rvo blocked
}
Community
  • 1
  • 1
Hugues
  • 2,865
  • 1
  • 27
  • 39