我的征尘是星辰大海。。。

The dirt and dust from my pilgrimage forms oceans of stars...

-------当记忆的篇章变得零碎，当追忆的图片变得模糊，我们只能求助于数字存储的永恒的回忆

作者:黄教授

二〇二二

Lambda, Lambda, Lambda

1. Every Lambda Is Unique

   For quite some time, I have been struggling to grasp the true nature of lambda which is one of the most significant feature for modern C++, in my personal opinion. The best way of learning is probably practice. Let's go!

   Here is a small use case. Let's image that we want to have a method that may require some customization of data processing. For example, if you are writing a hash function or a encyption method, then one of basic idea is to give a callback method which takes an integer parameter and do some work and return an integer. Obviously this small callback is a candidate for lambda.

   
   auto lambda=[](int n){return n+1;};
   int processing(int input,  decltype(lambda) lam){
   	return lam(input);
   }
   int main(){
   	processing(43, lambda);
   	return 0;
   }
   

   So far so good. Suddenly you want to try a different algorithm and it is natural for you to just plugin a new lambda into our method.

   
   processing(43, [](int n){return n+2;}); // It cannot compile!
   

   To your surprise, it cannot compile! Why? After some research, you realize that because each lambda is itself an anonymous unique class. So, compiler considers the new defined lambda is an incompatible class. And also you found some tips to make the code work by adding a mysterious "+" before lambda's capture expression:

   auto lambda=+[](int n){return n+1;};

   Now, it works!

So, this is the first step of our little adventure into the wonderland of Lambda. You can check the code here.

Composite Function

According to google, the definition of composite function is "a function made of other functions, where the output of one is the input to the other". For example, f(x) = 2*x+3 is a composite function of f(x)=2*x and f(x)=x+3. How do we represent this in c++?

int f1(int x){ return 2*x;}
int f2(int x){ return x+2;}
int composite(int x){
    return f2(f1(x));
}

This is natural in mathematics. However, it is not very convenient for programming because in c++, it is more natural to pass parameters. Considering you have a pipe line of operations and want to serialize calling them. How can we do it?

/*suppose we have a series of functions all take a parameter
 of double and returns a double with some operation*/

    auto plus1=[](double n){return n+2.0;}
    auto minus2=[](double n){return n-2.0;};
    auto multiply2=[](double n){return n*2.0;};
    auto divided2=[](double n){return n/2.0;};
    // we want to pass all functions as parameter like following
    compose(plus1,minus2,multiply2,divided2, 100.0);

The advantage of doing so is that we can programmatically try different of permutations to call them and compare possible results.

    tuple t(plus1, minus2, multiply2, divided2);
    auto seq1=index_sequence<0,1,2,3>{};
    auto seq2=index_sequence<0,2,1,3>{};
    auto seq3=index_sequence<2,3,1,0>{};
    auto lambda=[&t]<size_t...Is>(index_sequence<Is...>seq){
        return compose(get<Is>(t)..., 100.0);
    };
    cout<<lambda(seq1)<<endl;
    cout<<lambda(seq2)<<endl;
    cout<<lambda(seq3)<<endl;

There are other potentials of using compose function. Now it is time to reveal how we implement this "compose" function which is actually quite straight-forward by using "is_invocable_v" and "invoke". It recursively

template<typename F, typename...Args>
auto compose(F&& call, Args&&...args){
    if constexpr (is_invocable_v<F, Args...>){
        return invoke(forward<decay_t<F>>(call), forward<decay_t<Args>>(args)...);
    }else{
        return compose(forward<decay_t<F>>(call), compose(args...));
    }
}

Here is the code in compiler explorer.

A pointer pointing to nothing

The other day I felt curious about default_delete which is a default parameter of new operator. And interestingly, it has a static_cast to requires the size of type it points must be non-zero: sizeof(_Tp)>0

void operator()(_Tp* __ptr) const {
    static_assert(!is_void<_Tp>::value,
              "can't delete pointer to incomplete type");
    static_assert(sizeof(_Tp)>0,
              "can't delete pointer to incomplete type");
    delete __ptr;
}

This makes me wonder why this is necessary and can we truly new a type with sizeof zero?

At beginning, I thought about an empty struct like struct A{}; However, by c++ standard, empty struct has size of 1. i.e. sizeof(A) is equal to 1.

Then I am thinking about an empty array like int[0]; Can we new a pointer pointing to a type int[0]? Obviously it is not possible by convention because using new int[0] will only give you a pointer to int.

How about we use typedef? It is effectively no difference than normal new int[0]. For example,

typedef int EmptyInt[0];

