Brief Introduction to Functors

Summary

In this post, I will introduce function objects, also known as functors.

Conclusion

I provid the following snippets as a quick reference. See meeting-rooms-II for the problem details.

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    class CompareByStart {
    public:
        bool operator()(Interval const & a, Interval const & b) const {
            return a.start < b.start;
        }
    };
    class CompareByEnd {
    public:
        bool operator()(Interval const & a, Interval const & b) const {
            return a.end < b.end;
        }
    };
    int minMeetingRooms(vector<Interval>& intervals) {
        multiset<Interval, CompareByEnd> s; 
        CompareByStart cbs;
        sort(intervals.begin(), intervals.end(), cbs);
        for (auto const & interval : intervals) {
            if (s.size() == 0) {
                s.insert(interval);
            } else {
                if ((*s.begin()).end <= interval.start) {
                    s.erase(s.begin());
                    s.insert(interval);
                } else {
                    s.insert(interval);
                }
            }
        }
        return s.size();
    }
};

Details

A functor is an object that acts like a function by overloading the function call operator (unary, binary, …). It is kind of functional programming in object oriented programming.

Compared to pointers to functions, the calls of functors can be inlined in more cases, which is a great advantage. If you passed a function pointer to transform, unless that call got inlined and the compiler knows that you always pass the same function to it, it can’t inline the call through the pointer.

Functors are commonly used in STL algorithms and containers. I present two examples.

std::transform

Functors can hold state before and between function calls, like closure in functional languages. For example, you could define a MultiplyBy functor that multiplies its argument by a specified amount:

class MultiplyBy {
private:
    int factor;

public:
    MultiplyBy(int x) : factor(x) {
    }

    int operator () (int other) const {
        return factor * other;
    }
};
int main() {
        int array[5] = {1, 2, 3, 4, 5};
        std::transform(array, array + 5, array, MultiplyBy(3));
        // Now, array is {3, 6, 9, 12, 15}
        return 0;
}

std::multiset

Functors can be passed to many STL containers. It is more clear than using lambda expressions or function pointers.

bool fncomp (int lhs, int rhs) {return lhs<rhs;}

struct classcomp {
    bool operator() (const int& lhs, const int& rhs) const
    {return lhs<rhs;}
};

int main ()
{
    std::multiset<int> first;                          // empty multiset of ints

    std::multiset<int,classcomp> multiset1;                // class as Compare

    bool(*fn_pt)(int,int) = fncomp;
    std::multiset<int,bool(*)(int,int)> multiset2 (fn_pt); // function pointer as Compare

    auto comp = [](int lhs, int rhs) {return lhs<rhs;}; // lambda expressions
    std::multiset<int, decltype(comp)> multiset3 (comp); // function pointer as Compare

    return 0;
}