我必须编写一个程序来接收多行输入,然后根据给定的几个命令行参数对它们进行排序。行可以是可变长度的,行中的每一项都用逗号分隔,如下所示:
a,b,c,12,3
d,e,f,4,56
a,g,h,8,5
程序要做的是根据给定的参数对某些列的输入进行排序。这很简单,但困难的部分是我还必须能够对多个参数进行排序。
例如,命令行参数 1,4(均为升序)将输出:
a,g,h,8,5
a,b,c,12,3
d,e,f,4,56
所以它根据第一列排序,然后是第四列。我不确定如何对某些内容进行排序,然后只使用下一个参数对冲突元素进行排序,而不是对整个列进行排序。我目前正在将输入存储在 vector 的 vector 中。
作为旁注,我读过一些类似的问题,但所有这些问题都只有一定数量的东西可以排序。对于这个程序,每行的项目数可以是 1 以上的任何值,排序依据的参数数量也可以是可变的。
最佳答案
首先,使用 std::sort() ,它首先与迭代器一起工作,最后作为输入。 然后,使用递归。递归是解决方案的关键。
对于每个参数,即排序标准 C_i,您有一个递归级别 R_i。在每个递归级别 R_i 中,您有两个步骤:
- 根据标准 C_i 对给定的数据范围进行排序。
- 遍历数据范围。每当值 C_i 更改时,调用下一个递归级别 R_{i+1} 并带参数:
- first:指向最后一个更改的迭代器,或者范围的开头
- last:指向当前元素的迭代器(第一个改变了C_i的元素)
- 标准列表和 i+1 的引用/指针
就是这样!
这个解决方案的讨论:
- 由于有迭代器,这种方法非常高效,因为底层数据结构不需要重新初始化、复制等。
- 您需要编写一个用 i 初始化的自定义比较器仿函数,并始终根据 vector 的元素 i 进行比较。
- 哪个更快是有争议的:进行一次大排序,每次比较都必须通过所有排序标准,或者多次排序,就像我的方法一样,每次只检查一个标准。
- 在这个解决方案中,交换了很多 vector 。但这不是问题,因为 std::vector 交换很便宜。
关于c++ - 多次对 vector 进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15183953/