为何std::partial_sort_copy无法填充vector容器？

问题描述 #

尝试基于自定义比较器从std::map中选取前k个元素并插入vector，使用std::partial_sort_copy实现，但运行后vector未被填充。注释掉的代码可实现预期功能，需排查错误原因。

原代码 #

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

运行输出 #

0
0
100 10

错误原因及修复 #

核心错误 #

std::partial_sort_copy要求目标容器已分配足够的元素空间（即size满足需求），但你仅调用了v.reserve(map.size())：

• reserve仅预分配内存，不会改变vector的size，此时v的size仍为0。
• v.begin()到std::next(v.begin(),k)是非法的迭代器范围，后续操作属于未定义行为，自然无法填充元素。

修复方法 #

将v.reserve(map.size())替换为初始化vector的size为需要容纳的元素数量（需考虑map元素数少于k的情况）：

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;
        auto target_size = std::min(k, map.size());
        v.resize(target_size); // 分配足够的元素空间，让迭代器范围有效
        std::cout << v.size() << "\n";

        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; });
        std::cout << v.size() << "\n";

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

为什么注释代码能工作 #

注释中的std::transform搭配std::back_inserter(v)会实际向vector插入元素，改变了vector的size，后续的std::sort和v.erase都是基于有效的元素范围执行，因此能得到正确结果。

内容的提问来源于stack exchange，提问作者Setu