How to Remove Constness of Const_Iterator

How to remove constness of const_iterator?

There is a solution with constant time complexity in C++11: for any sequence, associative, or unordered associative container (including all of the Standard Library containers), you can call the range-erase member function with an empty range:

template <typename Container, typename ConstIterator>
typename Container::iterator remove_constness(Container& c, ConstIterator it)
{
    return c.erase(it, it);
}

The range-erase member functions have a pair of const_iterator parameters, but they return an iterator. Because an empty range is provided, the call to erase does not change the contents of the container.

Hat tip to Howard Hinnant and Jon Kalb for this trick.

Converting iterators and const_iterators

Both the methods you quote require non-const access to the container, so you can't get access to const underlying elements as non-const.

What you are suggesting doesn't, so it can be UB [dcl.type.cv]

How to remove constness of const_iterator?

There is a solution with constant time complexity in C++11: for any sequence, associative, or unordered associative container (including all of the Standard Library containers), you can call the range-erase member function with an empty range:

template <typename Container, typename ConstIterator>
typename Container::iterator remove_constness(Container& c, ConstIterator it)
{
    return c.erase(it, it);
}

The range-erase member functions have a pair of const_iterator parameters, but they return an iterator. Because an empty range is provided, the call to erase does not change the contents of the container.

Hat tip to Howard Hinnant and Jon Kalb for this trick.

How do I escape the const_iterator trap when passing a const container reference as a parameter

