Christopher Eltschka wrote in message
<36AD903C.CCDFBDDA@physik.tu-muenchen.de>...
>..
>What about replacing it with the requirement that pointers
>and references must remain valid? This would make sense, since
>pointers and references - unlike iterators - refer to the
>objects themselves, independant of any container. That is,
>if the pointers/references remain valid but the iterators get
>invalid, it's obvious that the objects remain the same, but only
>belong to the other container.


No, I don't think that is a good idea.

Notwithstanding the fact that pointers and references would not suffer from
the same implementation woes as iterators, and, being built-in types, could
not assert on an invalid use anyway, they nevertheless become invalid after
a pointer-twiddling swap.

The definition of 'valid' that you are using for pointers and references is
that they are merely dereferencable i.e. they point to *some* value and will
not core dump when used. I still assert, however, that they become invalid
*with repect to the semantics of swap* after a pointer-swapping swap. The
semantics of "swap" is that it swaps values, and by implication, it swaps
the values of all elements of a container
e.g. for valarray

valarray<double> v1(1.0, 1);
valarray<double> v2(2.0, 1);
double& d1 = v1[0];
double& d2 = v2[0];

swap(v1, v2);

The semantics of swap *requires* that after the swap d1 == 2.0 and d2 ==
1.0- it is the very definition of swapping values- and this in fact holds
for valarray. For vector<> it does not hold, and so the values of d1 and d2
must be said to be invalidated by the swap- the fact that they are
guaranteed to point at *some* value is irrelevant as it is the wrong value.

,Brian Parker
(bparker@uq.net.au)




