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

在我的算法中，我想迭代地找到尚未 visited 的具有最小 value 的元素，使用它，然后通过设置 [=16] 来“禁用”它=] 为 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

您的比较器未实现 std::min_element() 要求的 strict weak ordering。即，它没有考虑到两个输入元素可能具有不同的 visited 状态。由于您希望将未访问的结构优先于已访问的结构，因此仅当 both 元素具有 visited=false 时才需要比较它们的 val 字段。否则，如果 left-hand 元素有 visited=true 而 right-hand 元素有 visited=false 那么你需要优先考虑 right-hand 元素。但是你没有那样做。

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

话虽如此，试试这个：

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

Answer 2

可见你需要正确定义比较函数

给你。

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

程序输出为

如果你想定义一个单独的函数而不是 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 3

对于比较器，使用 std::tuple 作为投影确保尊重 strict weak ordering:

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

Demo

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

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

c++

algorithm

iterator

priority-queue

comparator