Найдите самые большие значения X в большом файле с помощью дополнительного метода анализа командной строки входного файл ⇐ C++

[Гость]

У меня есть файл в следующем фиксированном формате:

Код: Выделить всё

например,

Код: Выделить всё

1426828011 9
1426828028 350
1426828037 25
1426828056 231
1426828058 109
1426828066 111
.
.
.

Я хочу написать программу, которая считывает из стандартного ввода содержимое файла и, при необходимости, принимает
абсолютный путь к файлу из командной строки. Ожидается, что поток file/stdin
будет иметь указанный выше формат. Выходные данные должны представлять собой список уникальных идентификаторов, связанных
с наибольшими значениями X в крайнем правом столбце, где X указывается входным
параметром.
Например, учитывая приведенные выше входные данные и X=3, следующий результат будет
действительным:

Код: Выделить всё

1426828028
1426828066
1426828056

Обратите внимание, что вывод не обязательно должен быть в каком-то определенном порядке. Множественные экземпляры
одного и того же числового значения считаются отдельными записями общего числа X. Итак, если у нас есть 4
записи со значениями: 200, 200, 115, 110 и X=2, тогда результат должен состоять из два
идентификатора, которые указывают на 200 и 200 и не более.
Примечание: учитывайте очень большие файлы.
Моя идея и краткая реализация:
Сортировка по k-максимальным значениям

Код: Выделить всё

1st way: I want to read file content into multimap then iterate k elements to output
2nd way: Read file data into a vector
> then use heap sort (priority queue).

Мне интересно, какой способ имеет лучшую временную сложность и более высокую производительность? Временная сложность второго способа должна быть nlog(n). Является ли временная сложность первого способа log(n)? Расскажите, пожалуйста, о временной и пространственной сложности вышеуказанных методов и предложите другие, более эффективные методы.
Кроме того, входной файл огромен, поэтому я подумываю об использовании внешней сортировки. Но я не делал этого раньше. Я был бы признателен, если бы кто-нибудь мог проинструктировать меня или написать пример кода для моего лучшего понимания.
В любом случае сортировать вывод не требуется. Нам нужно вывести только X-максимальные значения в любом порядке. Поэтому мне интересно, нужно ли мне использовать какой-либо алгоритм сортировки. Требование печатать самые большие X-значения в любом порядке является странным, поскольку перед печатью мы должны отсортировать их по убыванию. Так что я даже не знаю, почему здесь написано «в любом порядке», как будто это упрощает задачу.
Мой краткий код:

Код: Выделить всё

#include 
#include 
#include 
#include 
//#include "stdafx.h"

using namespace std;

std::multimap mp;

typedef std::pair mypair;

struct IntCmp {
bool operator()(const mypair &lhs, const mypair &rhs) {
return lhs.second < rhs.second;
}
};

void printK(const std::map &mymap, int k) {
std::vector myvec(mymap.begin(), mymap.end());
assert(myvec.size() >= k);
std::partial_sort(myvec.begin(), myvec.begin() + k, myvec.end(), IntCmp());

for (int i = 0; i < k; ++i) {
std::cout 

Подробнее здесь: [url]https://stackoverflow.com/questions/71893605/find-x-largest-values-in-a-large-file-with-optional-input-file-command-line-pars[/url]