Problem
-------

Sometimes a user of a non-const container needs to convert a
const_iterator of that container to an iterator. There is no direct
way to express this in current C++.

Previous talk
-------------

This topic has been discussed earlier in C++ newsgroups. For your
convenience, I will summarize parts of discussions that I feel are
the most important. This way we need not repeat them.

(1) "converting a const_iterator to an iterator" in c.l.c.m.:

http://tinyurl.com/2ffsako

Summary:

JT:
"I have a class whose internal representation includes a list. I
want to give clients access to the list using const_iterator's. In
many cases I need to convert these const_iterator's into iterator's.
I see no reason why a list should not have a member function which
converts a const_iterator into an iterator."

MKK to JT:
"Scott Meyer has an article on this in _Effective STL_. If I recall
correctly, the guaranteed portable method is to make
a regular iterator and move it along the sequence until it points
to the same place as the const_iterator.  This is not fast on a
list, alas, but it will work even when the iterators are classes."

JE to JT:
"It is not clear to me that it would be any more efficient if the
containers handled this conversion. A list would still need to
iterate through its elements to ensure that the const_iterator was
pointing at one of its elements."

JP to JE:
"It has been stated that the modifying members of containers, like
erase, should take const_iterator anyway. It is the list not the
iterator that needs to be non-const."

VM:
"A while ago, I suggested in a post that every container should have
a 'deconstify' function that makes an iterator from const_iterator.
This is both safe, efficient and useful. Safe because deconstify is
a non-const member function, so it doesn't break the security of the
container. Efficient because - for the library implementor - it's
easy to convert a const_iterator to iterator. Useful because the
problem really exists."

VM to JE:
"The list (and any other container) doesn't need to check that
const_iterator points to one of its elements, it can _require_
that."
"Does the list ensure that the iterator passed to insert( ) points
to one of its elements? No, insert is a constant-time operation, it
assumes that the iterator will be ok."

DA to VM:
"But it (deconstify) would complicate both the library and user code
unneccessarily. I don't know why people keep proposing this hack to
the library. The container operations that accept iterators for
positional information should all be changed to accept
const_iterators." (extra context in brackets mine)

VM to DA:
"While I agree that those container operations should accept
const_iterators, it doesn't solve the problem I described in my
post. If I have a set of positions (const_iterators) and a non-const
container, I can't modify the elements located at those positions."

DA to VM:
"Fair enough; I missed your original post. As long as we make the
change I suggested, and in the absence of a property map interface,
I agree with you that something is needed. However, there's no need
to actually produce a non-const_iterator from a const_iterator is
there? All you need is a reference to an element."

Some interesting quotes follow later:

VM:
"The difference between const_cast and deconstify is that const_cast
can be used anywhere and with any type of container, it doesn't
protect your from modifying a container that's const in that
particular context. deconstify works with only non-const containers.
Thus, const_cast lacks the safety of deconstify."

JP:
"I understand that it is much more fun to talk about the broken STL
and how everything should be scrapped and start over.  We have the
STL, it is in the standard and not likely to go away anytime soon."

(2) "Problem with const_iterators for containers" in c.l.c.m:

http://tinyurl.com/2achnyh

Essentially the same points arise as in (1), so I'm not repeating
them here.

Comments
--------

The C++0x introduces const_iterators in container interfaces,
properly dealing with many issues that would have otherwise needed
const_iterator to iterator conversion.

However, despite this fact, I claim that a deconstify() member
function is still needed. A case is given by the specification of
the following function (let me use pseoudish code for brevity):

template <...>
pair<iter, iter> splicePartition(list<T>& c, const_iter begin,
const_iter end, Predicate predicate);

where
iter = list<T>::iterator
const_iter = list<T>::const_iterator

