 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Sergey P. Derevyago
Guest
|
 Posted: Wed Mar 01, 2006 4:06 pm Post subject: Iterators must be convertible to [const] void* |
 |
|
1. The essence of the problem.
------------------------------
Iterators are underspecified. The standard in 24.1 [lib.iterator.requirements]
stands "Iterators are a generalization of pointers..." and "Since iterators
are an abstraction of pointers, their semantics is a generalization of most of
the semantics of pointers in C++.". But the following fundamental pointers'
property wasn't caught:
1) Every T* is convertible to void*.
2) Every const T* is convertible to const void*.
That is the common const void* type can be used to point to the elements (when
for example we need to erase an element from a non-const container using a
const_iterator).
Also std::iterator has several responsibilities:
1) Point to elements.
2) Access elements to read/modify.
3) Move to next/prev element.
And const void* type is ideal for the first task. In particular, every
possible comparison works as expected.
2. Proposed actions.
--------------------
1) Require every iterator and const_iterator to define operator void*() const
and operator const void*() const respectively.
2) Redefine containers' member functions that require a position (such as
insert() and erase()) to use const void* position rather than iterator
position parameter.
3. Code sample.
---------------
The following code illustrates the idea. Only the key functions and/or
operations are shown:
template <class T> struct new_vector {
typedef T* iterator;
typedef const T* const_iterator;
iterator begin() { return iterator(/* ... */); }
const_iterator begin() const { return const_iterator(/* ... */); }
void erase(const void* pos)
{
// assume that pos points to T element to be erased
}
};
template <class T> struct nl_iterator {
operator void*() const { /* return node<T> address */ }
};
template <class T> struct nl_const_iterator {
operator const void*() const { /* return const node<T> address */ }
};
template <class T> struct new_list {
typedef nl_iterator<T> iterator;
typedef nl_const_iterator<T> const_iterator;
iterator begin() { return iterator(/* ... */); }
const_iterator begin() const { return const_iterator(/* ... */); }
void erase(const void* pos)
{
// assume that pos points to node<T> to be erased
}
};
template <class C>
void test()
{
C cont;
const C& c_cont=cont;
typename C::iterator it=cont.begin();
const typename C::iterator cit=cont.begin();
typename C::const_iterator c_it=c_cont.begin();
const typename C::const_iterator cc_it=c_cont.begin();
cont.erase(it); // erase via iterator
cont.erase(cit); // erase via const iterator
cont.erase(c_it); // erase via const_iterator
cont.erase(cc_it); // erase via const const_iterator
if (it==cit && cit!=it) {} // compare as void pointers
if (it==c_it && c_it!=it) {}
if (it==cc_it && cc_it!=it) {}
if (cit==c_it && c_it!=cit) {}
if (cit==cc_it && cc_it!=cit) {}
if (c_it==cc_it && cc_it!=c_it) {}
}
int main()
{
test<new_vector<int> >();
test<new_list<int> >();
}
--
With all respect, Sergey. http://ders.angen.net/
mailto : ders at skeptik.net
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
 |
