How to concatenate many std::vectors?

Question

There is already a question on how to concatenate two vectors: Concatenating two std::vectors. However, I found it appropriate to start a new one, as my question is a bit more specific....

I have two classes that look like this:

class AClass {
public:
    std::vector<double> getCoeffs() {return coeffs;}
private:
    std::vector<double> coeffs;
};

class BClass {
public:
    std::vector<double> getCoeffs() {return ...;}
private:
    std::vector<AClass> aVector;
};

What is the best way (i.e. avoiding unnecessary copying etc.) to concatenate the coefficients from each element in aVector?

My very first attempt was

std::vector<double> BClass::getCoeffs(){
    std::vector<double> coeffs;
    std::vector<double> fcoefs;
    for (int i=0;i<aVector.size();i++){
        fcoefs = aVector[i].getCoeffs();
        for (int j=0;j<fcoefs.size();j++{
            coeffs.push_back(fcoefs[j]);
        }        
    }
    return coeffs;
}

I already know how to avoid the inner for loop (thanks to the above mentioned post), but I am pretty sure, that with the help of some std algorithm this could be done in a single line.

I cannot use C++11 at the moment. Nevertheless, I would also be interested how to do it in C++11 (if there is any advantage over "no C++11").

EDIT: I will try to rephrase the question a bit, to make it more clear. Concatenating two vectors can be done via insert. For my example I would use this:

std::vector<double> BClass::getCoeffs(){
    std::vector<double> coeffs;
    std::vector<double> fcoefs;
    for (int i=0;i<aVector.size();i++){
        fcoefs = aVector[i].getCoeffs();
        coeffs.insert(coeffs.end(),fcoefs.begin(),fcoefs.end());        
    }
    return coeffs;
}

Is it possible to avoid the for loop? I could imagine that it is possible to write something like

for_each(aVector.begin(),aVector.end(),coeffs.insert(coeffs.end(),....);

does this help:http://stackoverflow.com/questions/3177241/best-way-to-concatenate-two-vectors — m0bi5, Feb 16 '15 at 15:54
See this [answer by Ben Voigt](https://stackoverflow.com/questions/17636690/nice-way-to-append-a-vector-to-itself). — , Feb 16 '15 at 15:54
@MohitBhasi thats a duplicate of the other question I was refering to. Maybe I should change the title to "How to concatenate MANY std::vectors" ;) — 463035818_is_not_an_ai, Feb 16 '15 at 15:55
Sum up the size, reserve, and use the range insert in a loop. Not much else you can do. — T.C., Feb 16 '15 at 15:58
Is it intentional that `AClass` returns a copy to the coefficients instead of a const reference, or is this just due to minimisation of the example? — MatthiasB, Feb 16 '15 at 16:07
@MatthiasB Partly it is due to minimisation of the example and partly it is intentional, because both AClass and BClass are supposed to implement the same interface and BClass holds no private copy of the coefficients (however, i could change it of course, by adding a field to BClass that holds all the coefficients) — 463035818_is_not_an_ai, Feb 16 '15 at 16:17
@remyabel the answer you linked to is about how to concatenate two vectors. My question was, how can this be generalized to concatenate many vectors and if possible by using some std algorithm instead of just looping over all vectors to be concatenated. I tried to make it more clear by editing the question. — 463035818_is_not_an_ai, Feb 16 '15 at 16:36

score 2 · Accepted Answer · edited May 23 '17 at 11:43

You can do this in C++11:

std::for_each(aVector.begin(), aVector.end(), [&](AClass i){const auto& temp = i.getCoeffs(); coeffs.insert(coeffs.end(), temp.begin(), temp.end());});

C++03 is more difficult because it lacks lambdas and bind.

About as good as you can do is to use copy in your internal loop:

for(std::vector<AClass>::iterator it = aVector.begin(); it != aVector.end(); ++it){
     const std::vector<double>& temp = it->getCoeffs();
     coeffs.insert(coeffs.end(), temp.begin(), temp.end());
}

These are both essentially the same thing, though you could improve your runtime on both by returning a const std::vector<double>& from getCoeffs.

EDIT:

Arg, just saw you added insert to your question. I thought I was really going to help you out there. As a consolation tip, what you are really asking about here is flattening a std::vector of std::vectors. That has an answer here. But should you have access to boost you should look at: http://www.boost.org/doc/libs/1_57_0/libs/multi_array/doc/reference.html#synopsis

Yakk - Adam Nevraumont · Answer 2 · 2015-02-16T18:18:39.180

1

The first step is to avoid extra allocations. If you know that you won't be growing the return value, you can reserve to exactly the right size.

std::vector<double> BClass::getCoeffs(){
  typedef std::vector<double> dvec;
  dvec coeffs;
  typedef std::vector<AClass> avec;
  typedef std::vector<dvec> ddvec;
  ddvec swap_space;
  swap_space.reserve(aVector.size());
  size_t capacity = 0;
  for (avec::const_iterator it = aVector.begin(); it != aVector.end(); ++it) {
    dvec v = it->getCoeffs(); // RVO elision!
    capacity += v.size();
    swap_space.push_back();
    v.swap(swap_space.back());
  }
  dvec retval;
  retval.reserve(capacity);
  for (ddvec::iterator it = swap_space.begin(); it != swap_space.end(); ++it) {
    retval.insert( retval.end(), it->begin(), it->end() );
  }
  return retval; // NRVO
}

this should avoid more than one allocation per AClass (as forced by their API! You should have a vector<?> const& accessor), plus one allocation for the return value.

Fixing AClass is advised.

edited Feb 16 '15 at 18:18

answered Feb 16 '15 at 17:36

Yakk - Adam Nevraumont

262,606
27
330
524

sorry, but without further explanation I dont understand why it has to be so complicated. By the way, 'AClass::coeffs' are all fixed sized. Would like to use std::array instead but I cannot use C++11. – 463035818_is_not_an_ai Feb 18 '15 at 08:50
@tobi303 well, every get allocates a buffer. So if I call it twice, I allocate twice. But I also want to size the combined buffer before I start appending, so I need to store every sub buffer while I total their length, then append them into the target. The simpler solution -- get, append, repeat instead of get repeat append repeat -- does O(lg(n)) more allocations (n is total number of elements). The above is probabky not worth it, but it does tell me your interface, that copies the buffer, should be improved *if* it is a performance bottleneck. – Yakk - Adam Nevraumont Feb 18 '15 at 11:06
thanks a lot. I will have to take a deeper look to really understand whats going on and what will be the best solution for my application. – 463035818_is_not_an_ai Feb 18 '15 at 12:04

How to concatenate many std::vectors?

2 Answers2