Recursive Lambdas and local references

Question

I need to understand the root of the following problem: I have some code which has to perform recursive traversal of data.I decided to try lambda expression. Here is complete example of my code(well,this is not my actual code but a stub with exactly the same flow):

  struct Item
  {
     std::vector<float> values;
  };
 int main(int argc, char* argv[])
 {
  std::function<void(uint32_t)> Recursive ;
  std::vector<Item> items;
  uint32_t sizes[2] = {7,2};
  uint32_t counter = 0;

  Recursive = [&items,&Recurse,&counter,&sizes](uint32_t c) 
  {
     if (!items.size())
     {
         items.emplace_back();
     }

     auto &currItem = items.back();
     currItem.values.resize(sizes[c++]);

     for (size_t i = 0; i <  currItem.values.size(); i++)
     {
         currItem.values[i]+=5;
         if (i == 3)
         {
             items.emplace_back();
              Recursive (c);
              printf("end\n");
         }
         printf("end\n");
     }
};
 Recursive (counter);
  return 0;
}

The code above grabs and empty vector of Item , in the first call to the function it pushes one Item and performs some operations on the members of Item::values vector. When the i index reaches 3, I call Recursive again. It performs again everything that the previous call has done.But then, after the second call returns, the first loop terminates! That happens because currItem reference doesn't point anymore to its original variable, but to some undefined object. What I am trying to understand is: Does it happen because of the way lambda works? But according to this answer that shouldn't be the problem in my implementation. My second guess, the original reference is lost once the lambda enters its recursive call and pushes the second member with the call to items.emplace_back();. I don't use recursions frequently and I never really encountered such a case before.

You're (potentially) changing the item vector's size during your calls. That can invalidate all references into it - think about what happens if the vector didn't have enough room reserved. — Mat, Feb 08 '18 at 15:39
There are still a number of problems here. `Recurse` is not the same identifier as `Recursive`, and doesn't appear elsewhere in your snippet. I'm not sure why you need to be recursive here, you could just loop over `sizes`. `counter` is unused within the body of `Recursive` — Caleth, Feb 08 '18 at 16:47
@Caleth first, 'Recurse' was a typo,and that's pretty obvious. Second - this whole code , as I said in my question is just a simplified stub of what I am doing in my app. And while you are right that I can do it without recursion,in my real case that would complicate a lot of things. — Michael IV, Feb 08 '18 at 16:55

LoPiTaL · Accepted Answer · 2018-02-08T15:46:12.213

This has nothing to do with recursion nor lambdas.

The main problem is in the call to emplace_back. As stated in cppreference:

If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.

One solution to your problem would be to use integer indexes instead of iterators.

Edit: Not only the iterators are invalidated, also the first element (items.begin()) and the past-the-end element (the return value of items.back()) are invalidated.

You are using the items.back() function to take the value of your currItem variable. After the emplace_back() call in the second call, the currItem variable of the first call is invalidated, thus the loop cannot continue correctly.

to clarify, `auto &currItem = items.back();` takes the last element that can be reallocated elsewhere. — Raxvan, Feb 08 '18 at 15:41

Recursive Lambdas and local references

1 Answers1