Как получить максимальный элемент std :: unordered_map? - PullRequest
Новая
       55

Как получить максимальный элемент std :: unordered_map?

1 голос
/ 03 мая 2019

Я знаю, как извлечь максимальный элемент из std::map с помощью std::max_element, но не могу добиться того же эффекта с std::unordered_map из-за различий между типами контейнеров.

Как найти максимальное значение в std::unordered_map и вернуть соответствующее std::pair?

Показан мой текущий метод для этого с std::map (основанный на этот ответ ).Я не могу понять, как сделать то же самое для std::unordered_map. 

template <typename KEY_T, typename VALUE_T>
std::pair<KEY_T, VALUE_T> findMaxValuePair(
    std::map<KEY_T, VALUE_T> const &x)
{
    return *std::max_element(x.begin(), x.end(),
                             [](const std::pair<KEY_T, VALUE_T> &p1,
                                const std::pair<KEY_T, VALUE_T> &p2)
                             {
                                 return p1.second < p2.second;
                             });
}

Когда я пытаюсь использовать вышеуказанную функцию на std::unorderd_map (замена std::map на std::unordered_mapЯ получаю Segmentation fault (core dumped).

Ответы [ 2 ]

2 голосов
/ 03 мая 2019

Заставить код работать на unordered_map

В этом случае мы можем сделать это, просто изменив тип с map на unordered_map.

До: 

template <class Key, class Value>
std::pair<Key, Value> findMaxValuePair(
    std::map<Key, Value> const &x)
{
    return *std::max_element(x.begin(), x.end(),
                             [](const std::pair<Key, Value> &p1,
                                const std::pair<Key, Value> &p2)
                             {
                                 return p1.second < p2.second;
                             });
}

После: мы изменили тип на unordered_map. 

template <class Key, class Value>
std::pair<Key, Value> findMaxValuePair(
    std::unordered_map<Key, Value> const &x)
{
    return *std::max_element(x.begin(), x.end(),
                             [](const std::pair<Key, Value> &p1,
                                const std::pair<Key, Value> &p2)
                             {
                                 return p1.second < p2.second;
                             });
}

Заставить код работать для обоих

Мы можем написать функцию, которая действительно просто работает со всеми стандартными контейнерами! Это будет работать для карт, векторов, списков и почти всего остального, что определяет begin(), end() и value_type! 

template <class Container>
auto findMaxValuePair(Container const &x) 
    -> typename Container::value_type
{
    using value_t = typename Container::value_type;
    const auto compare = [](value_t const &p1, value_t const &p2)
    {
        return p1.second < p2.second;
    };
    return *std::max_element(x.begin(), x.end(), compare);
}

А как насчет сегфо?

Этот код может вызвать ошибку, если карта или контейнер пусты, либо потому, что вы обращаетесь к памяти, которой вы не владеете; потому что память, на которую указывает map::end(), содержит мусор, из которого вы затем пытаетесь создать что-то вроде строки, или потому что он представлен как нулевой указатель.

В частности, для карт, если имеется повреждение памяти, это также может привести к segfault, хотя это будет верно независимо от того, как вы пытались выполнить итерацию по карте.

0 голосов
/ 03 мая 2019

Я заказал карту предпочтительнее, но ключ. Здесь вы стремитесь к значению. В любом случае вам нужно будет перебрать Troough весь порядок карты, чтобы найти максимальное значение. Упорядоченная карта может эффективно найти максимальные или минимальные ключи, но не значения. Таким образом, выбранный подход будет работать как для неупорядоченной, так и для упорядоченной карты.

...