我可以扩展std :: map :: lower_bound来搜索非key_type参数吗? [英] Can I extend std::map::lower_bound to search on non-key_type arguments?

问题描述

这是我的情况的例证.我有一个std::map，我想找到第一个pair<key,value>，其中的键是等效键类的任何成员.

Here is an illustration of my situation. I have a std::map and I want to find the first pair<key,value> where the key is any member of an equivalence class of keys.

#include <map>

struct Category
{
    int foo;
    int bar;

    bool operator < (const Category & rhs) const;    
    bool operator > (const Category & rhs) const;
};

struct Key
{
    Category category;
    float quality;

    bool operator < (const Key & rhs) const
    {
        if (category < rhs.category)
            return true;
        else if (category > rhs.category)
            return false;
        else
            return quality < rhs.quality;
    }
};

struct Value {};

typedef std::map <Key, Value> Container;

Container::iterator find_low_quality
(
    Container & container,
    const Category & category
)
{
    return container.lower_bound (category);
}

Container::iterator find_high_quality
(
    Container & container,
    const Category & category
)
{
    // some checks need to be done, here omitted for brevity
    return --container.upper_bound (category);
}

这不起作用，因为map::lower_bound和map::upper_bound仅采用key_type(即Key)自变量.我无法编译std::lower_bound，我看到它期望使用LegacyForwardIterator，但是我很难解释它的规范.

This doesn't work because map::lower_bound and map::upper_bound only take a key_type (i.e. Key) argument. I couldn't get std::lower_bound to compile, I see it expects a LegacyForwardIterator but I'm having a hard time interpreting the spec for this.

就我地图的Key排序而言，Key与Category具有兼容的排序，即:k<c当且仅当k.category<c时，所以我的要求似乎合乎逻辑.

Insofar as the Key for my map is ordered, the Key has a compatible ordering with Category, viz: k<c if and only if k.category<c, so my requirements seem to make logical sense.

在实际情况下，Key类更复杂，并且如果要解决的话，分离质量/类别组件(以使用map<category,map<quality,value>>解决方案)实际上是行不通的.想到.

In the real situation, the Key class is more complex, and separating the quality/category components (in order to use a map<category,map<quality,value>> solution) isn't really going to work, in case that's what you're thinking of.

如何在地图中找到其键等效于某些非键值的元素范围的下限(和上限)?

How can I find the lower (and upper) bounds of the range of elements in my map whose keys are equivalent to some non-key value?

推荐答案

C ++ 14引入了透明比较器的概念，可以在其中使用find，lower_bound， upper_bound，...，只要比较器明确选择采用这种行为，...就可以与键类型进行比较.

C++14 introduced the concept of a transparent comparator, where it is possible to use find, lower_bound, upper_bound, ... with anything that can be compared to the key type, as long as the comparator explicitly opts in to this behavior.

您需要添加自定义比较器

In your case you'd need to add a custom comparator

struct KeyComparator {
    // opt into being transparent comparator
    using is_transparent = void;

    bool operator()(Key const& lhs, Key const& rhs) const {
        return lhs < rhs;
    }

    bool operator()(Key const& lhs, Category const& rhs) const {
      return lhs.category < rhs;
    }

    bool operator()(Category const& lhs, Key const& rhs) const {
      return lhs < rhs.category;
    }
};

，然后您需要在Container

typedef std::map <Key, Value, KeyComparator> Container;

实时演示

这篇关于我可以扩展std :: map :: lower_bound来搜索非key_type参数吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！