C++ set: find & delete elements based on customized comparator

Question

In my program, set has elements of type pair<char, double>. I also implemented the logic so that set is sorted based on element's 2nd value, from smallest to largest:

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

Now, I want to delete an element from set, based on element's 1st value:

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

Unfortunately, I got error:

'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; }
         ~~~~~~^~~~~~~

I'm wondering how should I modify my lambda function to run the search correctly? Full codes attached below:

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

Answer 1

Your lambda is fine, but you're using the wrong algorithm. lower_bound requires a sorted range and strict weak ordering comparison, which you do not have for the value you're looking for.

You should use std::find_if, which is an O(N) linear search.

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