时间戳

首页 > 解决方案 > C++ set：根据自定义比较器查找和删除元素

c++ - C++ set：根据自定义比较器查找和删除元素

问题描述

在我的程序中，set有类型的元素pair<char, double>。我还实现了逻辑，以便set根据元素的第二个值从最小到最大进行排序：

using pair_item = std::pair<char, double>;
std::set<pair_item, decltype([](auto e1, auto e2){return e1.second < e2.second;})> pq;

set现在，我想根据元素的第一个值从中删除一个元素：

auto first_is_w = std::lower_bound(
    pq.begin(), pq.end(), [w](const auto& p) {
        return p.first == w;
    }
);
if (first_is_w != pq.end() && first_is_w->first == w) {
    pq.erase(first_is_w);
}

不幸的是，我得到了错误：

'const A_star(const std::vector<std::tuple<char, char, double> >&, std::unordered_map<char, double>&, char, char)::<lambda(const auto:13&)>' is not derived from 'const std::optional<_Tp>'
{ return *__it < __val; }
         ~~~~~~^~~~~~~

我想知道我应该如何修改我的 lambda 函数以正确运行搜索？下面附上完整代码：

#include <iostream>
#include <set>
#include <utility>
using pair_item = std::pair<char, double>;

void printSet(const auto& pq) {
    std::cout << "Current pq:" << std::endl;
    for (const auto& ele : pq) {
        std::cout << "(" << ele.first << ", " << ele.second << "), ";
    }
    std::cout << std::endl;
}

int main() {
    char w = 'A';
    
    std::set<pair_item, decltype([](auto e1, auto e2){return e1.second < e2.second;})> pq;
    pq.emplace('A', 30);
    pq.emplace('B', 20);
    pq.emplace('C', 10);
    printSet(pq);
    
    auto first_is_w = std::lower_bound(
        pq.begin(), pq.end(), [w](const auto& p) {
            return p.first == w;
        }
    );
    if (first_is_w != pq.end() && first_is_w->first == w) {
        pq.erase(first_is_w);
    }

    return 0;
}

标签： c++lambdasetstd-pairlower-bound

解决方案

你的 lambda 很好，但是你使用了错误的算法。lower_bound需要排序范围和严格的弱排序比较，而对于您要查找的值，您没有这些比较。

您应该使用std::find_if，这是一个 O(N) 线性搜索。

auto first_is_w = std::find_if(
    pq.begin(), pq.end(), [w](const auto& p) {
        return p.first == w;
    }
);
if (first_is_w != pq.end()) {
    pq.erase(first_is_w);
}

推荐阅读