Использование std :: equal_range с boost :: transform_iterator - PullRequest
Новая
       65

Использование std :: equal_range с boost :: transform_iterator

0 голосов
/ 01 августа 2020

Допустим, у меня есть структура Item s, которую я храню в std::set и сортирую так: 

struct Position
{
    int x;
    int y;
}

struct Item
{
    std::string id;
    Position position;

    // NOTE: only `position` should matter for equality
    operator==(const Item& other)
    {
        return position == position;
    }
};

inline bool operator<(const Item& lhs, const Item& rhs)
{
    if (lhs.position.x == rhs.position.x)
    {
        return lhs.position.y < rhs.position.y;
    }

    return lhs.position.x < rhs.position.x;
}

using ItemSet = std::set<Item>;

Я хочу использовать std::equal_range для поиска ItemSet , за исключением того, что я хочу искать по Position. Я знаю, что могу сделать что-то вроде: 

ItemSet items;

Item tempItem;
tempItem.position = some_position;
auto result = std::equal_range(items.begin(), items.end(), tempItem);

Но я бы хотел избежать временного Item.

Я пытался использовать boost::transform_terator вот так: 

  auto tr = [](const Item& item) { return item.pos; };
  auto tr_begin = boost::make_transform_iterator(items.begin(), tr);
  auto tr_end = boost::make_transform_iterator(items.end(), tr);
  
  Position findme { 2, 1 };
  auto result = std::equal_range(tr_begin, tr_end, findme);

Но это не компилируется по причинам, которых я не понимаю, и даже если бы это сработало, как мне получить итератор в исходную коллекцию из result? Или, может быть, есть лучший способ сделать это в целом?

Вот тестовый жгут, показывающий проблему: http://cpp.sh/3hzsq

Любая помощь будет принята с благодарностью!

1 Ответ

1 голос
/ 01 августа 2020

Вы можете использовать std::set::find с другим типом, чтобы не создавать Item. Обратите внимание, что ваш набор может содержать только один элемент с указанной позицией c.

Вы можете сделать Position напрямую сопоставимым с Item (добавить Item{} < Position{} и Position{} < Item{}) или создать новый прокси-класс: 

struct ItemPosition {
    Position p;
};

inline bool operator<(const ItemPosition& l, const Item& r) {
    return l.position.x == r.position.x ? l.position.y < r.position.y : l.position.x < r.position.x;
};

inline bool operator<(const Item& l, const ItemPosition& r) {
    return l.position.x == r.position.x ? l.position.y < r.position.y : l.position.x < r.position.x;
};

// Change the comparator so it can compare with `ItemPosition` too
using ItemSet = std::set<Item, std::less<>>;

В качестве альтернативы вы можете использовать совершенно другой компаратор, чтобы Position было сопоставимо с Item. 

struct ItemComparator {
    bool operator()(const Position& l, const Position& r) const {
        return l.x == r.x ? l.y < r.y : l.x < r.x;
    }
    bool operator()(const Item& l, const Item& r) const {
        return operator()(l.position, r.position);
    }
    bool operator()(const Item& l, const Position& r) const {
        return operator()(l.position, r);
    }
    bool operator()(const Position& l, const Item& r) const {
        return operator()(l, r.position);
    }

    using is_transparent = void;
};

using ItemSet = std::set<Item, ItemComparator>;

И использовать его так: 

    Position findme { 2, 1 };
    // Or just `items.find(findme)` if using a custom comparator
    auto result = items.find(ItemPosition{ findme });
    if (result == items.end()) {
        // No item found
    } else {
        Item& item = *result;
        // found item
    }
...