Obtaining a non-const iterators from a const_iterator and a non-const reference to the container

[Xavi Gratal]

Given a const_iterator ci to an element of a container c, it is already possible to obtain a non-const iterator with:

auto i=std::advance(c.begin(),std::distance(c.cbegin(),ci);

However, this is extremely inefficient for non-random-access containers. I would like to add some mechanism to the standard containers so that given a non-const reference to the container and a const_iterator, it is possible to obtain a non-const iterator in constant time.

This would be useful in a scenario where an algorithm takes a const reference to a container and finds some interesting element inside, returning a const_iterator to it. Then, as long as you have a non-const reference to the container, you should be able to modify the element you found. It is already possible to erase it using a const_iterator.

Is there any reason why such a facility doesn't exist for the standard containers?

[Xavi Gratal]

As a concrete example of why this would be useful, consider the following excerpt from a simple graph class:

template<typename vertex_data>
class graph {
    typedef std::list<vertex_data> vertex_list;
    typedef typename vertex_list::iterator vertex_iterator;
    typedef typename vertex_list::const_iterator vertex_const_iterator;

    struct edge {
        edge(const vertex_iterator &s,const vertex_iterator &d)
            :src(s),dst(d) {}
       
        vertex_iterator src;
        vertex_iterator dst;
    };
   
    typedef std::list<edge> edge_list;
    typedef typename edge_list::iterator edge_iterator;
    typedef typename edge_list::const_iterator edge_const_iterator;
   
public:
    graph() {}
   
    vertex_iterator add_vertex(const vertex_data v) {
        vertices.emplace_back(v);
        return vertices.end()-1;
    }

    edge_iterator add_edge(const vertex_iterator &src,const vertex_iterator &dst) {
        edges.emplace_back(src,dst);
        return edges.end()-1;
    }
   
private:
    vertex_list vertices;
    edge_list edges;
};

If edge contained const_iterators, it would later be impossible to return non-const references to vertices given edges, while, as is currently implemented, the add_edge function must take non-const iterators, while there is really no reason for it.

C++11 went one step in the right direction by having functions such as erase and insert take const_iterators. Having a way to obtain iterators from const_iterators would allow a class like the above to do the same.

[David Krauss]

On 1/2/14 12:19 PM, Xavi Gratal wrote:
> I would like to add some mechanism to the standard containers so that given a
> non-const reference to the container and a const_iterator, it is possible
> to obtain a non-const iterator in constant time.

It might even be reasonable to have const_iterator_cast, not requiring a
container reference. It seems pointless to legislate this kind of thing.
A programmer who doesn't "get it," whom the safer function is trying to
protect, may just pass a reference to the wrong container, and the
implementation will be none the wiser unless it does perhaps O(N) worth
of verification work.

> This would be useful in a scenario where an algorithm takes a const
> reference to a container and finds some interesting element inside,
> returning a const_iterator to it.

I the problem may become more relevant over time, as it can be
exacerbated by multithreading. A common fix is to grant write access to
more of the program, but that could have immediate consequences if the
compiler is trying to keep track of who might modify what.

[Miroslav Knejp]

Being able to get a const_iterator from a iterator would sometimes be
indeed useful. Just not the other way around or people start breaking
stuff as they tend to do now with const_cast.

An off-topic note about your code: if this is pasted from real-world use
you probably want to change the single-argument signature of add_vertex
to accept a non-const vetex_data by value and then std::move() it into
emplace_back. The current code as it is will always call vertex_data's
copy constructor because you cannot move from a const object and you end
up with two copy operations instead of one (or even zero if the argument
to add_vertex is a temporary).

[xavi]

2014/1/2 Miroslav Knejp <mi...@knejp.de>

Being able to get a const_iterator from a iterator would sometimes be indeed useful. Just not the other way around or people start breaking stuff as they tend to do now with const_cast.

Obtaining a const_iterator from an iterator is already possible. For most (all?) containers in the standard library, iterator is implicitly convertible to const_iterator.

What I'm proposing doesn't break the constness rules (as const_cast does). It merely adds a mechanism to optimize what is already possible with advance and distance. I think it should be implemented as a non-const member function of the container, so that it can't be used to bypass constness. It will actually increase constness-safety, since it will allow const_iterators to be used where iterators are currently needed.

 

An off-topic note about your code: if this is pasted from real-world use you probably want to change the single-argument signature of add_vertex to accept a non-const vetex_data by value and then std::move() it into emplace_back. The current code as it is will always call vertex_data's copy constructor because you cannot move from a const object and you end up with two copy operations instead of one (or even zero if the argument to add_vertex is a temporary).

It was a toy example, but yes, I agree that sink parameters should be passed by value. 

--

--- You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

[Billy O'Neal]

>If edge contained const_iterators, it would later be impossible to return non-const references to vertices given edges, while, as is currently implemented, the add_edge function must take non-const iterators, while there is really no reason for it.

That seems like the correct thing would be to have non-const iterators there. You intend to modify the object to which the iterator refers; and as such it shouldn't be a const iterator.

I'm not saying that this is a bad idea; I'm just saying that example isn't motivating.

> C++11 went one step in the right direction by having functions such as erase and insert take const_iterators. Having a way to obtain iterators from const_iterators would allow a class like the above to do the same.

But this breaks const correctness. The reason you have the workaround for the random-access containers is that you have a mutable reference to the container itself which avoids breaking const-correctness.

You would need something like:

iterator const_iterator_cast(Container& c, Container::const_iterator i)

This of course makes the assumption that there is some cheap way to recover an iterator given a const iterator; though I suspect 99.99% of the time that is true.

> if the compiler is trying to keep track of who might modify what.

The compiler cannot use const as a means of determining if someone is modifying something, because const_cast exists in the language. The compiler must be able to prove that the operations done on something are in fact constant operations in order to optimize based on this assumption.

> Being able to get a const_iterator from a iterator would sometimes be indeed useful. Just not the other way around or people start breaking stuff as they tend to do now with const_cast.

You can already do this -- const iterator has a constructor taking iterator. (e.g. a wchar_t* can turn into a wchar_t const* without a cast; and const_iterator must mimic this behavior)

Billy O'Neal

http://stackoverflow.com/users/82320/billy-oneal

[Miroslav Knejp]

>
> Obtaining a const_iterator from an iterator is already possible. For
> most (all?) containers in the standard library, iterator is implicitly
> convertible to const_iterator.
> What I'm proposing doesn't break the constness rules (as const_cast
> does). It merely adds a mechanism to optimize what is already possible
> with advance and distance. I think it should be implemented as a
> non-const member function of the container, so that it can't be used
> to bypass constness. It will actually increase constness-safety, since
> it will allow const_iterators to be used where iterators are currently
> needed.

Ok, I forgot about of the conversion. But then I don't see the point in
the proposal. Any mechanics that allow me to change a const_iterator to
iterator is implicitly a mechanic to change const T& to T& without a
verbose and easy to search keyword. If it is a dedicated function like
const_iterator_cast at least it's easy to search. Having a (reference
to) a container doesn't really help. You could just make a temporary
container and use it for the cast. Unless the iterators track their
container (which is probably only the case in debug builds, if at all)
this works even better than the advance/distance trick (which is at
least quite inefficient for most iterator types).

I'd say if you need to modify elements in a container, or get non-const
references to those elements, don't design your classes with const_iterator.

[xavi]

2014/1/2 Billy O'Neal <billy...@gmail.com>

>If edge contained const_iterators, it would later be impossible to return non-const references to vertices given edges, while, as is currently implemented, the add_edge function must take non-const iterators, while there is really no reason for it.

That seems like the correct thing would be to have non-const iterators there. You intend to modify the object to which the iterator refers; and as such it shouldn't be a const iterator.

I'm not saying that this is a bad idea; I'm just saying that example isn't motivating.

I believe it is analogous to having erase take const_iterators in the STL. It was changed in C++11, so someone must have thought it was a good idea. In add_edge you are not modifying the vertex, so there is no reason why the vertex iterators should be const. Also, to call add_edge you need to have a non-const reference to the graph, so there is no logical constness violation in any case. 

Forcing the user to pass non-const iterators to add_edge means that, for example, if we implement an algorithm that finds pairs of vertices that should be added to the graph to make it connected, we must make the algorithm take a non-const reference to the graph, so that the pairs of vertices it returns can be used to make the graph connected. Forcing such an algorithm to take a non-const reference greatly reduces the const-safety, since the algorithm doesn't need to modify the graph. So I think this example is quite motivating.

> C++11 went one step in the right direction by having functions such as erase and insert take const_iterators. Having a way to obtain iterators from const_iterators would allow a class like the above to do the same.

But this breaks const correctness. The reason you have the workaround for the random-access containers is that you have a mutable reference to the container itself which avoids breaking const-correctness.

Yes, my suggestion is to allow it only when you have the mutable reference, which is the case in which it's already possible. 

You would need something like:

iterator const_iterator_cast(Container& c, Container::const_iterator i)

I was thinking more along the lines of a member function:

iterator iterator_to(const_iterator i);

added to containers. The containers should have the knowledge to make the conversion, and since it's a non-const function const-correctness wouldn't be violated.

 

This of course makes the assumption that there is some cheap way to recover an iterator given a const iterator; though I suspect 99.99% of the time that is true.

> if the compiler is trying to keep track of who might modify what.

The compiler cannot use const as a means of determining if someone is modifying something, because const_cast exists in the language. The compiler must be able to prove that the operations done on something are in fact constant operations in order to optimize based on this assumption.

> Being able to get a const_iterator from a iterator would sometimes be indeed useful. Just not the other way around or people start breaking stuff as they tend to do now with const_cast.

You can already do this -- const iterator has a constructor taking iterator. (e.g. a wchar_t* can turn into a wchar_t const* without a cast; and const_iterator must mimic this behavior)

Billy O'Neal

http://stackoverflow.com/users/82320/billy-oneal

--

 
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.

To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.

[Thiago Macieira]

On quinta-feira, 2 de janeiro de 2014 08:29:48, Miroslav Knejp wrote:
> You could just make a temporary
> container and use it for the cast. Unless the iterators track their
> container (which is probably only the case in debug builds, if at all)
> this works even better than the advance/distance trick (which is at
> least quite inefficient for most iterator types).

The iterator doesn't need to track the container for the debug code to be able
to verify if the const_iterator being passed belongs to that container.

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358

[Howard Hinnant]

It does exist, and it is efficient:

auto i = c.erase(ci, ci);

Howard

[xavi]

Neat, hadn't thought of that. Thanks for the hint!

2014/1/2 Howard Hinnant <howard....@gmail.com>

[Billy O'Neal]

>I believe it is analogous to having erase take const_iterators in the STL

Not really. Erase takes const iterators because it does not modify the iterators' target; it modifies the container itself, and the iterators serve merely as position indicators. There's no conceptual const-ness violation there.

Billy O'Neal

https://github.com/BillyONeal/

http://stackoverflow.com/users/82320/billy-oneal

[Felipe Magno de Almeida]

On Thu, Jan 2, 2014 at 1:51 PM, Howard Hinnant <howard....@gmail.com> wrote:
>

[snip]

>> Is there any reason why such a facility doesn't exist for the standard containers?
>
> It does exist, and it is efficient:
>
> auto i = c.erase(ci, ci);

Wow, I'd never thought of that! And I agree, as the OP, that this
feature is really
useful. Maybe someone should propose Boost to create a free function that
does exactly this.

template <typename Container>
typename Container::iterator const_iterator_cast(Container& c,
typename Container::const_iterator i)
{
return c.erase(i, i);
}

> Howard
>
> --

Regards,
--
Felipe Magno de Almeida

[Billy O'Neal]

I wouldn't even call that a cast -- "cast" implies "messing with the type system" -- and this isn't. :)

Billy O'Neal

https://github.com/BillyONeal/

http://stackoverflow.com/users/82320/billy-oneal

[Felipe Magno de Almeida]

On Thu, Jan 2, 2014 at 5:25 PM, Billy O'Neal <billy...@gmail.com> wrote:
> I wouldn't even call that a cast -- "cast" implies "messing with the type
> system" -- and this isn't. :)

I wouldn't too. But I didn't find a better name. I'm open to suggestions :).

> Billy O'Neal
> https://github.com/BillyONeal/
> http://stackoverflow.com/users/82320/billy-oneal

[snip]

[xavi]

It kind of messes with the type system. You can use it to cheat, since the container c doesn't need to be the one containing the iterator. Also, at least in gcc 4.9 (it's not supported in 4.8 and earlier), it is implemented with a const_cast, so yes, I believe there's some messing :).

The only way to implement it without a cast is that const_iterators actually contain non-const pointers, which is possible, but not any safer.

2014/1/2 Felipe Magno de Almeida <felipe.m...@gmail.com>

[Felipe Magno de Almeida]

On Thu, Jan 2, 2014 at 5:57 PM, xavi <gra...@gmail.com> wrote:
> It kind of messes with the type system. You can use it to cheat, since the
> container c doesn't need to be the one containing the iterator. Also, at
> least in gcc 4.9 (it's not supported in 4.8 and earlier), it is implemented
> with a const_cast, so yes, I believe there's some messing :).
> The only way to implement it without a cast is that const_iterators actually
> contain non-const pointers, which is possible, but not any safer.

That is undefined behavior. The function's preconditions is obvious and if
you deviate from that then that's outside the function's goal. So,
if you use it for messing with the type system, then it is your fault and
not the function's objective.

[David Rodríguez Ibeas]

On Thu, Jan 2, 2014 at 4:47 PM, Felipe Magno de Almeida <felipe.m...@gmail.com> wrote:

That is undefined behavior. The function's preconditions is obvious and if

you deviate from that then that's outside the function's goal. So,
if you use it for messing with the type system, then it is your fault and
not the function's objective.

How does that differ from say 'const_cast'? The preconditions are clear and so on... Not saying it has to be one way or another, but this is borderline on the semantics of 'const_cast'. If you consider that an iterator models a pointer, a conversion from 'const_iterator' to 'iterator' is equivalent in semantics as a conversion from 'T const *' to 'T *'. And this is really a conversion from one type to another, which is commonly used by means of "casts".

At any rate this is bikeshed discussion, so ignoring the name, the question stands: should the standard provide a mechanism to transform a 'const_iterator' into an 'iterator'?

Adding to the bikeshed discussion: this could be part of the iterator traits:

iterator_traits<std::vector<int>::const_iterator>::mutable_iterator(cit)

This is unprocessed thought, it might be a function, a functor or some other mechanism, but if this is going to move forward users should be able to provide a way of transforming their own iterators.

[Billy O'Neal]

The difference is that it requires a *mutable* reference to the container. You aren't converting a const_iterator into an iterator -- you are asking the mutable container for a mutable iterator at the same position as a given const_iterator; which is safe.

Billy O'Neal

https://github.com/BillyONeal/

http://stackoverflow.com/users/82320/billy-oneal

[David Rodríguez Ibeas]

On Thu, Jan 2, 2014 at 5:37 PM, Billy O'Neal <billy...@gmail.com> wrote:

The difference is that it requires a *mutable* reference to the container. You aren't converting a const_iterator into an iterator -- you are asking the mutable container for a mutable iterator at the same position as a given const_iterator; which is safe.

This is a discussion that has been held before in this same thread. You are asking *a* container to transform the const iterator into a non-const one. The operation cannot be *checked* in constant time for any container in which doing `advance(begin(), distance(begin(),it))` is not already constant time. Without the operation being checked, it is *unsafe*. Felipe's point was that if the operation need not be checked, it is undefined behavior and that's that. I mentioned that this does not make a huge difference from 'const_cast', similar risk of undefined behavior and similar semantics.

Then you come back stating that having a valid mutable container makes it safe, but that is not checked, and at this point you can continue the unproductive discussion by rereading the previous paragraph. You can also add that undefined behavior could be 'checked' in debug builds, with checked iterators, using defensive programing techniques and you would have a point. That is why I mentioned that arguing on the naming is pretty useless at this point. Both sides have valid points

Summarizing and focusing on what I believe are more productive discussions:

The operation can take a mutable reference to a container together with const_iterator, *but* the constraints on the operation (constant time) mean that in the general case it cannot be verified.

Since it cannot be verified, a different approach could just take the iterator and behave as a cast. It is unsafe, but not much more unsafe than the previous alternative.

Other than that, we can discuss on the form of the operation (should this be a trait in 'iterator_traits'? A member function of the `const_iterator`? A function of the container? A separate operation? (How would users extend this for their own iterators?)

[Felipe Magno de Almeida]

On Fri, Jan 3, 2014 at 3:35 AM, David Rodríguez Ibeas <dib...@ieee.org> wrote:
> On Thu, Jan 2, 2014 at 5:37 PM, Billy O'Neal <billy...@gmail.com> wrote:
>>
>> The difference is that it requires a *mutable* reference to the container.
>> You aren't converting a const_iterator into an iterator -- you are asking
>> the mutable container for a mutable iterator at the same position as a given
>> const_iterator; which is safe.
>>
>
> This is a discussion that has been held before in this same thread. You are
> asking *a* container to transform the const iterator into a non-const one.
> The operation cannot be *checked* in constant time for any container in
> which doing `advance(begin(), distance(begin(),it))` is not already constant
> time. Without the operation being checked, it is *unsafe*. Felipe's point
> was that if the operation need not be checked, it is undefined behavior and
> that's that. I mentioned that this does not make a huge difference from
> 'const_cast', similar risk of undefined behavior and similar semantics.

const_cast is not UB to remove const from objects defined as mutable.
Actually, it exists exactly to allow that. The function I demonstrated
is to get an iterator from its mutable container that points to the same
position as a const_iterator. Being able to get a iterator from a
const_iterator without a reference to the correct container is UB.
So the semantics are *completely different*. That you can get away
with UB is just a coincidence and surely not true for all standard
implementations.

> --

[Maurice Bos]

Hello,

A bit late reply, but you might still be interested: This exact issue was discussed before: https://groups.google.com/a/isocpp.org/d/msg/std-proposals/1Q_HgjQpirA/jKXXuqaJMHsJ

Kind regards,
Maurice Bos

2014/1/2 Xavi Gratal <gra...@gmail.com>