c++setundefined-behaviormutableconst-cast

Getting a mutable element from a std::set, for operations that won't break the order


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

Playground

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


Solution

  • 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