C++使用自定义比较器查找结构向量的最小值

Question

我有一个结构向量：

struct element_t {
int val;
bool visited;
};

带有自定义比较器：

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

与一起使用

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

在我的算法中，我想迭代地找到具有最小value但还不是visited的元素，并对其进行处理，然后"；禁用"；通过将visited设置为true，以便在下一次迭代中找不到此元素。

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;

通常我会使用优先级队列，但由于在算法过程中需要索引到此数组，我找不到更好的方法。

问题是，这种做法是可疑的。在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}

计算的indx_smallest错误地为0，而不是2。

你能帮我找出错误吗，或者提出一些更合适的解决方案？

Answer 1

很明显，您需要正确定义比较函数。

给你。

#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';
}

程序输出为

2

如果你想定义一个单独的函数而不是lambda表达式，那么它看起来像

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

Answer 2

您的比较器没有实现std::min_element()所需的严格弱排序。也就是说，它没有考虑到两个输入元件可能具有不同的visited状态。由于您希望将未访问的结构优先于已访问的结构，因此仅当两个元素都具有visited=false时，才需要比较它们的val字段。否则，如果左侧元素具有visited=true，右侧元素具有visited=false，则需要对右侧元素进行优先级排序。但你没有这么做。

但是，需要注意的是，如果输入范围不为空，std::min_element()总是返回一个非结束迭代器。因此，如果您的所有元素都已被访问，则生成的迭代器必须指向一个已访问的元素。所以你也必须考虑到这一点。

话虽如此，试试这个：

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

在线演示

Answer 3

对于比较器，使用std::tuple作为投影确保遵守严格的弱排序：

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

演示