c++ - 如何从 HashTable C++ 中选取最大前 10 个数量？

Question

我已经写了一个工作项目，但我的问题是最后一部分。我已经从 csv 文件读取 500.000 行到 vector 中，然后放入哈希表中。我可以打印整个哈希表，但我需要选择顶部我的哈希表中的 10 个数量。请明确一点，我不会对整个哈希表进行排序，只是选择前 10 个。

我的项目主题是，程序必须能够从 csv 文件存储单个产品(用 StockCode 给出)并将其插入到合适的数据结构中。如果该产品已经插入到结构中，则其计数器必须按订单数量增加。读取和处理结束后，您的程序必须列出个人订购的“前 10 名”产品。

有关于库的规则，这将是一个正确的 C++ 类。您必须能够创建此类的许多实例。 (请不要使用第三方库和C++ STL、Boost等)但是，您可以使用iostream、ctime、fstream、string like IO和字符串类。

重要说明:我唯一应该关注的是速度，存储或大小不是问题。

What I've done so far is,

• Read Csv file row by row into vector
• Stockcodes in row[1], Quantity in row[3]
• Put them into Hashtable and increase their quantity by the quantity of the order.
• Print the whole hash table.

What I need to do is,

• Print the Top 10 Quantity

现在让我们分享示例 csv 文件、驱动程序代码、打印功能的输出。

Csv 文件如下所示:

InvoiceNo;StockCode;Description;Quantity;
536365;85123A;WHITE HANGING HEART T-LIGHT HOLDER;6
536365;71053;WHITE METAL LANTERN;6;
536365;84029G;KNITTED UNION FLAG HOT WATER BOTTLE;6;
536365;84029E;RED WOOLLY HOTTIE WHITE HEART.;6;
536365;22752;SET 7 BABUSHKA NESTING BOXES;2;
536365;21730;GLASS STAR FROSTED T-LIGHT HOLDER;6;

main.cpp

    void printMaxQuantity() {
        int maxValue=0;
        for (int i = 0; i < 1000000; ++i) {
            if(table[i] != nullptr) {
                if (table[i]->quantity > maxValue)
                    maxValue = table[i]->quantity;
                if (table[i]->quantity == maxValue) {
                    cout << "Index: " << i << endl;
                    cout << "StockCode: " << table[i]->stockCode << endl;
                    cout << "Quantity: " << table[i]->quantity << endl;
                    cout << endl << endl;
                }
            }
        }
    }
};

这里是输出:(编辑代码后 StockCode: 85123A 是正确的输出，但仍在前 10 名中挣扎)

Index: 41240
StockCode: 10002
Quantity: 48


Index: 309193
StockCode: 85123A
Quantity: 72



Process finished with exit code 0

还有最后一点，我正在为一个学校项目这样做，所以我不应该使用任何第三方软件或包含任何不同的库，因为这是不允许的(我稍后将实现我自己的 vector 类)

Answer 1

由于这是家庭作业，我将避免编写实际代码。由于您没有有关实际数据集的任何先验信息，因此您需要循环遍历它，这是线性复杂度。为了找到前 10 个项目，我建议您创建一个包含 10 个项目的数组来存储迄今为止获得的最佳项目。

第一步是将前 10 个元素复制到数组中。

第二步是按降序对包含 10 个项目的数组进行排序，因此您将始终使用最后一个项目进行比较。

现在您可以循环大结构，并在每一步中将当前项与十个元素数组中的最后一个进行比较。如果较低，则不执行任何操作。如果更高，则在 10 个项目的数组中找到排名最高的项目，该项目由于质量较高而小于您打算插入的项目。当您找到该项目时，从末尾循环直到该项目，直到您的十个元素的数组，并在每一步中用当前元素覆盖当前元素。最后覆盖现在重复的元素。

示例:假设您的第 7 个元素的质量低于您要插入的元素，但第 6 个元素的质量较高，用第 8 个元素覆盖第 9 个元素，然后用第 7 个元素覆盖第 8 个元素，然后用您刚刚找到的项目覆盖第 7 个元素。请记住，数组索引从 0 开始。