[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Siemel Naran wrote in message ...
>...
>One problem here is that we've complicated the definition of
>our range checked iterator.  It has been harder to write.
>It's sizeof has also increased.  But it does allow swap(...)
>to comply with 23.1/10.

Yes, Christopher Eltschka suggested a similar fix, but such convolutions
really are a travesty- before 23.1/10 was introduced one could write a debug
iterator without rewriting the whole container class.


>...
>Anyway, I think it is safer to change 23.1/10 to say that
>swap(...) may invalidate iterators.  The most fundamental
>reason for this is that it will discourage people to
>depend on the fact iterators into a container remain
>intact after a swap, and this should lead to code that is
>more maintainable.  Because, conceptually speaking,
>"swap(v1,v2)" swaps 'v1' and 'v2', 'i1' and 'i2',
>'p1' and 'p2', etc.  So it is strange to see that 'i1'
>is used as if it weren't swapped.


Yes, this is precisely my point (although I think that, even conceptually,
swap(v1, v2) *only* swaps v1 & v2, *not* any extant iterators). The main
user-visible semantic effect of 23.1/10 is that it *prohibits* an
implementation from asserting on such use of iterators after a swap, when,
in fact, one would almost always *want* an assertion. After a swap, either
the iterators should be validly pointing at the same containers (which can
occur with a full-copying swap of equally-sized containers) or they should
be invalidated and any use should assert. Writing functions that rely upon
some swap's (full-copying swaps) leaving the iterators validly pointing at
the *same*  container, and other swap's (23.1/10 style pointer swapping)
leaving iterators validly pointing at *different* containers is an
invitation to disaster and should be treated as a bug, not sanctioned as a
feature.

One minor point, 23.1/10 should not say that swap *may* invalidate pointers
for the standard containers, but rather that it will always invalidate them,
as the original intent of 23.1/10 (as far as I can divine) was to indicate
that the standard containers *must* use a pointer-copying swap which is
necessary for exception-safe implementations of the container functions.
Probably a paragraph explicitly stating this should be added to the
standard.

,Brian Parker
(bparker@uq.net.au)




[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Brian Parker wrote in message <78hu84$jpv$1@bunyip.cc.uq.edu.au>...

>vector<int> v1(10, 1);
>vector<int> v2(10, 2);
>
>vector<int>::iterator it1 = v1.begin() + 1;
>
>insert_iterator<vector<int> > it2(v1, it1);
>
>swap(v1, v2);


Good point.  Even with indirection it is tough to get constant-time swap
which leaves it2 in any kind of reasonable "valid" state (note that it2.c is
protected, not private).  Of course insert_iterator is an iterator_adaptor,
not an iterator.  On the other hand insert_iterator "conforms to the
requirements for an output iterator," so maybe it is an iterator?

I'd like to hear a clarification.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <slrn7ajpqv.vpd.sbnaran@localhost.localdomain>,
  sbnaran@uiuc.edu wrote:
>
> On 22 Jan 1999 23:15:58 GMT, Brian Parker <bparker@uq.net.au> wrote:
>
> >Another problem with this definition of valid is that it effectively rules
> >out, as far as I can see, using range-checked iterators in a debug build for
> >vector<>- such iterators hold a pointer to the original container and would
> >incorrectly assert on the supposedly valid use of iterators that now point
> >to a different container after a swap.
>
> No, I don't think range checked iterators should be a problem.  Eg,
>
> class vector<T>::iterator
> {
>    private:
>       vector<T> * vec;
>       T * ptr;
>       iterator(vector<T>* vec, T * ptr);
>    public:
>       T& operator*() const;
>       iterator& operator++();
>       iterator& operator++(int);
> };
>
> Suppose main(...) looks like this:
>
>    std::vector<int> v1(1), v2(0);
>    v1[0]=10;
>    std::vector<int>::iterator i1=v1.begin(), i2=v2.begin();
>    cout << *i1 << '\n'; // prints "10"
>    //cout << *i2 << '\n'; // gives range error
>    std::swap(v1,v2);
>    cout << *i1 << '\n'; // prints "10"
>    //cout << *i2 << '\n'; // gives range error
>
> Before the swap, 'i1' points to the number "10" in the vector 'v1',
> which is the vector with one element.
>
> After the swap, 'i1' still points to the number "10" in the same
> vector -- that is, the vector with one element -- but this vector
> is now called 'v2'.
>
> Swapping 'v1' and 'v2' has the effect of swapping 'i1' and 'i2',
> except that while the names 'v1' and 'v2' are swapped, the names
> 'i1' and 'i2' are not swapped.

But note that the address of object v1 has not changed, even though
it now holds all the elements that were previously called v2. And
note that iterator i1 contains a pointer to the vector v1. After the
swap, the pointer must be updated with v2's address. How would you
accomplish this?

One way to accomplish this is to have a linked list with every valid
iterator for a given vector. Swapping the vectors requires walking
the list to update the pointer values. But this is no longer linear
time!

Another way would be to change vector to an "interface" class.
Recall that such classes contain only one data element, which is
the address of a vector_Impl class object that does all the "real"
work. Most of vector's member functions are simply in-line
"forward" functions which call the corresponding vector_Impl member
function to do the "real" work. a.swap(b) is one of the few
exceptions; it performs swap(p_impl,b.p_impl); to exchange the
pointers to the low-level data.

If the iterator contained a pointer to the "real" low-level class
rather than to the "interface" class, it would not be affected by
calls to swap(). This method should work, however the cost is that
every member function call to vector() is at least a tiny bit
slower, as we dispatch to the "real" low-level class.

----
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <36AB666E.353AAADC@wizard.net>,
  James Kuyper <kuyper@wizard.net> wrote:
> Siemel Naran wrote:
> ....
> > In general, "swap" does invalidate iterators.  Suppose you have
> > a fixed size array class
> >    template <class T, size_t N> class fvector { T d_data[N]; ... };
> > Suppose you figured out a way to swap a fvector<int,7> with a
> > fvector<int,8>.  The swap will have to swap raw bytes as there
> > is no pointer field to swap.  But this means that an iterator
> > pointing to an element in the fvector<int,8> may be invalidated
> > after the swap.  So now the first interpreation of "invalid
> > iterator" comes into play.
>
> It was considerations like this that led me to realize that a
> fixed-sized array class couldn't meet the Standard's container
> requirements - rather annoying.

Were there other considerations as well?

I would guess that a fixed-size array class could meet the
standard's container requirements -- but it couldn't be
swapped with any other container type.

----
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Francis Glassborow wrote in message ...
>...
>While I have no problem with your choice of 1, I do not think it is what
>the Standard uses.  I wonder if the Standard actually clarifies this
>anywhere?  If not a DR might help settle the problem, even if we do not
>like the answer.

I think that everywhere else except 23.1/10 the standard only talks in terms
of valid iterators *to* a particular container e.g. see 23.1.1/3 and the
interface to insert(iterator, T).

(of course one could make the circular argument that 23.1/10 can't be a bug
as the standard talks about iterators being valid independently of
containers in 23.1/10 :-) )

This extended meaning of "valid" used by 23.1/10 could be closed by
rewording it to say that after a swap extant iterators are now validly
pointing *to the other container*, but, as I've discussed elsewhere I think
that this is exactly the wrong thing to do as it would remove the ability to
assert on what is almost certainly a bug (or at least very subtle code.)

23.1/10 and friends were, AFAIK, added to indicate that on a swap only
pointers are swapped and no copying of container elements is done for
exception safety reasons (i.e. swap is then guaranteed not to throw an
exception), and not to encourage the use of iterators after the swap.

I think that a DR should change 23.1/10 to  (1) explicitly state that no
element-copying is done on swap and (2) all extant iterators, references and
pointers are *invalidated* after the swap.

Thanks for your comments,
Brian Parker
(bparker@uq.net.au)
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

AllanW@my-dejanews.com wrote:
>
> In article <36AB666E.353AAADC@wizard.net>,
>   James Kuyper <kuyper@wizard.net> wrote:
....
> > It was considerations like this that led me to realize that a
> > fixed-sized array class couldn't meet the Standard's container
> > requirements - rather annoying.
>
> Were there other considerations as well?
>
> I would guess that a fixed-size array class could meet the
> standard's container requirements -- but it couldn't be
> swapped with any other container type.

After using the default ctor, or calling the empty() member, the
container requirements say that size() must return 0. By a fixed-size
array class, I mean a
 template <class T, size_t N> class array;

such that size() would always return N. I could have a flag which is set
only by the default ctor and empty(), and have size() return 0 if that
flag is set. That seems a waste of space (particularly for array<T,2>,
which would typically get 50% bigger as a result).

My fixed-size array<T,N> class is intended to produce compile-time
validity checks based upon N, for N typically 2, 3 or 4. Making it meet
the container requirements is a very low priority. Space and time
efficiency are both far more imporant. All I need to use most of the
relevant standard algoriths is to have array<T,N>::iterator meet the
iterator requirements, which is trivial. It has ctors corresponding to
each of the required sequence ctors, but with one less argument, since
the size is already known.


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <78j0tf$1h1$1@bunyip.cc.uq.edu.au>,
  "Brian Parker" <bparker@uq.net.au> wrote:
> One minor point, 23.1/10 should not say that swap *may* invalidate pointers
> for the standard containers, but rather that it will always invalidate them,
> as the original intent of 23.1/10 (as far as I can divine) was to indicate
> that the standard containers *must* use a pointer-copying swap which is
> necessary for exception-safe implementations of the container functions.
> Probably a paragraph explicitly stating this should be added to the
> standard.

The two statements would mean the same thing.

Stating that swap *MAY* invalidate the pointer means that using
the iterator's value introduces undefined behavior. It might
happen to refer to a real element, but even if it does there is
no way of knowing *which* element.

Stating that swap *MUST* invalidate the pointer could only have
two meanings. It might mean the same thing: Even though the
iterator still exists, you can't use it in any predictable way.
Or, it might mean that the swap() function must do something to
each and every iterator, perhaps set an "invalid" flag. Since
doing this would be at least as difficult as somehow making all
of the iterators continue to be valid, I doubt that this is what
you had in mind.

----
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

AllanW@my-dejanews.com wrote in message <78l5ms$an7$1@nnrp1.dejanews.com>...
>...
>The two statements would mean the same thing.

>...

Yes, that's true. Thanks.

,Brian Parker
(bparker@uq.net.au)



[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Siemel Naran wrote:

[...]

> No, I agree with Brian.  The paragraph should be polished up.  The
> problem is the word "invalid".  This is a word with lots of
> connotations.  To some, an "invalid iterator" is an iterator that
> does not point to an object.  To others, an "invalid iterator" is
> an iterator that points to an object, but conceptually the wrong
> object.  The second interpretation is the correct one, and it
> surely allows for a very efficient implementation of swap for
> non-reference counted vectors -- just swap the internal
> pointer-to-array and size and reserve fields.  But the first
> interpretation is reasonable too, and a clearer choice of words,
> phrases, and sentences would have been better.

What about replacing it with the requirement that pointers
and references must remain valid? This would make sense, since
pointers and references - unlike iterators - refer to the
objects themselves, independant of any container. That is,
if the pointers/references remain valid but the iterators get
invalid, it's obvious that the objects remain the same, but only
belong to the other container.

[...]
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 25 Jan 99 02:31:21 GMT, Francis Glassborow
>Siemel Naran

>>To some, an "invalid iterator" is an iterator that
>>does not point to an object.  To others, an "invalid iterator" is
>>an iterator that points to an object, but conceptually the wrong
>>object.  The second interpretation is the correct one, and it
>>surely allows for a very efficient implementation of swap for
>>non-reference counted vectors -- just swap the internal
>>pointer-to-array and size and reserve fields.

>Let me be stupid again:)  On what do you base your assertion that the
>second interpretation is correct.  As this is comp.std.c++ perhaps you
>could reference the Standard for this claim and save the rest of us
>having to find it (if it is there)

The expression "swap(v1,v2)" swaps the vectors 'v1' and 'v2'.
Conceptually, it also swaps all the iterators 'i1' and 'i2'.
Practically, it can't swap all the iterators as this would
lead to a very inefficient implementation.  That's why I say
that the iterator points to an object, but conceptually this
is the wrong object.  My thinking holds iterators as strongly
coupled to the container they iterate on because it makes
more sense to think this way.  But implementations hold
iterators as decoupled to the container they iterate on.  I'm
not really sure what point of view the standard takes.
The quote in 23.1.10 suggests that iterators and containers
are decoupled, but it doesn't say whether this is conceptually
correct or not.

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Brian Parker wrote:
>
> Francis Glassborow wrote in message ...
> >
> >I think that we must look at what it means to be a 'valid iterator'.
> >There seem to be two types and a special case:
> >
> >dereferencable iterators, i.e. does an attempt to dereference them
> >provide anything other than undefined behaviour?
> >
> >one-past-the end iterators, cannot be dereferenced  but accessing the
> >iterator without attempting to dereference is OK
> >
> >The NULL pointer
> >
> >What the swap requirements state is that if an iterator was valid before
> >it will be valid afterwards.  To be valid it has to be one of the three
> >above and swapping containers by swapping the pointers rather than the
> >contents would seem to maintain that guarantee.
>
> I disagree. I think that the issue of dereferencability is orthogonal to the
> issue of validity we are discussing.
>
> There are two concepts of what an iterator is-
> (1) that they are iterators into a *particular* container.
> (2) they are iterators into raw memory completely divorced from the
> container that originally owned that memory.
>
> (1) is my view of what an iterator is, and, I believe, what the original STL
> intended. In this case, if I retrieve an iterator into a container, then any
> other iterator to that same element of that container should give the same
> lvalue, and, if not, one of the iterators has been invalidated.
> i.e in
>
> vector<int> v(10, 1);
> vector<int>::iterator iter = v.begin();
>
> iter is an iterator to the first element *of v*, and IMO, as long as it
> remains valid, one should be able to rely on the fact that any other
> iterator to the first element points to the same value i.e. *v.begin() ==
> *iter always (which is not the case after a swap).
>
> The view of iterators (2) that the standard mandates in 23.1/10 is not a
> useful extension to the concept of iterators, and in fact lowers their level
> of abstraction to little more than raw memory pointers- a major advantage of
> using the higher level abstraction of iterators is that one can implement
> run-time checks for validity, and such an advantage is diluted by the
> standard's mandating of such a flexible definition of "valid" (and code that
> relied upon this "extension"  would be quite obscure, depending as it would
> on the vagaries of a particular implementation of swap).