If I understand what you're saying correctly, you're trying to use const to indicate to the caller that your function will not modify the collection, but you want the caller (who may have a non-const reference to the collection) to be able to modify the collection using the iterator you return. If so, I don't think there's a clean solution for that, unless the container provides a mechanism for turning a const interator into a non-const one (I'm unaware of a container that does this). Your best bet is probably to have your function take a non-const reference. You may also be able to have 2 overloads of your function, one const and one non-const, so that in the case of a caller who has only a const reference, they will still be able to use your function.

How to remove code duplication const_iterator and iterator in my case?

One way is to implement the bulk in const_iterator and to let iterator inherit from that. Some const_casts is bound to be required.

Another way is implement the iterator as a template, iterator_impl<> and then add two typedefs:

using iterator = iterator_impl<value_type>;
using const_iterator = iterator_impl<const value_type>;

I've opted for the latter in this answer and made it possible to convert an iterator to a const_iterator, but not the other way around. I have commented on my changes in the code:

#include <cstddef>
#include <iterator>
#include <numeric>
#include <unordered_map>
#include <utility>

template<typename K, typename V>
class MultiMap {
private:
    // these constants can be hidden in here as private:
    static constexpr size_t MAP_NUM_BITS = 5;
    static constexpr size_t MAP_NUM = 1ULL << MAP_NUM_BITS;

    using MapType = std::unordered_map<K, V>;

public:
    // some of the common public typedef's one expects:
    using value_type = typename MapType::value_type;
    using reference = typename MapType::reference;
    using const_reference = typename MapType::const_reference;
    using pointer = typename MapType::pointer;
    using const_pointer = typename MapType::const_pointer;

private:
    using MapIter = typename MapType::iterator;
    using MapConstIter = typename MapType::const_iterator;

    // The iterator template - it's private since it doesn't need to be
    // seen from the outside.

    template<class Type>
    struct iterator_impl {
        // Added a default and a converting constructor - this became necessary
        // when I added the constructor to convert from an iterator to a const_iterator
        iterator_impl() = default;
        iterator_impl(MapIter It, size_t Idx, MapType* mm) :
            it(It), idx(Idx), multi_maps(mm) {}

        // Convert from iterator to const_iterator
        template<class O, std::enable_if_t<std::is_same_v<O, value_type> &&
                                               !std::is_same_v<O, Type>,
                                           int> = 0>
        iterator_impl(const iterator_impl<O>& rhs) :
            it(rhs.it), idx(rhs.idx), multi_maps(rhs.multi_maps) {}

        // these should probably be made into free friend functions
        bool operator==(const iterator_impl& rhs) const { return it == rhs.it; }
        bool operator!=(const iterator_impl& rhs) const { return it != rhs.it; }

        // I didn't modify operator++

        // I made operator->() return a pointer type directly:
        auto operator->() { return &*it; }
        const_pointer operator->() const { return &*it; }

        auto operator*() { return *it; }
        const_reference operator*() const { return *it; }

        // conditionally selecting the underlying iterator type:
        std::conditional_t<
            std::is_same_v<Type, const value_type>,
            MapConstIter, MapIter> it{};

        size_t idx{};
        MapType* multi_maps{};
    };

public:
    // The actual public iterator types a user will use:
    using iterator = iterator_impl<value_type>;
    using const_iterator = iterator_impl<const value_type>;

    // Added cbegin() and cend():
    const_iterator cbegin() const {
        // Since finding the beginning isn't a simple task, I've chosen to
        // reuse the non-const begin() + the conversion to const_iterator here.
        // This should simplify maintenance. Note the safe const_cast here:
        return const_cast<MultiMap*>(this)->begin();
    }

    const_iterator cend() const {
        // same as above for consistency
        return const_cast<MultiMap*>(this)->end();
    }

    // Now these just call cbegin() and cend():
    const_iterator begin() const { return cbegin(); }
    const_iterator end() const { return cend(); }

    iterator begin() {
        size_t idx = 0;
        auto it = multi_maps_[idx].begin();
        while(it == multi_maps_[idx].end() && idx + 1 < MAP_NUM) {
            it = multi_maps_[++idx].begin();
        }
        return {it, idx, multi_maps_};
    }

    iterator end() {
        return {multi_maps_[MAP_NUM - 1].end(), MAP_NUM - 1, multi_maps_};
    }

    // I didn't modify find(), insert(), clear() or compute_idx()

    size_t size() const {
        // Just en example of using a standard algoritm (from <numeric>):
        return std::accumulate(
            std::begin(multi_maps_), std::end(multi_maps_), size_t(0),
            [](size_t current, const auto& m) { return current + m.size(); });
    }

private:
    MapType multi_maps_[MAP_NUM];
    std::hash<K> hasher_{};
};

Copy construction and conversion from iterator to const_iterator now works, but conversion from const_iterator to iterator fails to compile:

int main() {
    MultiMap<int, int>::iterator it1;
    MultiMap<int, int>::iterator it2 = it1;
    it1 = it2;
    MultiMap<int, int>::const_iterator cit1;
    MultiMap<int, int>::const_iterator cit2 = cit1;
    cit1 = cit2;

    cit2 = it1;
    // it1 = cit2; // error: no conversion from const_iterator to iterator
}

Assigning a const_iterator to an iterator

You cannot modify a sets elements. Keys must be const to ensure the invariant promised by the set: elements are sorted and unique. A maps elements are sorted too, but you can modify the mapped value of the elements (keys are const as well). Elements of a std::map<A,B> are std::pair<const A,B>.

On cppreference you can read that member aliases for iterators of std::set are

iterator Constant LegacyBidirectionalIterator

const_iterator Constant LegacyBidirectionalIterator

They are both const iterators.

On the other hand for a std::map they are:

iterator LegacyBidirectionalIterator

const_iterator Constant LegacyBidirectionalIterator

Assigning a const_iterator to a non-const one is wrong. Its like trying to cast const away by assigning a pointer to const to a pointer to non-const. It won't work because you cannot make something that cannot be modified modifiable. That would break const-correctness.

Removing code duplication from const and non-const methods that return iterators

I believe, it is only possible with the helper

typedef int Z;

class X
{
    std::vector<Z> vecZ;    
public:
    std::vector<Z>::iterator foo(size_t index)
    {
        return helper(*this);
    }
    std::vector<Z>::const_iterator foo(size_t index) const
    {
        return helper(*this);
    }

    template <typename T>
    static auto helper(T& t) -> decltype(t.vecZ.begin())
    {
        return t.vecZ.begin();
    }
};

EDIT
Same can be implemented without c++11

template <typename T>
struct select
{
    typedef std::vector<Z>::iterator type;
};
template <typename T>
struct select<const T&>
{
    typedef std::vector<Z>::const_iterator type;
};

template <typename T>
static
typename select<T>::type
helper(T t) 
{
    return t.vecZ.begin();
}

But, well, I think you should think twice before using this approcach

const_iterator and constness of const_iterator::value_type

It allows me to do this:

std::iterator_traits<I>::value_type val = *iter;
val += 5;
doSomething(val);

But that's harder if value_type is const, because I need to use remove_const.

If I don't want to get a modifiable value then it doesn't matter whether value_type is const or not:

const std::iterator_traits<I>::value_type cval = *iter;
std::iterator_traits<I>::reference        ref  = *iter;

Both of these work for const iterators and non-const iterators, and both work whether value_type is const or not, but the first example only works for const iterators if their value_type is non-const.

How are you supposed to take the underlying const correct type of an iterator?

An iterator doesn't necessarily have an underlying type of its own, an iterator usually refers to some range or some collection, and that collection is what has an underlying type. e.g std::list<int>::const_iterator's value_type is std::list<int>::value_type, which is int not const int.

You don't necessarily want to know what the underlying type is anyway, it's more likely you want to know what the result of *iter is, and that's what iterator_traits<I>::reference tells you.

In C++, is const_iterator the same as const iterator?

No, they are not the same.

Like any const object, you can not make changes to a const iterator:

// ++it gives error below since we try to change it:
for(const std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {}

You are, however, allowed to change the value of the object a const iterator is pointing at:

// this is ok (assuming there is at least one element in the vector):
const std::vector<int>::iterator it = vec.begin();
*it = 10;

A const_iterator is mutable, but you can not change the object that the iterator is pointing at:

// ++it is ok below:
for(std::vector<int>::const_iterator it = vec.begin(); it != vec.end(); ++it) {
    *it = 10;   // error:  `*it`  is an `int const&`
}

With a const const_iterator, you can neither make changes to the iterator nor what it is pointing at.

const std::vector<int>::const_iterator it = vec.begin();
++it;                     // error
*it = 10;                 // error
std::cout << *it << '\n'; // ok

---

A constructed example to illustrate:

struct foo {
    using const_iterator = char const*;
    using iterator = char*;

    const_iterator cbegin() const { return data; };
    const_iterator cend() const { return data + sizeof data; };
    const_iterator begin() const { return cbegin(); }
    const_iterator end() const { return cend(); }
    iterator begin() { return data; };
    iterator end() { return data + sizeof data; };

    char data[2];
};

As seen above, const_iterator and iterator are user defined type definitions. Only by convention are the names called what they are called. Using these conventional names also helpes when creating containers that are supposed to work well with other classes, since these type definitions are often used to create or specify instances/types. The names const_iterator and iterator do not give these alias any special properties though. It's all up to the creator of the class.

---

Related Topics