Passing other types to std::set::erase().

[JC]

I have a class where each instance has a unique ID associated with it,
like this (I use "..." to mean "other things", not a variable
parameter list):

typedef ... ID;

class Data {
public:
Data (ID id, ...);
bool operator < (const Data &d) const throw () { return id_ <
d.id_; }
...
private:
ID id_;
...
};

Instances are equivalent if their IDs are equivalent. I am storing
these in an std::set<Data>. I'd like to be able to erase elements from
the set given only an ID, that is:

std::set<Data> somedata = ...;
ID id = ...;
somedata.erase(id);

I've found two ways to make this work, neither are ideal for reasons I
don't want to get in to:

1) Provide an implicit Data(ID) constructor to construct dummy Data
instances used for ID comparisons.

2) Use an std::map<ID,Data> instead.

Is there a way I can erase elements from the set by ID without
constructing dummy Data instances, and without using some other
container type instead?

Thanks!
Jason

 

[joseph cook]

I have a class where each instance has a unique ID associated with it,
like this <snip>
Instances are equivalent if their IDs are equivalent.

If the IDs are unique, no two will ever be equivalant, but...

I am storing
these in an std::set<Data>. I'd like to be able to erase elements from
the set given only an ID, that is:

std::set<Data> somedata = ...;
ID id = ...;
somedata.erase(id);

I've found two ways to make this work, neither are ideal for reasons I
don't want to get in to:

  1) Provide an implicit Data(ID) constructor to construct dummy Data
instances used for ID comparisons.

Ack. Don't do that.

Is there a way I can erase elements from the set by ID without
constructing dummy Data instances, and without using some other
container type instead?

If you define operator==(ID&), then you can accomplish your goal.
Given your description, these seems like it would provide appropriate
semantics as well.

hth,
Joe C

 

[jasonc]

I have a class where each instance has a unique ID associated with it,
like this <snip>
Instances are equivalent if their IDs are equivalent. [snip]
I am storing
these in an std::set<Data>. I'd like to be able to erase elements from
the set given only an ID, that is:

std::set<Data> somedata = ...;
ID id = ...;
somedata.erase(id);

Is there a way I can erase elements from the set by ID without
constructing dummy Data instances, and without using some other
container type instead?

If you define operator==(ID&), then you can accomplish your goal.
Given your description, these seems like it would provide appropriate
semantics as well.

Thanks for your reply. An == operator makes sense in general; however,
this still doesn't solve the problem, as std::set<Data>::erase(const
Data&) takes a Data parameter, not an ID parameter, so compilation
would still fail with an error along the lines of "no match for
somedata.erase(ID)".

Also, AFAIK, doesn't set always use operator< for comparisons rather
than operator== (operator<(ID&) doesn't solve the problem either)?

Jason

 

[Alf P. Steinbach]

* JC:

I have a class where each instance has a unique ID associated with it,
like this (I use "..." to mean "other things", not a variable
parameter list):

typedef ... ID;

class Data {
public:
Data (ID id, ...);
bool operator < (const Data &d) const throw () { return id_ <
d.id_; }
...
private:
ID id_;
...
};

Instances are equivalent if their IDs are equivalent. I am storing
these in an std::set<Data>. I'd like to be able to erase elements from
the set given only an ID, that is:

std::set<Data> somedata = ...;
ID id = ...;
somedata.erase(id);

I've found two ways to make this work, neither are ideal for reasons I
don't want to get in to:

1) Provide an implicit Data(ID) constructor to construct dummy Data
instances used for ID comparisons.

2) Use an std::map<ID,Data> instead.

Is there a way I can erase elements from the set by ID without
constructing dummy Data instances, and without using some other
container type instead?

The map idea is the closest. The "reasons I don't want to get in to" are
important in order to provide more specific advice. However, keep in mind that
the general solution to any Computer Science problem is ... indirection (you may
have to use two collections, one to capture your idea of id->instance
association and another to capture the allocation/lifetime aspect).


Cheers & hth.,

- Alf

 

[James Kanze]

I have a class where each instance has a unique ID
associated with it, like this <snip>
Instances are equivalent if their IDs are equivalent. [snip]
I am storing these in an std::set<Data>. I'd like to be
able to erase elements from the set given only an ID, that
is:
std::set<Data> somedata = ...;
ID id = ...;
somedata.erase(id);
Is there a way I can erase elements from the set by ID
without constructing dummy Data instances, and without
using some other container type instead?

If you define operator==(ID&), then you can accomplish your
goal. Given your description, these seems like it would
provide appropriate semantics as well.

Thanks for your reply. An == operator makes sense in general;
however, this still doesn't solve the problem, as
std::set<Data>::erase(const Data&) takes a Data parameter, not
an ID parameter, so compilation would still fail with an error
along the lines of "no match for somedata.erase(ID)".

Also, AFAIK, doesn't set always use operator< for comparisons
rather than operator== (operator<(ID&) doesn't solve the
problem either)?

You're right on both counts.

In the end, your problem comes down to getting the set to find
the element, given just the idea. This is exactly what std::map
was designed for---if you need to find an element using an
object of a different type as key, you should be using std::map,
and not std::set.

If you're not doing a lot of insertions, you might also consider
using a sorted std::vector, and std::lower_bound---this function
does allow for a "key" with a different type.

 

[JC2]

I have a class where each instance has a unique ID
associated with it, like this <snip>
Instances are equivalent if their IDs are equivalent. [snip]
I am storing these in an std::set<Data>. I'd like to be
able to erase elements from the set given only an ID, that
is:
std::set<Data> somedata = ...;
ID id = ...;
somedata.erase(id);
Is there a way I can erase elements from the set by ID
without constructing dummy Data instances, and without
using some other container type instead?
If you define operator==(ID&), then you can accomplish your
goal.  Given your description, these seems like it would
provide appropriate semantics as well.

Thanks for your reply. An == operator makes sense in general;
however, this still doesn't solve the problem, as
std::set<Data>::erase(const Data&) takes a Data parameter, not
an ID parameter, so compilation would still fail with an error
along the lines of "no match for somedata.erase(ID)".
Also, AFAIK, doesn't set always use operator< for comparisons
rather than operator== (operator<(ID&) doesn't solve the
problem either)?

You're right on both counts.

In the end, your problem comes down to getting the set to find
the element, given just the idea.  This is exactly what std::map
was designed for---if you need to find an element using an
object of a different type as key, you should be using std::map,
and not std::set.

If you're not doing a lot of insertions, you might also consider
using a sorted std::vector, and std::lower_bound---this function
does allow for a "key" with a different type.

Thanks; I forgot about this project for a few days.

I ended up having to settle for an std::map. I don't particularly like
the redundancy of storing the ID both in the map and in the object
itself (it opens the possibility of inconsistent entries in the map
where the key doesn't match the actual ID), however I ended up going
with this as the solution and hiding it behind some container class so
consistency in the map would always be guaranteed. This seems to be
working well, so I guess the problem is solved.

Thanks!
JC