I've got a data type that consists of actual data and an id:
struct Data {
int value;
int DataId;
};
I've got a collection of these data from which I have to frequently get an element based on its id and modify its value (but not it's ID).
I thus chose a std::set
in order to have an efficient sort, with the following comparator:
class Comparator {
/// dummy type for declaring is_transparent type
struct SIsTransparentTag;
public:
// tag (falsely) indicating that operator() is transparent, i.e. accepts
// any type of argument: this is a workaround to allow std::set::find to
// use a int key instead of a full Data object.
// https://en.cppreference.com/w/cpp/container/set/find
// https://www.fluentcpp.com/2017/06/09/search-set-another-type-key/
using is_transparent = SIsTransparentTag;
// comparator between two Data
bool operator()(const Data &lhs, const Data &rhs) const {
return lhs.DataId < rhs.DataId;
}
// comparator between a Data and an id
bool operator()(const Data &lhs, const int id) const {
return lhs.DataId < id;
}
// comparator between an id and a Data
bool operator()(const int id, const Data &rhs) const {
return id < rhs.DataId;
}
};
Then I wrote a read-write getter:
Data* GetRWDataFromID(std::set<Data,Comparator> &collection,int id)
{
auto it = collection.find(id);
if (it == std::end(collection))
{
return nullptr;
}
// UB as soon as I will modify Data!!!
return const_cast<Data *>(&(*it));
}
std::set::find()
only returns an iterator to a non-mutable element. However, I only want to be able to modify the value
member, thus never changing the set order.
This design is broken because removing constness of an object and modifying it is undefined behavior: https://en.cppreference.com/w/cpp/language/const_cast.
How can I fix my design while keeping an efficient search (typically logarithmic) and letting the id attached to a data (when I get a data, I want to get its id from it, not from some book-keeping; thus I'd like to avoid a std::map
)?
A bonus would be to have DataId
non-mutable once a Data
object is created (for this one, I imagine I can make it private and use read-only getters?).
Just use std::map
directly.
when I get a data, I want to get its id from it, not from some book-keeping; thus I'd like to avoid a
std::map
Inside std::map
, it store the key and value as a std::pair
, so you do not need any book-keeping to get both key and value.
Further reading: more information about std::map