c++ - 采用 2D 输入并同时按行排序的最快方法

Question

我需要一种方法，我可以在其中获取二维数组中的输入并以最快的方式之一对其进行逐行排序。我尝试使用 Insertion Sort 同时获取 Input 和 Sort it。我使用的第二件事是我单独为一行取了一个 multimap 并插入键值作为我想要的值，映射值与该键相关作为一些虚拟值。由于 map 在插入时对键进行排序这可能是我认为的一种方式。

下面的代码用于确保我的 2D 中的 1 行的元素已排序 multimap 。基本上你可以说我根本不想使用 2D 结构，因为我将逐行单独使用这些行，因此可以将其视为一维数组。我也希望他们在阅读输入时重新排列，所以我不必做它们的额外操作。

for(long int j=1;j<=number_in_group;j++)
{
   cin >> arrival_time;
   arrival_map.insert(pair<long int, long int>(arrival_time,1));
}

Answer 1

试试STL std::priority_queue ？保证对输出进行排序，并且如果您将输入极化为二维对象(例如包含行号)，您的队列将完全完美地构建。在这一点上，只需将队列中的数字以 'n' 为一批，其中 'n' 是您的行大小，每个都会被正确排序。您将需要一个元素类型，它对优先级队列中的值和行进行编码，并首先对行进行排序，然后是值。您的示例使用 long int作为您的值的数据类型。假设您的行不大于系统 unsigned int 的大小:

class Element
{
public:
   Element(unsigned int row, long int val)
      : myrow(row), myval(val)
   {};

   bool operator <(const Element& elem)
   {
      return (myrow < elem.myrow || 
             (myrow == elem.myrow && myval < elem.myvel);
   }

   unsigned int myrow;
   long int myval;
};


typedef std::priority_queue<Element> MyQueue;

注意:这利用了优先级队列的默认比较运算符调用 std::less<> ，它使用项目定义的 operator <() 简单地比较项目.一旦你有了这个，只需将你的矩阵插入队列，在你切换到下一行时增加行索引。

我的队列队列；

mq.push_back(Element(1,100));
mq.push_back(Element(1,99));
mq.push_back(Element(2,100));
mq.push_back(Element(2,101));

完成后弹出队列将导致以下序列:99100100101

我希望这是你想要的。最后，请原谅语法错误和/或遗漏的垃圾，因为我只是匆匆忙忙地将它炸毁并且没有编译器来检查它。一定喜欢网吧。