我需要在C++中找到未排序的长度为n的数组/向量的k个最大元素的索引,其中k <n.我已经看到如何使用nth_element()来查找第k个统计量,但是我不确定使用它是否是我的问题的正确选择,因为我似乎需要对nth_statistic进行k调用,我猜它会有复杂度O(kn),它可能会得到它的好处吗？或者有没有办法在O(n)中做到这一点？
在没有nth_element()的情况下实现它似乎我将不得不迭代整个数组一次,在每一步填充最大元素的索引列表.
标准C++库中是否有任何内容可以使它成为一个单行或任何巧妙的方法来自己实现这几行？在我的特殊情况下,k = 3,n = 6,因此效率不是一个大问题,但找到一个干净有效的方法来为任意k和n做这个很好.
看起来Mark未排序数组的前N个元素可能是我在SO上找到的最接近的帖子,其中的帖子有Python和PHP.
我有这个C文件(sample.c):
#include <stdio.h>
#define M 42
#define ADD(x) (M + x)
int main ()
{
printf("%d\n", M);
printf("%d\n", ADD(2));
return 0;
}
我编译的是:
$ gcc -O0 -Wall -g3 sample.c -o sample
然后调试
$ gdb ./sample
GNU gdb (Gentoo 7.3.1 p2) 7.3.1
Copyright (C) 2011 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type …我正在实现一些类来表示映射(在数学意义上),即f:R x R ^ n - > R ^ n.我想实现一个抽象基类:1)将std :: array作为引用并修改它或者2)返回一个std :: array(按值或通过引用,不确定？)
选项2的语法对我来说更为可取,因为我认为代码看起来更像我试图表示的数学,但我想确保我不是不必要地复制东西并引发一堆不希望的开销.例如,如果我有:
// Function f declaration
std::array<double, 4> f(double t, const std::array<double, 4> & x);
// Some code snippet that uses f
std::array<double, 4> x = {0.0, 1.0, 2.0, 3.0};
double t = 0.0;
std::array<double, 4> dxdt = f(t, x);
如何确定是否在最后一行执行了副本,或者如何确保它不会发生？
在f()的定义中,我需要做什么(如果有的话)以确保在不调用复制构造函数的情况下返回它？我想保持使用简单,所以客户端不需要使用指针或智能指针,但也许这是必要的？
我知道我可以将其更改为返回void并且只使其中一个参数为std :: array dxdt,但我更喜欢返回值语法,只要没有性能损失或内存泄漏问题.