const_iterator ==> iterator (in constant time)
Scott Meyers
the book), I describe how to use distance and advance to produce an
iterator from a const_iterator. I've since received mail from several
readers, all of whom echo this sentiment:
Well I must say that was a disappointing realization! Does this mean that
you cannot grant someone read-only access to a list by providing them
with a const_iterator and then allow them constant-time insertions and
erasures using those same iterators?
One reader pointed out this:
When the idiom is applied to iterators that are not of the random access
category, the actual complexity averages to O(2n). That can be cut in
half to O(n) as follows:
C::iterator i(c.begin());
while (&*i != &*ci) ++i;
This is twice as fast on the average, because distance(c.begin(), ci)
passes through all the elements from the beginning of the container to ci
once, then advance(c.begin(), n) passes through all those same elements a
second time. The while loop shown above only traverses the elements
once. (I timed it using two different compilers. Sure enough -- about
twice as fast.) Neither solution is optimum for all iterator
categories. The best solution is one that is parameterized by the
category tag to invoke the advance(distance()) idiom only on random
access iterators, and the while loop on all others.
Another told me how he copes:
What I ended up doing was looking at my list implementation and figuring
out how to convert const_iterators to iterators in constant-time. With
Microsoft Visual C++ 6.0's STL it looks like this:
list<int>::const_iterator iConst= /* ... */;
list<int>::iterator i( iConst._Mynode() );
I verified that the same was possible (with a slightly different member
function) under one Linux G++ STL distribution (I've forgotten which).
This is obviously non-portable and my solution makes me terribly unhappy
every time I look at it, but it's the best I can do. I was hoping you
could either confirm my suspicions or better yet point out the hole in
my argument because this seems like an issue that can only be resolved
by changing the standard..?!
For Standards-related issues, I point people to
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-closed.html#180, and I sent
this to one person:
I don't think there's a portable way to do it without writing a custom
iterator. However, you could write a custom iterator class that
internally contains both an iterator and a const_iterator into a list,
and each operation on the custom iterator would internally affect both
contained iterators. The custom iterator could then offer a function to
get at the contained iterator, but this would be accessible only to the
class containing the list (i.e., the function would be private and the
class containing the list would be a friend). This is all off the top of
my head, but I think it would work, though I can't call it elegant.
If my mail is any indication, people want a portable constant-time
conversion from iterator to const_iterator for containers offering only
bidirectional iterators, and they're stunned to discover that the library
offers nothing in this regard.
I welcome all words of wisdom on this topic. Is there a portable
constant-time conversion from const_iterator to iterator I don't know
about? Is it practical to suggest a custom iterator (such as I sketched
above) for classes containing STL containers and wanting to expose only
const_iterator semantics while supporting constant-time internal conversion
to iterators?
Thanks,
Scott
--
Check out "THE C++ Seminar," http://www.gotw.ca/cpp_seminar/
Also check out "Effective STL," http://www.aw.com/estl/
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
Joel Dudgeon
Just wanted to say that I recently picked up Effective STL and it is the
*first* computer book I've read from start to finish (and without falling
asleep). A lot of the examples and pitfalls you pointed out really
surprised me.
Good job! :)
Joel Dudgeon
Consultant
MCP
Unisys Canada Inc
"Scott Meyers" <sme...@aristeia.com> wrote in message
news:MPG.15c94e9a3...@news.hevanet.com...
> In Effective STL Item 27 (as well as in my June 2001 CUJ article drawn
from
> the book), I describe how to use distance and advance to produce an
> iterator from a const_iterator. I've since received mail from several
> readers, all of whom echo this sentiment:
>
<snip>
>
> Scott
>
<snip>
John Potter
wrote:
> If my mail is any indication, people want a portable constant-time
> conversion from iterator to const_iterator for containers offering only
> bidirectional iterators, and they're stunned to discover that the library
> offers nothing in this regard.
24.1/1 Iterators are a generalization of pointers ...
Then they damn well ought to act like them. :)
> I welcome all words of wisdom on this topic. Is there a portable
> constant-time conversion from const_iterator to iterator I don't know
> about?
Depends upon how portable you want. When I don't know what I am doing,
I get the biggest hammer that I can find.
void do_something (const_some_iterator cit) {
some_iterator& it = (some_iterator&)cit;
If it is really a pointer, this is a const_cast that works.
If it is a class where iter inherits from citer (dinkum) this is a
static_cast down the hierarchy that works.
If they are unrelated classes which wrap a pointer (sgi) this is a
reinterpret_cast that works.
If this hammer is in the hands of a fool (vector<int>::iterator from
list<double>::const_iterator) the sparks may light a fire.
In theory, this is not portable. In practice, it is portable until
someone finds an implementation where it does not work. This has
been posted before and nobody has thrown an exception.
John
Peter Dimov
> If my mail is any indication, people want a portable constant-time
> conversion from iterator to const_iterator for containers offering only
> bidirectional iterators, and they're stunned to discover that the library
> offers nothing in this regard.
Within the current STL framework this cannot be done while maintaining
const-correctness.
There are three types of iterators:
[1] non-const iterators to non-const containers;
[2] const iterators to non-const containers;
[3] const iterators to const containers.
[1] and [2] are convertible to each other without const violations,
but the STL does not offer a way to distinguish [2] and [3].
--
Peter Dimov
Multi Media Ltd.
Carlos Moreno
Woaw!! I can't believe my eyes!! John Potter posting a
big, big hack!!! (a very nice, clever, and elegant one,
I must agree, but a hack!!) :-)
{Well I think that is a compliment rather than a flame:) -mod/fwg}
> In theory, this is not portable. In practice, it is portable until
> someone finds an implementation where it does not work. This has
> been posted before and nobody has thrown an exception.
Are you sure nobody has thrown an exception? Maybe nobody
had a catch for that class of exception, or maybe it was
caught in a catch(...) clause (i.e., someone posted code
saying that it was crashing and not knowing why -- maybe
the why happened to be this iterators conversion and no-
one ever knew! :-))
Carlos
--
John Potter
> Scott Meyers <sme...@aristeia.com> wrote in message news:<MPG.15c94e9a32fb3b2
498...@news.hevanet.com>...
>
> > If my mail is any indication, people want a portable constant-time
> > conversion from iterator to const_iterator for containers offering only
> > bidirectional iterators, and they're stunned to discover that the library
> > offers nothing in this regard.
>
> Within the current STL framework this cannot be done while maintaining
> const-correctness.
>
> There are three types of iterators:
>
> [1] non-const iterators to non-const containers;
> [2] const iterators to non-const containers;
> [3] const iterators to const containers.
>
> [1] and [2] are convertible to each other without const violations,
> but the STL does not offer a way to distinguish [2] and [3].
Agreed.
s/iterators/pointers/;s/containers/arrays/;s/STL/language/
It's still true.
The difference is that the language provides the means to convert [2]
(or unsafely [3]) to [1]. People are stunned to find that the library
does not provide the same.
The standard requires implicit conversion from iterator to
const_iterator. A DR requires comparison between iterator and
const_iterator. What is missing is a requirement for explicit
conversion from const_iterator to iterator. At least one
implementation provides it and it would be trivial for others.
It could be considered a real problem that the language provides the
explicit conversion via const_cast while the trivial library solution
provides the conversion for class type iterators via static_cast. An
iterator_const_cast would solve this. It can be a function in the
library with no core change required, and overloaded for pointers.
John
Bill Wade
"John Potter" <jpo...@falcon.lhup.edu> wrote
> void do_something (const_some_iterator cit) {
> some_iterator& it = (some_iterator&)cit;
> In theory, this is not portable. In practice, it is portable until
> someone finds an implementation where it does not work. This has
> been posted before and nobody has thrown an exception.
throw COW;
Most COW classes perform a deep copy when "handing out" a non-const
iterator, and many also set an "unshareable" flag. In all likelyhood your
cast does neither, with surprising results.
In general there is no such thing as an inexpensive conversion from a
read-only iterator to a read-write iterator, because in general gaining
write access is expensive.
James Kanze
news:<3B61CCF0...@cyberx.com>...
> Woaw!! I can't believe my eyes!! John Potter posting a
> big, big hack!!! (a very nice, clever, and elegant one,
> I must agree, but a hack!!) :-)
> {Well I think that is a compliment rather than a flame:) -mod/fwg}
> > In theory, this is not portable. In practice, it is portable
> > until someone finds an implementation where it does not work.
> > This has been posted before and nobody has thrown an exception.
> Are you sure nobody has thrown an exception? Maybe nobody had a
> catch for that class of exception, or maybe it was caught in a
> catch(...) clause (i.e., someone posted code saying that it was
> crashing and not knowing why -- maybe the why happened to be this
> iterators conversion and no- one ever knew! :-))
The only real problem is that the hammer is too big:-).
In order for John's solution not to work in the intended cases, an
implementation would have to use a different representation for const
and non-const iterators. And I can't think of any reason an
implementation might have to do so other than breaking John's hack.
Note that there are cases John didn't mention. A debugging
implementation is likely to have some extra data in the iterators to
link them to the container, for example. But the const and non-const
iterators will normally have exactly the same information, in the same
places, so the reinterpret_cast variant works anyway.
(It is, of course, a trivial exercise to write iterators where it
doesn't work.)
--
James Kanze mailto:ka...@gabi-soft.de
Beratung in objektorientierer Datenverarbeitung --
-- Conseils en informatique oriente objet
Ziegelhttenweg 17a, 60598 Frankfurt, Germany, Tl.: +49 (0)69 19 86 27
Louis Lavery
Scott Meyers wrote in message ...
>In Effective STL Item 27 (as well as in my June 2001 CUJ article
drawn from
>the book), I describe how to use distance and advance to produce an
>iterator from a const_iterator. I've since received mail from
several
>readers, all of whom echo this sentiment:
>
> Well I must say that was a disappointing realization! Does this
mean that
> you cannot grant someone read-only access to a list by providing
them
> with a const_iterator and then allow them constant-time insertions
and
> erasures using those same iterators?
>
Surely you don't want to make it easy to convert from const_iterator
to iterator as that's effectively a const_cast, isn't it?
I worry about const-correctness.
The way I see it is that you can't do as you want because iterators,
const_iterators, containers and const interact as follows...
+---------+---------++------+------+-------+-------+
| iterator|container|| read | write| insert| erase |
+---------+---------++------+------+-------+-------+
| | || 1 | 1 | 1 | 1 |
| | const || 1 | 1 | 0 | 0 |
| const_ | || 1 | 0 | 0 | 0 |
| const_ | const || 1 | 0 | 0 | 0 |
+---------+---------++------+------+-------+-------+
...while if it was as...
+---------+---------++------+------+-------+-------+
| iterator|container|| read | write| insert| erase |
+---------+---------++------+------+-------+-------+
| | || 1 | 1 | 1 | 1 |
| | const || 1 | 1 | 0 | 0 |
| const_ | || 1 | 0 | 1 | 1 |
| const_ | const || 1 | 0 | 0 | 0 |
+---------+---------++------+------+-------+-------+
...then you could.
Louis.
Louis Lavery
Peter Dimov wrote in message
<7dc3b1ea.01072...@posting.google.com>...
>Scott Meyers <sme...@aristeia.com> wrote in message
news:<MPG.15c94e9a3...@news.hevanet.com>...
>
>> If my mail is any indication, people want a portable constant-time
>> conversion from iterator to const_iterator for containers offering
only
>> bidirectional iterators, and they're stunned to discover that the
library
>> offers nothing in this regard.
>
>Within the current STL framework this cannot be done while
maintaining
>const-correctness.
>
>There are three types of iterators:
>
>[1] non-const iterators to non-const containers;
>[2] const iterators to non-const containers;
>[3] const iterators to const containers.
>
Then surely there must four...
[4] non-const iterators to const containers;
Louis.
Steven E. Harris
> Then surely there must four...
>
> [4] non-const iterators to const containers;
How do you get one? begin() and end() returning iterator are non-const
member functions.
--
Steven E. Harris :: seha...@raytheon.com
Raytheon :: http://www.raytheon.com
Louis Lavery
Steven E. Harris wrote in message
<877kwnj...@harris.sdo.us.ray.com>...
>"Louis Lavery" <Lo...@DevilsChimney.co.uk> writes:
>
>> Then surely there must four...
>>
>> [4] non-const iterators to const containers;
>
>How do you get one? begin() and end() returning iterator are
non-const
>member functions.
void f(Container const & c,c::iterator i)
{
//....
}
void g()
{
Container c;
f( c, c.begin() );
}
Louis.
Dave Harris
> Surely you don't want to make it easy to convert from const_iterator
> to iterator as that's effectively a const_cast, isn't it?
> I worry about const-correctness.
Indeed. The cast is motivated by the fact that erase() et al take
iterators instead of const_iterators. Arguably this is a design flaw,
since the erase() is modifying the container directly. The container needs
to be non-const, but it's not clear that the iterator must be. (Was this
what you were trying to say with your tables?)
I think we can make two observations:
(1) On every occasion that we desire the cast, we will have a non-const
reference to the container available.
(2) A non-const reference to the container must be available for the cast
to be performed (in general).
It follows that this iterator cast ought to be a function with two
arguments: const_iterator *and* container, not just the const_iterator. It
might even be a member function of the container. (Alternatively, we could
change erase() et al to accept const_iterators and the motivation for the
cast would go away.)
Scott Meyers opening article gives some justification for (1). I would be
interested in counter-examples. Logically it is the non-const container
which legitimises the cast.
For (2), consider that const_iterator and iterator need not have the same
representation. For example, suppose we want the container to track which
items have been modified - or at least, accessed in a non-const way. For
these items we set a "dirty" flag. Here is a very brief sketch for a
hardwired container of 10 integers:
class Container {
int data[10];
bool isDirty[10];
public:
typedef const int *const_iterator;
class iterator {
Container *pContainer;
int index;
public:
int &operator*() {
pContainer->isDirty[index] = true;
return pContainer->data[index];
}
//...
};
const_iterator begin() const {
return data+0;
}
iterator begin() {
return iterator( this, 0 );
}
iterator convert( const_iterator i ) {
return iterator( this, i - data );
}
//...
};
Here a const_iterator is a simple pointer, hopefully maximally efficient.
A non-const iterator is a pointer to the container plus an index.
Dereferencing a non-const iterator sets the isDirty flag. Later we can
write just the dirty items back to a persistent store, or invalidate a
cache, or whatever.
Notice that this scheme will be broken by John Potter's "big hammer".
There simply isn't enough information in a const_iterator to convert it
into a non-const one unless the container is provided. We could make the
"big hammer" approach work by making const_iterator use the same
representation as iterator, but that would double the size of
const_iterator and be generally inefficient.
Of course, no std container would look like this. I think it is a
legitimate design for user-written containers, though, and I hope that
these user-written iterators would conform to the std iterator concept.
So, if some kind of iterator cast function is added, I hope a non-const
instance of the container is made available to it.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
Louis Lavery
Dave Harris wrote in message ...
>Lo...@DevilsChimney.co.uk (Louis Lavery) wrote (abridged):
>> Surely you don't want to make it easy to convert from
const_iterator
>> to iterator as that's effectively a const_cast, isn't it?
>> I worry about const-correctness.
>
>Indeed. The cast is motivated by the fact that erase() et al take
>iterators instead of const_iterators. Arguably this is a design flaw,
>since the erase() is modifying the container directly. The container
needs
>to be non-const, but it's not clear that the iterator must be. (Was
this
>what you were trying to say with your tables?)
>
Yes.
>I think we can make two observations:
>
>(1) On every occasion that we desire the cast, we will have a
non-const
>reference to the container available.
>
>(2) A non-const reference to the container must be available for the
cast
>to be performed (in general).
>
>It follows that this iterator cast ought to be a function with two
>arguments: const_iterator *and* container, not just the
const_iterator. It
>might even be a member function of the container. (Alternatively, we
could
>change erase() et al to accept const_iterators and the motivation for
the
>cast would go away.)
>
What would be the point of passing tbe container? I mean how will the
cast
know, without a check that's as expensive as the one we're trying to
avoid,
that the const_iterator points into the container.
I much prefer the alternative, erase() et al taking const_iterators,
as it's
simple and does exactly what we want. Plus it can be added without
breaking
current code.
[snip]
Louis.
Dave Harris
> cast know, without a check that's as expensive as the one we're
> trying to avoid, that the const_iterator points into the container.
Passing the wrong container should result in undefined behaviour, so no
check is needed.
An O(1) check can always be achieved, at some cost in space and speed, by
having the const_iterator include a pointer to the container. Thus an
implementation could offer an optional check in a "safe STL" version and
still conform to the standard's complexity requirements. A "fast STL"
version needn't bother with the check or the space overhead. This sort of
thing is down to quality of implementation. Making the "wrong container"
behaviour undefined allows either policy.
A similar problem arises with erase() et al. Passing an iterator from one
container to the erase() of another results in undefined behaviour. I see
no reason why the const_cast() function should be different.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
David Abrahams
> If my mail is any indication, people want a portable constant-time
> conversion from iterator to const_iterator for containers offering only
> bidirectional iterators, and they're stunned to discover that the library
> offers nothing in this regard.
>
> I welcome all words of wisdom on this topic.
I can't promise these words are wise., but...
I think people are asking for what seems like the most expedient route to
their goal. I don't think their ultimate goal is to convert a constant
iterator into a mutable iterator. I think they have got ahold of a constant
iterator which they want to use to indicate an insertion/deletion/splice
position in a non-const container. I've said this before, and I'll say it
again: the right solution is to fix the standard so that works.
It might also be nice to have a non-const container function which produces
a non-const iterator from a const_iterator, but I can't think of a strong
argument for it.
> Is there a portable
> constant-time conversion from const_iterator to iterator I don't know
> about?
Nope.
> Is it practical to suggest a custom iterator (such as I sketched
> above) for classes containing STL containers and wanting to expose only
> const_iterator semantics while supporting constant-time internal
conversion
> to iterators?
Practical, sure, but possibly unweildy. I think the boost iterator_adaptors
library would make it easy to generate such an iterator, though. I don't see
any reason for it to contain the const_iterator, since the mutable iterator
does everything that the const_iterator can, and more.
-Dave
Louis Lavery
David Abrahams wrote in message <9khktc$nms$1...@bob.news.rcn.net>...
>
>"Scott Meyers" <sme...@aristeia.com> wrote in message
>news:MPG.15c94e9a3...@news.hevanet.com...
>
>> If my mail is any indication, people want a portable constant-time
>> conversion from iterator to const_iterator for containers offering
only
>> bidirectional iterators, and they're stunned to discover that the
library
>> offers nothing in this regard.
>>
>> I welcome all words of wisdom on this topic.
>
>I can't promise these words are wise., but...
>
>I think people are asking for what seems like the most expedient
route to
>their goal. I don't think their ultimate goal is to convert a
constant
>iterator into a mutable iterator. I think they have got ahold of a
constant
>iterator which they want to use to indicate an
insertion/deletion/splice
>position in a non-const container. I've said this before, and I'll
say it
>again: the right solution is to fix the standard so that works.
>
Bang on! And it's easily fixed by insert/erase etc taking a
const_iterator and...
>It might also be nice to have a non-const container function which
produces
>a non-const iterator from a const_iterator, but I can't think of a
strong
>argument for it.
...isn't it nice that they return an iterator?
OTOH if you want only to over write the item then the fact that you
*can* but it takes longer via a const_iterator seems justification for
adding an non-const member function to do the job.
Louis.
Louis Lavery
Dave Harris wrote in message ...
>> What would be the point of passing tbe container? I mean how will
the
>> cast know, without a check that's as expensive as the one we're
>> trying to avoid, that the const_iterator points into the container.
>
>Passing the wrong container should result in undefined behaviour, so
no
>check is needed.
>
>An O(1) check can always be achieved, at some cost in space and
speed, by
>having the const_iterator include a pointer to the container. Thus an
>implementation could offer an optional check in a "safe STL" version
and
>still conform to the standard's complexity requirements. A "fast STL"
>version needn't bother with the check or the space overhead. This
sort of
>thing is down to quality of implementation. Making the "wrong
container"
>behaviour undefined allows either policy.
>
It's getting too complicated. Casting away constness is a no no, we
certainly
don't want to see it encouraged by its use in the STL.
As I see it...
If we have a (non const) container and an iterator into it then
we can (1) read the item in constant time.
(2) write the item in constant time.
(3) insert/erase in constant time if it's a list and
in O(n) time if it's a vector.
If we have a (non const) container and an const_iterator into it then
we can (1) read the item in constant time
(2) write the item in constant time if it's a vector and
in O(n) time if it's a list.
(3) insert/erase in O(n) time.
...we can achieve the same end result in both cases, it's just that
in the later it takes longer and as programmers are resorting to
hacks (i.e. const_casts) it smells, as you said in your earlier
post, of a design flaw. One way round it is...
(3) can be fixed by erase/insert taking a const_iterator.
(2) can be fixed by adding a member function...
iterator container::substitute(const_iterator,new_item);
...that replaces the item addressed by the const_iterator
and returns an iterator to it.
Neither of these fixes compromises const-correctness (if they
do then it must already be compromised).
Regards,
Louis.
John Potter
wrote:
>
> Steven E. Harris wrote in message
> <877kwnj...@harris.sdo.us.ray.com>...
> >"Louis Lavery" <Lo...@DevilsChimney.co.uk> writes:
> >
> >> Then surely there must four...
> >>
> >> [4] non-const iterators to const containers;
> >
> >How do you get one? begin() and end() returning iterator are
> non-const
> >member functions.
> void f(Container const & c,c::iterator i)
> {
> //....
> }
> void g()
> {
> Container c;
>
> f( c, c.begin() );
> }
That does not answer the question. You do not have a const container
anywhere, only a const reference to a non-const container. There is
no way to get one without a cast and it is trivial to get one with a
cast.
int const stuff[] = { 1, 2, 3, 42 };
list<int> const l(stuff, stuff + sizeof(stuff) / sizeof(stuff[0]));
list<int>::iterator = const_cast<list<int>&>(l).begin();
Just for fun, we can modify a const container through a const_iterator
also.
const_cast<int&>(*l.begin()) = 69;
These are all nasty things which the language allows us to do at our
own risk. We can also remove the const from a pointer with const_cast
at our own risk. The library seems to present a holier-than-thow
view by not providing the same for const_iterator. Why do we need such
a hack to do such a simple thing?
*const_cast<list<int>::iterator&>(l.begin()) = 69;
All of these things are useful when we start with a const reference to
a non-const container and know what we are doing. They are all fatal
when we start with a const container.
John
John Potter
>
> "John Potter" <jpo...@falcon.lhup.edu> wrote
>
> > void do_something (const_some_iterator cit) {
> > some_iterator& it = (some_iterator&)cit;
>
> > In theory, this is not portable. In practice, it is portable until
> > someone finds an implementation where it does not work. This has
> > been posted before and nobody has thrown an exception.
>
> throw COW;
Great! I would hate to see that hack go uncontested.
> Most COW classes perform a deep copy when "handing out" a non-const
> iterator, and many also set an "unshareable" flag. In all likelyhood your
> cast does neither, with surprising results.
>
> In general there is no such thing as an inexpensive conversion from a
> read-only iterator to a read-write iterator, because in general gaining
> write access is expensive.
If we restrict the application to the original problem, I don't think
that exception will be herd. The original problem was bidirectional
iterators from standard node based contianers. I think the standard
built strong enough fences to keep COWs out of that pasture.
However, your exception is valid for std::string. That splits the
solution into random_access and other. That simplifies the cast
hack to just reinterpret_cast which will work for the two types of
bidirectional iterator mentioned. It also shows a subtle bug in
Scott's solution for random_access iterators.
Container c;
Citer ci;
// point ci into c
Iter i(c.begin()); // invalidates ci
The following should work with or without COWs.
Container::difference_type d =
distance(static_cast<Container const&>(c).begin(), ci);
Iter i(c.begin()); // invalidates ci, but we don't care.
advance(i, d);
On 1 Aug 2001 14:52:10 -0400, ka...@gabi-soft.de (James Kanze) wrote:
> The only real problem is that the hammer is too big:-).
Actually it was a huge shrink-to-fit hammer. The reinterpret_cast
would cover the static_cast case, but not the const_cast case. If
we use the above for random_access iterators, that removes the
const_cast case and I agree that a reinterpret_cast where a
static_cast would work is better than an invisible C-style or
functional style cast.
> In order for John's solution not to work in the intended cases, an
> implementation would have to use a different representation for const
> and non-const iterators. And I can't think of any reason an
> implementation might have to do so other than breaking John's hack.
> (It is, of course, a trivial exercise to write iterators where it
> doesn't work.)
Agreed.
On 4 Aug 2001 18:48:05 -0400, "David Abrahams" <david.a...@rcn.com>
wrote:
> I think people are asking for what seems like the most expedient route to
> their goal. I don't think their ultimate goal is to convert a constant
> iterator into a mutable iterator. I think they have got ahold of a constant
> iterator which they want to use to indicate an insertion/deletion/splice
> position in a non-const container. I've said this before, and I'll say it
> again: the right solution is to fix the standard so that works.
Strongly agreed. Maybe that hack will give some incentive to fix the
standard as a lesser evil.
Or maybe we don't understand, and people really want the same ability to
remove the const from iterators that the language provides for pointers.
I can easily understand the desire to do what I want and not be
restricted by someone elses view of what I should be able to do. Moral
issues should not be legislated.
John
Louis Lavery
[snip stuff on const containers etc]
>These are all nasty things which the language allows us to do at our
>own risk. We can also remove the const from a pointer with
const_cast
>at our own risk. The library seems to present a holier-than-thow
>view by not providing the same for const_iterator.
I don't see it as a "holier-than-thow view ". If the library were
to supply a const_iterator_cast wouldn't it
(1) compromise const-corectness and
(2) be seen to be condoning casting away const-ness in general?
I agree with the sentiment "casting away const-ness is a sign of bad
design".
Louis.
Fabio Lopiano
> the book), I describe how to use distance and advance to produce an
> iterator from a const_iterator.
[...]
Hello,
I've read the article and the thread, but I am still missing the point...
I don't understand why someone should have the need to convert a
const_iterator to an iterator.
I mean : if I need to modify a container, i would use an iterator
from the beginning.
I would use a const_iterator only if the container I'm working with is
const. And, if that is const, It would be impossible to make an insertion
or a deletion on it.
I make large use of iterators (and const_iterators) in my work, but I never
had this need to convert a const_iterator to an iterator. In fact I usually
get const_iterator only from containers I'm not allowed to modify and this
is what I thought const_iterators were supposed to be used for.
So, what am I missing ?
Ciao,
Fabio Lopiano
Erik Max Francis
> I would use a const_iterator only if the container I'm working with is
> const. And, if that is const, It would be impossible to make an
> insertion
> or a deletion on it.
Or if you know for a fact that you have no need to modify it. Which if
true, you've no business wanting to convert the const_iterator to an
iterator.
--
Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/
__ San Jose, CA, US / 37 20 N 121 53 W / ICQ16063900 / &tSftDotIotE
/ \ Do not stand in a place of danger trusting in miracles.
\__/ (an Arab proverb)
Alcyone Systems' Daily Planet / http://www.alcyone.com/planet.html
A new, virtual planet, every day.
Blair Fraser
>
> I don't understand why someone should have the need to convert a
> const_iterator to an iterator.
I recently coded up an ObservedList using std::list. You only had
access to const_iterators until you wanted to modify the list, then
you would pass the list a const_iterator and request for a key to
modify the element, when the key died, registered callbacks were
called to notify other classes of a change. To modify the object the
ObservedList would have to take a const_iterator and return an
iterator and key. This required a conversion and was O(n). I ended
up having a #define CONST_IS_NONCONST so I could make it O(1) in
production by throwing out const-correctness and having
const_iterators be iterators, and O(n) in debugging code with
const-correctness. Not an ideal solution. All I needed was a O(1)
const_iterator -> iterator. I'm sure this kind of thing comes up with
iterators in many other situations, but there's my example.
Blair Fraser
---
T-11 Los Alamos National Laboratory
Mark Rodgers
news:9khktc$nms$1...@bob.news.rcn.net...
> It might also be nice to have a non-const container function which
> produces a non-const iterator from a const_iterator, but I can't
> think of a strong argument for it.
What about avoiding cut and paste when overloading for const and
non-const:
class Foo
{
public:
std::list<int>::const_iterator bar() const;
std::list<int>::iterator bar()
{
const Foo *const This = this;
return /* the missing cast */ This->bar();
}
};
Mark
Bruce G. Stewart
>
> Fabio Lopiano wrote:
>
> > I would use a const_iterator only if the container I'm working with is
> > const. And, if that is const, It would be impossible to make an
> > insertion
> > or a deletion on it.
>
> Or if you know for a fact that you have no need to modify it. Which if
> true, you've no business wanting to convert the const_iterator to an
> iterator.
Oddly enough, despite the title, the article at the head of this thread
says "If my mail is any indication, people want a portable constant-time
conversion from iterator to const_iterator for containers offering only
bidirectional iterators, and they're stunned to discover that the
library offers nothing in this regard."
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Dave Harris
> it encouraged by its use in the STL.
What we are doing is not the moral equivalent of casting away constness.
We can always write a function like:
template <typename Container>
typename Container::iterator iterator_convert(
Container &c, typename Container::const_iterator i ) {
const Container &cc = c;
typename container::iterator result = c.begin();
advance( result, distance( cc.begin(), i ) );
return result;
}
(untested code) which does the conversion without using any casts. The
problem is one of efficiency, not ethics.
> It's getting too complicated.
I don't think so. What I am suggesting amounts to having the above
function added to the std library, and specialised for the various
containers. The various restrictions are already implicit in the above. It
may be easier to add a function than to meddle with the existing container
APIs. (Eg vendors can add iterator_convert without waiting for a standard
change.)
Still, I agree with your conclusions even though I don't agree with your
reasoning. I would rather erase() et al took const_iterators than an
iterator_convert() function be added. I wrote mainly because some people
were writing such functions, and, as in John Potter's example, not
providing them with the non-const container argument.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]