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