可中断的排序函数

5
在我的应用程序中,我需要对一个相当大的数组进行排序,使用例如std::sort是标准的任务。由于该应用程序位于GUI中,我想在排序过程中提供一些响应。我的第一次尝试是确定所需的比较数量的近似值(对于std::sortn*log2(n)),然后在传递给std::sort的比较函数中简单地计数。这个方法非常有效。
为了保持GUI的响应性,排序算法在单独的线程中执行。它使用Qt的信号或某些类似的线程安全机制将其进度通知GUI。
但是,我也希望可以中断排序操作。也就是说,用户可以提供一个按钮或类似的东西来终止整个操作。目前我只看到两种选择:
1. 预先终止线程(例如pthread_cancel)。 2. 重写排序算法并插入显式取消点。
考虑到线程取消应该作为最后的手段,并拒绝重写标准库算法,我正在控制局面。

1
使用例如std::asyncasync launch policy,如果被中止,就不要使用结果,您觉得如何? - Some programmer dude
3
比较器中抛出异常怎么处理? - ks1322
兄弟:我认为与其放弃排序线程,采用一个相当类似的解决方案是更好的选择。但这样会一直占用CPU资源 :-) - Kamajii
@ks1322:英雄所见略同——在我回答之时,我还没有看到您的评论。 - Martin Bonner supports Monica
1个回答

7

让比较函数检查原子标志并在标志被设置时抛出异常。排序线程应该捕获异常并干净地退出。然后GUI线程只需要设置这个标志。


也就是说,@ks1322:这真是让人沮丧的精彩。对我来说,异常处理终于有了一个合理的应用... - Kamajii
排序数组存在潜在问题,可能被异常破坏。由于std::sort是原地排序,因此可能是安全的,但是std::stable_sort或std::list::sort(通常是归并排序的变体)可能会有一些数据卡在临时缓冲区中。 - rcgldr
@rcgldr 这可以归为“如果你正在使用异常,你的代码必须是异常安全的”这个范畴。最基本的要求是对象必须可析构;但你还需要确保任何未被异常销毁的对象在之后处于一致的状态。 - Martin Bonner supports Monica
@MartinBonner - 最近在Visual Studio的std::list::sort中出现了这个问题。请查看关于异常安全性的先前线程(特别是抛出异常的比较)。 - rcgldr

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接