Cached std::sort

cached_sort.cpp

#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <vector>

struct Foo {
    int value;

    bool operator==(const Foo& other) const {
        return value == other.value;
    }   
};

namespace std {
    template <>
    struct hash<Foo> {

        size_t operator()(const Foo& foo) const {
            return hash<int>()(foo.value);
        }

    };  
}

int evaluate(const Foo& foo) {
    std::cout << "Evaluating complex function on an instance of Foo..." << std::endl;
    return foo.value;
}

bool compare(const Foo& left, const Foo& right) {
    static std::unordered_map<Foo, int> cache;
    auto leftIt = cache.find(left);
    auto rightIt = cache.find(right);
    if (leftIt == cache.end())
        leftIt = cache.emplace(left, evaluate(left)).first;
    if (rightIt == cache.end())
        rightIt = cache.emplace(right, evaluate(right)).first;
    return (*leftIt).second < (*rightIt).second;
}

int main() {
    std::vector<Foo> bar = { Foo{3}, Foo{1}, Foo{2}, Foo{3}, Foo{1} };
    std::sort(bar.begin(), bar.end(), compare);
    for (const auto& foo : bar) {
        std::cout << foo.value << std::endl;
    }   
    return 0;
}