Why const_iterator does not provide a base like reverse_iterator?

Question

Why does const_iterator not provide a const_iterator::base() function, to obtain corresponding non-const iterator like reverse_iterator does?

Considering following pseudocode (say, geometric algorithm):

std::container< point > universe;
auto it = std::cbegin(universe);
std::list< decltype(it) > interesting_subset = sieve(it, std::cend(universe));
auto structure = algorithm(interesting_subset);

where universe is all the input points. After sieve()-ing the interesting_subset contains iterators to subset of universe's members. Following algorithm() constructs a resulting structure from interesting_subset, which consists of references (iterators) to members of the universe.

At the end, I want to change the points, containing into resulting structure (say, shift them). But equally I want to protect them from modyfining during algorithm action, and therefore I used std::cbegin/std::cend as opposite to std::begin/std::end. Finally I have only const_iterator references to source points.

This is a very use case for iterator std::container< T >::const_iterator::base() const member function I want to be present into STL containers.

Answer 1

Why does const_iterator not provide a const_iterator::base() function, to obtain corresponding non-const iterator like reverse_iterator does?

To maintain const-safety. Providing such function would be very dangerous as already discussed here at length.

At the end, I want to change the points, containing into resulting structure (say, shift them). But equally I want to protect them from modyfining during algorithm action, and therefore I used std::cbegin/std::cend as opposite to std::begin/std::end. Finally I have only const_iterator references to source points.

Well, you're asking for the wrong thing with the base-member. Sure it would solve your problem, but as said, it's just too dangerous. Let me rephrease a question for you:

If I have a const_iterator to an object and non-const access to the container, how do I efficiently (in constant time) get an iterator to the referred object?

Here's a fancy trick to do exactly that:

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

I don't take any credit for the trick. I found it from https://stackoverflow.com/a/10669041/2079303 and they credit Howard Hinnant and Jon Kalb

As discussed in the comments of that answer, this trick works with all standard containers, but not necessarily with all possible standard-compliant third-party containers because they're not required to provide erase.

Personally, I would prefer that standard containers had a non-const member function that would convert a given const_iterator to an iterator, but they don't, so you need to work around it.

Answer 2

For the same reason that there is no conversion from const T* to T*: const-correctness.

Comparisons with reverse_iterator are not valid, because the distinction between "reverse iterator" and "forward iterator" is entirely orthogonal to the distinction between "const iterator" and "non-const iterator". The latter has ramifications; the former ultimately does not.

Answer 3

It's an interesting question. You want to be able to protect the points while you reason about them, but return mutable references to them once they've been reasoned about.

As a result of reasoning about the points, what you're actually returning is their 'names' or 'identifiers'.

We could conceivably map them by name, and get sieve() to return a vector of relevant names. Such a name could simply be an address if we wanted to avoid the overhead of storing a formal name (unique number, text string etc).

If we use an address of a const object as a name, then of course to turn it back into a reference to a mutable object we would need a const_cast. This might be seen as one of the few times we might reasonably use a const cast. When doing so we should encapsulate it in a utility class in order to limit any fallout.

EDIT: rethought the solution. this one is now un-abusable by unruly client code.

#include <iostream>
#include <vector>

struct point { int x, y; };

inline std::ostream& operator<<(std::ostream& os, const point& p)
{
    os << "(" << p.x << ", " << p.y << " )";
    return os;
}

struct point_collection
{
    using container_type = std::vector<point>;

    point_collection(container_type points) : _points(std::move(points)) {}

    using const_iterator = const point*;
    using iterator = point*;

    const_iterator begin() const { return &*_points.begin(); }
    const_iterator end() const { return &*_points.end(); }

    // note that this function is only available on a non-const point_collection
    point& mutable_reference(const_iterator input)
    {
        // could put an assert in here to ensure that input is within our range
        return *const_cast<iterator>(input);
    }

    container_type _points;
};


std::vector<point_collection::const_iterator> sieve(point_collection::const_iterator first,
                                                    point_collection::const_iterator last)
{
    std::vector<point_collection::const_iterator> result;

    for ( ; first != last ; ++first )
    {
        if (first->x > 6)
            result.push_back(first);
    }
    return result;
}


point_collection make_a_universe()
{
    return {
        std::vector<point> {
            { 10, 10 },
            { 6, 6 }
        }
    };
}

auto main() -> int
{
    using namespace std;
    auto universe = make_a_universe();

    auto interesting = sieve(universe.begin(), universe.end());

    for (auto point_id : interesting) {
        auto& p = universe.mutable_reference(point_id);
        p.x = -p.x;
        cout << p << endl;
    }
    return 0;
}

expected output:

(-10, 10 )

Answer 4

A reverse_iterator does not change whether the underlying object is const or not and a const_iterator is not related to iterator (other than the requirement to be convertible and the referencing) so you're comparing apples and oranges.

If a const_iterator indeed would provide access to a non-const iterator via base it would be possible to do stuff like

auto const & a = std::vector<int>(20, 1);
auto it = std::cbegin(a);
*it.base() = 4;

The standard kindly permits this.

You do -in principle- want to circumvent the protection against modification which is provided by const_iterator. But that's what the const_iterator is about. So that is neither a good idea nor likely to happen, I think (and hope).

Eventhough I think this is a XY Problem, I answered to the question rather than providing guidance on how to do it properly.

-edit-

If you want a const_iterator to be able to return an iterator, it is iterator that you want.

Your intention seems to be

1. Pass const_iterator to sieve where sieve is not allowed to change the elements.
2. Pass the very same iterators to algorithm allowing it to modify them.

You require two different things from one and the same object. Nobody keeps the implementor of sieve from using it.base() so there would be no guarantee at all that sieve does not change the elements. This is, I repeat, the point of the matter const_iterator.

If there was any way of changing things using const_iterators it would just break them.