1

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 ?

wohlstad
  • 12,661
  • 10
  • 26
  • 39
learner
  • 57
  • 8
  • 2
    How about storing the `car`s in a `std::map` ? deleting an entry is guaragteed to be O(log n). – wohlstad Oct 17 '22 at 09:48
  • @wohlstad yes thats one solution. – learner Oct 17 '22 at 09:49
  • 1
    Related: [How to delete an object in a set](https://stackoverflow.com/questions/5838922/how-to-delete-an-object-in-a-set) – Jason Oct 17 '22 at 09:49
  • 1
    How is your comparison operator defined? The one that is used to order the elements in the set. If it compares IDs, you could just overload it to compare to int and use [`set::erase` (4)](https://en.cppreference.com/w/cpp/container/set/erase) – Jakob Stark Oct 17 '22 at 09:53

2 Answers2

1

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);
Caleth
  • 52,200
  • 2
  • 44
  • 75
  • Hello Caleth, Thanks for your answer. I am using a custom comparator so my set is `sets` – learner Oct 17 '22 at 10:00
  • @learner what's the definition of `cmp`? Does it just have the first of my `operator()`? – Caleth Oct 17 '22 at 10:01
  • Yes there is operator in my cmp defintion `bool operator()(const car a, const car b) const { }` – learner Oct 17 '22 at 10:02
  • @learner oh, that's unfortunate. You can't keep that ordering *and* have lookup by ID, in `std::set`. If you have access to the boost library, you can use `boost::multi_index_container` to have both sorted-by-time and lookup-by-id. – Caleth Oct 17 '22 at 10:08
0

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?.

wohlstad
  • 12,661
  • 10
  • 26
  • 39