CODEWITHSUNDEEP
c++stdvectorstdmaplibstdc++c++23
Setu
Setu

Reputation: 980

How to pick top k elements from std::map

I have a std::map with uint32_t as the key type and a custom value type. I want to pick out the top k key value pairs from this map based on the members of the value type. To do this, I'm first copying all the elements of the std::map to a std::vector followed by sorting the vector. Finally I'm erasing all the elements in the vector with indices greater than k. Here's my code:

#include <algorithm>                                                                                                                                                                                           
#include <cstdint>
#include <iostream>
#include <map>
#include <vector>

struct Values
{
        uint32_t a = 0;
        uint32_t b = 0;

        Values(uint32_t x, uint32_t y): a(x), b(y) {}
};

template <typename MapType>
auto print_top_k(std::size_t k, MapType&& map)
{
        std::vector<typename MapType::value_type> v;
        v.reserve(map.size());

        std::transform(map.begin(), map.end(), std::back_inserter(v), [](const auto& kv) { return kv; });
        std::sort(v.begin(), v.end(), [](const auto& lhs, const auto& rhs){ return lhs.second.a > rhs.second.b; }); 
        v.erase(v.begin() + k, v.end());

        for(const auto& kv: v)
                std::cout << kv.first << " -> (" << kv.second.a << ", " << kv.second.b << ")\n";
}

int main()
{
        std::map<uint32_t, Values> data;
        for(uint32_t i = 0; i < 100; i++)
                data.emplace(std::piecewise_construct, std::forward_as_tuple(i), std::forward_as_tuple(2*i, 3*i));

        print_top_k(10, std::move(data));

        return 0;
}

I'm using GCC to compile this:

gcc -std=c++23 -Ofast -Wall -Wextra -Wpedantic -Wconversion -Werror main.cpp

Here's the link to compiler explorer.

However, this code doesn't compile as I get an error at std::sort.

  1. Why am I getting compilation errors in this code?
  2. What do these errors mean? Can someone please translate them from GCC-speak to English?
  3. How can I fix these errors?

Upvotes: 2

Views: 70

Answers (1)

Ahmed AEK
Ahmed AEK

Reputation: 18090

std::map is already sorted, you can take the last k elements from the end for the greatest and k elements from the start for the smallest.

for (auto it = map.rbegin(); it != map.rend(); it++)
{
    if (v.size() == k)
    {
        break;
    }
    v.push_back(*it);
}

for an unordered_map, The standard library has a function std::partial_sort_copy to pick the largest or smallest elements of any container, which can be called with an unordered_map.

As for your question.

std::vector<typename MapType::value_type> v;

map's value_type is std::pair<const Key, T>, and const elements disable the copy assignment operator which std::sort needs to copy/move the elements.

you need to use

std::vector<std::pair<typename MapType::key_type, typename MapType::mapped_type>> v;

godbolt link

as for the translation, the error you got is:

error: use of deleted function 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(const std::pair<_T1, _T2>&) [with _T1 = const unsigned int; _T2 = Values]

which translates to, that std::pair<const unsigned int, Values> has operator= deleted.

Upvotes: 3

Related Questions