C 使用自定義比較器查找結構向量中的最小值

我有一個結構向量：

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。

你能幫我找出錯誤，或者提出一些更合適的解決方案嗎？

uj5u.com熱心網友回復：

很明顯，您需要正確定義比較函式。

給你。

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

uj5u.com熱心網友回復：

您的比較器并不能實施需要的嚴格弱排序std::min_element()。即，它沒有考慮到兩個輸入元素可以具有不同的visited狀態。由于您希望在訪問的結構之前優先考慮未公開的結構，因此您需要在兩個元素具有val時才會比較它們的欄位。否則，如果左側元素具有并且右側元素，則需要優先考慮右手元件。但你不是這樣做的。visited=falsevisited=truevisited=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;
}

在線演示

uj5u.com熱心網友回復：

對于比較，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);
}

演示

標籤：C 算法 迭代器 比较器 优先队列

上一篇：MLP是用于URL分類的正確DL演算法嗎？

下一篇：在陣列中查找并不總是一致的模式