Range checking would still be possible:

The vector can hold not only the elements, but also its
"management data" (i.e. size etc.) via pointer. Then, the
iterator would have a pointer to the data element and a
pointer to the vector info block, but no pointer to the vector
itself (which doesn't have anything but a pointer to the info
block anyway). A vector swap would then just exchange the
two info block pointers; the iterators would not note anything,
since they have their own info block pointers.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <78dvvi$t9l$1@bunyip.cc.uq.edu.au>, Brian Parker
<bparker@uq.net.au> writes
>There are two concepts of what an iterator is-
>(1) that they are iterators into a *particular* container.
>(2) they are iterators into raw memory completely divorced from the
>container that originally owned that memory.
>
>(1) is my view of what an iterator is, and, I believe, what the original STL
>intended. In this case, if I retrieve an iterator into a container, then any
>other iterator to that same element of that container should give the same
>lvalue, and, if not, one of the iterators has been invalidated.
>i.e in
>
>vector<int> v(10, 1);
>vector<int>::iterator iter = v.begin();
>
>iter is an iterator to the first element *of v*, and IMO, as long as it
>remains valid, one should be able to rely on the fact that any other
>iterator to the first element points to the same value i.e. *v.begin() ==
>*iter always (which is not the case after a swap).

While I have no problem with your choice of 1, I do not think it is what
the Standard uses.  I wonder if the Standard actually clarifies this
anywhere?  If not a DR might help settle the problem, even if we do not
like the answer.


Francis Glassborow      Chair of Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 24 Jan 1999 17:02:43 GMT, Brian Parker <bparker@uq.net.au> wrote:
>Siemel Naran wrote in message ...

>>No, I don't think range checked iterators should be a problem.  Eg,

>Hang on, you haven't actually implemented the assertion checks- if you do so
>you will find that the checked iterator asserts on the use of *either*
>iterator after swapping (see following code sample). This is as it should
>be, IMO, as an iterator is an iterator on a particular container and when
>swap assigns a memory block to another container then it can no longer be
>viewed as a valid iterator into the original container. Unfortunately, this
>iterator (if implemented as vector::iterator) is not standard-conforming as
>a user is guaranteed by 23.1/10 that they can use the iterator after the
>swap- a guarantee of dubious benefit in my opinion.

OK, I compiled your example, and I see now that there is a problem.
Let me summarize my understanding.  The iterator 'i1' points to an
element in 'v1' and contains a reference to 'v1'.  The expression
"swap(v1,v2)" swaps 'v1' and 'v2'.  Now the iterator 'i1' points
to the same element of the old 'v1' but contains a reference to
'v2'.

