c++ - 将 std::set 与基于键的比较器一起使用

Question

假设我有一组(或映射)字符串，我想使用一个只比较前 5 个字符的自定义比较器。所以“abcde”和“abcdef”在我的集合中是相同的。

typedef std::set<std::string, Cmp> MySet;

Cmp 的最佳写法是什么？

最明显的方式是这样的:

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

问题是这段代码重复了.substr(0, 5) .在这个例子中它很短，但在一般情况下它可能会更长。我想避免这种重复代码。

一般来说，给定类型 T1, T2和函数 T2 key(T1& const) , 我想要一套 T1根据 key(a) < key(b) 比较的元素, 比较 T2已经明确定义。写这个的最好方法是什么？我想写一个新的 class KeyBaseSet ，但这对于我的单一用例来说是过度设计的。有什么方法可以使用 std 来做到这一点吗？还是提升？

我正在寻找类似于 key 的东西在 Python 中排序时的参数(https://docs.python.org/3/howto/sorting.html#key-functions)，或 compare `on` Haskell 中的成语 ( https://stackoverflow.com/a/2788262/351105 )。

Answer 1

您可以使用 key 策略自定义Cmp。最小示例:

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 可以通过将其设置为 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);
    }
};

当我们这样做的时候

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

不会为字符串文字 "abc" 构造临时 std::string。

Demo 2