建议C++容器保存前20个最小值

如果我的SQL是正确的,比如10,000条记录,这应该返回我的数据库中的20个最小距离.

我没有数据库.我有一个100,000元素的简单数组.

是否有C++容器,Boost,MFC或STL为结构提供简单的代码

struct closest{
    int    ID;
    double distance;
    closest():ID(-1), distance(std::numeric_limits::max( )){}
};

我可以在哪里建立一个按距离排序的容器

boost::container::XXXX top(20);

然后有一个简单的

top.replace_if(closest(ID,Distance));

如果容器将使用我的新条目替换当前最高距离的条目,如果它小于我容器中的当前最高距离.

我并不担心速度.我喜欢优雅干净的解决方案,其中容器和代码做所有的繁重.

编辑.收到所有重要答案后的附录.

由于它的优雅,我真的很想找到它.是一个可以使用容器大小限制创建的已排序容器.在我的情况下20.然后我可以推送或插入我心中的内容10万件或更多.但.总有一个但是.如果容器的比较器值不在最低的20个值内,则通过替换或不插入项目,容器将保持最大20的大小.

是.我现在从所有这些答案中知道,通过编程和调整现有容器,可以实现相同的效果.也许当C&C++标准委员会的下一轮建议出现时.我们可以建议.自我分类(我们已经有了)和自我限制容器.

你需要的是有一个大小为20的最大值.回想一下你的堆的根将是堆中的最大值.

此堆将包含到目前为止遇到的距离最小的记录.对于10000个值中的前20个,您只需按下堆即可.

此时,您将遍历其余记录,并为每条记录将其与堆的根进行比较.

请记住,堆的根基本上是最好的最差的.(具有最大距离的记录,在迄今为止遇到的最短距离的20条记录中).

如果您考虑的值不值得保留(它的距离大于树的根),请忽略该记录并继续移动.

否则你弹出你的堆(摆脱根)并推入新的值.优先级队列将自动再次将其记录与根上的最大距离放在一起.

一旦你在整个10000个值的集合中继续这样做,你将留下20个距离最小的记录,这就是你想要的.

每个push-pop需要持续的O(1)时间,迭代N的所有输入都是O(n),因此这是一个线性解决方案.

编辑:我认为用C++代码展示我的想法会很有用.这是一个玩具示例,您可以使用模板编写通用版本,但我选择保持简单和简约:

#include 
#include 
using namespace std;
class smallestElements
{
private:
    priority_queue,std::less > pq;
    int maxSize;
public:
    smallestElements(int size): maxSize(size)
    {
    pq=priority_queue, std::less >();
    }
    void possiblyAdd(int newValue)
    {
        if(pq.size(),std::less > cp=pq;
        while(cp.size()!=0)
        {
            cout<

你如何使用它是非常直截了当的.基本上在你的主要功能中你将拥有:

smallestElements se(20); //we want 20 smallest
//...get your stream of values from wherever you want, call the int x
se.possiblyAdd(x); //no need for bounds checking or anything fancy
//...keep looping or potentially adding until the end

se.printAllValues();//shows all the values in your container of smallest values
// alternatively you can write a function to return all values if you want

        
是的,但是对于O(n)迭代,它不接近线性解,但它是线性解. 

2> MikeMB..：
如果这是关于在运行中过滤流中的20个最小元素,那么基于std::priority_queue(或std::multiset)的解决方案是可行的.

但是,如果要找到给定数组中的20个最小元素,我根本不会选择一个特殊容器,而只是算法std::nth_element- 一个部分排序算法,它将为您提供n个最小元素 - 编辑:或者std::partial_sort(谢谢Jarod42)如果元素也必须排序.它具有线性复杂性,它只是一行编写(+比较运算符,在任何情况下都需要):  

#include 
#include 
#include 

struct Entry {
    int ID;
    double distance;    
};

std::vector data;    

int main() {
    //fill data;

    std::nth_element(data.begin(), data.begin() + 19, data.end(), 
        [](auto& l, auto& r) {return l.distance < r.distance; });

    std::cout << "20 elements with smallest distance: \n"; 
    for (size_t i = 0; i < 20; ++i) {
        std::cout << data[i].ID << ":" << data[i].distance << "\n";
    }
    std::cout.flush();
}


如果您不想更改原始数组的顺序,则必须首先复制整个数组.

        

3> Mario..：
我的第一个想法是使用std::map或std::set使用自定义比较器(编辑:甚至更好,std::priority_queue如评论中所述).

您的比较器进行排序.

您基本上将所有元素添加到它.添加元素后,检查内部是否有多个n元素.如果有,请删除最后一个.

        

4> Marandil..：
我不是百分百肯定,没有更优雅的解决方案,但即使是std :: set也非常漂亮. 

您所要做的就是为元素定义一个合适的比较器(例如>运算符),然后执行以下操作:

std::set tops(arr, arr+20)
tops.insert(another);
tops.erase(tops.begin());

        

5> graham.reeds..：
nth_element在删除它之前我会像@juanchopanza一样使用它.

他的代码看起来像:

bool comp(const closest& lhs, const closest& rhs)
{
    return lhs.distance < rhs.distance;
}


然后

std::vector v = ....;
nth_element(v.begin(), v.begin() + 20, v.end(), comp);


虽然如果它只有二十个元素,那么我会用一个std::array.