How can I find the minimum value in a map?

Question

I have a map and I want to find the minimum value (right-hand side) in the map. Here is how I did it:

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;

The code above works fine and I'm able to get the minimum value. However, when I put this code inside my class as follows, it doesn't seem to work:

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

How can I make the code work with my class? Also, is there a better solution which doesn't require writing the additional compare function?

Solution 1

You have a few options. The "best" way to do this is with a functor, this is guaranteed to be the fastest to call:

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

(You can also nest the CompareSecond class inside MyClass.

With the code you have now, you can easily modify it to work, however. Just make the function static and use the correct syntax:

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

Solution 2

In C++11 you can do this:

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

Or put it in a nice function like this (note I'm not a template guru; this is probably wrong in many ways):

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

---

With C++14, it further simplifies to:

min_element(pairs.begin(), pairs.end(),
            [](const auto& l, const auto& r) { return l.second < r.second; });

Solution 3

The problem is that this:

bool MyClass::compare

Requires an instance of the class to be called on. That is, you can't just call MyClass::compare, but you need someInstance.compare. However, min_element needs the former.

The easy solution is to make it static:

static bool MyClass::compare

// ...

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

This no longer requires an instance to be called on, and your code will be fine. You can make it more general with a functor, though:

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());

All this does is grab the second from each pair and grab them, works with any pair. It could be made for general, but that's a bit too much.

If you need to look up by value enough, I recommend you use Boost's Bimap. It's a bi-directional map, so both the key and value can be used to lookup. You would simply get the front of the value-key map.

Lastly, you can always just keep track of the minimum element going into your map. Every time you insert a new value, check if it's lower than your current value (and that should be probably be a pointer to a map pair, start it as null), and if it's lower, point to the new lowest. Requesting the lowest becomes as simple as dereferencing a pointer.

Solution 4

I actually have another question: if you need to regularly obtain the minimum of the right-hand side values are you sure than a map is the best structure ?

I would suggest using Boost.MultiIndex in general for these problems of multiple ways of indexing the same set of objects... but if you only need this "reverse-mapping" bit Boost.Bimap might prove easier.

This way you won't have a linear search when looking for the minimum :)

Solution 5

C++14

As mentioned in Jonathan Geisler's comment on Timmmm's answer, C++14 allows lambda function parameters to be declared with the auto type specifier. As a result, you can shorten Timmmm's lambda-based min_element line (and improve its readability) as follows:

auto it = std::min_element(std::begin(mymap), std::end(mymap),
                           [](const auto& l, const auto& r) { return l.second < r.second; });

Note 1: If you put this line into your MyClass::getMin() function, you have to return it->second. However, to account for an empty map, you should adapt the return line as follows (or similar):

return it == mymap.end() ? -1 : it->second;

Note 2: As also mentioned by Lance Diduck, you should be passing the map by const reference to your getMin() function. The way you did it, you are creating an unnecessary copy of the whole map.

Code on Ideone

View more solutions