c-如何使用其他类型的键搜索std :: map

如果我有std :: map< X,Blah&gt ;,使用Y实例在地图中查找匹配项的最佳方法是什么? 假设Y中的信息足以唯一地找到X,但是出于性能原因,我不想通过复制Y值来创建X的实例. 我意识到我可以通过为X和Y创建一个通用的基类或接口并使其成为映射键来做到这一点,但是还有其他方法吗?例如创建某种比较器对象? 为了清晰起见,下面是示例代码:

class X
{
public:
    int id;
    int subId;
};

std::map<X, Details> detailsMap;

class Y
{
public:
    int getId();
    int getSubId();
    int someOtherUnrelatedThings1;
    int someOtherUnrelatedThings2;
};

现在,如果我有一个Y实例,原则上我应该能够在我的地图中找到匹配的项,前提是我可以得到一个id和subId对.但是我可以在不创建X实例并复制id和subId的情况下做到这一点吗?

解决方法:

使用C 14可以使用异构查找.

如果您想找到一个键的元素与std :: map :: find的参数进行比较,则应提供一个Comparator作为第三个模板参数,该参数应将Comparator :: is_transparent表示为类型.它还应包含bool operator(),将您的地图密钥与您想要的任何其他类型进行比较.

除了有趣的描述,这里有一个例子:

struct X
{
    int id;
    int subid;
};

struct Details {};

struct Comparator
{
    using is_transparent = std::true_type;

    // standard comparison (between two instances of X)
    bool operator()(const X& lhs, const X& rhs) const { return lhs.id < rhs.id; }

    // comparison via id (compares X with integer)
    bool operator()(const X& lhs, int rhs) const { return lhs.id < rhs; }
    bool operator()(int lhs, const X& rhs) const { return lhs < rhs.id; }

    // Same thing with Y
    bool operator()(const X& lhs, const Y& rhs) const { return lhs.id < rhs.getId(); }
    bool operator()(const Y& lhs, const X& rhs) const { return lhs.getId() < rhs.id; }
};

int main()
{
    std::map<X, Details, Comparator> detailsMap = {
        { X{1, 2}, Details{} }, 
        { X{3, 4}, Details{} },
        { X{5, 6}, Details{} }
    };

    // it1 and it2 point to the same element.
    auto it1 = detailsMap.find(X{1, 2});
    auto it2 = detailsMap.find(1);

    std::cout << detailsMap.size() << std::endl;
    std::cout << std::boolalpha << (it1 == detailsMap.end()) << std::endl; // false
    std::cout << std::boolalpha << (it1 == it2) << std::endl; // true
}

但是请注意,GCC直到版本219888才实现.

上一篇:数据结构之堆与Java实现


下一篇:Java 8 Comparator keyExtractor