How to have a collection of integers with adaptive ordering based on past success in C++?

Question

I have a set of integers in C++03, where the integers represent guesses relative to a reference point. The algorithm runs through a long list of items, and for each item, it tries each integer guess (an expensive operation) relative to the reference point of that item until it finds a match or all the guesses are exhausted. An item matches at most one guess, but may match none. I would like to count the number of times each relative integer guess successfully finds a match such that on each next item being iterated over, the set of guesses for that item is ordered such that those guesses with the most success come before those with less success based on the items already processed.

I could imagine using a std::map that maps each relative guess to the number of times that relative guess has successfully found a match. With that, on each item's iteration, I could reverse the map and multimap all the map's values backwards to their keys. Iterating over the second multimap in reverse, I could process the guesses on each item, starting with the most successful guesses downward until a match is found. At this point the first map would be updated to indicate which guess now has one more success. Similarly, the second multimap would be updated to remove the matching guess from its old success count and reinserting it in its now incremented success count.

However, this seems complex and I imagine there is a more elegant answer. Although, perhaps it is worth the wasted effort to make the code simpler to understand by rebuilding the multimap from scratch each iteration instead of trying to incrementally maintain it?

Is there a known design pattern data structure that fits well to this problem? How can I best order my guesses such that more successful guesses bubble up to the top? Does it make sense to apply a priority queue here?

Answer 1

I'd go with a struct that holds a success count and a guess. Start out with a std::vector of all the initial guesses, each with a success count of 0. On each pass, start at my_vec.begin() and iterate through to my_vec.end(). If a guess succeeds, stop the iteration, increment the success count, and bubble it up to the right position based on the success count.

for (auto it = my_vec.begin(); it != my_vec.end(); ++it) {
    if (try_it(it->guess)) {
        ++it->successes;
        while (it != my_vec.begin() && it->successes > (it - 1)->successes) {
            swap(*it, *(it - 1));
            --it;
        }
        break;
    }
}