Then you will see you still get a pointer point to int, not our expected type int[0].

    auto new_ptr=new EmptyInt;
    static_assert(is_same_v<decltype(new_ptr), int*>);
    static_assert(sizeof(*new_ptr)==sizeof(int));
    delete[]new_ptr;

How about we use traditional malloc?

    auto malloc_ptr=static_cast<EmptyInt*>(malloc(sizeof(EmptyInt)));
    static_assert(is_same_v<decltype(malloc_ptr), EmptyInt*>);
    static_assert(sizeof(EmptyInt)==0);
    free(malloc_ptr);

Yes, we can! the pointer variable malloc_ptr is pointing to a type EmptyInt (aka int[0] by typedef) which has size of 0.

Well, all this is a wasting-time meaningless game because what is the usage of a pointer pointing to nothing? I cannot imagine. But the root cause is that malloc(0) is allowed and returns a valid pointer for almost all compiler! Why do compilers allow to return a valid pointer when user really has nothing to point to?

All I can explain to myself is that the famous quote I heard somewhere: C++ does NOT prevent programmer to shoot himself! That is the price of freedom. Is zero-length-array completely useless? Maybe not, see GCC explanation here.

Declaring zero-length arrays is allowed in GNU C as an extension. A zero-length array can be useful as the last element of a structure that is really a header for a variable-length object:

struct line{
  int length;
  char contents[0];
};

struct line *thisline = (struct line *)
  malloc (sizeof (struct line) + this_length);
thisline->length = this_length;

Create our own lambda

In my last article, I have shown that it is possible to mimic lambda by implement the functor's conversion operator. However, everything is hard coded and user has to do all this tedious boiler-plate work. Here I show we can automated this procedure by using so-called curiously recurring template pattern (CRTP).

Just recall that lambda has a pre-defined operator+() that will return a function pointer with identical return type and argument list as its operator (). We will define a base template class FunctorBase for other functor to inherit from.

FunctorBase takes template argument Derived of type of functor which inherits from FunctorBase. The rest template argument is the return type R and arguments list Args... of our functor's operator (). FunctorBase will define a type of function pointer FunPtr that its operator+() will return. So does a converting operator FunPtr().

template<typename Derived, typename R, typename...Args>
struct FunctorBase{
    using FunPtr=R(*)(Args...);
    operator FunPtr() const {
        auto lambda=+[](Args...args)->R{
            auto ptr=mem_fn(&Derived::operator());
            return ptr(Derived{}, args...);
        };
        return lambda;
    }
    FunPtr operator+()const{
        return static_cast<FunPtr>(Derived{});
    }
};

Now lets define functor and it inherits from our FunctoBase. It then defines its operator() with return type string and arguments list of const string&, int, double.

struct Functor: public FunctorBase<Functor, string, const string&, int, double>
    string operator()(const string& name, int age,  double salary){
        cout<<__PRETTY_FUNCTION__<<endl;
        stringstream ss;
        ss<<"name:"<<name<<"\tage:"<<age<<"\tsalary:"<<salary<<endl;
        return ss.str();
    }
};

Since we uses CRTP inheritance, our functor will automatically acquire the ability to have operator+() and converting operator Functor().

    // operator+ returns function pointer
    auto ptr1=+Functor{};
    cout<<ptr1("Alice", 5, 105.25)<<endl;
    //explicit cast functor to a function pointer
    Functor::FunPtr ptr2=Functor{};
    cout<<ptr2("Bob", 15, 135.55)<<endl;

This is the expected result:

std::string Functor::operator()(const std::string &, int, double)
name:Alice	age:5	salary:105.25


std::string Functor::operator()(const std::string &, int, double)
name:Bob	age:15	salary:135.55

Here is the complete code.

std::get for index_sequence

From time to time, std::get<N> for a tuple is such a handy tool which makes me feel that I should have an overloaded version for index_sequence because it is one of most basic thing to do meta programming.

The natural thought is to use recursion which is similar as get<N> for tuple.

template< size_t N, size_t Head, size_t...Is>
requires (N< 1+sizeof...(Is))
constexpr size_t get(index_sequence<Head, Is...>seq){
    if constexpr (N==0) {
        return Head;
    }else{
        return get<N-1>(index_sequence<Is...>{});
    }
}

Isn't it a shame to use recursive function for such a trivial job? Why cannot I take advantage of array's random access for a sequence? But first of all, I need to convert index_sequence to an array.

template<size_t...Is>
struct index_sequence_to_array{
    constexpr static array<size_t, sizeof...(Is)> value{Is...}; 
};

Then implement get<N> is just a piece of cake.

