如何基於過去在C++中的成功獲得具有自適應排序的整數集合？

Question

我在C++ 03中有一組整數，其中整數表示相對於參考點的猜測。該算法通過一長串項目運行，並且對於每個項目，它會嘗試相對於該項目的參考點的每個整數猜測（昂貴的操作），直到找到匹配或所有猜測都用盡。一個項目最多匹配一個猜測，但可能不匹配。我想計算每個相對整數猜測成功找到匹配的次數，以便在迭代的每個下一個項目上，對該項目的猜測集合進行排序，以使得那些成功最多的猜測來到那些成功較少的猜測基於已經處理的項目。

我可以想象使用std :: map將每個相對猜測映射到相對猜測已成功找到匹配的次數。因此，在每個項目的迭代中，我可以反轉地圖，並將所有地圖的值多重映射到其鍵。反過來在第二個multimap上迭代，我可以處理每個項目的猜測，從最成功的猜測開始，直到找到匹配。此時，第一張地圖將被更新，以指示現在哪個猜測還有更多的成功。同樣，第二個multimap將被更新以從其舊成功計數中移除匹配猜測，並將其重新插入到現在遞增的成功計數中。

但是，這看起來很複雜，我想有一個更優雅的答案。雖然，可能值得浪費的努力，通過從頭開始重新構建多重映射而不是試圖增量維護它，使代碼更易於理解。

有沒有一種適合這個問題的已知設計模式數據結構？我怎麼能最好地排序我的猜測，使更多的成功猜測冒泡到頂端？在這裏應用優先級隊列有意義嗎？

Answer 1

我會帶着一個struct去成功計數和猜測。從所有初始猜測開始，每個成功計數爲0.在每次通過時，從my_vec.begin()開始並遍歷到​​3210。如果猜測成功，則停止迭代，增加成功計數，並根據成功計數將其提升到正確的位置。

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

的（guess，correct）pair S（或struct多個）std::vector。

遞增correct（二進制？）搜索正確的點，在正確的猜測和新的點之間滑動元素1.可能滑入「叢」會比一次滑動一個元素快，但可能不會。

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

鑑於您已經從開始到這裏迭代，搜索和幻燈片將足夠快。迭代的局部性和速度將彌補兩個整數的幻燈片成本。

如果你想要更少的代碼，從計數到猜測的多重映射，迭代記憶迭代器，如果成功通過迭代器刪除，增加計數，並重新插入。可能會變慢。

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