Iterators must be convertible to [const] void*
Sergey P. Derevyago
------------------------------
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...@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Andrew Koenig
news:4405C58F...@iobox.com...
> 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.
Sergey P. Derevyago
> > 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>
>
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).
> or std::reverse_iterator<T>.
>
IMHO the answer is obvious: it can delegate the calls to it's Iterator
current member.
> 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
---
Dave Steffen
In addition to the other, and far better, responses, my $.02 ...
non-ex...@iobox.com ("Sergey P. Derevyago") writes:
[...]
>
> 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.
> 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
dgst...@numerica.us is under construction. -- Noelie Alito
john...@yahoo.com
> 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).
Bob Bell
> 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?
> 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.
> 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
Dave Steffen
> 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
dgst...@numerica.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.
John Nagle
> 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
kuy...@wizard.net
> 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*.
Bob Bell
> > 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
Sergey P. Derevyago
> 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,
>
I believe a static_cast should be used: please refer to 5.2.9p10.
> 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.
> > 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.
> 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
---
John Nagle
> 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
Ron House
> 1. The essence of the problem.
> ------------------------------
> Iterators are underspecified.
That's not a problem, that's your opinion of the reason why there's a
problem. What's the problem (that is, the programming task that is being
obstructed) for which the underspecification of iterators is the reason?
> 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*.
My first reaction: Very good! K&R C was so unsafe it wasn't funny.
Modern C++ has tried hard to provide us with high-level concepts that
are safely type-checked. And you say it's a 'problem' that one of the
most productive causes of errors isn't implemented?
> 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.
Okay, the ball's in your court. Write a version of *all* the STL
containers, providing void* as your pointer to element. Perhaps that's
possible, but for some I very much doubt the efficiency of the resulting
implementation. But you must do _all_, as you claim that iterators in
general are undespecified, so you must show the feasibility of a
solution for all iterators. Then, after you've done that, show us the
real _problem_ (see above) that you can solve in an efficient and
type-safe way with your new containers, that couldn't be solved as well
with the existing ones.
--
Ron House ho...@usq.edu.au
http://www.sci.usq.edu.au/staff/house
Ethics website: http://www.sci.usq.edu.au/staff/house/goodness
Sergey P. Derevyago
> Why the enthusiasm for "void *"? I tend to think that if you
> need "void *" in C++, you're doing something wrong.
>
If you are going to denote a position, a [const] void* pointer is the choice.
In particular, you aren't able to dereference (*ptr) or change (ptr++) the
position.
---
Sergey P. Derevyago
> > Which throws type safety out the window.
>
> Indeed.
>
> std::list<int> lst;
>
> lst.erase(0);
>
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
---
Sergey P. Derevyago
> 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.
>
---
Andrew Koenig
> 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.
john...@yahoo.com
> 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?
kuy...@wizard.net
> John Nagle wrote:
> > Why the enthusiasm for "void *"? I tend to think that if you
> > need "void *" in C++, you're doing something wrong.
> >
> Not, really.
> If you are going to denote a position, a [const] void* pointer is the choice.
It is "a" choice, it's not "the" choice, and it's not always (or even
usually) the right one. The position of an object of type T is best
indicated by a [const] T*, or more generally, by an iterator with a
value_type of [const] T. If you're trying to keep track of a position
without also keeping track of the type of the object occupying that
position, what you're doing is risky, and probably not the best
solution to the problem.
Sergey P. Derevyago
> > 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. If you have
- a container,
- a bound container::iterator
- and container::erase(container::iterator pos) member funtion
then the value of a [const] void pointer (an iterator object produces) is
obvious: it must help to container::erase() function to identify the element.
2. If you have
- a freestanding iterator
then the value of a [const] void pointer (an iterator object produces) is
obvious too: it must lead to the same comparison results the
operator==(iterator, iterator) produces currently.
--
With all respect, Sergey. http://ders.angen.net/
mailto : ders at skeptik.net
---
kuy...@wizard.net
> kuy...@wizard.net wrote:
> > 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.
> >
> No, you cannot: list::iterator converts to node<T>* rather than to T*.
I was suggesting a substitute for void*; I wouldn't expect that a
function for which a list::iterator was an intended valid input, to be
using 'void*' as the interface for recieving that input (unless, for
instance, you did indeed want to the function ot recieve a node<T>*).
For functions which might actually use list::iterator as a argument,
I'd recommend templating on an iterator type. There's still no
justification for the use of void* here.
Pete Becker
>
> Iterators are not pointers. Iterators are, conceptually, opaque
> handles from which collection elements can be reached.
To use the terminology from the language definition, iterators are
opaque handles from which elements of a sequence can be reached.
Sequences are the fundamental concept in the STL. Containers are one way
of managing sequences, but not the only way. This, of course, has
nothing to do with John's point, which is absolutely correct. But aside
from being non-standard, "collection" says something slightly different
from "sequence".
--
Pete Becker
Roundhouse Consulting, Ltd.
Sergey P. Derevyago
> > 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?
>
talking about.
---
Sergey P. Derevyago
> > If you are going to denote a position, a [const] void* pointer is the choice.
>
> It is "a" choice, it's not "the" choice, and it's not always (or even
> usually) the right one. The position of an object of type T is best
> indicated by a [const] T*,
>
---
kuy...@wizard.net
> kuy...@wizard.net wrote:
> > > If you are going to denote a position, a [const] void* pointer is the choice.
> >
> > It is "a" choice, it's not "the" choice, and it's not always (or even
> > usually) the right one. The position of an object of type T is best
> > indicated by a [const] T*,
> >
> I'm talking about a position in general.
That's convenient, since I was also.
If what you mean by "in general" isn't covered by the idea of
templating over T and using T*, or templating over an interator type,
then what you're talking about IS covered by my comments about it being
risky, and probably not a good idea.
The standard library functions that were inherited from C which use
void* interfaces are good examples of the risk, and in the context of
C++, they don't qualify as good ideas, either. They were good ideas in
C, and keeping them in C++ for backwards compatibility was a practical
necessity, but they aren't good ideas in the C++ context.
Even in C++, there are rare cases where void* makes sense, despite type
safety concerns. However, those cases can and should be well hidden
inside type-safe wrappers, not exposed where they can easily tempt
developers to misuse them. I don't see a need for mandating a
conversion to void* for iterators.
Andrew Koenig
>> Here are examples of three kinds of iterators that I do not see how I can
>> cause to meet these requirements:
> OK, the answers are obvious:
> 1. If you have
> - a container,
> - a bound container::iterator
> - and container::erase(container::iterator pos) member funtion
> then the value of a [const] void pointer (an iterator object produces) is
> obvious: it must help to container::erase() function to identify the
> element.
> 2. If you have
> - a freestanding iterator
> then the value of a [const] void pointer (an iterator object produces) is
> obvious too: it must lead to the same comparison results the
> operator==(iterator, iterator) produces currently.
I am sorry, but these statements make no sense to me.
I gave you three concrete examples; your "obvious" answers do not appear to
me to address any of the aspects of the concrete examples that I gave.
In general terms, these aspects are:
1) An iterator with instances that include two or more other iterators,
together with information about which of those iterators is active at the
moment.
2) An iterator that does not represent an element of a sequence at all,
but contains information from which the value of each element can be
computed. This information is too large to fit in a single pointer.
3) An iterator with a destructor that affects allocation of other
resources.
Each of these examples shows why it might be desirable to be able to include
more information in an iterator than is capable of fitting in a single
pointer.
Andrew Koenig
>> Is there a reason to prefer the void* approach to more specific
>> solutions tailored to solve specific problems?
> The proposed solutions are unnatural as compared to the approach we're
> talking about.
Often when people talk about a solution to a problem as being "unnatural,"
they really mean that they don't like the solution but don't want to explain
why.
john...@yahoo.com
> If you are going to denote a position, a [const] void* pointer is the choice.
If by "position" you mean the address of a byte in memory, then this
makes sense. But I'm not sure the same thing follows if "position"
means "a point in an arbitrary sequence," which is what an iterator
denotes. Not all iterators iterate over a range of bytes in memory.
(Consider, e.g. std::vector<bool>::iterator.)
One thing that isn't clear to me about the proposal is whether it is
intended to apply to all iterators (i.e. an amendment to 24.1) or just
to the interator types provided by the standard containers (i.e. an
amendment to 23.1).
Bob Bell
> john...@yahoo.com wrote:
> > > 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?
> >
> The proposed solutions are unnatural as compared to the approach we're
> talking about.
OK, I really don't get this at all. How can converting iterators to
void*s (with all the accompanying problems this brings up, like the
type safety problems mentioned elsewhere) be more natural than
solutions that address the problems directly. How is comparing
iterators to const_iterators unnatural? How is allowing erase to take
a const_iterator unnatural?
Bob
kuy...@wizard.net
.
> 1. If you have
> - a container,
> - a bound container::iterator
> - and container::erase(container::iterator pos) member funtion
> then the value of a [const] void pointer (an iterator object produces) is
> obvious: it must help to container::erase() function to identify the element.
That needs explaining - why is any help needed to identify the element?
The value of 'pos' already does so, perfectly. It does it better, in
fact, than a void* would, because it does so in a type-safe manner.
> 2. If you have
> - a freestanding iterator
> then the value of a [const] void pointer (an iterator object produces) is
> obvious too: it must lead to the same comparison results the
> operator==(iterator, iterator) produces currently.
But, as you point out, operator--(iterator, iterator) already handles
this. Why is anything more needed?
Markus Moll
Sergey P. Derevyago wrote:
[about conversion iterator --> void* being unsafe]
> 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.
I don't think so.
What about:
std::vector<int> v(10, 42);
std::string str = "Hello World";
v.erase(str.begin());
This would obviously fail to compile right now, but it would happily compile
with your conversion to void*.
Even in
std::vector<int> v(10, 42);
std::vector<int> w(42, 10);
v.erase(w.begin());
it's allowed that the iterators carry information about which container they
are bound to, so a runtime check is possible.
With the conversion to void*, you lose that.
Markus
Sergey P. Derevyago
> Not all iterators iterate over a range of bytes in memory.
> (Consider, e.g. std::vector<bool>::iterator.)
>
It seems like std::vector<bool> template specialization is broken beyond all
repair.
> One thing that isn't clear to me about the proposal is whether it is
> intended to apply to all iterators (i.e. an amendment to 24.1) or just
> to the interator types provided by the standard containers (i.e. an
> amendment to 23.1).
>
1. Every iterator can use the conversion to get all the required == and !=
operators for free.
2. The containers use an additional benefit: the position in the members like
erase().
--
With all respect, Sergey. http://ders.angen.net/
mailto : ders at skeptik.net
---
Sergey P. Derevyago
> That needs explaining - why is any help needed to identify the element?
> The value of 'pos' already does so, perfectly.
>
Please refer to the issue: 180. Container member iterator arguments constness
has unintended consequences.
---
Sergey P. Derevyago
> I am sorry, but these statements make no sense to me.
>
iterators implement right now. I think it will be possible to return a pointer
that leads to the same (or more natural in some sense) comparison results.
> Each of these examples shows why it might be desirable to be able to include
> more information in an iterator than is capable of fitting in a single
> pointer.
>
The point taken, thanks.
--
With all respect, Sergey. http://ders.angen.net/
mailto : ders at skeptik.net
---
Sergey P. Derevyago
> > The proposed solutions are unnatural as compared to the approach we're
> > talking about.
>
> OK, I really don't get this at all. How can converting iterators to
> void*s (with all the accompanying problems this brings up, like the
> type safety problems mentioned elsewhere) be more natural than
> solutions that address the problems directly.
>
operators like:
const_iterator::const_iterator(const iterator&);
bool operator==(const const_iterator&, const const_iterator&);
bool operator==(const iterator&, const iterator&);
--
With all respect, Sergey. http://ders.angen.net/
mailto : ders at skeptik.net
---
Sergey P. Derevyago
> What about:
>
> std::vector<int> v(10, 42);
> std::string str = "Hello World";
> v.erase(str.begin());
>
> This would obviously fail to compile right now, but it would happily compile
> with your conversion to void*.
>
benefits.
In particular, we are used to thoughtfully check which iterators we are
passing to which containers right now -- they can be invalidated, at least.
---
Sergey P. Derevyago
> Often when people talk about a solution to a problem as being "unnatural,"
> they really mean that they don't like the solution but don't want to explain
> why.
>
iterator erase(const void* pos);
member is better than two:
iterator erase(iterator pos);
const_iterator erase(const_iterator pos);
2. The conversion returns pointers so the comparison operators are already
defined.
--
With all respect, Sergey. http://ders.angen.net/
mailto : ders at skeptik.net
---
Matti Rintala
> 2. The conversion returns pointers so the comparison operators are already
> defined.
That is one aspect of your void* iterators that I don't understand. As you
said, pointer comparison is already defined with pointers. The comparison
compares memory addresses.
How can you achieve correct < etc. comparisons with void* (for deque, for
example)? The comparison of iterators is based on their position in the
container, and that doesn't have anything to do with memory addresses of
contained items. I know that for vector the pointer comparison works (vector
guarantees continuous memory), but that's not the case in general.
--
------------- Matti Rintala ------------ matti....@tut.fi ------------
Painting is the art of inclusion. Photography is an art of exclusion.
Sergey P. Derevyago
> How can you achieve correct < etc. comparisons with void* (for deque, for
> example)?
>
operator< and the like (as opposed to the operator== family) requires special
attention and must be implemented using the iterator parameters.
> The comparison of iterators is based on their position in the
> container, and that doesn't have anything to do with memory addresses of
> contained items. I know that for vector the pointer comparison works (vector
> guarantees continuous memory), but that's not the case in general.
--
With all respect, Sergey. http://ders.angen.net/
mailto : ders at skeptik.net
---
Andrew Koenig
> Andrew Koenig wrote:
>> Often when people talk about a solution to a problem as being
>> "unnatural,"
>> they really mean that they don't like the solution but don't want to
>> explain
>> why.
> 1. Single
> iterator erase(const void* pos);
> member is better than two:
> iterator erase(iterator pos);
> const_iterator erase(const_iterator pos);
If you can convert an iterator to a const_iterator, you don't need the
overload.
> 2. The conversion returns pointers so the comparison operators are already
> defined.
You mean you want to impose the additional requirement that whenever two
iterators convert to unequal pointers, they must compare unequal? You've
just made your job that much harder.
David Abrahams
> I gave you three concrete examples; your "obvious" answers do not appear to
> me to address any of the aspects of the concrete examples that I gave.
>
> In general terms, these aspects are:
>
> 1) An iterator with instances that include two or more other iterators,
> together with information about which of those iterators is active at the
> moment.
See boost::zip_iterator. You don't even need the 2nd half of that
sentence; they're all active.
> 2) An iterator that does not represent an element of a sequence at all,
> but contains information from which the value of each element can be
> computed. This information is too large to fit in a single pointer.
See boost::transform_iterator.
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
Andrew Koenig
> OK, let's put it another way: Please show me the operator== these bizarre
> iterators implement right now. I think it will be possible to return a
> pointer
> that leads to the same (or more natural in some sense) comparison results.
I don't want to overwhelm the newsgroup with code, so I'll just sketch out
one of them.
I'm going to define an "arithmetic sequence iterator" as a class that acts
like an input iterator over a sequence of integer values. Because these
values represent an arithmetic sequcnce, they are evenly spaced. Each
iterator therefore needs to store three values:
1) The number of elements remaining in the sequence;
2) The next element in the sequence, if any;
3) The distance between adjacent elements.
The number of elements remaining is an unsigned long; the other two
quantities are signed long. So the class looks something like this:
class ASIter {
private:
unsigned long count;
long next;
long dist;
public:
// ...
};
The property of being an arithmetic sequence suggests that unary * should be
implemented something like this:
if (this->count == 0)
throw <<an appropriate exception>>;
return *this->next;
and (prefix) ++ should be implemented something like this:
if (this->count == 0)
throw <<an appropriate exception>>;
--this->count;
this->next += this->dist;
I said that two iterators should be considered equal if and only if they
represent the same sequence. That happens in one of three cases:
1) The sequences are both empty;
2) The sequences both have exactly one element and the element's value
is the same;
3) The sequences are the same length and their "next" and "dist"
elements are also the same.
So == might be implemented this way:
bool operator==(const ASIter& i, const ASIter& j) {
if (i.count != j.count)
return false;
switch (i.count) {
default:
if (i.dist != j.dist)
return false;
// no break
case 1:
if (i.next != j.next)
return false;
// no break
case 0:
return true;
}
}
or, less cleverly, this way:
bool operator==(const ASIter& i, const ASIter& j) {
if (i.count != j.count)
return false;
if (i.count == 0)
return true;
if (i.count == 1)
return i.next == j.next;
return i.next == j.next && i.dist == j.dist;
}
Anyway, you should get the idea. So how do you propose to convert an ASIter
to a pointer?
kuy...@wizard.net
> kuy...@wizard.net wrote:
> > That needs explaining - why is any help needed to identify the element?
> > The value of 'pos' already does so, perfectly.
> >
> No, it doesn't.
> Please refer to the issue: 180. Container member iterator arguments constness
> has unintended consequences.
I'm afraid I don't see the relevance of that issue. 'pos' still
contains all the information needed to identify the element. The
difference between iterator and const_iterator is normally a matter
only of const qualification (though it's legal for them to be unrelated
types); the actual information content is the same. In order to perform
the various actions required of iterators, it must include sufficient
information to uniquely identfy the location currently pointed at by
the iterator.
Since the designer of the container knows the implementation of it's
iterators, writing the erase() function so it can extract that
information in the form needed by erase() is no special challenge, and
I don't see how requiring that there be a conversion to void* makes
that already unchallenging job any less challenging.
For the standard containers, and for user-defined container types that
emulate the design of the standard containers, the container designer
will be relying upon the Allocator<node> member functions to implement
erase() (where "node" represents a type that might be T itself, or it
might be a structure containing or referring to T). Those member
functions all upon Alloctor<node> typedefs for their arguments; they
have no need or even any use for void* arguments.
Richard Smith
> Andrew Koenig wrote:
> > I am sorry, but these statements make no sense to me.
> >
> OK, let's put it another way: Please show me the operator== these bizarre
> iterators implement right now. I think it will be possible to return a pointer
> that leads to the same (or more natural in some sense) comparison results.
Perhaps a different example would help. I sometimes write code to do
graph theoretic calculations. I'm usually interested in very large
regular graphs -- i.e. ones where many properties can be computed on
demand. This means that my "vertex" class is just a wrapper around a
large integer which simply labels that vertex. Unfortunately, when I
say "very large" graphs, I really do mean very large -- sometimes as
many as 16! vertices [! is factorial] -- a 45 bit number. I generally
work on a 32-bit platform and so use a custom fixed_width_int class
that can handle larger numbers (often via a compiler extension such as
long long or __int64_t),
How does this relate to iterators? One thing I often need is a way of
iterating over all the vertices in a graph, and for this purpose I have
writen an iterator class. This is effectively just a counter over the
range [0,n!). How can I possibly convert an iterator that points to,
say, 20922789888000 (= 16!) different sequence elements to a void*
pointer which, on my platform, can only hold 4294967296 (= 2^32)
different values? It simply can't be done.
--
Richard Smith
Sergey P. Derevyago
> Anyway, you should get the idea. So how do you propose to convert an ASIter
> to a pointer?
>
1. I propose to convert iterators to [const] void pointers because any
element (the iterator points to) occupies some unique memory area.
2. You ask me: What can we do if the iterator doesn't point to the elements
in memory but calculates the elements on demand?
3. The answer is obvious: The conversion has no value for such kind of
iterators.
4. Now the question is: Does it make sense to define the conversion for the
iterators that point to unique memory locations? Does it make sense to
explicitly define this special iterator category?
--
With all respect, Sergey. http://ders.angen.net/
mailto : ders at skeptik.net
---
Andrei Polushin
> 1. Single
> iterator erase(const void* pos);
> member is better than two:
> iterator erase(iterator pos);
> const_iterator erase(const_iterator pos);
The proposed solution for #180 is to change one single method
iterator erase(iterator p);
to another single method:
iterator erase(const_iterator p);
thus the problem was solved already, taking into account that
X::iterator must be convertible to X::const_iterator.
> 2. The conversion returns pointers so the comparison operators are already
> defined.
There is no need to define (unnatural) conversion to void*, once you
can define an operator==() as a member of your X::const_iterator - thus
solving the #179 issue completely.
On the other hand, if you want iterators to behave like C/C++ pointers,
requiring them to define a conversion to (void*) is inappropriate.
Instead, you should define the third entity, more abstract than the
const_iterator, to 'indicate a position', such as
position_indicator:
class X {
public:
struct position_indicator { // just like (const void*)
operator==();
operator!=();
};
struct const_iterator : position_indicator {
const_reference operator*();
};
struct iterator : const_iterator {
reference operator*();
};
// and modifiers will look like:
iterator erase(position_indicator i);
iterator insert(position_indicator i, value_type v);
};
but note that
1. A position_indicator cannot be replaced by (const void*) in all
possible implementations, but only in those that can perform a lossless
conversion from const_iterator to const_pointer (see Andrew Koenig
examples).
2. There is no need to introduce such an over-abstraction, because the
responsibility to 'indicate a position' is equally admitted by
const_iterator.
3. However, it can be introduced for cases where the non-deferenceable
iterator is currently returned, such as for return value of X::end(),
but such change will break most STL algorithms.
--
With best regards,
Andrei Polushin
David Abrahams
> Andrew Koenig wrote:
>> Anyway, you should get the idea. So how do you propose to convert an ASIter
>> to a pointer?
>>
> OK, got it!
>
> 1. I propose to convert iterators to [const] void pointers because any
> element (the iterator points to) occupies some unique memory area.
> 2. You ask me: What can we do if the iterator doesn't point to the elements
> in memory but calculates the elements on demand?
> 3. The answer is obvious: The conversion has no value for such kind of
> iterators.
> 4. Now the question is: Does it make sense to define the conversion for the
> iterators that point to unique memory locations? Does it make sense to
> explicitly define this special iterator category?
It's already defined: they're known as forward iterators, and you can
get the pointer you want by writing &*p. But those pointers can't be
compared to give you the ordering you want (consider std::deque's
iterators). One other problem is that you can't do &*p when p is a
past-the-end iterator.
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
---
Bob Bell
> Bob Bell wrote:
> > > The proposed solutions are unnatural as compared to the approach we're
> > > talking about.
> >
> > OK, I really don't get this at all. How can converting iterators to
> > void*s (with all the accompanying problems this brings up, like the
> > type safety problems mentioned elsewhere) be more natural than
> > solutions that address the problems directly.
> >
> At least, you don't have to define all the set of required conversions and
> operators like:
>
> const_iterator::const_iterator(const iterator&);
> bool operator==(const const_iterator&, const const_iterator&);
> bool operator==(const iterator&, const iterator&);
This doesn't argue that converting to void* is "more natural." In fact
would argue that defining the conversions and operators is a natural
solution because it is a direct expression of the solution. Contrast
this with the "convert-to-void*" approach that doesn't address the
problem directly, and as a consequence introduces a ton of undesirable
side-effects.
Bob
Andrew Koenig
news:uacc29...@boost-consulting.com...
> non-ex...@iobox.com ("Sergey P. Derevyago") writes:
>> 4. Now the question is: Does it make sense to define the conversion for
>> the
>> iterators that point to unique memory locations? Does it make sense to
>> explicitly define this special iterator category?
> It's already defined: they're known as forward iterators, and you can
> get the pointer you want by writing &*p. But those pointers can't be
> compared to give you the ordering you want (consider std::deque's
> iterators). One other problem is that you can't do &*p when p is a
> past-the-end iterator.
Also, when you evaluate and save &*p and then destroy p, there is no
guarantee that the pointer you are holding is still valid--which I think is
a guarantee that the OP wants.
Michiel...@tomtom.com
Dave Steffen wrote:
> In addition to the other, and far better, responses, my $.02 ...> [...]
> >
> > 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;
Consider that Sergey wants to have this operator for every iterator. An
Input
Iterator doesn't have to return an lvalue. std::vector<bool>::iterator
is also
going to be fun.
HTH,
Michiel Salters
Dave Steffen
> Dave Steffen wrote:
> > In addition to the other, and far better, responses, my $.02 ...
> >
> > non-ex...@iobox.com ("Sergey P. Derevyago") writes:
> >
> > [...]
> > >
> > > 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;
>
> Consider that Sergey wants to have this operator for every
> iterator. An Input Iterator doesn't have to return an
> lvalue. std::vector<bool>::iterator is also going to be fun.
I've forgotten the context of my original post, but IIRC that's why I
added "iterators for which such a thing would make sense".
I think my point was that, for iterators for which one might like a
void* conversion, it's easy to do that yourself. For iterators where
void* conversion doesn't make sense (e.g. input iterators), you
wouldn't want one anyway. (And of course vector<bool> is broken in
many ways, at least as far as "standard container"-ish-ness is
concerned. :-) )
IIRC the original poster never presented a convincing argument for
what he was suggesting (which was, IIRC, something like having
iterators act like void*s, or be interchangeable with them, or some
such). I thought his notion indicated a lack of understanding of what
iterators are, how they work, and what they're for. Removing the type
information from an iterator seems crazy to me, but if he really needs
do to it, he already can.
I may be wrong about my recollections, though. Corrections are
welcome.
----------------------------------------------------------------------
Dave Steffen, Ph.D. Fools ignore complexity.
Software Engineer IV Pragmatists suffer it.
Numerica Corporation Some can avoid it.
ph (970) 419-8343 x27 Geniuses remove it.
fax (970) 223-6797 -- Alan Perlis
dgsteffen at numerica dot us
Sergey P. Derevyago
> IIRC the original poster never presented a convincing argument for
> what he was suggesting (which was, IIRC, something like having
> iterators act like void*s, or be interchangeable with them, or some
> such).
>
1. Some iterators are used to point to in-memory elements.
2. Some container operations need only a position of an element/node to
perform the action. For example, container::erase(pos).
3. It was proposed to use the [const] void* conversion to return a position.
The original message is:
http://groups.google.com/group/comp.std.c++/msg/923710443bd99f0f
And the following message explains why the "in-memory" is a key:
http://groups.google.com/group/comp.std.c++/msg/cbed1f06d92469a4
--
With all respect, Sergey. http://ders.angen.net/
mailto : ders at skeptik.net
---
Dave Steffen
> Dave Steffen wrote:
> > IIRC the original poster never presented a convincing argument for
> > what he was suggesting (which was, IIRC, something like having
> > iterators act like void*s, or be interchangeable with them, or some
> > such).
> >
> I believe, I explained the point several times:
>
> 1. Some iterators are used to point to in-memory elements.
> 2. Some container operations need only a position of an element/node to
> perform the action. For example, container::erase(pos).
> 3. It was proposed to use the [const] void* conversion to return a position.
Well, yes; let me ammend my previous comment:
"IMHO the original poster presented a description of what he wanted,
but never presented a convincing (IMHO) reason for why he wanted it,
nor a convincing reason why he couldn't get what he wanted using
existing language constructs."
That is to say: yes, I think I understand what you want. I don't
understand why you want it.
IMHO using raw memory pointers gives you nothing an iterator gives
you; and lacks things an iterator has, such as type information and
possible "smart" operations (e.g. a set iterator knows how to find
the next element, whereas a void* into a set does not). Raw memory
pointers provide only a subset of the functionality of iterators
while giving no additional capabilities.
So I don't really see the point.
This may be rehashing an old thread that is better left dead, so feel
free to ignore. :-)
----------------------------------------------------------------------
Dave Steffen, Ph.D. Fools ignore complexity.
Software Engineer IV Pragmatists suffer it.
Numerica Corporation Some can avoid it.
ph (970) 419-8343 x27 Geniuses remove it.
fax (970) 223-6797 -- Alan Perlis
dgsteffen at numerica dot us
---
Andrei Polushin
> IMHO using raw memory pointers gives you nothing an iterator gives
> you;
No, it gives the _absence_ of the things the iterator has.
> and lacks things an iterator has, such as type information and
> possible "smart" operations (e.g. a set iterator knows how to find
> the next element, whereas a void* into a set does not). Raw memory
> pointers provide only a subset of the functionality of iterators
> while giving no additional capabilities.
And those capabilities are not required to indicate position.
Consider a pointer hierarchy (arrow means `convertible to'):
(const void*) <---- (void*)
^ ^
| |
| |
(const char*) <---- (char*)
And now an iterator hierarchy proposed by Sergey:
(const void*) <------------\
^ |
| |
| |
(const_iterator) (iterator)
That looks like crazy, primarily because it lacks for type safety, so
I propose:
(position) <--------------\
^ |
| |
| |
(const_iterator) (iterator)
(see http://groups.google.com/group/comp.std.c++/msg/92e513bee0df6705)
The reason is that a `position type' is to indicate a position, which
could be compared to another position, but neither advanced nor
dereferenced.
> So I don't really see the point.
I see the following:
* Comparison operators are the properties of position, so they should
be defined for position, as it is more abstract than the iterator.
* insert() and erase() methods require a position, not the iterator.
Current library has the difficulties to accept const_iterator here.
* The iterator returned by end() could not be dereferenced - it might
be a position, for the best static safety (currently run-time
assertions are used here).
* Some algorithms could be restricted in their use of InputIterator,
where the position is actually required:
template<class InputIterator, class Position, class Type>
InputIterator find(InputIterator first,
Position last,
const Type& val);
* istream_iterator has the default constructor, which initializes it as
the end-of-stream position, not the iterator.
All those problems could be a sort of inconsistency for lack of
`position' concept.
--
Andrei Polushin
Sergey P. Derevyago
> The reason is that a `position type' is to indicate a position,
>
be used as vector<T>::iterator-s?
I use void* as the root because any T* is automatically convertible to void*.
> which could be compared to another position, but neither advanced
> nor dereferenced.
>
Void* is a natural solution and it can neither be advanced nor dereferenced.
--
With all respect, Sergey. http://ders.angen.net/
mailto : ders at skeptik.net
---
Dave Steffen
> Dave Steffen writes:
> > IMHO using raw memory pointers gives you nothing an iterator gives
> > you;
>
> No, it gives the _absence_ of the things the iterator has.
Well, OK, yes. I don't understand why that's a good thing, but
let's go on....
> > and lacks things an iterator has, such as type information and
> > possible "smart" operations (e.g. a set iterator knows how to find
> > the next element, whereas a void* into a set does not). Raw
> > memory pointers provide only a subset of the functionality of
> > iterators while giving no additional capabilities.
>
> And those capabilities are not required to indicate position.
>
> Consider a pointer hierarchy (arrow means `convertible to'):
>
> (const void*) <---- (void*)
> ^ ^
> | |
> (const char*) <---- (char*)
Yes, and those conversions are implicit (is char* -> void* implicit?
I never do such things, so I don't know off the top of my head).
>
> And now an iterator hierarchy proposed by Sergey:
>
> (const void*) <------------\
> ^ |
> | |
> (const_iterator) (iterator)
These conversions exist today, but explicitly; you have to do the
moral equivalent of a cast to make the conversions ( void* p =
&*iter ). So, one question I have is why the implicit conversion is
valuable; I haven't heard (or missed, or didn't understand) a good
argument for that.
> That looks like crazy, primarily because it lacks for type safety, so
> I propose:
>
> (position) <--------------\
> ^ |
> | |
> | |
> (const_iterator) (iterator)
>
>
> (see http://groups.google.com/group/comp.std.c++/msg/92e513bee0df6705)
>
> The reason is that a `position type' is to indicate a position, which
> could be compared to another position, but neither advanced nor
> dereferenced.
OK. Why not iterator -> position, const iterator -> const position?
I.E. why is const-ness not important for positions?
And by the way, I now presume you're not arguing in favor of
Sergey's proposal, but for a related proposal of your own that lets
iterators be implicitly convertible to "position" objects.
[...]
> I see the following:
>
> * Comparison operators are the properties of position, so they should
> be defined for position, as it is more abstract than the iterator.
Uhh... you mean, comparisons of where objects are in a container?
What about containers for which such a thing doesn't exist
(e.g. non-standard but STL-conformand hashes, or the upcoming
unordered_sets).
But yes, I agree that there is (or could be) a notion of a
'position' that is more abstract than an iterator. Onward...
> * insert() and erase() methods require a position, not the iterator.
> Current library has the difficulties to accept const_iterator here.
I agree with the first sentence. Iterators have more stuff in 'em
than is needed for some container operations. The second is true,
but that's not fundamental to the notion of 'iterator', it's a fact
(quirk?) of the curent standard, or maybe implementations of the
standard.
That iterators aren't implicitly convertible to const_iterators (or,
alternately, that some operations that _could_ take const_iterators
have not been overloaded to do so) is not a good reason to introduce
implicit conversions to void* (or, if you prefer, 'positions'), it's
a good reason to revisit some aspects of the STL. :-)
> * The iterator returned by end() could not be dereferenced - it might
> be a position, for the best static safety (currently run-time
> assertions are used here).
Uhh... why do you want to deref end()? How would a position
representing one-past-the-end be any safer? You've lost me here.
> * Some algorithms could be restricted in their use of InputIterator,
> where the position is actually required:
>
> template<class InputIterator, class Position, class Type>
> InputIterator find(InputIterator first,
> Position last,
> const Type& val);
OKaaay... IIRC input iterators are more than positions for
fundamental reasons; the function you've got here is reading from a
stream of some description, yes? Don't know that you can, in
general, iterate through positions in a stream without reading from it?
> * istream_iterator has the default constructor, which initializes it as
> the end-of-stream position, not the iterator.
I'm missing something here, what's the problem?
> All those problems could be a sort of inconsistency for lack of
> `position' concept.
I'm not sure I buy your examples, but I'll buy that the notion of a
'position' as separate from 'iterator' is logically correct;
iterators represent 'position' plus some other stuff. I'm not sure
I understand that last statement; the only inconsistency I see here
is that iterators aren't implicitly convertible to const_iterators,
while nonconst pointers _are_ implicitly convertible to const
pointers; and that's a separate problem.
I'm not at all sure I understand what, from a practical point of
view, either your proposal (or the original) gains anybody.
And I _really_ don't buy that void* is a good candidate for being a
'position'. I'm not sure that void*'s have any buisiness being used
for much of _anything_ in C++ except low-level code and (sometimes)
binary I/O.
Can you give me any concrete examples - I.E. code - that demonstrate
what you're buying?
----------------------------------------------------------------------
Dave Steffen, Ph.D. Fools ignore complexity.
Software Engineer IV Pragmatists suffer it.
Numerica Corporation Some can avoid it.
ph (970) 419-8343 x27 Geniuses remove it.
fax (970) 223-6797 -- Alan Perlis
dgsteffen at numerica dot us
---
Dave Steffen
> Andrei Polushin wrote:
> > The reason is that a `position type' is to indicate a position,
> >
> OK, is your struct position_indicator approach prevents plain T* pointers to
> be used as vector<T>::iterator-s?
> I use void* as the root because any T* is automatically convertible to void*.
>
> > which could be compared to another position, but neither advanced
> > nor dereferenced.
> >
> Void* is a natural solution and it can neither be advanced nor dereferenced.
Andrei is propsing some sort of 'position' concept, which is more
fundamental than iterators; one might think of iterators classes of
publicly deriving from position classes, or some such. I agree with
him from a logical standpoint - yes, the notion of position is more
fundamental than that of iterator - but I don't see what, from a
practical language point of view, you gain by it, aside from a
mechanism to treat iterators and const_iterators identically under
circumstances that warrant it.
I still don't understand why you want what you want. I don't
understand why it's bad to have type information. If you want a
fundamental 'position' sort of thing, OK, we can talk about that, it
might be useful. If you want to use void*s to represent positions
_because it's the best we can do right now_, OK, we can talk about
better ways to do that. None of this is (IMHO) a _language design_
issue, or even a _language standard_ issue.
The (possible) imperfections in our standard iterators are both a
language design and language standard issue, and on-topic for this
NG; but it seems to me that you're pushing for a solution that
"throws the baby out with the bathwater" and takes us back to the
bad-old C days with un-typed memory and null-pointer errors. :-)
What am I missing?
----------------------------------------------------------------------
Dave Steffen, Ph.D. Fools ignore complexity.
Software Engineer IV Pragmatists suffer it.
Numerica Corporation Some can avoid it.
ph (970) 419-8343 x27 Geniuses remove it.
fax (970) 223-6797 -- Alan Perlis
dgsteffen at numerica dot us
---
Andrei Polushin
> OK, is your struct position_indicator approach prevents plain T* pointers to
> be used as vector<T>::iterator-s?
Well, you can (carefully) use `const void*' as a `position' type for
those rare containers, which iterators are plain pointers.
> I use void* as the root because any T* is automatically convertible to void*.
But your actual proposal is neither limited to plain-pointer-iterators,
nor it limited to specific kind of plain-memory-containers.
You propose it for /any/ iterator, but /not every/ iterator is a
pointer, and /not every/ iterator is replaceable by pointer.
--
Andrei Polushin
David Abrahams
> OK. Why not iterator -> position, const iterator -> const position?
> I.E. why is const-ness not important for positions?
The biggest problem that iterators have comes from binding positioning
and access, such as writability. Once you add constness to the mix,
you don't have a pure position anymore, and you're back to the same
old problems.
See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1873.html
and http://www.boost.org/libs/iterator/doc/new-iter-concepts.html for
details.
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
---
Andrei Polushin
> "Andrei Polushin" <polu...@gmail.com> writes:
>> I propose:
>>
>> (position) <--------------\
>> ^ |
>> | |
>> | |
>> (const_iterator) (iterator)
>
> I.E. why is const-ness not important for positions?
The constness could be unimportant if the position is not
dereferencable. There are reasons I see for const_position, but I will
not advocate it right now.
> And by the way, I now presume you're not arguing in favor of
> Sergey's proposal, but for a related proposal of your own that lets
> iterators be implicitly convertible to "position" objects.
What am I trying is to make some constructive remarks, to extract a
rational substance from his proposal.
>> * Comparison operators are the properties of position, so they should
>> be defined for position, as it is more abstract than the iterator.
>
> Uhh... you mean, comparisons of where objects are in a container?
> What about containers for which such a thing doesn't exist
> (e.g. non-standard but STL-conformand hashes, or the upcoming
> unordered_sets).
If there is an iterator, there is a position. Recall the
unordered_set::erase that takes a position parameter, overloaded for
iterator and const_iterator, but not for local_iterator and
const_local_iterator.
I mean the issue #179 (pointed by Sergey in this thread)
"Comparison of const_iterators to iterators doesn't work"
<http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#179>,
its proposed resolution is to explicitly specify the common
operations, but not to specify the common entity for iterator types.
As a consequence, why not to have an issue like "Comparison of
iterators to reverse_iterators doesn't work"? :) Why not to have them
all comparable, as in the example:
set<int> s;
const set<int>& const_s = s;
// C++98: may not compile, see issue #179
s.begin() == const_s.begin();
// C++98: often compiles, see issue #179
const_s.begin() == s.begin();
// C++98: cannot compare reverse_iterator to const_reverse_iterator
// C++0x: compiles
s.rbegin() == const_s.rbegin();
// C++98: cannot compare iterator to reverse_iterator
// C++0x: not even considered yet
s.begin() == s.rend();
>> * insert() and erase() methods require a position, not the iterator.
>> Current library has the difficulties to accept const_iterator here.
>
> I agree with the first sentence. Iterators have more stuff in 'em
> than is needed for some container operations. The second is true,
> but that's not fundamental to the notion of 'iterator', it's a fact
> (quirk?) of the curent standard, or maybe implementations of the
> standard.
>
> That iterators aren't implicitly convertible to const_iterators (or,
> alternately, that some operations that _could_ take const_iterators
> have not been overloaded to do so) is not a good reason to introduce
> implicit conversions to void* (or, if you prefer, 'positions'), it's
> a good reason to revisit some aspects of the STL. :-)
Introducing `position' is just one of the possible revisions.
>> * The iterator returned by end() could not be dereferenced - it might
>> be a position, for the best static safety (currently run-time
>> assertions are used here).
>
> Uhh... why do you want to deref end()? How would a position
> representing one-past-the-end be any safer? You've lost me here.
>
>> * Some algorithms could be restricted in their use of InputIterator,
>> where the position is actually required:
>>
>> template<class InputIterator, class Position, class Type>
>> InputIterator find(InputIterator first,
>> Position last,
>> const Type& val);
>
> OKaaay... IIRC input iterators are more than positions for
> fundamental reasons; the function you've got here is reading from a
> stream of some description, yes? Don't know that you can, in
> general, iterate through positions in a stream without reading from it?
>
>> * istream_iterator has the default constructor, which initializes it as
>> the end-of-stream position, not the iterator.
>
> I'm missing something here, what's the problem?
>
> [snip]
>
> Can you give me any concrete examples - I.E. code - that demonstrate
> what you're buying?
The example for all of the above:
// a classical template, intentionally written with mistake,
// causes a run-time failure.
template<class InIt, class T>
InIt std::find(InIt first, InIt last, const T& val) {
for (; first != last; ++first) {
if (*last == val) { // `first' should be here
break;
}
}
return first;
}
// the same template code with `position',
// but it causes a compile-time error.
template<class InIt, class Position class T>
InIt nonstd_find(InIt first, Position last, const T& val) {
for (; first != last; ++first) {
if (*last == val) { // error: cannot dereference `last'
break;
}
}
return first;
}
void test1() {
std::istream_iterator<int> isit(std::cin);
std::istream_iterator<int> isend; // end-of stream `iterator'
isit = std::find(isit, isend, 22); // BAD: run-time failure
std::istream_position<int> posend; // end-of stream `position'
isit = nonstd_find(isit, posend, 22); // GOOD: compile failure
}
void test2() {
set<int>& s;
set<int>::iterator it;
set<int>::position itend = s.end(); // end-of-set `iterator'
it = std::find(s.begin(), itend, 22); // BAD: run-time failure
set<int>::position posend = s.end(); // end-of-set `position'
it = nonstd_find(it, posend, 22); // GOOD: compile failure
set<int>::reverse_iterator rit;
rit = s.find(23); // BAD: cannot convert
for ( ; rit != s.rend(); ++rit) { // but I need reverse_iterator
s.erase(rit); // BAD: cannot convert from reverse_iterator
}
}
This code can contain typos.
--
Andrei Polushin
Sergey P. Derevyago
> These conversions exist today, but explicitly; you have to do the
> moral equivalent of a cast to make the conversions ( void* p =
> &*iter ).
>
&*iter gives you T* rather than container<T>::iterator. For example,
list<T>::iterator points to a list node rather than to a list element.
---
Sergey P. Derevyago
> You propose it for /any/ iterator,
>
I propose it for iterators that point to in-memory elements only. For
example, input iterators that calculate the values on demand don't need to be
position indicators in this sense.
---