template<size_t N,size_t...Is>requires (N<sizeof...(Is))
size_t get(index_sequence<Is...>seq){    
    return index_sequence_to_array<Is...>::value[N];
}

Here is a little test

    auto seq=make_index_sequence<5>{}
    cout<<(get<0>(seq))<<endl;
    cout<<(get<1>(seq))<<endl;
    cout<<(get<2>(seq))<<endl;
    cout<<(get<3>(seq))<<endl;
    cout<<(get<4>(seq))<<endl;
    // compilation fails due to constraint violation
    //cout<<(get<5>(seq))<<endl;

Interestingly, the two version of get can co-exist without any issue. It is hard to say which one is used by compiler. The first non-error one?

Here is the complete code.

next_permutation for index_sequence

I always consider next_permutation is very useful for index_sequence. However, implement it requires a lot of work, at least it is in my case.

In my last article, I have shown how to efficiently implement get<N> for index_sequencce. Now, we need more helper function. But before that, let's see the algorithm of next_permutation.

1. find_longest_non_increasing_suffix: We need to start from the last of sequence and return the index of "peak" point where non-increasing suffix changes to increasing.

template<size_t...Is> requires (sizeof...(Is)>1)
constexpr size_t find_longest_non_increasing_suffix(index_sequence<Is...>seq){
    auto ary=index_sequence_to_array<Is...>::value;
    size_t back=sizeof...(Is)-1;
    size_t front=back-1;
    while (!(ary[front]<ary[back])){
        if (front==0){
            return 0;
        }
        front--;
        back--;
    }
    return back;
}

2. find_pivot_successor: From result of above find_longest_non_increasing_suffix, the pivot is just one more left step. And the pivot_successor is the one we want to do swap next step.

// find_longest_non_increasing_suffix already has constraints
template<size_t Pivot, size_t...Is> 
constexpr size_t find_pivot_successor(index_sequence<Is...>seq){
    auto ary=index_sequence_to_array<Is...>::value;
    size_t last=sizeof...(Is)-1;
    while (!(ary[Pivot]<ary[last])){ last--;}
    return last;
}

3. So far so good, we can all use "get<N>" from last article. However, our next "swap" and "reverse" index_sequence requires a lot of efforts.

template<size_t...Seq1, size_t...Seq2>
constexpr auto merge_index_sequence(index_sequence<Seq1...>seq1, index_sequence<Seq2...>seq2){
    return index_sequence<Seq1..., Seq2...>{};
}
template<size_t N, size_t...Is>
constexpr auto add_index_sequence_N(index_sequence<Is...>seq){
    return index_sequence<Is+N...>{};
}
template<size_t N, size_t Size> requires (N<Size-1)
constexpr auto make_index_sequence_without_N(){
    return merge_index_sequence(make_index_sequence<N>{},
            add_index_sequence_N<N+1>(make_index_sequence<Size-N-1>{}));
}
template<size_t N, size_t...Is>
constexpr auto remove_index_N(index_sequence<Is...>seq){
    return [seq]<size_t...Indexes>(index_sequence<Indexes...>s){
        return index_sequence<get<Indexes>(seq)...>{};
    }(make_index_sequence_without_N<N, sizeof...(Is)>());
}
template<size_t Start, size_t End, size_t...Is>
requires (Start<=End && End<= sizeof...(Is))
constexpr auto get_sub_index_sequence(index_sequence<Is...>seq){
    return [seq]<size_t...Indexes>(index_sequence<Indexes...>s){
        return index_sequence<get<Indexes>(seq)...>{};
    }(add_index_sequence_N<Start>(make_index_sequence<End-Start>{}));
}
template<size_t N, size_t...Is>
constexpr auto append_index_N(index_sequence<Is...>seq){
    return index_sequence<Is..., N>{};
}

These functions are used for a seemingly "simple" swap operation because we have to divide sequence into "three" parts and merge them together.

template<size_t M, size_t N, size_t...Is> requires(M<=N && N<sizeof...(Is)
constexpr auto swap_index_sequence_M_N(index_sequence<Is...>seq){
    if constexpr (M==N){
        return seq;
    }else{
        auto seq1=append_index_N<get<N>(seq)>(get_sub_index_sequence<0, M>(seq)); // exclude index M
        auto seq2=merge_index_sequence(seq1, get_sub_index_sequence<M+1, N>(seq));
        return merge_index_sequence(append_index_N<get<M>(seq)>(seq2),
                get_sub_index_sequence<N+1, sizeof...(Is)>(seq));
    }
})

4. reverse is surprisingly easier compared with swap as long as you know how to make a reversed index sequence.

