Why isn't std::partial_sort_copy populating the vector?

Question

I'm trying to pick the first k elements from a std::map based on a custom compactor and insert them into a vector. I'm trying to do this via std::partial_sort_copy. However, when I run the code, I find that nothing was inserted in the vector. 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<std::pair<typename MapType::key_type, typename MapType::mapped_type>> v;
        v.reserve(map.size());
        std::cout << v.size() << "\n";

        // 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());

        std::partial_sort_copy(map.begin(), map.end(), v.begin(), std::next(v.begin(), k), [](const auto& lhs, const auto& rhs){ return lhs.second.a > rhs.second.b; });
        std::cout << v.size() << "\n";

        std::cout << std::distance(map.begin(), map.end()) << " " << std::distance(v.begin(), std::next(v.begin(), k)) << "\n";
        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;
}

Here's the link to compiler explorer.

Here's the output that I get when I run this code:

0
0
100 10

The commented out code performs the computation that I want to do using std::partial_sort_copy. What am I doing wrong? Why doesn't my implementation work?

Answer 1

Under the circumstances (you already know the size of the destination container), it's almost certainly easiest to set the correct size.

You also need to be able to default-construction a Values object (well, strictly speaking, that's not an absolute necessity, but it's a common an effective way to handle the situation).

#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) {}
        Values() = default;
};

template <typename MapType>
auto print_top_k(std::size_t k, MapType&& map)
{
        std::vector<std::pair<typename MapType::key_type, typename MapType::mapped_type>> v{k};
        
        std::partial_sort_copy(map.begin(), map.end(), v.begin(), v.end(), [](const auto& lhs, const auto& rhs){ return lhs.second.a > rhs.second.b; });

        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;
}

Result:

99 -> (198, 297)
98 -> (196, 294)
86 -> (172, 258)
97 -> (194, 291)
62 -> (124, 186)
61 -> (122, 183)
43 -> (86, 129)
63 -> (126, 189)
85 -> (170, 255)
45 -> (90, 135)

Live on Godbolt

Answer 2

As mentioned in the comments std::partial_sort_copy does not modify the size of the container that it writes to. So if the original size of the vector is 0, the size will not change. Therefore, nothing will get placed in the vector.