""Mirek Fidler"" <cxl@volny.cz> ...
>
> Is there anywhere in standard place that states that type pointed to by
> random access iterator must have copy-constructor ? That is if
>
> i
>
> is random access iterator and
>
> *i
>
> has type T then
>
> T x = *i;
>
> is defined ? I think there must be such place, but I cannot find it...


What about the following proof:

random access iterator is bidirectional is foreward.

bidi, table 75: *i--  ... convertible to T.
'convertible' is not really defined, but common agreement seems
to be that it means 'implicitely convertible' (4, par3):

=> "T a = *i--" is OK.

table 75 again, operational semantics of i--

=> "T a = *i" is OK.

Is this OK ?
Btw, this doesnt say anything about copy-constructor.

One problem with it: IIRC there are a lot of DR's around
iterators, so this part of table 75 might not be valid
when we need 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.jamesd.demon.co.uk/csc/faq.html                       ]

Is there anywhere in standard place that states that type pointed to by
random access iterator must have copy-constructor ? That is if

i

is random access iterator and

*i

has type T then

T x = *i;

is defined ? I think there must be such place, but I cannot find it...

Mirek


---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

Mirek> Is there anywhere in standard place that states that type pointed to by
Mirek> random access iterator must have copy-constructor ?

I can't think of any such requirement offhand.  Why do you think it
would be useful?

--
Andrew Koenig, ark@research.att.com, http://www.research.att.com/info/ark

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"Andrew Koenig" <ark@research.att.com> p   se v diskusn   m pr   spevku
news:yu99vfz9ifm1.fsf@europa.research.att.com...
> Mirek> Is there anywhere in standard place that states that type
pointed to by
> Mirek> random access iterator must have copy-constructor ?
>
> I can't think of any such requirement offhand.  Why do you think it
> would be useful?

   I was studying 'sort' implementation in several STL implementation
and it seems that each of them is using copy-constructor at some point
(BTW, it is avoidable, but not using copy contructor harms performance).
But so far I have not found requirement for copy-constructor - not in
iterator requirements, not in general algorithms requirements, not in
sort requirements. I think I must have overlooked it...

Mirek


---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

>I think I must have overlooked it...

I don''t think you have overlooked it. Don't look at types of iterator but
instead look at the containers that support such iterators: vector and
deque. Have a look at 23.1/3:

"The type of objects stored in these components must meet the requirements
of CopyConstructible
types (20.1.3), and the additional requirements of Assignable types."

Stephen Howe


---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

cxl@volny.cz ("Mirek Fidler") wrote in message news:<b3e5fh$1dl$1@news.vol.cz>...
> "Andrew Koenig" <ark@research.att.com> p   se v diskusn   m pr   spevku
> news:yu99vfz9ifm1.fsf@europa.research.att.com...
> > Mirek> Is there anywhere in standard place that states that type
>  pointed to by
> > Mirek> random access iterator must have copy-constructor ?
> >
> > I can't think of any such requirement offhand.  Why do you think it
> > would be useful?
>
>    I was studying 'sort' implementation in several STL implementation
> and it seems that each of them is using copy-constructor at some point
> (BTW, it is avoidable, but not using copy contructor harms performance).
> But so far I have not found requirement for copy-constructor - not in
> iterator requirements, not in general algorithms requirements, not in
> sort requirements. I think I must have overlooked it...
>
> Mirek
>
>

I believe that you are correct that this requirement does not appear
in either the iterator or algorithm requirements, however it does
appear in the Container Requirements of 23.1/3 which requires
contained objects to be both CopyConstructible and Assignable.
Perhaps this container requirement is carried through by implication
or assumption?

Randy.

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

Randy> I believe that you are correct that this requirement does not
Randy> appear in either the iterator or algorithm requirements,
Randy> however it does appear in the Container Requirements of 23.1/3
Randy> which requires contained objects to be both CopyConstructible
Randy> and Assignable.  Perhaps this container requirement is carried
Randy> through by implication or assumption?

Well, if you're going to sort a sequence, the elements of the sequence
had better be capable of being sorted -- which means that they had
better be capable of being compared and swapped.  That has nothing to
do with iterator requirements as such.

Similarly, if you're going to put elements into a container, it must
be possible to put them into the container, which means that they
must be capable of being copied and (at least for vectors) assigned.

But those are requirements on containers and algorithms, not on
iterators themselves.

--
Andrew Koenig, ark@research.att.com, http://www.research.att.com/info/ark

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

> >I think I must have overlooked it...
>
> I don''t think you have overlooked it. Don't look at types of iterator
but
> instead look at the containers that support such iterators: vector and
> deque. Have a look at 23.1/3:
>
> "The type of objects stored in these components must meet the
requirements
> of CopyConstructible
> types (20.1.3), and the additional requirements of Assignable types."

    Yes. But that implies that sort can be used only for std
