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?

CodePudding user response：

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

CodePudding user response：

Your comparator doesn't implement the strict weak ordering that std::min_element() requires. Namely, it doesn't take into account that the two input elements may have different visited states. Since you want to prioritize unvisited structs ahead of visited structs, you need to compare their val field only when both elements have visited=false. Otherwise, if the left-hand element has visited=true and the right-hand element has visited=false then you need to prioritize the right-hand element. But you are not doing that.

However, something to watch out for - std::min_element() always returns a non-end iterator if the input range is not empty. So, if all of your elements have been visited, the resulting iterator will have to be to a visited element. So you will have to account for that, too.

With that said, try this:

bool cmp(const element_t& lhs, const element_t& rhs)
{
    if (!lhs.visited && !rhs.visited) return (lhs.val < rhs.val);
    return lhs.visited ? rhs.visited : true;

    /* alternatively:
    return (lhs.visited || rhs.visited)
        ? rhs.visited
        : (lhs.val < rhs.val);
    */

    /* alternatively:
    return (!lhs.visited) && (rhs.visited || lhs.val < rhs.val);
    */
}

...

auto it = std::min_element(std::begin(vct_priority), std::end(vct_priority), cmp);
if (it == std::end(vct_priority)) {
    // vct_priority is empty
}
else if (it->visited) {
    // there are no unvisited items in vct_priority
}
else {
    // use *it element as needed ...
    it->visited = true;
}

Online Demo