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

Question

在SQL中有一个类似的功能

SELECT TOP 20 distance FROM dbFile ORDER BY distance ASC

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

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

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

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

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

boost::container::XXXX<closest> top(20);

然后有一个简单的

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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

#include <iostream>
#include <queue>
using namespace std;
class smallestElements
{
private:
    priority_queue<int,std::vector<int>,std::less<int> > pq;
    int maxSize;
public:
    smallestElements(int size): maxSize(size)
    {
    pq=priority_queue<int, std::vector<int>, std::less<int> >();
    }
    void possiblyAdd(int newValue)
    {
        if(pq.size()<maxSize)
        {
            pq.push(newValue);
            return;
        }
        if(newValue < pq.top())
        {
            pq.pop(); //get rid of the root
            pq.push(newValue); //priority queue will automatically restructure
        }
    }
    void printAllValues()
    {
        priority_queue<int,std::vector<int>,std::less<int> > cp=pq;
        while(cp.size()!=0)
        {
            cout<<cp.top()<<" ";
            cp.pop();
        }
        cout<<endl;
    }
};

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

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

Answer 2

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

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

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

struct Entry {
    int ID;
    double distance;    
};

std::vector<Entry> 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();
}

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

Answer 3

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

您的比较器进行排序.

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

Answer 4

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

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

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

Answer 5

nth_element在删除它之前我会像@juanchopanza一样使用它.

他的代码看起来像:

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

然后

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

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