containers - and this is not mentioned anywhere... (or, again, is
overlooked by me :)

Mirek


---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

Andrew Koenig <ark@research.att.com> wrote:
> But those are requirements on containers and algorithms, not on
> iterators themselves.

The only requirement stated for 'std::sort(It begin, It end)' is that 'It'
is a random access iterator. This is, however, clearly not the only
requirement imposed on the sequences. There are additional requirements
and you actually mentioned "swapable" but some implementation might decide
to use "assignable" and "copy constructible" instead. Note that "swapable"
and the combination of "assignable and "copy constructible" is not
equivalent and it might indeed be important since I can easily imagine
"swapable" types which are not "copy constructible".

The missing requirements should be added to the algorithm chapter. Well,
personally I think that the whole algorithm chapter needs a rather thorough
rework as I'm convinced that the algorithms are actually based on the wrong
abstraction: iterators are doing two things at once which should be split
into two separate abstractions, namely iterators and property maps. I want
to provide a corresponding proposal which, of course, retains the existing
interfaces soon but I won't be able to do so for the next meeting. This
proposal would also include explicit listing of all involved requirements.
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

Andrew Koenig <ark@research.att.com> wrote in message
news:<yu99znoknpqt.fsf@europa.research.att.com>...
> Randy> I believe that you are correct that this requirement does not
> Randy> appear in either the iterator or algorithm requirements,
> Randy> however it does appear in the Container Requirements of 23.1/3
> Randy> which requires contained objects to be both CopyConstructible
> Randy> and Assignable.  Perhaps this container requirement is carried
> Randy> through by implication or assumption?

> Well, if you're going to sort a sequence, the elements of the sequence
> had better be capable of being sorted -- which means that they had
> better be capable of being compared and swapped.  That has nothing to
> do with iterator requirements as such.

I think his real point is that while the standard defines very precisely
what it means by "being capable of being sorted", it doesn't really say
anything to the effect that swaping is necessary, or that std::swap will
be used.

What if I define an object which is not copiable nor assignable, but I
provide a specialization for std::swap?  Can I call std::sort on a
sequence of the object?  What if I do the opposite: I define the object
to be copiable and assignable, but specialize std::sort on it in a way
that makes it impossible to use?

The specification of std::swap says that an object must be Assignable,
but it doesn't mention CopyConstructable.  I suspect that this is a
defect.

Other algorithms (e.g. std::copy) don't say a thing.  Presumably, the
destination type of std::copy must be Assignable, but...  In the case of
std::copy, the last parameter is often an insertion iterator.  In which
case, the target type must be CopyConstructable, rather than Assignable.
In this case, the requirements do depend on the type of the iterator.
In the end, the actual requirement is that the expression "*iter = ..."
be legal and have the appropriate semantics.  I don't know how to
express that in standardese, however.

How far can the standard depend on common sense.  Given the semantics of
std::copy, it is rather obvious (to me, at least), that somewhere in the
function, the code must do a "*iter = ...".  Is it obvious enough that
we don't have to mention it in the standard?  And back to std::sort -- I
certainly don't think it obvious that std::sort must use std::swap.

> Similarly, if you're going to put elements into a container, it must
> be possible to put them into the container, which means that they must
> be capable of being copied and (at least for vectors) assigned.

> But those are requirements on containers and algorithms, not on
> iterators themselves.

True.  But the standard seems to lack some requirements for the
algorithms.  Some (like those I mention on copy) are obvious.  The
requirements of sort are less obvious.

--
James Kanze                           mailto:jkanze@caicheuvreux.com
Conseils en informatique orient   e objet/
                    Beratung in objektorientierter Datenverarbeitung

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"Andrew Koenig" <ark@research.att.com> p   se v diskusn   m pr   spevku
news:yu99znoknpqt.fsf@europa.research.att.com...
> Randy> I believe that you are correct that this requirement does not
> Randy> appear in either the iterator or algorithm requirements,
> Randy> however it does appear in the Container Requirements of 23.1/3
> Randy> which requires contained objects to be both CopyConstructible
> Randy> and Assignable.  Perhaps this container requirement is carried
> Randy> through by implication or assumption?
>
> Well, if you're going to sort a sequence, the elements of the sequence
> had better be capable of being sorted -- which means that they had
> better be capable of being compared and swapped.  That has nothing to
> do with iterator requirements as such.

    But being able to be swapped does not mean that they must have copy
constructor - swapping could be satisfied by swap or iter_swap too...
and in that case it is not that complicated to create 'sort' without
copy constructor.

    As for comparing, this requirement is present in standard.

> Similarly, if you're going to put elements into a container, it must
> be possible to put them into the container, which means that they
> must be capable of being copied and (at least for vectors) assigned.

    Again, above is described in standard.

    Problem here is whether potential implementer of 'sort' is allowed
to use copy-constructor or not. OTOH, there no mention about swap or
iter_swap too...

Mirek


---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]