How to find the minimum element in vector of pairs in c++?

Question

if vector is <0,8> <0,3> <1,4> <2,9> <3,5>

Suppose minimum need to be found considering second key of pair value only, here it will be 3.

output: sample.cpp: In function ‘int main()’: sample.cpp:24:45: error: cannot convert ‘std::pair’ to ‘int’ in initialization int i1=*std::min_element(v.begin(),v.end());

How would you do it by hand? Start there, turn that into pseudo code, and then covert that into actual code. — NathanOliver, Dec 04 '18 at 18:46
`std::min_element` with a lambda will solve this. Can you show your attempt? — Cory Kramer, Dec 04 '18 at 18:46
sample.cpp: In function ‘int main()’: sample.cpp:24:45: error: cannot convert ‘std::pair’ to ‘int’ in initialization int i1 =*std::min_element(v.begin(),v.end()); // to find the minimum — Rishav Kumar, Dec 04 '18 at 18:49
you should add the code and the error message in your question. Code in comments is impossible to read — 463035818_is_not_an_ai, Dec 04 '18 at 18:53

tangy · Answer 1 · 2018-12-04T19:00:49.050

You could either do it by a handcrafted for-loop or using STL std::min_element using a lambda. The way you have used it above is incorrect. Here is the correct way:

auto v = std::vector<std::pair<int,int>>{{0,8},{0,3},{1,4},{2,9},{3,5}};
auto result = *std::min_element(v.cbegin(), v.cend(), [](const auto& lhs, const auto& rhs) {
        return lhs.second < rhs.second;    
    });
std::cout << result.first << " " << result.second  << std::endl; // 0 3

You can try this online here and maybe tinker to understand how the lambda works.
std::min_element will work correctly for native types the way you have used it, but for derived ones like std::pair with the custom condition of only picking the second, you need to supply the criteria via a lambda.
I'd recommend reading up on C++ lambdas - theyre extremely handy in general but especially when needing to supply a custom predicate like in your case! Here is another example: C++ priority queue in ascending order by specific method for objects

score 4 · Accepted Answer · edited Jul 21 '20 at 19:09

4

You can use std::min_element and make it test only the second element.

Something like:

std::get<1>(*std::min_element(begin(v), end(v), [](auto lhs, auto rhs) {
  return std::get<1>(lhs) < std::get<1>(rhs)
}));

I'm using get here because I don't know if you are using std::pairs or std::tuples.

As it's still very small structures, no need to pass by const&.

edited Jul 21 '20 at 19:09

Augustin

2,444
23
24

answered Dec 04 '18 at 19:00

Matthieu Brucher

21,634
7
38
62

score 1 · Answer 3 · answered Dec 04 '18 at 18:58

So, the vector looks like this:

vector<pair <int, int> > items = { <0,8> <0,3> <1,4> <2,9> <3,5> };

We need to loop through the items to find the smallest second item. To do that:

int saveIndex = 0
//now we can loop through all of the items in the vector
for(int i = 1; i < items.size(); i++)
{
    if(items[saveIndex].second > items[i].second)
    {
        saveIndex = i;
    }
}

//the smallest second value will be found at
int smallestValue = items[saveIndex].second;

How to find the minimum element in vector of pairs in c++?

3 Answers3