'splicePartition' reorders the elements in a subrange [begin, end[
in 'c', using splicing. If you call the return value a 'result',
this reordering is such that [result.first, result.second[ contains
those elements that fulfill the predicate, and [result.second, end[
contains those that do not fulfill the predicate.

We want the 'splicePartition' function to return non-const
iterators. This is so that we can, for example, to transform() those
elements which fulfill the predicate.

Proposal
--------

Following suggestions already made by others, add a deconstify()
non-const member function to containers to convert a const_iterator
to an iterator. This function should have constant complexity.

Even if the schedule for making the change would be too late, let's
discuss the problem and solution in principle.

What do you think?

--
http://kaba.hilvi.org

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use
mailto:std-c++@netlab.cs.rpi.edu<std-c%2B%2B@netlab.cs.rpi.edu>
]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Kaba wrote:
>
> Proposal
> --------
>
> Following suggestions already made by others, add a deconstify()
> non-const member function to containers to convert a const_iterator
> to an iterator. This function should have constant complexity.
>
> Even if the schedule for making the change would be too late, let's
> discuss the problem and solution in principle.
>
> What do you think?

I think the features are already there , just with a different name.

For random access iterators you could just do

Iter = c.begin() + (constIter - c.begin());

For containers like std::list, you could abuse the erase() function in
C++0x:

Iter = l.erase(constIter, constIter);

Having an empty range it will erase nothing, but still return an
iterator to the "next" element.


Bo Persson



--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Bo Persson wrote:
> > Following suggestions already made by others, add a deconstify()
> > non-const member function to containers to convert a const_iterator
> > to an iterator. This function should have constant complexity.
>
> I think the features are already there , just with a different name.
>
> For random access iterators you could just do
>
> Iter = c.begin() + (constIter - c.begin());
>
> For containers like std::list, you could abuse the erase() function in
> C++0x:
>
> Iter = l.erase(constIter, constIter);

Two problems:
1) These indirectly express a basic intent, a bit embarassing.
2) The erase() trick does not work for unordered containers.

--
http://kaba.hilvi.org

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Kaba wrote:
> Bo Persson wrote:
>>> Following suggestions already made by others, add a deconstify()
>>> non-const member function to containers to convert a
>>> const_iterator to an iterator. This function should have constant
>>> complexity.
>>
>> I think the features are already there , just with a different
>> name.
>>
>> For random access iterators you could just do
>>
>> Iter = c.begin() + (constIter - c.begin());
>>
>> For containers like std::list, you could abuse the erase()
>> function in C++0x:
>>
>> Iter = l.erase(constIter, constIter);
>
> Two problems:
> 1) These indirectly express a basic intent, a bit embarassing.

Yes, but if it is needed in some applications, you easily add
deconstify as a free function. Possibly overloading it for different
iterator types.

There is no real need to have it as a member function for the
containers.


> 2) The erase() trick does not work for unordered containers.

Doesn't it? At least there is an erase function with the same
signature as for std::list.



Bo Persson



--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Jul 28, 1:07 am, "Bo Persson" <b...@gmb.dk> wrote:
> Kaba wrote:
> > Bo Persson wrote:
> >>> Following suggestions already made by others, add a deconstify()
> >>> non-const member function to containers to convert a
> >>> const_iterator to an iterator. This function should have constant
> >>> complexity.
>
> >> I think the features are already there , just with a different
> >> name.
>
> >> For random access iterators you could just do
>
> >> Iter = c.begin() + (constIter - c.begin());
>
> >> For containers like std::list, you could abuse the erase()
> >> function in C++0x:
>
> >> Iter = l.erase(constIter, constIter);
>
> > Two problems:
> > 1) These indirectly express a basic intent, a bit embarassing.
>
> Yes, but if it is needed in some applications, you easily add
> deconstify as a free function. Possibly overloading it for different
> iterator types.
>
> There is no real need to have it as a member function for the
> containers.

I agree.

> > 2) The erase() trick does not work for unordered containers.
>
> Doesn't it? At least there is an erase function with the same
> signature as for std::list.

Per current FCD wording, yes. But this might change, depending
on the outcome of library issue

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#579

Greetings from Bremen,

Daniel Kr=FCgler


--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use
mailto:std-c++@netlab.cs.rpi.edu<std-c%2B%2B@netlab.cs.rpi.edu>
]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Bo Persson wrote:
> >> For containers like std::list, you could abuse the erase()
> >> function in C++0x:
> >>
> >> Iter = l.erase(constIter, constIter);
> >
> > Two problems:
> > 1) These indirectly express a basic intent, a bit embarassing.
>
> Yes, but if it is needed in some applications, you easily add
> deconstify as a free function. Possibly overloading it for different
> iterator types.
>
> There is no real need to have it as a member function for the
> containers.

Only the container knows how to safely and efficiently to carry out the
conversion. Thus there needs to be _at least one_ member function which
can do this without side effects. But you probably mean that since there
is range-erase, there is no real need, right?

That some containers have a range-erase which can be abused to carry out
the task does not mean it should be done that way. In particular, I
don't think it can be guaranteed that a range erase always makes sense
for all containers now and in the future, in contrast to a deconstify
function. Bottom line: mixed responsibilities cause problems (just think
of the famous stack pop returning the top element).

> > 2) The erase() trick does not work for unordered containers.
>
> Doesn't it? At least there is an erase function with the same
> signature as for std::list.

Looking at the latest draft, I see you are right. I wonder how it is
defined? By definition, the elements are unordered (hashed most
probably), so I think the user can not have any idea what elements
belong to the iterator range. Moreover, even the removal or insertion of
a single element can cause a reordering (a rehashing) which invalidates
all iterators ranges.

--
http://kaba.hilvi.org

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use
mailto:std-c++@netlab.cs.rpi.edu<std-c%2B%2B@netlab.cs.rpi.edu>
]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]