Merging / smoothing subvectors into a single C ++ vector (transform 2d to 1d)

Question

I have vector<vector<int> > Y I want to combine subvectors (name it y) inside Y into one vector<int> . But I do not want to sort them, i.e. Combine them in the order they appear. How can I do this efficiently, possibly using STL algorithms? The std::merge method is combined by sorting, which I do not want.

edits: I want: {{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 smoothing:

 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 really 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 a nested container:

 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 want to move items from the first container to the last (in case the items are only moveable or expensive to copy) use std::move with std::back_inserter or apply std::make_move_operator to each source iterator.

Watch live Coliru

Update: Variadic Concatenation

At first, I expected you to find yourself after a variational solution: let me demonstrate how you can make this much 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 merge dissimilar 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 will (correctly) expect that to_vector is just a convenient short hand for concatenate<std::vector<...>> . Here is full monty, look at 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, this has several performance advantages:

• It calculates the final size of the result and predetermines the memory. This means that there is no need for redistribution.
• It uses range insertion instead of singleton insertion, as in another version. This allows the container to apply some optimizations, especially if the elements are trivially copied (i.e. One memcpy for the inner container).

On the other hand, it only works with a vector, not with a deque or list.