Могу ли я расширить std :: map :: lower_bound для поиска по аргументам не-key_type? - PullRequest
Новая
       54

Могу ли я расширить std :: map :: lower_bound для поиска по аргументам не-key_type?

0 голосов
/ 05 января 2019

Вот иллюстрация моей ситуации. У меня есть std::map, и я хочу найти первый pair<key,value>, где ключ - это любой член класса эквивалентности ключей. 

#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, но мне трудно интерпретировать спецификацию для этого.

Поскольку заказано Key для моей карты, Key имеет совместимый порядок с Category, а именно: k<c тогда и только тогда, когда k.category<c, поэтому мои требования, кажется, имеют логический смысл.

В реальной ситуации класс Key является более сложным, и разделение компонентов качества / категории (для использования решения map<category,map<quality,value>>) на самом деле не сработает, если это то, что вы думать о.

Как найти нижние (и верхние) границы диапазона элементов в моей карте, ключи которых эквивалентны некоторому неключевому значению?

1 Ответ

0 голосов
/ 05 января 2019

C ++ 14 ввел концепцию прозрачного компаратора, где можно использовать find, lower_bound, upper_bound, ... с чем угодно, что можно сравнить с тип ключа, если компаратор явно выбирает это поведение.

В вашем случае вам нужно добавить собственный компаратор 

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;

Живая демоверсия

...