0

My goal is to generate vector with pattern {1} given max_=2, {1,2,1} given max_=3, {1,2,1,3,1,2,1} given max_=4... etc

Here is my psuedocode:

std::vector<int> generate_zimin(int max_)
{
    if(max_ == 2)
    {
        return {1};
    }
    else
    {
        return {generate_zimin(max_-1), (max_-1), generate_zimin(max_-1)};
    }
}

How do I insert vectors into an anonymous vector?

edit: 

std::vector<int> generate_zimin(std::vector<int> current, int max_)
{
    if(max_ == 2)
    {
        return {1};
    }
    else
    {
        std::vector<int> prev = generate_zimin(current, max_-1);
        current.insert(current.end(), std::begin(prev), std::end(prev));
        current.push_back(max_-1);
        current.insert(current.end(), std::begin(prev), std::end(prev));
        return current;
    }
}

looks a lot less elegant, and I was just trying to avoid that, but I can see why I was wrong.

Bo Work
  • 135
  • 1
  • 6
  • You don't. Why does it have to be "anonymous"? What's wrong with using a local variable to accumulate the result? – Igor Tandetnik Nov 24 '18 at 03:56
  • There isn't really a way to do it in a one-liner. See this question about concatenating vectors: https://stackoverflow.com/questions/201718/concatenating-two-stdvectors – alter_igel Nov 24 '18 at 03:56
  • @IgorTandetnik By using local variable, I should declare an empty vector at the start of the function, and append generate_zimin(max_-1) to it, then push_back max_-1 to it, then append generate_zimin(max_z-1), then return it? – Bo Work Nov 24 '18 at 04:14

1 Answers1

0

Not only is there no syntax for this, it is a bad idea for performance. You'll be allocating and deallocating vectors on every function call. You should create a single vector at the beginning and use it in all the calls. This could improve performance by a factor of 100.

You can even calculate the total size of the vector at the beginning and reserve() the needed capacity.

John Zwinck
  • 239,568
  • 38
  • 324
  • 436
  • How would I reserve the needed capacity when its function is also recursive? A generate_zimin(n)'s total space = 2*generate_zimin(n-1)'s total space +1. I must be overthinking this too much – Bo Work Nov 24 '18 at 04:10
  • Total capacities are 1, 3, 7, 15, 31. Punch that into a search and voila: https://oeis.org/A000225 - it is `2^n - 1`. – John Zwinck Nov 24 '18 at 04:24