我正在用c++编写一个国际象棋引擎，并试图制作尽可能干净和正确的代码，因为这是一个学习练习。目前，我有一个move类，它定义了一个可能的move。然后AI对每一个可能的动作进行评分。在数据结构中，将移动的分数与移动本身配对的最佳方法是什么？
每个分数必须能够有一个以上的移动(两个移动都可以有735的分数)。我认为这排除了std:：map？
它也应该是可快速排序的，这样我就可以向前看，并递归地这样做，以获得最佳的移动。
任何帮助都将不胜感激，包括链接。谢谢
您的问题并不完全清楚。一方面，你说你想要一个排序的容器，但另一方面，谈论事情的方式是，你要生成移动，将它们放入容器中，然后根据你的AI定义的标准对它们进行排序。
让我们单独考虑一下。首先，我们假设您想使用分数作为关键，并查找与特定分数相关的动作。在这种情况下，你将生成一个移动，AI将对该移动进行评分，然后你将存储该移动，并将其分数作为关键。由于可以使用相同的分数进行多次移动(即等效键)，因此在这种情况下需要的数据结构是std::multimap。
另一种可能性是，你生成所有的动作，将它们全部放入数据结构中，对它们进行评分，然后按分数对它们进行排序。对于这种情况，您可能希望使用std::vector<std::pair<score_type, move>>。在这种情况下，当你生成每个动作时，你可能会给它分配一个类似0的分数。然后，你可以遍历向量，让人工智能为每个动作生成一个分数。然后你可以使用只考虑分数的比较函数对它们进行排序。
这两种方法都可行。更可取的将取决于具体情况。使用向量可能会最大限度地减少开销——也就是说，它将使用最少的内存和最少的CPU时间来从原始移动到所有移动都按排序顺序存储的向量。
std::multiset的优势在于它始终保持排序。例如，如果你想在达到某个时间限制之前生成移动，它会让你非常干净地完成这一任务——生成移动，得分，将其插入多集。无论你什么时候停下来，到那时为止你生成的所有动作都已经排序了，所以(例如)如果与你的程序对抗的人可以迫使人工智能立即做出动作，人工智能总是有它发现的最佳动作的记录，所以它可以立即做出它"认为"最好的动作。
另一种可能性是使用优先级队列。在国际象棋的典型情况下，你要做的一件事是生成(比如)几十个或可能的下一步。然后，你将从中挑选出最好的，并在可能的反击中得分。然后，你会从中选出最好的，并为这些动作的反击得分，以此类推，直到你在4或5个完整的动作中得分。
为此，您并不真的关心所有的移动是否有序——您只想能够快速检索N个最佳移动。对于这种情况，优先级队列工作得非常好。你可以检索N个最好的动作，然后忽略其余的。这意味着你只对N个最好动作(你关心的动作)进行完全排序，并最大限度地减少其余动作的开销，但只做足够的工作来验证它们的得分是否较低。
我还应该提到，如果这是您真正想要的，那么您可以在数组的情况下完成同样的操作。您可以使用nth_element只查找N个最佳分数，而不是使用sort按分数对所有移动进行排序。nth_element将数组/向量分为两组：一组在某个选定元素之前排序，另一组在选定元素之后排序。例如，给定100个移动，其中你想保留前5个，你可以使用nth_element将它们排列成95个较小的移动，第95个元素，然后是其他4个。但没有尝试在每组中订购物品。
这样做的优点是它可以在O(N)时间内完成，而不是完成排序所需的O(N log N)
在这两种可能性(priority_queue与nth_element)之间，我们得到了与set::multiset和std::vector与std::sort之间大致相同的折衷：priority_queue始终保持其顺序。即使您或多或少地任意混合插入和删除，它仍然非常有效。对于std::vector和std::nth_element，通常需要插入所有元素，然后调用nth_element，然后考虑顶部项目。如果你要混合这两者(插入一些元素，然后删除一些最好的元素，再插入一些，再删除一些，等等)，每次从插入转换到删除时，你都必须调用nth_element，这可能会很快降低效率。
听起来您想要的是一个优先级队列。
它们通常使用Heap(Fibonacci堆，如果你想要效率的话)来实现。堆本身并没有完全排序，但你可以保证在任何给定的时刻都能在顶部获得最佳移动。
Boost有一个Fibonacci堆实现。
你可以看看这个问题。该问题中的MyType可以是一对标准的：Data和Priority
std:：set可以满足您的需要。std:：set>其中X是分数，Y是类对象，或者您可以定义自己的自定义比较器。请参阅：使用自定义std：：设置比较器