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;
    }
}

Answer 2

std::vector of pairs (or structs) of (guess, correct).

Increment correct, (binary?) search for right spot, slide elements between correct guess and new spot over 1. Possibly sliding in "clumps" will be faster than sliding them one at a time, but maybe not.

std::vector< std::pair< int, std::size_t > > guess_buffer;
template<typename TryGuess>
bool Try( guess_buffer& guesses, TryGuess const& try_guess ) {
  for (guess_buffer::iterator it = guesses.begin(); it != guesses.end(); ++it) {
    if (try_guess( it->first)) {
      it->second++;
      while (it != guesses.begin()) {
        --it;
        if (it->second < (it+1)->second) {
          std::swap( *it, *(it+1) );
        } else {
          return true;
        }
      }
      return true;
    }
  }
  return false;
}

Given that you have iterated from start to here, the search and slide will be fast enough. Locality and speed of iteration will make up for slide costs of two ints.

If you want less code, multi map from count to guess, iterate remembering iterator, if successful remove via iterator, increment count, and reinsert. Will probably be slower.

template<typename X>
struct reverse_order {
  template<typename T, typename U>
  bool operator()( T const& t, U const& u ) const {
    return std::less<X>()( u, t );
  }
};
typedef std::multi_map< std::size_t, int, reverse_order<std::size_t> > guess_map;
template<typename TryGuess>
bool Try( guess_map& guesses, TryGuess const& try_guess ) {
  for( guess_map::iterator it = guesses.begin(); it != guesses.end(); ++it ) {
    if( try_guess( it->second ) )
    {
      std::pair<std::size_t, int> modify = *it;
      guesses.erase(it);
      modify.first++;
      guesses.insert(modify);
      return true;
    }
  }
  return false;
}