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

score 3 · Answer 1 · edited Dec 01 '20 at 22:13

3

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

edited Dec 01 '20 at 22:13

Remy Lebeau

555,201
31
458
770

answered Dec 01 '20 at 22:01

1201ProgramAlarm

32,384
7
42
56

Thanks. Is there any way of searching `pair` in time complexity of `Olog(N)`, perhaps by modifying the order in `pair_item`, or providing a self-written binary-search algorithm? – Heifetz_Fan Dec 01 '20 at 23:10
@Heifetz_Fan: You have sorted by the second value in the pair. That gives you fast lookup by the second value, but no you can't search on the first value efficiently. Maybe you want a data structure with multiple indexing (the tradeoff is that insertion becomes more and more expensive as you make more lookup operations cheap) – Ben Voigt Dec 01 '20 at 23:11
@Heifetz_Fan The question you raise in the comment is a duplicate of https://stackoverflow.com/q/1858306/103167 – Ben Voigt Dec 01 '20 at 23:14
Thanks @BenVoigt. For using boost library's multi-index container for my case, do you mean I consider pair's both first and second elements to be indices? If that's the case, I'll face a situation that I have 2 keys with no values... – Heifetz_Fan Dec 03 '20 at 22:35
@Heifetz_Fan: multi-index is very different from a composite key (composite key can look like `std::map< std::pair, T >` or `std::map >`). With the composite keys, you need all key data to do a lookup. With a multi-index you can find items using any one of the keys. – Ben Voigt Dec 03 '20 at 22:42

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

1 Answers1