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?

Piscatory

THe getMin function should be passing the argument by const reference, and not by value. Also, you will have a problem when the map has no elements at all, so consider not dereferecing the iterator before makig sure end() was not returned. – Facelifting

en.cppreference.com/w/cpp/algorithm/min_element has linear time. So it's better to implement its own associative container R/B, AVL, 2-3 and support minimum operation for it if standard library does not support it. – Chemosmosis

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

Homesteader

I hit the format button for you. You need to specify the template arguments to the functor or pass an unused argument to a factory. Or template the operator() instead of the whole class… that's the best way, yeah :vP . – Homing

I agree, operator() should be templated in best practice. However, I think the code should illustrate the point. What do you mean by "specify the template arguments"? Do you mean derive from binary_function? I don't believe that is required for min_element... – Homesteader

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

Starknaked

I made my lambda more succient by just using auto for the parameter types l and r. That may require C++14, however. – Gitlow

Answer 3

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

Autocatalysis

Answer 4

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.

Gnathic

Answer 5

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 :)

Bentinck

I suppose there is still no strictly standards-blessed container for this if I am frequently finding myself trying to get the max/min values of a map? – Bertelli

@Dilip: No, there is not. The Standard only provides the most common structures; and none support double-indexing. Boost.MultiIndex and Boost.Bimap are fairly stable (for years), or you have to do you it yourself. – Bentinck