在地圖中查找最小值

Question

我有地圖，我想在地圖中找到最小值（右側）。現在，這裏是我是如何做到的

bool compare(std::pair<std::string ,int> i, pair<std::string, int> j) { 
    return i.second < j.second; 
} 
//////////////////////////////////////////////////// 
std::map<std::string, int> mymap; 

mymap["key1"] = 50; 
mymap["key2"] = 20; 
mymap["key3"] = 100; 

std::pair<char, int> min = *min_element(mymap.begin(), mymap.end(), compare); 
std::cout << "min " << min.second<< " " << std::endl; 

這工作得很好，我能得到最小值的問題是，當我把這個代碼我的課裏面似乎並沒有工作

int MyClass::getMin(std::map<std::string, int> mymap) { 
    std::pair<std::string, int> min = *min_element(mymap.begin(), mymap.end(), 
               (*this).compare); 
               //error probably due to this 

    return min.second; 
} 

bool MyClass::compare(
    std::pair<std::string, int> i, std::pair<std::string, int> j) { 
    return i.second < j.second; 
} 

還有一個更好的解決方案，不涉及寫入額外compare函數

Answer 1

您有幾個選項。 「最好」的方式做到這一點與函子，這是保證以最快的速度撥打：

typedef std::pair<std::string, int> MyPairType; 
struct CompareSecond 
{ 
    bool operator()(const MyPairType& left, const MyPairType& right) const 
    { 
     return left.second < right.second; 
    } 
}; 



int MyClass::getMin(std::map<std::string, int> mymap) 
{ 
    std::pair<std::string, int> min 
     = *min_element(mymap.begin(), mymap.end(), CompareSecond()); 
    return min.second; 
} 

（還可以嵌套在CompareSecond類中MyClass

隨着代碼。你現在，你可以輕鬆地修改它的工作，但只是使功能static，並使用正確的語法：

static bool 
MyClass::compare(std::pair<std::string, int> i, std::pair<std::string, int> j) 
{ 
    return i.second < j.second; 
} 

int MyClass::getMin(std::map<std::string, int> mymap) 
{ 
    std::pair<std::string, int> min = *min_element(mymap.begin(), mymap.end(), 
               &MyClass::compare); 
    return min.second; 
} 

Answer 2

的問題是這樣的：

bool MyClass::compare 

需要調用該類的實例。也就是說，你不能只打電話MyClass::compare，但你需要someInstance.compare。但是，min_element需要前者。

簡單的解決方法是讓static：

static bool MyClass::compare 

// ... 

min_element(mymap.begin(), mymap.end(), &MyClass::compare); 

此不再需要一個實例來調用，並且您的代碼將被罰款。你可以把它更普遍的一個函子，雖然：

struct compare2nd 
{ 
    template <typename T> 
    bool operator()(const T& pLhs, const T& pRhs) 
    { 
     return pLhs.second < pRhs.second; 
    } 
}; 

min_element(mymap.begin(), mymap.end(), compare2nd()); 

這一切確實是從每對搶第二，抓住他們，任何對工作。它可以做成普通的，但有點太過分了。

如果您需要按價值查找，我建議您使用Boost的Bimap。這是一個雙向映射，所以鍵和值都可以用來查找。您只需獲得價值鍵映射的前端。

最後，您可以隨時跟蹤進入地圖的最小元素。每次插入新值時，檢查它是否低於當前值（並且應該可能是指向地圖對的指針，將其作爲空值啓動），如果值較低，則指向新的最低值。請求最低就像取消引用指針一樣簡單。

Answer 3

我其實還有另外一個問題：如果您需要定期獲得最小的右手邊值，您確定比map是最好的結構？

我建議一般爲索引同一組對象的多種方式這些問題用Boost.MultiIndex ...但如果你只需要這個「反向映射」位Boost.Bimap可能被證明更容易。

這種方式尋找最小:)

Answer 4

在C++ 11，你能做到這一點的時候，你不會有一個線性搜索：

auto it = min_element(pairs.begin(), pairs.end(), 
         [](decltype(pairs)::value_type& l, decltype(pairs)::value_type& r) -> bool { return l.second < r.second; }); 

或者把它在一個不錯的功能，像這（注意我不是一個模板大師;這可能是錯誤的在許多方面）：

template <typename T> 
typename T::iterator min_map_element(T& m) 
{ 
    return min_element(m.begin(), m.end(), [](typename T::value_type& l, typename T::value_type& r) -> bool { return l.second < r.second; }); 
}