Path: csiph.com!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c++
Subject: Re: thread about the pros and cons of lambdas, but more about cons
Date: Thu, 26 Sep 2024 10:27:13 -0700
Organization: A noiseless patient Spider
Lines: 161
Message-ID: <86y13e5nri.fsf@linuxsc.com>
References: <20240925195423.00007ecc@yahoo.com> <871q17idqr.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Thu, 26 Sep 2024 19:27:14 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="fcae6191366e67ac7893d7838d1abab6"; logging-data="284655"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/v6cReGMIHcHugG9jef1/N4KH/gcDbUxY="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:ANG4H/OmLV5NWCvGtgGHN/YJR9E= sha1:+0KAgovC9hEPCzMAlpJsR29FoPQ=
Xref: csiph.com comp.lang.c++:120386

Ben Bacarisse <ben@bsb.me.uk> writes:

> Michael S <already5chosen@yahoo.com> writes:

[...]

>> Some time ago on comp.lang.c we had very long thread about
>> floodfill4 algorithm (that both myself and TimR took more
>> seriously than an issue deserves, but that's off topic).
>>
>> Today I coded two implementations of original brute-force
>> recursive algorithm.
>>
>> // floodfill_recursive_nested.
>> // Implementation is in none-tricky C++
>> // Very similar to what can be done in C
>>
>> #include <cstddef>
>>
>> int floodfill4(
>>   unsigned char *grey,
>>   int width, int height,
>>   int x, int y,
>>   unsigned char target, unsigned char dest)
>> {
>>   if (width < 1 || height < 1)
>>     return 0;
>>   if (x < 0 || x >= width || y < 0 || y >= height)
>>     return 0;
>>
>>   size_t w = width, h = height;
>>   if (grey[y*w+x] != target)
>>     return 0;
>>
>>   struct {
>>     unsigned char *grey;
>>     size_t width, height;
>>     unsigned char target, dest;
>>     void core(size_t x, size_t y) const
>>     {
>>       if (x < width && y < height) {
>>         auto idx = y*width+x;
>>         if (grey[idx] == target) {
>>           grey[idx] = dest;
>>           core(x - 1, y);
>>           core(x + 1, y);
>>           core(x, y - 1);
>>           core(x, y + 1);
>>         }
>>       }
>>     }
>>   } context = {
>>     .grey = grey,
>>     .width = w, .height = h,
>>     .target = target, .dest = dest,
>>   };
>>   context.core(x, y);
>>   return 1;
>> }
>>
>> // end of floodfill_recursive_nested.
>>
>>
>>
>> // floodfill_recursive_lambda.
>> // Implementation in tricky C++
>> // C can not do it
>>
>> #include <cstddef>
>>
>> int floodfill4(
>>   unsigned char *grey,
>>   int width, int height,
>>   int x, int y,
>>   unsigned char target, unsigned char dest)
>> {
>>   if (width < 1 || height < 1)
>>     return 0;
>>   if (x < 0 || x >= width || y < 0 || y >= height)
>>     return 0;
>>
>>   size_t w = width, h = height;
>>   if (grey[y*w+x] != target)
>>     return 0;
>>
>>   auto core = [=] (auto& a_ref, size_t x, size_t y) {
>>     if (x >= w || y >= h)
>>       return;
>>     auto idx = y*w+x;
>>     if (grey[idx] == target) {
>>       grey[idx] = dest;
>>       a_ref(a_ref, x - 1, y);
>>       a_ref(a_ref, x + 1, y);
>>       a_ref(a_ref, x, y - 1);
>>       a_ref(a_ref, x, y + 1);
>>     }
>>   };
>>   core(core, x, y);
>>   return 1;
>> }
>>
>> // end of floodfill_recursive_lambda.
>>
>>
>> In the second variant in order to make it compile at all I had to
>> uses very dirty trick with lambda passed as parameter to itself.
>> I copied it from Stack Overflow, but don't pretend to understand
>> why it works and why it needed in the first place.
>
> For this part the answer is simple.  The lambda only captures
> names that are defined at its point of definition, and core is not
> defined until the end of the declarator which include the
> initialisation -- the lambda you are defining.  The lambda stored
> in 'core', can't therefore refer to the name core because core was
> not defined before the lambda.

This explanation isn't right.  In both C and C++ a declared name is
available as soon as its declarator is complete, and declarators are
complete before the following initializer (if any).  The following code
compiles just fine:

  #include <functional>

  int revised_floodfill4(
    unsigned char *const grey,
    int width, int height,
    int x, int y,
    unsigned char target, unsigned char dest)
  {
    if (width < 1 || height < 1)
      return 0;
    if (x < 0 || x >= width || y < 0 || y >= height)
      return 0;

    const size_t w = width, h = height;
    if (grey[y*w+x] != target)
      return 0;

    std::function<void(size_t, size_t)> core = [=]
    (size_t x, size_t y) {
      if (x >= w || y >= h)
        return;
      auto idx = y*w+x;
      if (grey[idx] == target) {
        grey[idx] = dest;
        core(x - 1, y);
        core(x + 1, y);
        core(x, y - 1);
        core(x, y + 1);
      }
    };
    core(x, y);
    return 1;
  }

The problem with the earlier definition is not the use of 'core' in
the body of the lambda, but the 'auto' part of the declaration.
Because the type of 'core' is not yet known, it can't be used in the
body.  Once that problem is fixed by giving 'core' a specific type,
there is no problem calling it recursively in the body of the
lambda.