CODEWITHSUNDEEP
c++c++11lambda
Gautam
Gautam

Reputation: 1119

Parameters passed to multiple argument lambda expression

I just watched this lecture about STLs by STL.

Around 57 minutes into the lecture, we have this code:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main()
{
    std::vector<std::string> v;

    v.push_back("cat");
    v.push_back("antelope");
    v.push_back("puppy");
    v.push_back("bear");

    std::sort(v.begin(), v.end(),
              [](const std::string& left, const std::string& right)
                  {
                      return left.size() < right.size();
                  }
             );

    for (std::vector<std::string>::iterator i = v.begin(); i != v.end(); ++i)
    {
        std::cout << *i << " ";
    }

    std::cout << std::endl;

    return 0;
}

As expected, this prints the strings in the vector in increasing order of their lengths. My question is about the lambda expression which is the 3rd argument to the sort function. Internally, what gets passed to the input parameters 'left' & 'right'?

I added the line:

std::cout << "left: " << left << ", right: " << right << std::endl;

inside the body of the lambda, and the output I got was:

left: antelope, right: cat
left: antelope, right: cat
left: puppy, right: cat
left: puppy, right: antelope
left: puppy, right: cat
left: bear, right: cat
left: bear, right: antelope
left: bear, right: puppy
left: bear, right: cat
cat bear puppy antelope

So it looks like the 'left' and 'right' arguments are somehow related to the internal sorting algorithm in play. Can anyone shed more light on what exactly is going on?

My understanding is that if the lambda were to be a unary function, then it's input argument would have been whatever the iterator is currently pointing to. Is this correct?
But with a binary function, the input arguments puzzle me.

Upvotes: 2

Views: 2141

Answers (1)

Benjamin Lindley
Benjamin Lindley

Reputation: 103693

At the heart of most sorting algorithms is a comparison between two elements, in order to determine which one should precede the other. For example, here is quicksort, taken from Wikipedia.

function quicksort(array)
     if length(array) ≤ 1
         return array  // an array of zero or one elements is already sorted
     select and remove a pivot element pivot from 'array'  // see '#Choice of pivot' below
     create empty lists less and greater
     for each x in array
         *****if x ≤ pivot then append x to less***** this line here
         else append x to greater
     return concatenate(quicksort(less), list(pivot), quicksort(greater)) // two recursive calls

In the case of this pseudocode, the comparison is this

if x ≤ pivot

Notice that this is a binary operation, the two arguments being x, and pivot. In the case of the standard library function std::sort, this would instead be:

if (comp(x,pivot))

Where comp is the functor you pass in as the last argument. So, to answer your question: "Which 2 things are begin passed into the comparator", whatever 2 elements of the range need to be compared at that particular time in the logic of the algorithm.

Upvotes: 6

Related Questions