26

Say I have a binary search function which initializes and uses a lambda:

bool custom_binary_search(std::vector<int> const& search_me)
{
  auto comp = [](int const a, int const b)
    {
      return a < b;
    };

  return std::binary_search(search_me.begin(), search_me.end(), comp);
}

Without pointing out that this is completely redundant and just focusing on the lambda; is it expensive to be declaring and defining that lambda object every time? Should it be static? What would it mean for a lambda to be static?

George Gribkov
  • 3
  • 2
quant
  • 21,507
  • 32
  • 115
  • 211
  • 2
    You can't declare the *lambda expression* static. You can only declare the *variable* `comp` static. In which case it means the same as for any variable. – Kerrek SB Oct 15 '13 at 08:14
  • @KerrekSB I don't understand; if I declare the lambda object static, would this change anything? Could the function still take local parameters just like before? Would it reduce the need to redeclare the variable everytime my function runs? – quant Oct 15 '13 at 08:19
  • 2
    As I said, you can only declare the variable static, i.e. `static auto comp = ...`. And then it will be initialized precisely once, when the control flow first passes the declaration. Since the lambda is stateless, it shouldn't make any difference at all. Even the way it's written now it probably doesn't even generate any code. – Kerrek SB Oct 15 '13 at 08:20
  • 1
    Instead of "declaring and defining a lambda object every time", people usually make it a simple non-member function ([free function](http://stackoverflow.com/q/4861914/183120)) and use it with algorithms. This should also solve the problem of declaring it only once in a header and defining once in some code file. – legends2k Oct 15 '13 at 11:13

2 Answers2

15

The variable 'comp' with type <some anonymous lambda class> can be made static, pretty much as any other local variable, i.e. it is the same variable, pointing to the same memory address, every time this function is run).

However, beware of using closures, which will lead to subtle bugs (pass by value) or runtime errors (pass-by-reference) since the closure objects are also initialized only once:

bool const custom_binary_search(std::vector<int> const& search_me, int search_value, int max)
{
  static auto comp_only_initialized_the_first_time = [max](int const a, int const b)
  {
      return a < b && b < max;
  };

  auto max2 = max;
  static auto comp_error_after_first_time = [&max2](int const a, int const b)
  {
      return a < b && b < max2;
  };

  bool incorrectAfterFirstCall = std::binary_search(std::begin(search_me), std::end(search_me), search_value, comp_only_initialized_the_first_time);
  bool errorAfterFirstCall = std::binary_search(std::begin(search_me), std::end(search_me), search_value, comp_error_after_first_time);

  return false; // does it really matter at this point ?
}

Note that the 'max' parameter is just there to introduce a variable that you might want to capture in your comparator, and the functionality this "custom_binary_search" implements is probably not very useful.

Martin J.
  • 5,028
  • 4
  • 24
  • 41
  • 1
    Is this even possible? I would have assumed that static local variables are initialized before the first time the function is called. Therefore, I assumed that static lambda variables cannot use capturing. – Aaron McDaid Oct 15 '13 at 10:44
  • (I edited the answer for a couple of typos, `(` -> `{` for example.) – Aaron McDaid Oct 15 '13 at 10:57
  • 1
    @AaronMcMaid static local is syntactic sugar for `if (global_var_initialized) global_var = ...)`. So it is initialized on the first call. I also think capturing in a static lambda is a bad idea. max is going to keep the value of the first call. – log0 Oct 15 '13 at 11:18
  • thanks for the edit - I re-edited to make the search value an argument of the top-level function for clarity – Martin J. Oct 15 '13 at 13:50
1

the following code compiles and runs ok in visual studio 2013:

bool const test(int & value)
{
    //edit `&value` into `&` @log0
    static auto comp = [&](int const a, int const b)
    {
        return a < (b + value);
    };

    return comp(2,1);
}

And later:

int q = 1;
cout << test(q); // prints 0 //OK
q++;
cout << test(q); // prints 1 //OK

The compiler will transform any lambda declaration into a regular function and this is done at compile time. The actual definition in the test function is just a regular assignment to the comp variable with the pointer to a c function. Closures are the generaly the same but will work ok only in the scope they were defined. In any other scope they will fail or generate a memory corruption bug.

Defining comp static would only improve the performance insignificantly or not at all.

Hope this helps: Razvan.

Raxvan
  • 6,257
  • 2
  • 25
  • 46
  • @log0, In this particular code snippet, the behaviour is actually defined, I think. The reference that is being held is a reference to `q`, and that variable remains in scope through both calls to `test(q)`. This works because there are references used in both places: taking the arg to the normal function, and capturing it in the lambda. If either of those `&` were missing, there would be a problem. But as it stands, it is defined behaviour. (But it is a strange program!) – Aaron McDaid Oct 15 '13 at 12:06
  • 1
    @Raxvan I does the same thing no? you capture everything by ref, but only use `value` from the closure so `value` is taken by ref as before. – log0 Oct 15 '13 at 12:12
  • @AaronMcDaid It seems very risky for me. the lambda capture a ref to a ref so it may work assuming that the ref `value` will always be stored at the same address regardless of the address of the argument given to `test`. But if the compiler do any optimization like giving directly the address of `q` to the lambda it is going to fail (if you are lucky) at the next call with another argument. I think it is generally not safe to capture in a static lambda. – log0 Oct 15 '13 at 12:25
  • @log0, I think our question can be simplified such that it doesn't involve lambdas. The issue is: What is a 'ref to a ref?'. Consider this: `void f(int &i) { i++; }; void g(int &j) { f(j); };` and then we run this: `int main() { int q = 3; g(q); cout << q; } `. This will print 4, because the reference to `q` survived two function calls - within `f` it was still a ref to `q`.If instead, g was `void g(int j)` then only the local variable in g would have changed. If you agree, and is fully standard defined behaviour, then we can imagine an object that holds the reference for a longer time. – Aaron McDaid Oct 15 '13 at 12:34
  • @AaronMcDaid there is no problem in your example because `q` exists for the lifetime of `g` and `j` exists for the lifetime of `f`. So `i` is always referencing a valid variable during the entire execution of `f`. Once `g` returns, `int & j` does not exist anymore, so any reference pointing to `j` is no longer valid after `g` returns. What @Raxvan is doing is keeping a reference on `j` after `g` returned. – log0 Oct 15 '13 at 12:46
  • I understand my initial example was too simple. It was just a starting point before introducing falling in and out of scope. Consider the output from [this code on ideone](http://ideone.com/dfQlyi). It shows that the address of `q` (the only non-ref int) is the same as the address of the static reference. Therefore, the reference is initialized with an address that will remain valid until the end. It is not a 'reference on `j`' - it's a reference on `q`. I'll add another question in a moment that might help ... (extra: I don't believe this is a compiler optimization - it is standard) – Aaron McDaid Oct 15 '13 at 14:03
  • `q` is an `int`. Everything else is an `int&`. This tells us that there are no other `int`s at any stage. There is no temporary copy of the int. Therefore, there is no temporary value sitting on the stack that can become invalid after it goes out of scope. The question is: how many (non-ref) `int`s exist in these programs? – Aaron McDaid Oct 15 '13 at 14:05
  • @AaronMcDaid rereading the thread I totally agree with you. The reference can only reference `q` directly. The call to test starts to have undefined behavior as soon as the object you call it with the first time get destructed. – log0 Oct 15 '13 at 23:29