Delete from set by first parameter-CodePudding

I am storing a struct inside set . The struct contains five variables, including an ID.

struct car{int ID;.....} 
set<car>s;

I want to delete a car from the set given a particular ID. Suppose ID is x , then delete that car which has ID has x.(All car IDs are distinct no duplicates).
Is it possible to do it in O(log n) time ?

CodePudding user response：

To lookup by ID, you will need to have a transparent compare. By default, std::set doesn't use one, so you will need to change the definition of your set.

struct id_less {
    using is_transparent = void;
    bool operator()(const car & lhs, const car & rhs) { return lhs.ID < rhs.ID; }
    bool operator()(const car & lhs, int rhs) { return lhs.ID < rhs; }
    bool operator()(int lhs, const car & rhs) { return lhs < rhs.ID; }
}

std::set<car, id_less> cars;

if (auto it = cars.find(x); it != cars.end()) cars.erase(it);

In C 23 we will get an overload of erase that uses the transparent compare, so it will become

cars.erase(x);

CodePudding user response：

I recommend to use std::map for that purpose, where the ID of the car object serves as a key:

std::map<int, car> s;  // key: car ID, value: car

Erasing an element from a std::map by a given key can be done in O(log n) with std::map::erase:

int id = ...
auto n = s.erase(id);
assert(n == 1);

Note that std::map::erase returns the number of erased elements for error checking.

A side note: better to avoid using namespace std - see here Why is "using namespace std;" considered bad practice?.