CODEWITHSUNDEEP
c++vectorstdvector
463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122133

How to concatenate many std::vectors?

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(),....);

Upvotes: 5

Views: 5905

Answers (2)

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275280

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.

Upvotes: 1

Jonathan Mee
Jonathan Mee

Reputation: 38919

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

Upvotes: 3

Related Questions