CODEWITHSUNDEEP
c++stdset
Tomer Vromen
Tomer Vromen

Reputation: 1812

How do I use std::set with a comparator that applies a projection to the key?

Suppose I have a set (or map) of strings, and I want to use a custom comparator that compares only the first 5 characters. So "abcde" and "abcdef" are the same in my set.

using MySet = std::set<std::string, Cmp>;

What is the best way to write Cmp?

The obvious way is like this:

struct Cmp
{
    bool operator()(const string& x, const string& y) const
    {
        return x.substr(0, 5) < y.substr(0, 5);
    }
};

The problem is that this code repeats .substr(0, 5). In this example it's pretty short, but in the general case it could be longer. I want to avoid this repeating code.

In general, given the types T1, T2 and the function T2 key(T1& const), I want a set of T1 elements that compares according to key(a) < key(b), where comparison on T2 is already well-defined. What is the best way to write this? I thought about writing a new class KeyBaseSet, but that would be over-designing for my single use-case. Is there some way to do this using std or Boost?

I'm looking for something similar to the key argument when sorting in Python (https://docs.python.org/3/howto/sorting.html#key-functions), or the compare `on` idiom in Haskell (https://stackoverflow.com/a/2788262/351105).

Upvotes: 5

Views: 419

Answers (2)

Marti Nito
Marti Nito

Reputation: 814

Your problem could be solved with higher order functions. Essentially a function that takes the T2 key(const T1&) function and returns a new function that can be used as comparator for the std::set. Something like:

auto make_comp(T key) {
    return [key](const auto& v1, const auto& v2){return key(v1) < key(v2);};
}

Obviously this example requires generic lambdas, but it should be possible to achieve this with template structs as well :)

It should be possible to define a set as std::set<decltype(make_comp([](){...}))>.

Upvotes: 0

Evg
Evg

Reputation: 26302

You can customize Cmp with a key policy. Minimal example:

template<class Key>
struct Compare_on {
    Compare_on(Key key = Key()) : key_(key)
    {}

    template<class T>
    bool operator()(const T& x, const T& y) const {
        return key_(x) < key_(y);
    }

private:
    Key key_;
};

struct First3 {
    std::string_view operator()(const std::string& s) const {
        return std::string_view(s).substr(0, 3);
    }
};

// Example:
std::set<std::string, Compare_on<First3>> set;
set.insert("abc1");
set.insert("abc2");

Demo

Compare_on can be improved by making it a transparent comparator:

template<class Key>
struct Compare_on {
    using is_transparent = void;

    Compare_on(Key key = Key()) : key_(key)
    {}

    template<class T1, class T2>
    bool operator()(const T1& x, const T2& y) const {
        return key_(x) < key_(y);
    }

private:
    Key key_;
};

struct First3 {
    template<class T>
    std::string_view operator()(const T& s) const {
        return std::string_view(s).substr(0, 3);
    }
};

Now when we do

auto pos = set.find("abc");

no temporary std::string will be constructed for the string literal "abc".

Demo 2

Upvotes: 6

Related Questions