Make std::max_element skip element if bool flag is set

Question

I have a vector of items and a boolean flag:

std::vector<std::pair<Item, bool>> items;

I'm doing a greedy (and inneficient, I'm aware of that and it's on purpose) search of all the best items in this vector at each iteration. After each iteration I invalidate the current best item by setting the boolean flag to false. So in the next iteration this item will no longer be considered, at least that's what I'm trying to do. I want to keep this going untill all elements are false. I get the best value with this GetYield function provided by the Item class:

while( std::any_of( items.begin(), items.end(),
    []( const auto& item ) { return item.second; } ) )
{
    auto max_element = std::max_element( items.begin(), items.end(),
        [&]( auto& itema, auto& itemb )
        {
                return  itema.second && itemb.second && ( itema.first.GetYield() < itemb.first.GetYield() );
        } );

    max_element->second = false;
}

This code hangs as soon as the first element is set to false, it keeps returning the same element over and over. How can I fix this without removing elements from the vector(that's the whole reason I made a pair with a boolean) ?

Answer 1

Your predicate is incorrect. It should compare two elements in the vector, and returns false if the first one is 'less' than the second.

There are four cases here:

• If both items are empty, then the comparison should return false.
• if itemA.second is false, the the comparison should return true.("empty" is less than anything)
• if itemB.second is false is the comparison should return false. ("something" is always greater than "empty")
• If neither is empty, then you can compare GetYield()

Your comparison function returns false, false, false, and GetYield() for these four cases.

Answer 2

Your comparison is wrong, safer is to rely on std::tuple/std::pair/std::vector comparison with appropriate projection;

const auto proj = [](const auto& p){ return std::pair{p.second, p.first.GetYield()}; };
while (true)
{
    auto it = std::max_element(items.begin(), items.end(),
                               [](const auto& lhs, const auto& rhs){
                                   return proj(lhs) < proj(rhs);
                               });
    if (it == items.end() || it->second == false) { break; }
    // do_job(it->first);
    it->second = false;
}