Как вызвать `find` для набора итераторов, глядя на то, на что указывает итератор? - PullRequest
Новая
       36

Как вызвать `find` для набора итераторов, глядя на то, на что указывает итератор?

1 голос
/ 03 марта 2020

В c ++ 17 я попробовал следующее, чтобы иметь как упорядоченный список пар, так и средство быстрого поиска случайных записей в этом списке на основе первого элемента в паре. Идея состояла в том, чтобы создать класс, в котором обычная итерация по парам будет иметь фиксированный порядок, при этом сохраняя эффективный произвольный доступ к ним. Записи в unordered_list предназначены только для того, чтобы быть итераторами в order_list, и игнорируя последствия для безопасности потоков, order_list и unordered_list всегда обновляются вместе. Вот фрагмент кода, подобный тому, что я пытался: 

class ordered_pairs {
public:
    typedef std::list<std::string, std::string> list_t;

    struct iterator_hash {
        std::size_t operator()(const list_t::iterator &it) const; // hash of first element in pair
        std::size_t operator()(const std::string &s) const;
    };
    struct iterator_eq {
        bool operator()(const list_t::iterator &left, const list_t::iterator &right) const; // compares first elements of each pair
        bool operator()(const list_t::iterator &left, const std::string &right) const; // compares first element to a string
    };

    list_it::iterator find(const std::string &s)
    {
        auto iter = unordered_list.find(s);
        if (iter == unordered_list.end()) {
            return ordered_list.end();
        } else {
            return *iter;
        }
    }
    ...
private:
    std::unordered_set<list_t::iterator, iterator_hash, iterator_eq> unordered_list;
    list_t ordered_list;
};

Проблема, которую я нахожу, однако, заключается в моем методе find(), компилятор жалуется на невозможность преобразовать std::string в тип итератора, который хранится в ordered_list. Я думал, что если бы я перегружал operator() в iterator_hash и iterator_eq, чтобы принимать строковые аргументы, а также итераторы, я мог бы сделать быстрый поиск записей в наборе. Тем не менее, это не тот случай.

Единственное исправление для этого, которое я обнаружил до сих пор, заключается в изменении поиска следующим образом: 

list_it::iterator find(const std::string &s)
{
    list_t dummy;
    dummy.insert(std::pair(s,""));
    auto iter = unordered_list.find(dumy.begin());
    if (iter == unordered_list.end()) {
        return ordered_list.end();
    } else {
        return *iter;
    }
}

Однако этот метод предполагает создание нового списка добавление элемента к нему только для того, чтобы получить для него итератор, и добавление элемента в этот список вызовет динамическое выделение кучи c (и освободится при выходе из функции). Есть ли способ найти итераторы в моем unordered_list, где я мог бы просто искать по начальной строке?

Пожалуйста, не стесняйтесь задавать вопросы в комментариях ниже, если мой вопрос неясен, и я постараюсь уточнить вопросы внесения изменений в мой вопрос.

1 Ответ

2 голосов
/ 03 марта 2020

Гетерогенный поиск для неупорядоченных контейнеров является функцией C ++ 20 ( P0919 и P1690 ). Согласно cppreference , MSV C 19.23 является единственной из основных стандартных библиотек, которая пока поддерживает это.

До C ++ 20 только две перегрузки unordered_set::find: 

iterator find( const Key& key );
const_iterator find( const Key& key ) const;

Именно поэтому вы получаете сообщение об ошибке, которую видите.

...