Analogue of `std::pair` with mutable members?

Question

I am implementing analogue of std::map called expiring_map which is based on boost::multi_index::multi_index_container. Idea is simple: when there is new insert to the expiring_map there will be check up for expired elements and removal if they are present.

I want to have some similar interface to the std::map:

template <class Clock, class Key, class T, class Compare = std::less<Key>>
class expiring_map
{
    explicit expiring_map(clock_type cl, duration expiry_duration);

    void insert_or_assign(value_type v);

    iterator begin();
    iterator end();
    const_iterator begin() const;
    const_iterator end() const;

    // size(), clear() and lookup-methods are omitted for simplicity
};

I also want for next code to be valid

    auto clock = std::make_shared<std::chrono::steady_clock>();
    expiring_map<decltype(clock), int, std::string> m{ clock, std::chrono::seconds{ 1 } };
    m.insert_or_assign({ 1, "value" });
    const auto b = m.begin();
    auto v = std::move(b->second);
    EXPECT_EQ(v, "value");
    EXPECT_TRUE(b->second.empty());

Since all elements for boost::multi_index::multi_index_container indices are considered non-mutable the only way (according to this answer) for me to reach desired results is to specify as value_type of expiring_map next struct

struct value_type {
    const Key first;
    mutable T second;
};

Because using value_type = std::pair<const Key, mutable T> is not valid c++ expression as keyword mutable is about storage duration and not about the type. From https://en.cppreference.com/w/cpp/language/cv

The C++ language grammar treats mutable as a storage-class-specifier, rather than a type qualifier, but it does not affect storage class or linkage.

Question

My problem with this solution is my const overloads for begin() and end() are not really const and next code is compiling:

using subject_type = ::expiring_map<std::shared_ptr<std::chrono::steady_clock>, int, std::string>;

void foo(const subject_type& s) {
   s.begin()->second = "new";
}

How can I change my implementation for const overloads of begin() and end() to achieve compilation error but preserve these methods (to still be able to iterate with range-based-for using const expiring_map&)?

Link to godbolt with current implementation and tests

What have I tried

I have tried using different extractor like

    struct extract_value_type_as_const_ref {
        [[nodiscard]] std::pair<const Key&, const T&> operator()(const node_type& n) const { return { n.second.first, n.second.second }; }
    };

    using const_iterator = decltype(boost::make_transform_iterator<extract_value_type_as_const_ref>(std::declval<underlying_type>().template get<by_value_type>().cbegin()));

but ::testing::ElementsAre requires for result of *(map.begin()) to be convertible to value_type but I really don't want to copy all of constructors of std::pair for my value_type

Answer 1

The second member in your value_type should not be mutable. This is the fix:

struct value_type {
    const Key first;
    T second;
};

Making this change makes your assertion on Compiler Explorer pass.

Maybe you've misunderstood something about the value_type of maps in general. A std::map<Key, Value> will store a value_type = std::pair<const Key, Value>.

• The Key has to be const. Otherwise, we would be able to mutate the key without also changing the position of the pair in the map, which breaks the data structure.
• The Value is not mutable. A const std::map will expose const value_type&, and the Value stored inside that pair is then also const.¹⁾

Furthermore, it makes sense that std::pair<const Key, mutable T> wouldn't compile. mutable is a property of data members (like private or static), it's not part of the a type.

In general, mutable is only meant to be used for data members which have to be mutable under all circumstances, even inside of const objects. For example, a std::mutex member is typically mutable, because a const std::mutex is unusable, and you need to be able to use it regardless.

---

¹⁾ It is possible that the Value stored inside is not a const object, but a mutable object. Technically, you could still mutate it through const_cast then. However, this cannot be relied upon.