template<size_t N>
constexpr auto make_reverse_index_sequence(){
    return []<size_t...Indexes>(index_sequence<Indexes...>seq){
        if constexpr(N>0) return index_sequence<N-1-Indexes...>{};
        else return seq;
    }(make_index_sequence<N>{});
}
template<size_t...Is>
constexpr auto reverse_index_sequence(index_sequence<Is...>seq){
    return [seq]<size_t...Indexes>(index_sequence<Indexes...>s){
        return index_sequence<get<Indexes>(seq)...>{};
    }(make_reverse_index_sequence<sizeof...(Is)>());
}

5. So, finally this is how permutation is made. Pay attention to those "constexpr" keywords because without it program can go to some branches which you don't expect. This is the trick of compile-time programming.

template<size_t...Is>
constexpr auto next_permutation_sequence(index_sequence<Is...>seq){
    if constexpr (sizeof...(Is)<2){
        return seq;
    }else {
        constexpr size_t suffix_start=find_longest_non_increasing_suffix(seq);
        if constexpr (suffix_start==0)return seq;// the last one
        constexpr size_t pivot=suffix_start-1;
        constexpr size_t pivot_successor=find_pivot_successor<pivot>(seq);
        constexpr auto seq1=swap_index_sequence_M_N<pivot, pivot_successor>(seq);
        constexpr auto seq2=reverse_index_sequence(get_sub_index_sequence<suffix_start, sizeof...(Is)>(seq1));
        return merge_index_sequence(get_sub_index_sequence<0, suffix_start>(seq1), seq2);
    }
}

The complete code is here.

binary_search for a sorted index_sequence

Who would need such a utility function such that you have a very long sorted index_sequence and need to do binary search for an occurrence of a number N? I really doubt it, but anyway it is a good practice, especially we have a handy tool to convert index_sequence to array.

The standard binary_search is depended on a so-called lower_bound function that return the "first element e such that it satisfy e<N" for the to-be-searched number N.

// assume sequence is sorted
template<size_t N,size_t...Is>
constexpr size_t lower_bound(index_sequence<Is...>seq){
    constexpr auto& ary=index_sequence_to_array<Is...>::value;
    int count=sizeof...(Is),  first=0, mid, step;
    while (count>0){
        step=count/2;
        mid=first+step;
        if (ary[mid]<N){
            first=mid+1;
            count-=step+1;
        }else{
            count=step;
        }
    }
    return first;
}

We can use static_assert to test our function here and the returned index 2 indicating the starting of lower_bound is the first "2" because it is the first element that !(2<2):

static_assert(lower_bound<2>(index_sequence<0,1,2,2,2,3,4>{})==2);

Then the binary_search is very trivial to just linear search the first occurrence of N starting from lower_bound result.

// assume sequence is sorted
template<size_t N, size_t...Is>
constexpr size_t binary_search(index_sequence<Is...>seq){
    constexpr auto& ary=index_sequence_to_array<Is...>::value;
    size_t low;
    for (low=lower_bound<N>(seq); low<ary.size(); low++){
        if (ary[low]==N) return low;
    }
    return low;
}

Note that it can return the "size" of sequence in case no such N exists. i.e.

static_assert(binary_search<5>(index_sequence<0,1,2,2,2,3,4>{})==7);

Interestingly, upper_bound, the sister of lower_bound, has almost identical code except the condition is different which makes the result very subtle. And it is this tiny difference that costs me a lot of time to debug. Silly of me.

// assume sequence is sorted
template<size_t N, size_t...Is>
constexpr size_t upper_bound(index_sequence<Is...>seq){
    constexpr auto& ary=index_sequence_to_array<Is...>::value;
    int count=sizeof...(Is), first=0, mid, step;
    while (count>0){
        step=count/2;
        mid=first+step;
        if (!(N<ary[mid])){
            first=mid+1;
            count-=step+1;
        }else{
            count=step;
        }
    }
    return first;
}

So, this upper_bound is like a free bonus and because of this free bonus, it makes me to get another free bonus: equal_range which is a range of occurrence of all searched number N. Instead of returning a pair of iterator, I decide to just return the count of result.

// assume sequence is sorted
template<size_t N, size_t...Is>
constexpr size_t equal_count(index_sequence<Is...>seq){
    return upper_bound<N>(seq)-lower_bound<N>(seq);
}

So cheap to count it.

The complete code is here.

Any difference between a template lambda and a template lambda member function?

I have been debating with myself which one is better? Or is there any pros and cons? A template lambda or simply just template lambda's built-in operator()?

case 1: a template lambda

