How does this std::set initialization work?

I am having some trouble understanding how the std::set initialization works. I have the following code in a function:

std::map<int, int> my_map  = {
    {16, 24},
    {19, 29},
    {15, 23},
    {14, 22},
    {13, 21},   
    {17, 28},
};

typedef std::function<bool(std::pair<int, int>, std::pair<int, int>)> comparefunction;


comparefunction compare = 
    [](std::pair<int, int> a, std::pair<int, int> b){
        if(lessthan(a,b))
            std::cout << "a" << std::endl;
        else
            std::cout << "b" << std::endl;


        return true;
    };

std::set<std::pair<int, int>, comparefunction>
    values(my_map.begin(), my_map.end(), compare);

When calling this function it prints "b" a few times, how come?

Edit: I realized I used the range constructor, but how does it "automatically" call the lambda function using elements in the map? I can't seem to find this in the documentation. Printing contents of a and b shows that they're always the same, why is this?

Solution

You are initializing a set with some values. These values happen to come from your map, but sourcing them is not important. What is important is that the set's constructor will be given the following values with which to work (these are actually std::pairs, but the brace notation is convenient):

{13,21}  {14,22}  {15,23}  {16,24}  {17,28}  {19,29}

[At this point, someone might notice that, instead of the order in which the map was initialized, I put these in order by their first coordinate (the key of the map). This is because the map is ordered, so begin() to end() traverses the map from the lowest key to the highest.]

So what happens? The set's constructor creates a set, then adds these elements to it. The first element ({13,21}) goes in no problem; it's easy to add an element to an empty set.

The second element, though, needs to be placed in the set at a location that maintains order. That is, the constructor needs to know if the new element ({14, 22}) compares less than the existing element ({13,21}). How does it find out? It calls the function you gave it: compare({14, 22}, {13,21}). This returns true, so the new element goes before the old in the set.
Note: the order of the parameters is not fixed; since the output was "b", I'm guessing this is the order that was used.

Adding the third element ({15,23}) is similar. The constructor needs to know where it goes in the set, so it starts with one of the existing elements (implementor's choice as to which we start with) and calls your function with that element and the new one. Your function returns true, so the new element will be placed before the existing element. Depending on which element was chosen, another call to compare might be needed to determine that the new element goes first in the set.
Note: if the implementor had chosen the other order of parameters, the new element would go last in the set; presumably you would have seen "a"s instead of "b"s had this happened.

And so on for the remaining three elements.

Want to confuse the constructor? Have your lambda return false instead of true. This will convince the constructor that all of your pairs are equivalent, meaning that after construction with six elements, the set will contain just one ({13,21}). In this case, changing "set" to "multiset" would allow the other elements to be added.

Actually, the constructor could potentially be confused by the function always returning true. Better to have it return whether or not a is considered less than b.