>struct safe_iter
>{
> safe_iter(int* p_in, const vector<int>& c_in) :p(p_in), c(&c_in) {}
>
> int& operator*() const {
>  assert(c->begin() <= p && p < c->end());
>  return *p;
> }
>
> int* p;
> const vector<int>* c;
>};

This means that "swap(v1,v2)" does invalidate iterators into 'v1'
and 'v2'.  There is one way to make "swap(v1,v2)" not invalidate
iterators into 'v1' and 'v2'.  Give your class safe_iter pointers
not to the vector, but rather to the implementation of the
vector.  Eg,

struct safe_iter
{
 safe_iter(int* p_, const vector<int>& v)
    : p(p_), begin(v.begin()), end(v.end()) { }

 int& operator*() const {
  assert(begin<= p && p<end);
  return *p;
 }

 int * p;
 int const *const begin;
 int const *const end  ;
};


Now "swap(v1,v2)" leaves 'i1' pointing to the element of the
original 'v1', and leaves the vector in 'i1' pointing to the
original 'v1'.

One problem here is that we've complicated the definition of
our range checked iterator.  It has been harder to write.
It's sizeof has also increased.  But it does allow swap(...)
to comply with 23.1/10.

A second problem is that in general we might not be able to
store pointers to the internal representation, because the
internal representation might be totally private.  In this
case, we would have to store a pointer/reference to the
container and then employ the container's public member
functions to do the range checking.  But I don't think any
of the standard containers suffer this problem.

Anyway, I think it is safer to change 23.1/10 to say that
swap(...) may invalidate iterators.  The most fundamental
reason for this is that it will discourage people to
depend on the fact iterators into a container remain
intact after a swap, and this should lead to code that is
more maintainable.  Because, conceptually speaking,
"swap(v1,v2)" swaps 'v1' and 'v2', 'i1' and 'i2',
'p1' and 'p2', etc.  So it is strange to see that 'i1'
is used as if it weren't swapped.


--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper <kuyper@wizard.net> writes:

> Francis Glassborow wrote:
> ....
> > No, according to my reading a 'full copying' swap is now allowed
> > because, except in a limited number of special cases, it will invalidate
> > some iterators (such as at least one of the one-past-the-end iterators)
>
> Table 65: _Container Requirements_ indicates that swap() must be have
> constant-time complexity. That would appear to rule out full-copying
> swap() implementations.

Not quite: the precise words are "Those entries marked `(Note A)'
should have constant complexity."

The words "should" and "must" are related, but they are not the same.
In standardese (which is not quite the same as English), "should" is a
magic word that is used for what's known as normative encouragement.
Roughly, it means that an implementation ought to have this property
unless there is some good reason for it not to.  This is specified in
the ISO style guide, which gives English and French phrases for
normative encouragement.



