Merging/flattening sub-vectors into a single vector c++ (converting 2d to 1d)

Question

I have vector<vector<int> > Y. I want to merge the sub-vectors (call it y) inside Y into one vector<int>. But I don't want to sort them,i.e, merge them in the order of their occurence. How would I do this efficiently, perhaps by using STL algorithms? The std::merge method merges by sorting which I don't want.

Edits: What I want is: given {{1,6,5},{5,3-1,77},{0},...} return {1,6,5,5,3,-1,77,0,...}

Answer 1

The word for this is concatenation or flatten:

std::vector<int> a { 1,2,3 },
                 b {9,0,-7};

std::vector<int> c(begin(a), end(a));
c.insert(end(c), begin(b), end(b));

Or, indeed simpler:

auto c = a;
c.insert(end(c), begin(b), end(b));

c now contains 1,2,3,9,0,-7

You can generalize this to handle your nested container case:

template <template<typename...> class R=std::vector, 
          typename Top, 
          typename Sub = typename Top::value_type> 
   R<typename Sub::value_type> flatten(Top const& all)
{
    using std::begin;
    using std::end;

    R<typename Sub::value_type> accum;

    for(auto& sub : all)
        accum.insert(end(accum), begin(sub), end(sub));

    return accum;
}

If you wanted to move elements from the first container to the last (in case the elements are moveable only, or expensive to copy) use std::move with std::back_inserter or apply std::make_move_operator to each source iterator.

See it live on Coliru

Update: Variadic concatenation

Initially, I had expected you to be after a variadic solution: let me demonstrate how you can make this a lot more general, so you can say:

 auto x = to_vector(std::vector<int> { 1,2,3 }, std::list<int> { 9,8,11 }, std::set<int> { 42 });

In fact, I made it so general, that you concatenate heterogeneous collections into "arbitrary" containers:

// fun with maps:
auto y = concatenate<std::map<long, std::string> >(
        std::map<int,      const char*> { { 1, "one" }, { 2, "two" } },
        std::map<unsigned, std::string> { { 1, "one" }, { 3, "three" } }            
    );

You'll (correctly) expect that to_vector is just a convenience short-hand for concatenate<std::vector<...>>. Here's the full monty, see it live on Coliru and ideone:

#include <vector>
#include <utility>
#include <iterator>

namespace detail
{
    template <typename R>
    void do_concatenation(R& accum) {}

    template <typename R, typename First, typename... More> 
    void do_concatenation(R& accum, First const& first, More const&... more)
    {
        using std::begin;
        using std::end;
        std::copy(begin(first), end(first), std::inserter(accum, end(accum)));

        do_concatenation(accum, more...);
    }
}

template <typename Result, typename... Containers> 
   Result concatenate(Containers const&... containers)
{
    Result accum;
    detail::do_concatenation(accum, containers...);
    return accum;
}

template <typename First, typename... More> 
   std::vector<typename First::value_type> to_vector(First const& first, More const&... containers)
{
    return concatenate<std::vector<typename First::value_type>>(first, containers...);
}

/// demo
#include <set>
#include <list>
#include <iostream>

#include <map>
#include <string>

int main()
{
    auto x = to_vector(std::vector<int> { 1,2,3 }, std::list<int> { 9,8,11 }, std::set<int> { 42 });

    for (auto i : x)
       std::cout << i << " ";

    std::cout << std::endl;

    // fun with maps:
    auto y = concatenate<std::map<long, std::string> >(
            std::map<int,      const char*> { { 1, "one" }, { 2, "two" } },
            std::map<unsigned, std::string> { { 1, "one" }, { 3, "three" } }            
        );

    for (auto kvp : y)
       std::cout << "(" << kvp.first  << ", " << kvp.second << ")";

}

Output:

1 2 3 9 8 11 42 
(1, one)(2, two)(3, three)

Answer 2

template <typename T>
std::vector<T> flatten(const std::vector<std::vector<T>>& v) {
    std::size_t total_size = 0;
    for (const auto& sub : v)
        total_size += sub.size(); // I wish there was a transform_accumulate
    std::vector<T> result;
    result.reserve(total_size);
    for (const auto& sub : v)
        result.insert(result.end(), sub.begin(), sub.end());
    return result;
}

Compared to @not-sehe's solution, this has a few performance advantages:

• It calculates the final size of the result and preallocates storage. This means there is no need for repeated reallocation.
• It uses range-insert instead of single-element insert as the other version does. This allows the container to apply some optimizations, especially if the elements are trivially copyable (i.e. a single memcpy per inner container).

On the downside, it only works with vector, not deque or list.