C++ Finding minimum in vector of structs using custom comparator

Question

I have a vector of structs:

struct element_t {
    int val;
    bool visited;
};

With a custom comparator:

bool cmp(const element_t& lhs, const element_t& rhs)
{
    return ((lhs.val < rhs.val) && (!lhs.visited) && (!rhs.visited));
}

Used with:

std::vector<element_t> vct_priority(n_elems, {2147483647, 0});

In my algorithm, I want to iteratively find the element with the smallest value that has not been visited yet, work with it, and then "disable" it by setting visited to true, so that this element is not found in the next iteration.

it = std::min_element(std::begin(vct_priority), std::end(vct_priority), cmp);
indx_smallest = std::distance(std::begin(vct_priority), it);
// do something here
vct_priority[indx_smallest].visited = 1;

Normally I would use a priority queue, but as I need to index into this array during the algorithm, I couldn't find a better way.

The problem is, that this approach is fishy. In cases where vct_priority looks like this:

{1,true}
{0,true}
{1,false}
{0,true}
{2,false}
{2147483647,false}
{2147483647,false}
{0,true}
{1,false}
{0,true}
{2,false}
{2147483647,false}
{1,false}

The computed indx_smallest is incorrectly 0, instead of 2.

Could you help me find the error, or suggest some better suitable solution?

Answer 1

It is evident that you need to define the comparison function correctly.

Here you are.

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int main()
{
    struct element_t {
        int val;
        bool visited;
    };

    std::vector<element_t> vct_priority =
    {
        { 1, true }, { 0, true }, { 1, false }, { 0, true },
        { 2, false }, { 2147483647, false }, { 2147483647, false },
        { 0, true }, {1, false }, { 0, true }, { 2, false },
        { 2147483647, false }, { 1, false }
    };

    auto less_not_visited = []( const auto &e1, const auto &e2 )
    {
        return ( not e1.visited ) && ( e2.visited or e1.val < e2.val );
    };

    auto min = std::min_element( std::begin( vct_priority ),
        std::end( vct_priority ),
        less_not_visited );

    std::cout << std::distance( std::begin( vct_priority ), min ) << '\n';
}

The program output is

2

If you want to define a separate function instead of the lambda expression then it looks like

bool less_not_visited( const element_t &e1, const element_t &e2 )
{
    return ( not e1.visited ) && ( e2.visited or e1.val < e2.val );
};