多次对向量进行排序 [英] Sorting a vector multiple times

问题描述

我必须编写一个程序，该程序接受多行输入，然后根据给定的几个命令行参数对它们进行排序.该行可以是可变长度的，并且该行上的每个项目都用逗号分隔，如下所示:

I have to write a program that takes in several rows of input, then sorts them based on several command line arguments given. The row can be of variable length, and each item on the row is separated by a comma, like this:

a,b,c,12,3
d,e,f,4,56
a,g,h,8,5

程序要做的是根据给定的参数对某些列上的输入进行排序.这很简单，但是困难的部分是我还必须能够对多个参数进行排序.

What the program has to do is sort the input on certain columns based on the argument given. That's simple, but the hard part is I also have to be able to sort on multiple arguments.

例如，命令行参数1,4(均为升序)将输出以下内容:

for example, the command line arguments 1,4 (both ascending) would output this:

a,g,h,8,5
a,b,c,12,3
d,e,f,4,56

因此，它基于第一列，然后是第四列进行排序.我不确定如何排序，然后仅使用下一个参数对冲突的元素进行排序，而无需重新排序整个列.我目前正在将输入存储在向量的向量中.

So it sorts based on the first column, then the 4th column. I'm not sure how to sort something, then only sort the conflicting elements using the next argument without resorting the entire column. I'm currently storing the input in a vector of vectors.

作为旁注，我已经阅读了一些类似的问题，但是所有这些问题都有一定数量要分类.对于此程序，每行的项目数可以是1到向上的任意值，并且要作为排序依据的参数的数量也可以是可变的.

As a side note, I've read some similar questions, but all of them only have a set number of things to sort by. For this program, the number of items per row can be anywhere from 1 upwards, and the number of arguments to sort by can be variable too.

推荐答案

首先，使用std :: sort()首先将其与迭代器一起使用，最后将其作为输入. 然后，使用递归.递归是您解决方案的关键.

First of all, use std::sort() which works with iterators first, last as input. Then, use recursion. Recursion is key to your solution.

对于每个参数，即排序标准C_i，您有一个递归级别R_i.在每个递归级别R_i中，您可以执行两个步骤:

For each argument, i.e. sorting criterion C_i, you have one recursion level R_i. Within each recursion level R_i, you have two steps:

1. 根据条件C_i对给定的数据范围进行排序.
2. 遍历数据范围.每当值C_i更改时，请使用参数调用下一个递归级别R_ {i + 1}:
   • 第一个:迭代器到最后一个更改或范围的开始
   • last:迭代到当前元素(第一个C_i更改的元素)
   • 对标准列表和i + 1的引用/指针

1. Sort the given data range according to criterion C_i.
2. Loop through the data range. Whenever the value C_i changes, call the next recursion level R_{i+1} with arguments:
   • first: iterator to the last change, or, beginning of the range
   • last: iterator to the current element (the first element with changed C_i)
   • reference/pointer to the criterion list and i+1

就是这样！

讨论此解决方案:

• 由于迭代器的存在，此方法非常有效，因为不需要重新初始化底层数据结构，在周围复制等.
• 您需要编写一个自定义比较器函子，该函子用i初始化，并将始终根据向量的元素i进行比较.
• 更快的速度值得商::更快地进行一次大分类，每次比较都必须符合所有分类标准，或者像我的方法那样进行多次分类，并且每次仅检查一个标准.
• 在此解决方案中，交换了许多向量.但这不是问题，因为std :: vector交换很便宜.

这篇关于多次对向量进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！