c++ - 从 3 个数组中查找最大前 5 个数的优雅代码

Question

我读到 blog其中一位 C# 程序员展示了如何使用 LINQ 从 3 个不同的数组中提取前 5 个数字。

我尝试用 C++ 做同样的事情并编写了以下代码，只有 5 行代码使用 vector 和排序。输出如预期的那样是 88 89 110 888 921。

但问题是，你有更好的解决方案吗？

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

int main(int argc, char* argv[])
{
    int Array1 [] = { 9, 65, 87, 89, 888 };
    int Array2 [] = { 1, 13, 33, 49, 921 };
    int Array3 [] = { 22, 44, 66, 88, 110 };

    vector<int> A1(begin(Array1), end(Array1)); 
    A1.insert(end(A1), begin(Array2), end(Array2)); 
    A1.insert(end(A1), begin(Array3), end(Array3));
    sort(begin(A1), end(A1));
    vector<int> max(end(A1)-5, end(A1));

    copy(begin(max), end(max), ostream_iterator<int>(cout, " "));

    return 0;
}

Answer 1

我会使用 boost::zip_iterator优雅地附加 3 个输入数组，和 std::nth_element与 std::greater以未指定的顺序获取 5 个最大的元素

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>
#include <boost/iterator/zip_iterator.hpp>

int main()
{
    int Array1 [] = { 9, 65, 87, 89, 888 };
    int Array2 [] = { 1, 13, 33, 49, 921 };
    int Array3 [] = { 22, 44, 66, 88, 110 };

    std::vector<int> v;
    v.reserve((sizeof(Array1) + sizeof(Array2) + sizeof(Array3)) / sizeof(int));

    std::for_each(
        boost::make_zip_iterator(boost::make_tuple(std::begin(Array1), std::begin(Array2), std::begin(Array3))),
        boost::make_zip_iterator(boost::make_tuple(std::end(Array1), std::end(Array2), std::end(Array3))),
        [&v](boost::tuple<int, int, int> const& t) {
            v.push_back(t.get<0>()); v.push_back(t.get<1>()); v.push_back(t.get<2>());
        }
    );

    std::nth_element(begin(v), begin(v) + 5, end(v), std::greater<int>());
    std::copy(begin(v), begin(v) + 5, std::ostream_iterator<int>(std::cout, " "));
}

Live Example .

复杂度:线性 O(N1 + N2 + N3) .

如果你想按顺序排列最大的元素，你可以使用 std::partial_sort而不是 std::nth_element或进行后处理 std::sort v 的前 5 个元素. std::partial_sort的复杂性前 K 个元素是 O(N log K) ，接近O(N log N)进行全面排序。对于 K=5 , std::nth_element 之间应该没有什么区别和 std::partial_sort .