C++ - 读取 1000 个 float 并通过仅保留最低的 10 个数字将它们插入大小为 10 的 vector 中

Question

所以我是 c++ 的新手，我不确定是否已经创建了一个数据结构来促进我正在尝试做的事情(所以我不会重新发明轮子):

我想做什么

我正在读取一个文件，我需要在其中解析文件，对文件每一行的每个浮点值进行一些计算，然后按升序返回文件中的前 10 个结果。

我要优化什么 我正在处理一个 1k 文件和一个 190 万行文件，因此对于每一行，我将得到大小为 72 的结果，因此在 1k 行中，我需要为 190 万行分配一个包含 72000 个元素的 vector 。 .. 好吧，你明白了。

到目前为止我有什么

我目前正在为结果使用一个 vector ，然后我对其进行排序并将其大小调整为 10。

const unsigned int vector_space = circularVector.size()*72;
//vector for the results
std::vector<ResultType> results;
results.reserve(vector_space);

但这是非常低效的。

*我想完成的事情* 我只想保留一个大小为 10 的 vector ，每当我执行计算时，我只需将值插入 vector 并删除 vector 中最大的 float ，从而保持前 10 个结果按升序排列。

C++ 中是否已经存在具有这种行为的结构？

谢谢!

Answer 1

编辑:更改为使用 10 个最低元素而不是最高元素，因为现在的问题清楚地表明需要哪些元素

您可以使用包含 10 个元素的 std::vector 作为最大堆，其中元素是部分排序的，因此第一个元素始终包含最大值.请注意，以下内容均未经测试，但希望它能帮助您入门。

// Create an empty vector to hold the highest values
std::vector<ResultType> results;

// Iterate over the first 10 entries in the file and put the results in the vector
for (... ; i < 10; i++) {
    // Calculate the value of this row
    ResultType r = ....
    // Add it to the vector
    results.push_back(r);
}

// Now that the vector is "full", turn it into a heap
std::make_heap(results.begin(), results.end());

// Iterate over all the remaining rows, adding values which are lower than the
// current maximum
for (i = 10; .....)  {
    // Calculate the value for this row
    ResultType r = ....

    // Compare it to the max element in the heap
    if (r < results.front()) {
         // Add the new element to the vector
         results.push_back(r);
         // Move the existing minimum to the back and "re-heapify" the rest
         std::pop_heap(results.begin(), results.end());
         // Remove the last element from the vector
         results.pop_back();
    }
}

// Finally, sort the results to put them all in order
// (using sort_heap just because we can)
std::sort_heap(results.begin(), results.end());