https://stackoverflow.com/questions/20963421
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianYour question isn't entirely clear. On one hand, you say you want a sorted container, but on the other, the way you talk about things is that you're going to generate moves, put them into a container, then sort them according to criteria defined by your AI.
Let's consider those separately. For the first, we'll assume you want to use the scores as a key, and look up the moves that go with particular scores. In this scenario, you'll generate a move, the AI will score that move, then you'll store the move, with its score as the key. Since you can have multiple moves with the same score (i.e., equivalent keys), the data structure you want for this case is an std::multimap.
The other possibility would be that you generate all the moves, put them all into a data structure, score them all, then sort them all by score. For this scenario, you probably want to use an std::vector<std::pair<score_type, move>>. In this case, when you generate each move you'd probably assign it a score of something like 0. Then you'd walk through the vector and have the AI generate a score for each move. Then you'd sort them, using a comparison function that only considers the score.
Either of these could work. The one that's preferable would depend on circumstances. Using a vector is likely minimize overhead--that is, it'll use the least memory and least CPU time to get from raw moves to a vector with all the moves stored in sorted order.
The strength of an std::multiset is that it stays sorted all the time. For example, if you want to generate moves until you reach some time limit, it'll let you accomplish that quite cleanly--generate a move, score it, insert it into the multiset. No matter when you stop, all the moves you generated up to that point are already sorted, so (for example) if the person playing against your program can force the AI to make a move immediately, the AI always has a record of the best move its found yet, so it can immediately make the move it "thinks" is best.
Another possibility would be to use a priority queue. In a typical case for chess, one thing you'll do is generate (say) a couple dozen or possible next moves. Then you'll pick the best of those, and score possible counter-moves to those. Then you'll pick the best of those and score the counters to those moves, and so on until you've scored (say) 4 or 5 full moves deep.
For this, you don't really care about having all the moves in order--you just want to be able to retrieve the N best moves quickly. For that case, a priority queue works quite well. You can retrieve the N best moves, then ignore the rest. This means you only fully sort the N best moves (the ones you care about) and minimize the overhead for the rest, but only doing enough to verify that they have lower scores.
I should also mention that if this is what you really want, you can accomplish the same in the array case. Instead of using sort to sort all the moves into order by score, you can use nth_element to find only the N best scores. nth_element arranges an array/vector into two groups: those that would sort before some selected element, then the selected element, then the ones that would sort after that selected element. For example, given 100 moves, of which you want to keep the top 5, you'd use nth_element to arrange them into the 95 lesser moves, the 95th element, then the other 4. No attempt is made at ordering the items within each group though.
The advantage of this is that it can be completed in O(N) time instead of the O(N log N) needed for a complete sort.
Between these two possibilities (priority_queue vs. nth_element) we get much the same tradeoff as between set::multiset and std::vector with std::sort: the priority_queue maintains its order at all times. It remains quite efficient, even if you intermingle insertions and removals more or less arbitrarily. With a std::vector and std::nth_element, you normally want to insert all the elements, then call nth_element, then consider the top items. If you were going to mix the two (insert some elements, then remove a few of the best, insert some more, remove a few more, etc.) you'd have to call nth_element every time you transitioned from inserting to removing, which could kill the efficiency fairly quickly.