[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

>Francis Glassborow wrote:
>....
>> No, according to my reading a 'full copying' swap is now allowed
                                                        ^^^
One of the most hated of typos that reverses the intended meaning, for
'now' read 'not'


>> because, except in a limited number of special cases, it will invalidate
>> some iterators (such as at least one of the one-past-the-end iterators)
Francis Glassborow      Chair of Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Christopher Eltschka wrote in message
<36AC4B7E.4D263019@physik.tu-muenchen.de>...
>...
>Range checking would still be possible:
>
>The vector can hold not only the elements, but also its
>"management data" (i.e. size etc.) via pointer. Then, the
>iterator would have a pointer to the data element and a
>pointer to the vector info block, but no pointer to the vector
>itself (which doesn't have anything but a pointer to the info
>block anyway). A vector swap would then just exchange the
>two info block pointers; the iterators would not note anything,
>since they have their own info block pointers.


Hmmm... yes, I suppose an extra level of indirection can solve any problem
but the main point is, why are such convolutions necessary just to allow the
use of iterators after a swap, rather than simply allowing an implementation
to invalidate the iterators? Can anyone give some example code where this
capability is actually useful and safe, such that one would prefer *not* to
assert? I see no advantage, and only disadvantages to the extra capability
Sec. 23.1 /10 grants.

It is not just checked iterators, but any iterator implementation that
maintains a back-pointer that would need such convolutions to be standard
conforming e.g.

vector<int> v1(10, 1);
vector<int> v2(10, 2);

vector<int>::iterator it1 = v1.begin() + 1;

insert_iterator<vector<int> > it2(v1, it1);

swap(v1, v2);

// it1 is still "valid" according to Sec 23.1 /10  and v1 certainly is, so
it2 must still be.
*it2 = 2;    // v1 will need to maintain a register of current iterators so
this can work correctly after a swap

In fact, this example can be simplified to

vector<int> v1(10, 1);
vector<int> v2(10, 2);

vector<int>::iterator it1 = v1.begin() + 1;
// it1 is a valid iterator into v1

swap(v1, v2);
// it1 remains "valid" (into v1 or v2?? Sec 23.1 /10  doesn't say.)

v1.insert(it1, 2);    // it1 is "valid" so this should work, but it doesn't

An implementation of vector::iterator that stores a integer index and a
pointer to the container to index is another example of an implementation
that was standard-conforming before Sec 23.1 /10 was added, but is not now.

It is still my opinion that Sec 23.1 /10  was never intended to allow the
use of iterators after a swap but was apparently added to indicate that the
implementation does a pointer swap rather than a full copying swap (which,
BTW, it doesn't do anyway- an implementation of swap that did a full copying
swap when the two vectors were the same size would also leave all iterators
valid- truly valid by my definition- and so would fulfill Sec 23.1 /10 )

At the very least Sec 23.1 /10 should state that after a swap, iterators are
now valid iterators into the *other* container, which would have the dubious
"benefit" of not allowing an implementation to assert on what would almost
certainly be a bug in any normal code.

,Brian Parker
(bparker@uq.net.au)




[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 25 Jan 1999 17:15:20 GMT, Siemel Naran

Need to fix a typo.

>OK, I compiled your example, and I see now that there is a problem.
>Let me summarize my understanding.  The iterator 'i1' points to an
>element in 'v1' and contains a reference to 'v1'.  The expression
>"swap(v1,v2)" swaps 'v1' and 'v2'.  Now the iterator 'i1' points
>to the same element of the old 'v1' but contains a reference to
>'v2'.
 ^^^^

Change the last line to

>the old 'v2'

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 22 Jan 1999 23:15:58 GMT, Brian Parker <bparker@uq.net.au> wrote:

>Another problem with this definition of valid is that it effectively rules
>out, as far as I can see, using range-checked iterators in a debug build for
>vector<>- such iterators hold a pointer to the original container and would
>incorrectly assert on the supposedly valid use of iterators that now point
>to a different container after a swap.

No, I don't think range checked iterators should be a problem.  Eg,

class vector<T>::iterator
{
   private:
      vector<T> * vec;
      T * ptr;
      iterator(vector<T>* vec, T * ptr);
   public:
      T& operator*() const;
      iterator& operator++();
      iterator& operator++(int);
};

Suppose main(...) looks like this:

   std::vector<int> v1(1), v2(0);
   v1[0]=10;
   std::vector<int>::iterator i1=v1.begin(), i2=v2.begin();
   cout << *i1 << '\n'; // prints "10"
   //cout << *i2 << '\n'; // gives range error
   std::swap(v1,v2);
   cout << *i1 << '\n'; // prints "10"
   //cout << *i2 << '\n'; // gives range error

Before the swap, 'i1' points to the number "10" in the vector 'v1',
which is the vector with one element.

After the swap, 'i1' still points to the number "10" in the same
vector -- that is, the vector with one element -- but this vector
is now called 'v2'.

Swapping 'v1' and 'v2' has the effect of swapping 'i1' and 'i2',
except that while the names 'v1' and 'v2' are swapped, the names
'i1' and 'i2' are not swapped.

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <78aack$3cj$1@nnrp1.dejanews.com>, AllanW@my-dejanews.com
writes
>If swapping whole containers, perhaps it makes sense to say that
>the iterators are still valid, although they point into the
>other container. After all, that is the only way that they could
>possibly still have a meaningful value.

I think that we must look at what it means to be a 'valid iterator'.
There seem to be two types and a special case:

dereferencable iterators, i.e. does an attempt to dereference them
provide anything other than undefined behaviour?

one-past-the end iterators, cannot be dereferenced  but accessing the
iterator without attempting to dereference is OK

The NULL pointer

What the swap requirements state is that if an iterator was valid before
it will be valid afterwards.  To be valid it has to be one of the three
above and swapping containers by swapping the pointers rather than the
contents would seem to maintain that guarantee.


Francis Glassborow      Chair of Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <qFBPdvBko2p2EwN9@robinton.demon.co.uk>, Francis Glassborow
<francisG@robinton.demon.co.uk> wrote:

> In article <7870dk$m87$1@bunyip.cc.uq.edu.au>, Brian Parker
> <bparker@uq.net.au> writes
> >*no* swap function invalidates any references, pointers or iterators
> >referring to the elements of the containers being swapped.
> >
> >Surely this should state the opposite- that the swap function *does*
> >invalidate iterators et al.- because the previous paragraphs indicate that
> >swap is intended to be a constant time swap of pointers to memory blocks,
> >not a linear time copy of each element. But only a full copying swap will
> >leave iterators valid, a swapping of memory blocks will invalidate them as
> >they would be left pointing at the wrong object.
>
> I think you are misunderstanding the meaning of invalidate.  After swap,
> iterators may now point to different instances but they still point to
> instances (in other words memory must not be reloccated by a swap
> function).

Perhaps another way of saying this is:

a.swap(b);

Outstanding iterators and references of "a" before the swap will refer to
"b" after the swap.

Or is that not what the standard is trying to say here?  If that is not
the case, then surely one must consider outstanding iterators and
references invalidated.

-Howard
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper wrote in message <36A7D82E.73BF84FD@wizard.net>...
>...
>No, it was precisely that clause that made it clear to me what the
>standard meant by an invalid iterator. I'd previously considered that an
>iterator which still pointed to the 5'th element of a fixed vector<>,
>could be considered valid as long as that vector<> still contained 5
>elements. However, if you swap two vector<>'s with different numbers of
>elements, you couldn't have all of the iterators remain valid if they
>were of that type. Therefore, I realized that the standard was defining
>validity in terms of continuing to point to the same object, regardless
>of whether that object had been swap()'d to a new container.

Swapping differently sized vectors would invoke resize() which is itself
defined to invalidate extant iterators and references, so that should not be
an issue.

But as to your first point, if the intent of 23.1/10 is to actually *define*
"invalid" then I suppose the current wording is fair enough... but it is not
the definition I would use.

Anyway, thanks for your, and other's, comments in this thread- the consensus
appears to be that the current wording is, in fact, not a typo.

,Brian Parker
(bparker@uq.net.au)
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 22 Jan 1999 15:51:12 GMT, James Kuyper <kuyper@wizard.net> wrote:
>Brian Parker wrote:

>> 23.1/10 should instead just directly state what it intends- that the
>> allocated memory blocks storing the elements are not reallocated by swap,
>> and hence extant iterators, pointers and references refer to the same lvalue
>> after as before the swap. Describing this in terms of the (otherwise
>> undefined) expression "invalid iterator" is ambiguous- people will have
>> different expectations of what a "valid iterator/reference" means (or is it
>> just me :-) ).

>No, it was precisely that clause that made it clear to me what the
>standard meant by an invalid iterator. I'd previously considered that an
>iterator which still pointed to the 5'th element of a fixed vector<>,
>could be considered valid as long as that vector<> still contained 5
>elements. However, if you swap two vector<>'s with different numbers of
>elements, you couldn't have all of the iterators remain valid if they
>were of that type. Therefore, I realized that the standard was defining
>validity in terms of continuing to point to the same object, regardless
>of whether that object had been swap()'d to a new container.

No, I agree with Brian.  The paragraph should be polished up.  The
problem is the word "invalid".  This is a word with lots of
connotations.  To some, an "invalid iterator" is an iterator that
does not point to an object.  To others, an "invalid iterator" is
an iterator that points to an object, but conceptually the wrong
object.  The second interpretation is the correct one, and it
surely allows for a very efficient implementation of swap for
non-reference counted vectors -- just swap the internal
pointer-to-array and size and reserve fields.  But the first
interpretation is reasonable too, and a clearer choice of words,
phrases, and sentences would have been better.

But this is a matter of grammar and literary style.  The way I see
it, what clause 23.1.10 is really saying is that the implementation
of swap(container&,container&) where container is vector, list,
string, or whatever, is required to be maximally efficient.  That
is, swap(...) is O(1).

In general, "swap" does invalidate iterators.  Suppose you have
a fixed size array class
   template <class T, size_t N> class fvector { T d_data[N]; ... };
Suppose you figured out a way to swap a fvector<int,7> with a
fvector<int,8>.  The swap will have to swap raw bytes as there
is no pointer field to swap.  But this means that an iterator
pointing to an element in the fvector<int,8> may be invalidated
after the swap.  So now the first interpreation of "invalid
iterator" comes into play.

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <78b0je$icl$1@bunyip.cc.uq.edu.au>, Brian Parker
<bparker@uq.net.au> writes
>Yes, it is the only way to define "valid" such that iterators and references
>*always* have meaningful values after a swap, but my point was that this is
>a weird and dangerous definition to use in practice- some swap functions
>will leave iterators validly pointing at the other container whilst others
>(full copying swaps) leave them validly pointing at the same container.
>Actually relying upon such semantics, particularly in generic functions,
>would be quite subtle and, for my money, it would be safer and more correct
>to simply regard the iterators/references as being invalidated in the
>pointer-exchanging swap implementation.

No, according to my reading a 'full copying' swap is now allowed
because, except in a limited number of special cases, it will invalidate
some iterators (such as at least one of the one-past-the-end iterators)


Francis Glassborow      Chair of Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Siemel Naran wrote in message ...
>...
>No, I don't think range checked iterators should be a problem.  Eg,
>
>class vector<T>::iterator
>{
>   private:
>      vector<T> * vec;
>      T * ptr;
>      iterator(vector<T>* vec, T * ptr);
>   public:
>      T& operator*() const;
>      iterator& operator++();
>      iterator& operator++(int);
>};
>
>Suppose main(...) looks like this:
>
>   std::vector<int> v1(1), v2(0);
>   v1[0]=10;
>   std::vector<int>::iterator i1=v1.begin(), i2=v2.begin();
>   cout << *i1 << '\n'; // prints "10"
>   //cout << *i2 << '\n'; // gives range error
>   std::swap(v1,v2);
>   cout << *i1 << '\n'; // prints "10"
>   //cout << *i2 << '\n'; // gives range error
>
>Before the swap, 'i1' points to the number "10" in the vector 'v1',
>which is the vector with one element.
>
>After the swap, 'i1' still points to the number "10" in the same
>vector -- that is, the vector with one element -- but this vector
>is now called 'v2'.
>
>Swapping 'v1' and 'v2' has the effect of swapping 'i1' and 'i2',
>except that while the names 'v1' and 'v2' are swapped, the names
>'i1' and 'i2' are not swapped.


Hang on, you haven't actually implemented the assertion checks- if you do so
you will find that the checked iterator asserts on the use of *either*
iterator after swapping (see following code sample). This is as it should
be, IMO, as an iterator is an iterator on a particular container and when
swap assigns a memory block to another container then it can no longer be
viewed as a valid iterator into the original container. Unfortunately, this
iterator (if implemented as vector::iterator) is not standard-conforming as
a user is guaranteed by 23.1/10 that they can use the iterator after the
swap- a guarantee of dubious benefit in my opinion.

#include <vector>
#include <assert.h>
using namespace std;

struct safe_iter
{
 safe_iter(int* p_in, const vector<int>& c_in) :p(p_in), c(&c_in) {}

 int& operator*() const {
  assert(c->begin() <= p && p < c->end());
  return *p;
 }

 int* p;
 const vector<int>* c;
};

int main(int argc, char* argv[])
{
   vector<int> v1(1), v2(0);
   v1[0]=10;
   safe_iter i1(v1.begin(), v1);
   safe_iter i2(v2.begin(), v2);
   cout << *i1 << '\n'; // prints "10"
   //cout << *i2 << '\n'; // gives range error
   swap(v1,v2);
   cout << *i1 << '\n'; // gives range error
   cout << *i2 << '\n'; // gives range error
}

,Brian Parker
(bparker@uq.net.au)




[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Francis Glassborow wrote in message ...
>
>I think that we must look at what it means to be a 'valid iterator'.
>There seem to be two types and a special case:
>
>dereferencable iterators, i.e. does an attempt to dereference them
>provide anything other than undefined behaviour?
>
>one-past-the end iterators, cannot be dereferenced  but accessing the
>iterator without attempting to dereference is OK
>
>The NULL pointer
>
>What the swap requirements state is that if an iterator was valid before
>it will be valid afterwards.  To be valid it has to be one of the three
>above and swapping containers by swapping the pointers rather than the
>contents would seem to maintain that guarantee.


I disagree. I think that the issue of dereferencability is orthogonal to the
issue of validity we are discussing.

There are two concepts of what an iterator is-
(1) that they are iterators into a *particular* container.
(2) they are iterators into raw memory completely divorced from the
container that originally owned that memory.

(1) is my view of what an iterator is, and, I believe, what the original STL
intended. In this case, if I retrieve an iterator into a container, then any
other iterator to that same element of that container should give the same
lvalue, and, if not, one of the iterators has been invalidated.
i.e in

vector<int> v(10, 1);
vector<int>::iterator iter = v.begin();

iter is an iterator to the first element *of v*, and IMO, as long as it
remains valid, one should be able to rely on the fact that any other
iterator to the first element points to the same value i.e. *v.begin() ==
*iter always (which is not the case after a swap).

The view of iterators (2) that the standard mandates in 23.1/10 is not a
useful extension to the concept of iterators, and in fact lowers their level
of abstraction to little more than raw memory pointers- a major advantage of
using the higher level abstraction of iterators is that one can implement
run-time checks for validity, and such an advantage is diluted by the
standard's mandating of such a flexible definition of "valid" (and code that
relied upon this "extension"  would be quite obscure, depending as it would
on the vagaries of a particular implementation of swap).

,Brian Parker
(bparker@uq.net.au)




[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <slrn7ai6ba.9dj.sbnaran@fermi.ceg.uiuc.edu>, Siemel Naran
<sbnaran@fermi.ceg.uiuc.edu> writes
>To some, an "invalid iterator" is an iterator that
>does not point to an object.  To others, an "invalid iterator" is
>an iterator that points to an object, but conceptually the wrong
>object.  The second interpretation is the correct one, and it
>surely allows for a very efficient implementation of swap for
>non-reference counted vectors -- just swap the internal
>pointer-to-array and size and reserve fields.

Let me be stupid again:)  On what do you base your assertion that the
second interpretation is correct.  As this is comp.std.c++ perhaps you
could reference the Standard for this claim and save the rest of us
having to find it (if it is there)




Francis Glassborow      Chair of Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Brian Parker wrote:
....
> Swapping differently sized vectors would invoke resize() which is itself
> defined to invalidate extant iterators and references, so that should not be
> an issue.

There's no need for resize() to be called, and swap itself explicitly
says that the iterators and references are not invalidated, without any
excemption for differently sized vectors. The implementation of these
requirements is simple - the pointers to the allocated memory are
swapped, and also the size and reservation information. Iterators point
to the memory itself, not to the container.

> But as to your first point, if the intent of 23.1/10 is to actually *define*
> "invalid" then I suppose the current wording is fair enough... but it is not
> the definition I would use.

It doesn't seem intended as a definition, but there is no other
definition given. Figuring out what needed to be done to meet that
section's requirements clarified the implicit definition, but implicit
definitions are always tricky. I'd prefer an explicit one.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Siemel Naran wrote:
....
> In general, "swap" does invalidate iterators.  Suppose you have
> a fixed size array class
>    template <class T, size_t N> class fvector { T d_data[N]; ... };
> Suppose you figured out a way to swap a fvector<int,7> with a
> fvector<int,8>.  The swap will have to swap raw bytes as there
> is no pointer field to swap.  But this means that an iterator
> pointing to an element in the fvector<int,8> may be invalidated
> after the swap.  So now the first interpreation of "invalid
> iterator" comes into play.

It was considerations like this that led me to realize that a
fixed-sized array class couldn't meet the Standard's container
requirements - rather annoying.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Francis Glassborow wrote:
....
> No, according to my reading a 'full copying' swap is now allowed
> because, except in a limited number of special cases, it will invalidate
> some iterators (such as at least one of the one-past-the-end iterators)

Table 65: _Container Requirements_ indicates that swap() must be have
constant-time complexity. That would appear to rule out full-copying
swap() implementations.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Sec 23.1 /10 [lib.container.requirements] states that :

*no* swap function invalidates any references, pointers or iterators
referring to the elements of the containers being swapped.

Surely this should state the opposite- that the swap function *does*
invalidate iterators et al.- because the previous paragraphs indicate that
swap is intended to be a constant time swap of pointers to memory blocks,
not a linear time copy of each element. But only a full copying swap will
leave iterators valid, a swapping of memory blocks will invalidate them as
they would be left pointing at the wrong object.

,Brian Parker
(bparker@uq.net.au)





[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <7870dk$m87$1@bunyip.cc.uq.edu.au>, Brian Parker
<bparker@uq.net.au> writes
>*no* swap function invalidates any references, pointers or iterators
>referring to the elements of the containers being swapped.
>
>Surely this should state the opposite- that the swap function *does*
>invalidate iterators et al.- because the previous paragraphs indicate that
>swap is intended to be a constant time swap of pointers to memory blocks,
>not a linear time copy of each element. But only a full copying swap will
>leave iterators valid, a swapping of memory blocks will invalidate them as
>they would be left pointing at the wrong object.

I think you are misunderstanding the meaning of invalidate.  After swap,
iterators may now point to different instances but they still point to
instances (in other words memory must not be reloccated by a swap
function).


Francis Glassborow      Chair of Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 21 Jan 99 19:36:09 GMT, Francis Glassborow
>In article <7870dk$m87$1@bunyip.cc.uq.edu.au>, Brian Parker

>>*no* swap function invalidates any references, pointers or iterators
>>referring to the elements of the containers being swapped.

>I think you are misunderstanding the meaning of invalidate.  After swap,
>iterators may now point to different instances but they still point to
>instances (in other words memory must not be reloccated by a swap
>function).

Is this along the lines of what you mean?


#include <vector>

int main()
{
     typedef std::vector<int> Container;
     typedef Container::iterator Iter;

     Container a(1); a[0]=1;
     Container b(2); b[0]=2; b[1]=3;

     Iter i=b.begin()+1;
     cout << *b << '\n'; // prints "3"

     swap(a,b);
     cout << *i << '\n'; // prints "3"
}


Before the swap
   'i' points to b[1]
   since b[1] is "3", 'i' points to the number "3"

After the swap
   'i' still points to the number "3"
   but this is now a[1]


We see that after the swap, the iterators still point to the same
old instances.  But to get to the instance via the container's
accessor functions, we must use the new container name.  So if
before we said "b[i]" to get a certain object, then after the swap
of 'a' and 'b', we must say "a[i]" to get the same object.  But an
iterator pointing to "b[i]" before the swap points to "b[i]" after
the swap.

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Siemel Naran wrote in message ...

<example snipped>

>We see that after the swap, the iterators still point to the same
>old instances.  But to get to the instance via the container's
>accessor functions, we must use the new container name.  So if
>before we said "b[i]" to get a certain object, then after the swap
>of 'a' and 'b', we must say "a[i]" to get the same object.  But an
>iterator pointing to "b[i]" before the swap points to "b[i]" after
>the swap.

Yes, essentially the problem is that we speak of an iterator iterating on a
particular object. If that iterator no longer points at that object then it
is invalid- whether it is now pointing into a different object, or a
randomly allocated block of memory, or is dangling is irrelevant to its
validity; one may be able to dereference it without getting a core dump, but
it is still invalid.

(In fact, by the definition of "valid" used in 23.1/10, a garbage-collecting
implementation of vector<> that didn't delete[] its old memory block when
reallocating on a resize() could be said to leave existing references and
iterators to the garbage block  valid- hardly a  useful definition of
"valid".)

As another example, in the following function func( ) I assume that swap
acts as {lhs = temp; lhs = rhs; rhs = temp;} and hence double& d remains
valid.

#include <iostream>
#include <valarray>
#include <vector>

using namespace std;

template<typename T>
double& func(T& v1, T& v2)
{
 double& d = v1[1];

 cout << d << " ";

 swap(v1, v2);

 cout << d << endl;

 double& d2 = v1[1];
 T temp(v2);
 swap(v1, temp);

 return d2;
}

int main(int argc, char* argv[])
{
 valarray<double> v1(1.0, 3);
 valarray<double> v2(2.0, 3);
 cout << func(v1, v2) << endl;
 // outputs "1.0 2.0" as one would expect from the semantics of swap

 vector<double> vec1(3, 1.0);
 vector<double> vec2(3, 2.0);
 cout << func(vec1, vec2) << endl;
 // outputs "1.0 1.0" and func() returns a dangling reference- this is *not*
the semantics expected of swap
 // which implies that d in func is *invalid* after the swap.
}

This works correctly for valarray which has such a swap function, but leads
to buggy output when used with vector instead. I contend that the only
correct output in this example is "1.0 2.0" -anything else is simply wrong-
and the reason that func fails for vector is that d in func becomes
*invalid* after a swap- i.e. func()'s assumptions are not met by type
vector<>.

I think that 23.1 /10 in the standard is misusing and redefining the usual
meaning of "invalid" reference or iterator- in the example above, I would
define d as remaining valid *only* for a full copying swap, and as being
*invalidated* by a pointer-swapping swap- exactly the opposite
implementation of swap intended by 23.1/10.

23.1/10 should instead just directly state what it intends- that the
allocated memory blocks storing the elements are not reallocated by swap,
and hence extant iterators, pointers and references refer to the same lvalue
after as before the swap. Describing this in terms of the (otherwise
undefined) expression "invalid iterator" is ambiguous- people will have
different expectations of what a "valid iterator/reference" means (or is it
just me :-) ).

,Brian Parker
(bparker@uq.net.au)



[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Brian Parker wrote:
....
> 23.1/10 should instead just directly state what it intends- that the
> allocated memory blocks storing the elements are not reallocated by swap,
> and hence extant iterators, pointers and references refer to the same lvalue
> after as before the swap. Describing this in terms of the (otherwise
> undefined) expression "invalid iterator" is ambiguous- people will have
> different expectations of what a "valid iterator/reference" means (or is it
> just me :-) ).

No, it was precisely that clause that made it clear to me what the
standard meant by an invalid iterator. I'd previously considered that an
iterator which still pointed to the 5'th element of a fixed vector<>,
could be considered valid as long as that vector<> still contained 5
elements. However, if you swap two vector<>'s with different numbers of
elements, you couldn't have all of the iterators remain valid if they
were of that type. Therefore, I realized that the standard was defining
validity in terms of continuing to point to the same object, regardless
of whether that object had been swap()'d to a new container.


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <788i25$qvr$1@bunyip.cc.uq.edu.au>,
  "Brian Parker" <bparker@uq.net.au> wrote:
>
> Siemel Naran wrote in message ...
>
> <example snipped>
>
> >We see that after the swap, the iterators still point to the same
> >old instances.  But to get to the instance via the container's
> >accessor functions, we must use the new container name.  So if
> >before we said "b[i]" to get a certain object, then after the swap
> >of 'a' and 'b', we must say "a[i]" to get the same object.  But an
> >iterator pointing to "b[i]" before the swap points to "b[i]" after
> >the swap.
>
> Yes, essentially the problem is that we speak of an iterator iterating on a
> particular object. If that iterator no longer points at that object then it
> is invalid- whether it is now pointing into a different object, or a
> randomly allocated block of memory, or is dangling is irrelevant to its
> validity; one may be able to dereference it without getting a core dump, but
> it is still invalid.

Are we talking about swapping containers, or swapping elements in
the containers?

If swapping individual elements, I'm sure that it depends on the
container type. For instance, I doubt that most implementations
of vector can meaningfully swap individual elements without
copying the whole object. For a list, however, it should be
possible to unlink an element from one list and re-link it onto
another. Forgive me for not looking it up -- I'm running short
on time today -- but my memory is that the rule parallels that
of erase(). That is, the only iterators that are invalidated are
the ones that point to the elements affected.

If swapping whole containers, perhaps it makes sense to say that
the iterators are still valid, although they point into the
other container. After all, that is the only way that they could
possibly still have a meaningful value.

----
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

AllanW@my-dejanews.com wrote in message <78aack$3cj$1@nnrp1.dejanews.com>...
>,,,
>If swapping whole containers, perhaps it makes sense to say that
>the iterators are still valid, although they point into the
>other container. After all, that is the only way that they could
>possibly still have a meaningful value.


Yes, it is the only way to define "valid" such that iterators and references
*always* have meaningful values after a swap, but my point was that this is
a weird and dangerous definition to use in practice- some swap functions
will leave iterators validly pointing at the other container whilst others
(full copying swaps) leave them validly pointing at the same container.
Actually relying upon such semantics, particularly in generic functions,
would be quite subtle and, for my money, it would be safer and more correct
to simply regard the iterators/references as being invalidated in the
pointer-exchanging swap implementation.

Another problem with this definition of valid is that it effectively rules
out, as far as I can see, using range-checked iterators in a debug build for
vector<>- such iterators hold a pointer to the original container and would
incorrectly assert on the supposedly valid use of iterators that now point
to a different container after a swap.

,Brian Parker
(bparker@uq.net.au)




[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

[Note to moderator: this is the second send attempt for this- my newsreader
apparently failed on the first attempt; my apologies if this appears twice]

AllanW@my-dejanews.com wrote in message <78aack$3cj$1@nnrp1.dejanews.com>...
>,,,
>If swapping whole containers, perhaps it makes sense to say that
>the iterators are still valid, although they point into the
>other container. After all, that is the only way that they could
>possibly still have a meaningful value.

Yes, it is the only way to define "valid" such that iterators and references
*always* have meaningful values after a swap, but my point was that this is
a weird and dangerous definition to use in practice- some swap functions
will leave iterators validly pointing at the other container whilst others
(full copying swaps) leave them validly pointing at the same container.
Actually relying upon such semantics, particularly in generic functions,
would be quite subtle and, for my money, it would be safer and more correct
to simply regard the iterators/references as being invalidated in the
pointer-exchanging swap implementation.

Another problem with this definition of valid is that it effectively rules
out, as far as I can see, using range-checked iterators in a debug build for
vector<>- such iterators hold a pointer to the original container and would
incorrectly assert on the supposedly valid use of iterators that now point
to a different container after a swap.

,Brian Parker
(bparker@uq.net.au)



[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]