Parameters passed to multiple argument lambda expression

Question

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.

Am I missing something, or are you asking why the comparator function that compares two things requires two parameters? While the sorting algorithm runs it frequently compares items to determine if their "order" is correct, stressing the s in the word "items". — WhozCraig
– WhozCraig, Commented Oct 18, 2013 at 23:35
I do understand that a comparator function needs two things. My question is 'which' 2 things are being passed into the comparator, and if possible, 'how'. In other words, as a programmer, what can I expect to get as input arguments so that I can decide what check to perform inside the lambda. — Gautam
– Gautam, Commented Oct 18, 2013 at 23:41
@Gautam Ah. You can expect anything in your sequence. When and how-often something appears is entirely dependent on the algorithm being used. And I advise you thoroughly understand the concept of a strict-weak-ordering before writing your own, especially if writing one that orders based on multiple field values in a complex object. — WhozCraig
– WhozCraig, Commented Oct 19, 2013 at 1:20

Benjamin Lindley · Accepted Answer · 2013-10-18 23:52:59Z

6

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.

edited Oct 18, 2013 at 23:52

answered Oct 18, 2013 at 23:47

Benjamin Lindley

104k11 gold badges210 silver badges285 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Gautam Over a year ago

Thanks for the answer. Also, is my understanding about a single-argument lambda correct? Quoting from the question: "... if the lambda were to be a unary function, then it's input argument would have been whatever the iterator is currently pointing to ..."

Collectives™ on Stack Overflow

Parameters passed to multiple argument lambda expression

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related