4

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.

Improve this question
5
  • 1
    What if the underlying container is const? Commented Oct 29, 2015 at 10:14
  • @molbdnilo :) interesting question. Maybe runtime error (exception throwing)? Or maybe there shoud be two versions of const_iterator (say, the current should be replaced with really_const_iterator =). Commented Oct 29, 2015 at 10:15
  • @molbdnilo Maybe std::cbegin(non_const_container) should return augmented version of const_iterator having member function base(). Commented Oct 29, 2015 at 10:31
  • If container supports random access iterators, you can easily convert it to a non-const version using auto offset = it - cbegin(universe); auto new_it = begin(universe) + offset;. If it is not random access, this will be less efficient. Commented Oct 29, 2015 at 10:31
  • @BoPersson Yes, it is. Also for any other container (if it consists of strictly different elements) I can find correspoinding element by means of std::addressof(*cit) == std::addressof(*it) comparison. But it results in additional quadratic complexity step to find all the coresponding elements. Commented Oct 29, 2015 at 10:35

4 Answers 4

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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.

Improve this answer

6 Comments

Calling to ’base()' member function is definitely explicit conversion.
It matters much in the context of the question.
Please do read all the my aalready existant comments to other answers prior to discuss it further.
The second subparagraph is evident. I mentioned reverse_iterator just for member function name borrowing.
@Orient You know best then mate.
|
1

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.

Improve this answer

10 Comments

What about two different (but possilby compatible) types modeling the same semantic as const_iterator only differs by presence of base() member function? const_iterator std::begin(T const &) and desired_const_iterator std::begin(T &) overloadings possible.
WRT member functions. std::containers can provide non-const-qualified member function able to convert const_iterator to iterator.
That's not a problem to write: template<class C> typename C::iterator iter_deconst(typename C::const_iterator iter, C &c) { return std::begin(c)+std::distance(std::cbegin(c), iter); }
What about a wide kind of containers not supporting the random access iterators (std::list/std::forward_list and all the associative containers)? Even if I use std::next for forward iterators, then it would be additional linear complexity for each iterator from output of the whole algorithm.
@Orient: So the point is that algorithm shall operate on a const container (const set of iterators) returning a structure that itself can modify the container?
|
1

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 )
Improve this answer

5 Comments

const_cast is surely workaround (but ugly). Wrapper to iterator is very nice workaround (concept). It would be nice if STL have its implementation by itself.
@Orient stl already has the concept of a map. A map maps keys (names) to objects (values). All i've done in this case is taken a shortcut, but the principle is similar.
'std::map< const_iterator, iterator >' have a memory cost as well as a runtime one, but doing the trivial thing.
if the universe was modelled by a unordered_map<ident, point> then you wouldn't need iterators at all - you could just reason about sets of idents. However, you're right there is a tradeoff between logical correctness and performance in this particular case.
@orient last comment. Updated the solution. This one is fully const-correct because it only allows a conversion of a const_ref through a mutable container. It's now optimally fast and safe.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.