Andrew Koenig
Guest
|
| Posted: Wed Mar 01, 2006 5:06 pm Post subject: Re: Iterators must be convertible to [const] void* |
|
|
""Sergey P. Derevyago"" <non-existent (AT) iobox (DOT) com> wrote in message
news:4405C58F.C431099 (AT) iobox (DOT) com...
| Quote: | 1) Require every iterator and const_iterator to define operator void*()
const
and operator const void*() const respectively.
|
I don't see how this requirement can be implemented for types such as
std::istream_iterator<T> or std::reverse_iterator<T>. I also have no
trouble imagining iterators that meet the current requirements that would
not meet your proposed requirements.
In other words, your proposal would break existing code, both in the
standard library and in user-written programs. It's very hard to convince
anyone to consider such proposals seriously.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Sergey P. Derevyago
Guest
|
| Posted: Wed Mar 01, 2006 5:57 pm Post subject: Re: Iterators must be convertible to [const] void* |
|
|
Andrew Koenig wrote:
| Quote: | 1) Require every iterator and const_iterator to define operator void*()
const and operator const void*() const respectively.
I don't see how this requirement can be implemented for types such as
std::istream_iterator<T
There is no container with the container<T>::erase(istream_iterator<T |
position) member so the answer is obvious: The operator void*() conversion
shall be defined to support the istream_iterator requirements stated in
24.5.1. In particular, 24.5.1p3.
Also I mean only the "member iterators" in my requirement above (for which
the positioning responsibility is a must).
| Quote: | or std::reverse_iterator<T>.
IMHO the answer is obvious: it can delegate the calls to it's Iterator |
current member.
| Quote: | I also have no
trouble imagining iterators that meet the current requirements that would
not meet your proposed requirements.
Such as? |
--
With all respect, Sergey. http://ders.angen.net/
mailto : ders at skeptik.net
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Dave Steffen
Guest
|
| Posted: Wed Mar 01, 2006 9:18 pm Post subject: Re: Iterators must be convertible to [const] void* |
|
|
In addition to the other, and far better, responses, my $.02 ...
non-existent (AT) iobox (DOT) com ("Sergey P. Derevyago") writes:
[...]
| Quote: |
2. Proposed actions.
--------------------
1) Require every iterator and const_iterator to define operator void*() const
and operator const void*() const respectively.
|
Hmm. For those kinds of iterators for which such a thing would make
sense, what's wrong with
void* my_void_ptr = &*iter;
? You now have a void pointer pointing to what you wanted it to point
to. No language or library changes necessary. For the (presumably
rare) situations where you might need this, you've already got it.
| Quote: | 2) Redefine containers' member functions that require a position (such as
insert() and erase()) to use const void* position rather than iterator
position parameter.
|
Which throws type safety out the window. Also, how can a container
(e.g. a list) iterate over its elements if you give it a void pointer?
The whole point of iterators is that they (can) have more information
than a raw pointer, which is why they work so well.
----------------------------------------------------------------------
Dave Steffen, Ph.D. Nowlan's Theory: He who hesitates is not
Software Engineer IV only lost, but several miles from the
Numerica Corporation next freeway exit.
ph (970) 419-8343 x27
fax (970) 223-6797 The shortest distance between two points
dgsteffen (AT) numerica (DOT) us is under construction. -- Noelie Alito
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Guest
|
| Posted: Wed Mar 01, 2006 9:46 pm Post subject: Re: Iterators must be convertible to [const] void* |
|
|
Dave Steffen wrote:
| Quote: | Hmm. For those kinds of iterators for which such a thing would make
sense, what's wrong with
void* my_void_ptr = &*iter;
|
The trouble is that you can't apply this to an iterator returned by a
container's end() function (because you can't safely de-reference it).
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Bob Bell
Guest
|
| Posted: Wed Mar 01, 2006 9:55 pm Post subject: Re: Iterators must be convertible to [const] void* |
|
|
"Sergey P. Derevyago" wrote:
| Quote: | 1. The essence of the problem.
------------------------------
Iterators are underspecified. The standard in 24.1 [lib.iterator.requirements]
stands "Iterators are a generalization of pointers..." and "Since iterators
are an abstraction of pointers, their semantics is a generalization of most of
the semantics of pointers in C++.". But the following fundamental pointers'
property wasn't caught:
1) Every T* is convertible to void*.
2) Every const T* is convertible to const void*.
That is the common const void* type can be used to point to the elements (when
for example we need to erase an element from a non-const container using a
const_iterator).
|
It sounds like you're saying
-- iterators are supposed to behave like pointers
-- pointers are implicitly convertible to void* and const void*
-- therefore, iterators should be convertible to void* and const void*
What I don't get is why it matters.
Consider that I can reinterpret_cast a void* back to its original type,
as in:
int x;
void* p = &x;
int* xp = reinterpret_cast<int*>(p);
Following your logic, should we allow similar conversions from void*
back to iterator? How would you expect that to work? If you don't think
we should allow it, what criteria are you using to decide that iterator
--> void* is OK, but not void* --> iterator?
| Quote: | Also std::iterator has several responsibilities:
1) Point to elements.
2) Access elements to read/modify.
3) Move to next/prev element.
And const void* type is ideal for the first task.
|
Hardly; the element type is lost.
| Quote: | In particular, every
possible comparison works as expected.
|
But you can't dereference it, so what good is it?
[snip]
I don't see what problem you're trying to solve.
Bob
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Dave Steffen
Guest
|
| Posted: Wed Mar 01, 2006 11:06 pm Post subject: Re: Iterators must be convertible to [const] void* |
|
|
johnchx2 (AT) yahoo (DOT) com writes:
| Quote: | Dave Steffen wrote:
Hmm. For those kinds of iterators for which such a thing would make
sense, what's wrong with
void* my_void_ptr = &*iter;
The trouble is that you can't apply this to an iterator returned by a
container's end() function (because you can't safely de-reference it).
|
Oh, yeah... of course, that's yet another problem with the OP's
proposal. To what memory address does one-past-the-end void*'s point
to? I see at least one can of worms opening up. :-)
----------------------------------------------------------------------
Dave Steffen, Ph.D. Nowlan's Theory: He who hesitates is not
Software Engineer IV only lost, but several miles from the
Numerica Corporation next freeway exit.
ph (970) 419-8343 x27
fax (970) 223-6797 The shortest distance between two points
dgsteffen (AT) numerica (DOT) us is under construction. -- Noelie Alito
___________________
Numerica Disclaimer:
This message and any attachments are intended only for the individual
or entity to which the message is addressed. It is proprietary and
may contain privileged information. If you are neither the intended
recipient nor the agent responsible for delivering the message to the
intended recipient, you are hereby notified that any review,
retransmission, dissemination, or taking of any action in reliance
upon, the information in this communication is strictly prohibited,
and may be unlawful. If you feel you have received this communication
in error, please notify us immediately by returning this Email to the
sender and deleting it from your computer.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Bob Bell
Guest
|
| Posted: Thu Mar 02, 2006 3:35 am Post subject: Re: Iterators must be convertible to [const] void* |
|
|
Dave Steffen wrote:
| Quote: | 2) Redefine containers' member functions that require a position (such as
insert() and erase()) to use const void* position rather than iterator
position parameter.
Which throws type safety out the window.
|
Indeed.
std::list<int> lst;
lst.erase(0);
Bob
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Guest
|
| Posted: Thu Mar 02, 2006 3:35 am Post subject: Re: Iterators must be convertible to [const] void* |
|
|
"Sergey P. Derevyago" wrote:
| Quote: | 1. The essence of the problem.
------------------------------
Iterators are underspecified. The standard in 24.1 [lib.iterator.requirements]
stands "Iterators are a generalization of pointers..." and "Since iterators
are an abstraction of pointers, their semantics is a generalization of most of
the semantics of pointers in C++.". But the following fundamental pointers'
property wasn't caught:
1) Every T* is convertible to void*.
2) Every const T* is convertible to const void*.
|
I don't think it's desireable to catch those properties. Those are two
of the properties that make pointers very dangerous to use. One of the
key things about C++ that makes it better than C is increased
opportunities for type safety (which can, of course, be wasted if you
don't actually take advantage of them). Because of the existence of
templates, the need for void* is greatly reduced: instead of defining a
single function that takes a void* argument, you can template on T, and
define a function that takes a T* as an argument.
There is still a need for void* in C++, but almost all of the cases
where you might want to convert an interator 'i' to a void*, you can
instead convert "&*i" to a void*.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
John Nagle
Guest
|
| Posted: Thu Mar 02, 2006 4:06 am Post subject: Re: Iterators must be convertible to [const] void* |
|
|
johnchx2 (AT) yahoo (DOT) com wrote:
| Quote: | Dave Steffen wrote:
Hmm. For those kinds of iterators for which such a thing would make
sense, what's wrong with
void* my_void_ptr = &*iter;
The trouble is that you can't apply this to an iterator returned by a
container's end() function (because you can't safely de-reference it).
|
Right. "operator*()" for an iterator is entitled to report
an error in that situation, and there are checked implementations
that do so. Even in unchecked implementations, the value of
"end()" for lists and maps is likely to be something you can't
successfully dereference.
Why the enthusiasm for "void *"? I tend to think that if you
need "void *" in C++, you're doing something wrong.
John Nagle
Animats
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Sergey P. Derevyago
Guest
|
| Posted: Thu Mar 02, 2006 1:06 pm Post subject: Re: Iterators must be convertible to [const] void* |
|
|
Bob Bell wrote:
| Quote: | It sounds like you're saying
-- iterators are supposed to behave like pointers
-- pointers are implicitly convertible to void* and const void*
-- therefore, iterators should be convertible to void* and const void*
Yes, I am. |
| Quote: | What I don't get is why it matters.
Consider that I can reinterpret_cast a void* back to its original type,
I believe a static_cast should be used: please refer to 5.2.9p10. |
| Quote: | as in:
int x;
void* p = &x;
int* xp = reinterpret_cast<int*>(p);
Following your logic, should we allow similar conversions from void*
back to iterator?
No, we should not. |
1. Iterator can be converted to [const] void pointer. The value of the
pointer is implementation defined. In particular, the user shall not assume
that the pointer points to the T element.
2. The user is supposed to pass these pointers to the containers' member
functions that require a position (such us erase()).
3. The user is allowed to compare these pointers.
| Quote: | Also std::iterator has several responsibilities:
1) Point to elements.
2) Access elements to read/modify.
3) Move to next/prev element.
And const void* type is ideal for the first task.
Hardly; the element type is lost.
Yes, it is the advantage: we need a position and nothing more. |
| Quote: | I don't see what problem you're trying to solve.
There are several issues around. For example: |
179. Comparison of const_iterators to iterators doesn't work
180. Container member iterator arguments constness has unintended consequences
--
With all respect, Sergey. http://ders.angen.net/
mailto : ders at skeptik.net
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
John Nagle
Guest
|
| Posted: Thu Mar 02, 2006 3:29 pm Post subject: Re: Iterators must be convertible to [const] void* |
|
|
Sergey P. Derevyago wrote:
| Quote: | 1. The essence of the problem.
------------------------------
Iterators are underspecified. The standard in 24.1 [lib.iterator.requirements]
stands "Iterators are a generalization of pointers..." and "Since iterators
are an abstraction of pointers, their semantics is a generalization of most of
the semantics of pointers in C++.". But the following fundamental pointers'
property wasn't caught:
1) Every T* is convertible to void*.
2) Every const T* is convertible to const void*.
|
Iterators are not pointers. Iterators are, conceptually, opaque
handles from which collection elements can be reached.
An iterator is bound to a collection and an element of that
collection. There are debug implementations of iterators that
actually do have a link to the collection, for checking purposes.
One cannot assume that, underneath, an iterator is a pointer.
This is actually a good thing. Iterators have cleaner
semantics than pointers. Certain undesirable operations, like
incrementing an iterator equal to "end()", are
explicitly illegal for iterators, but are undefined
behavior for pointers.
John Nagle
Animats
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Guest
|
| Posted: Thu Mar 02, 2006 3:34 pm Post subject: Re: Iterators must be convertible to [const] void* |
|
|
"Sergey P. Derevyago" wrote:
| Quote: | Bob Bell wrote:
I don't see what problem you're trying to solve.
There are several issues around. For example:
179. Comparison of const_iterators to iterators doesn't work
180. Container member iterator arguments constness has unintended consequences
|
But in both of these cases, specific solutions have been proposed.
What's not clear is why introducing an implicit conversion to void*
would be better.
If the problem is that X::iterator and X::const_iterator can't be
compared, then make them comparable (proposed solution to 179, status
WP).
If the problem is that X::erase() (and the like) don't take
const_iterators, then change the signatures to accept const_iterators
(proposed solution to 180, status NAD-Future).
Is there a reason to prefer the void* approach to more specific
solutions tailored to solve specific problems?
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Sergey P. Derevyago
Guest
|
| Posted: Thu Mar 02, 2006 4:06 pm Post subject: Re: Iterators must be convertible to [const] void* |
|
|
Bob Bell wrote:
| Quote: | Which throws type safety out the window.
Indeed.
std::list<int> lst;
lst.erase(0);
Std::iterators are already unsafe (but fast). |
I don't propose to make unsafe something safe.
I propose to make convenient something inconvenient; the safety is almost
unaffected.
--
With all respect, Sergey. http://ders.angen.net/
mailto : ders at skeptik.net
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
Andrew Koenig
Guest
|
| Posted: Thu Mar 02, 2006 4:06 pm Post subject: Re: Iterators must be convertible to [const] void* |
|
|
""Sergey P. Derevyago"" <non-existent (AT) iobox (DOT) com> wrote in message
news:4406D8E6.97CB8B66 (AT) iobox (DOT) com...
| Quote: | 1. Iterator can be converted to [const] void pointer. The value of the
pointer is implementation defined. In particular, the user shall not
assume
that the pointer points to the T element.
2. The user is supposed to pass these pointers to the containers' member
functions that require a position (such us erase()).
3. The user is allowed to compare these pointers.
|
Here are examples of three kinds of iterators that I do not see how I can
cause to meet these requirements:
1) An iterator that refers to elements of an arithmetic sequence that is
computed on demand by dereferencing the iterator. We might name such an
iterator Range, and define two Range objects as equal if and only if they
represent the same sequence.
std::vector<int> v;
std::copy(Range(0, 10), Range(10, 10), std::back_inserter(v));
or even
std::vector<int> v(Range(0, 10), Range(10, 10));
Dereferencing a Range object yields a const int&.
In general, each Range object will need to contain two integers: The current
value (if any) and an indication of how many more values remain. There is
no reason to believe that this information can be stored in a single
pointer.
2) An iterator (template) that can be constructed from three objects: an
iterator pair and a third iterator. It is a forward iterator that yields
the sequence denoted by the first iterator pair, followed (if necessary) by
the sequence starting at the location denoted by the third iterator.
Provided that this iterator is only a forward iterator, it doesn't seem
particularly hard to implement. Each instance stores the three iterators
together with an indication of whether it has exhausted the sequence denoted
by the first two. That indication might be obtained by comparing the first
two iterators.
Again, I do not see how to crowd all of this information into a single
pointer.
3) An iterator that refers to an element of a container that is a
use-counted singly-linked list. Each container element is implemented as a
value, a pointer to the next element, and a reference count. The iterator's
copy constructor, assignment operator, and destructor manipulate the use
count of the element to which the iterator points.
This iterator *can* be represented as a single pointer. However, if you
convert such an iterator to a pointer, and then destroy the iterator, the
container element goes away--thus invalidating the pointer. I can see no
way to avoid either invalidating such pointers or creating memory leaks.
I am not sure about example (2) above, but (1) and (3) have been documented
for years, and I know someone who used a class along the lines of (3) in a
commercial project. I doubt he would be very happy to learn that a future
version of the C++ standard would remove the requirement that the
standard-library algorithms work with his iterators.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ] |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
