Алгоритм std::includes занимается ерундой выполняя две операции сравнения (x < y и y < x) там где достаточно одной (compare(x, y)):

    vector<string> vs1, vs2;
    . . .
    includes
        ( vs1.begin(), vs1.end()
        , vs2.begin(), vs2.end()
        );

Для типов с компаратором, возвращающим целое число, можно написать свой алгоритм, выполняющий в 2 раза меньше операций сравнения:

template <class II1, class II2, class COMP>
inline bool includes_comp
    ( II1 first1, II1 const last1
    , II2 first2, II2 const last2
    , COMP const compare
    )
{
    while (first1 != last1 && first2 != last2) {
        int const i(compare(*first1, *first2));
        if (i > 0)
            return false;
        if (i == 0)
            ++first2;
        ++first1;
    }
    return first2 == last2;
}


    vector<string> vs1, vs2;
    . . .
    int (string::*compare)(string const&) const (&string::compare);
    includes_comp
        ( vs1.begin(), vs1.end()
        , vs2.begin(), vs2.end()
        , mem_fun_ref(compare)
        );