template<typename T>
using LambdaTemmplateClass=decltype([](T n){
    cout<<__PRETTY_FUNCTION__<<":"<<n<<endl;
    });

case 2: a lambda with its operator() a template function (using auto as generic lambda or using traditional template argument typename T are almost identical)

auto lambdaMemberTemplate=[]<typename T>(T n){
    cout<<__PRETTY_FUNCTION__<<":"<<n<<endl;
};


auto lambdaAuto=[](auto n){
    cout<<__PRETTY_FUNCTION__<<":"<<n<<endl;
};

Let's compare their usage for these three use cases:

1. directly invoke
2. used as callback function
3. used as function pointer

case 1 of directly invoke:

    LambdaTemmplateClass<int>{}(42);
    lambdaMemberTemplate(42);
    lambdaAuto(42);

Here for "LambdaTemmplateClass" which is a type, you have to give template argument and create an instance. While the other two are already instances.

case 2 as callback function

    auto callLambda=[](auto lam, auto data){
        lam(data);
    };
    callLambda(LambdaTemmplateClass<int>{}, 42);
    callLambda(lambdaMemberTemplate, 42);
    callLambda(lambdaAuto, 42);

Similar to case 1 above

case 3 as function pointer

void callPtr(void(*ptr)(int), int n){
    ptr(n);
}   
callPtr(LambdaTemmplateClass<int>{}, 42);
callPtr(lambdaMemberTemplate, 42);
callPtr(lambdaAuto, 42);

Using as callback function or using as function pointer are no difference! As they all can be smoothly converted as if following:

void(*ptr)(int) =nullptr;
ptr=LambdaTemmplateClass<int>{};
callPtr(ptr, 42);
ptr=lambdaMemberTemplate;
callPtr(ptr, 42);
ptr=lambdaAuto;
callPtr(ptr, 42);

So, it seems there is no difference between them except only a template lambda still keeps ability to explicitly convert to a function pointer.

static_assert(is_same_v<decltype(+LambdaTemmplateClass<int>{}),
        void(*)(int)>);
// there is no way to invoke its operator+
static_assert(is_same_v<decltype(static_cast<void(*)(int)>(lambdaMemberTemplate)), 
    void(*)(int)>);
//static_assert(is_same_v<decltype(+lambdaAuto), void(*)(int)>);         
//static_assert(is_same_v<decltype(+lambdaMemberTemplate), void(*)(int)>);        

Pay attention to the operator +(), you can no longer explicitly call the little magic "+" before our lambda because for case of lambdaMemberTemplate or lambdaAuto, it is becoming an invalid operand. i.e. their member function is a template function and you cannot give compiler a clear guide what template argument you want.

Here is the complete code.

Lambda is more than just a functor

Lambda is not just an anonymous functor because it can be converted to a function pointer which functor can not.

For example, a callback parameter ptr of a function callPtr is a function pointer.

typedef void(*FunPtr)();
void callPtr(FunPtr ptr){
    ptr();
}

Then obviously you cannot plugin a functor as argument.

struct functor{
    void operator()(){
        cout<<__PRETTY_FUNCTION__<<endl;
    }
};
// it won't compile because functor is not a function pointer
//callPtr(functor{}); 

But you can pass a lambda.

    auto lambda=[](){
        cout<<__PRETTY_FUNCTION__<<endl;
    };
    callPtr(lambda);
  

Why? The standard says so:

The closure type for a non-generic lambda-expression with no lambda-capture whose constraints (if any) are satisfied has a conversion function to pointer to function with C++ language linkage having the same parameter and return types as the closure type's function call operator.

In other words, you can convert lambda to FunPtr without any cast at all.

FunPtr ptr=lambda;
ptr(); //calling lambda

So, that is natural to pass lambda as parameter of type of FunPtr without any cast at all.

Can we make our functor like lambda like this? Unfortunately it is not so easy. However, knowing lambda can do this, we can use a lambda to simulate this:

struct functor{
    void operator()(){
        cout<<__PRETTY_FUNCTION__<<endl;
    }
    operator FunPtr(){
        FunPtr result=+[](){
            auto ptr=mem_fn(&functor::operator ());
            return ptr(functor{});
        };
        return result;
    }
};

Here we implement the conversion operator FunPtr() by using a lambda with its "converting operator +" to convert the lambda as a function pointer. This internal lambda just calls our functor's operator () with an temporary functor instance as parameter. Of course this functor doesn't take extra parameter, if so, we need to add some.

This is the effect of our functor:

FunPtr ptr=functor{};
ptr();// call functor's operator()

Here is complete code.