Anthony Williams wrote:

> It is a common idiom to reduce the capacity of a vector by swapping it with
> an empty one:
>
> std::vector<SomeType> vec;
> // fill vec with data
> std::vector<SomeType>().swap(vec);
> // vec is now empty, with minimal capacity


I think the idiom works like this:

   std::vector<SomeType>(vec).swap(vec);

This creates a copy of vec with minimal capacity. This new vector gets
swapped with vec. The old vec is now stored in a temporary variable
and will get destroyed.

Best Regards
Ralph Peterson

---
[ 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.research.att.com/~austern/csc/faq.html                ]

"Ralph Peterson" <ralph.peterson@gmx.net> wrote in message
news:3BC318DD.6000503@gmx.net...
> Anthony Williams wrote:
>
> > It is a common idiom to reduce the capacity of a vector by swapping it
with
> > an empty one:
> >
> > std::vector<SomeType> vec;
> > // fill vec with data
> > std::vector<SomeType>().swap(vec);
> > // vec is now empty, with minimal capacity
>
>
> I think the idiom works like this:
>
>    std::vector<SomeType>(vec).swap(vec);
>
> This creates a copy of vec with minimal capacity. This new vector gets
> swapped with vec. The old vec is now stored in a temporary variable
> and will get destroyed.

This is also common, and the same arguments apply wrt the semantics.

Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optoelectronics
The opinions expressed in this message are not necessarily those of my
employer



---
[ 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.research.att.com/~austern/csc/faq.html                ]

It is a common idiom to reduce the capacity of a vector by swapping it with
an empty one:

std::vector<SomeType> vec;
// fill vec with data
std::vector<SomeType>().swap(vec);
// vec is now empty, with minimal capacity

However, the wording of 23.2.4.2 [lib.vector.capacity] paragraph 5 prevents
the capacity of a vector being reduced, following a call to reserve(). This
invalidates the idiom, as swap() is thus prevented from reducing the
capacity. The proposed wording for issue #329 does not affect this.
Consequently, the example above requires the temporary to be expanded to
cater for the contents of vec, and the contents be copied across. This is a
linear-time operation.

However, the container requirements state that swap must have constant
complexity (23.1 [lib.container.requirements] note to table 65).

This is an important issue, as reallocation affects the validity of
references and iterators.

If the wording of 23.2.4.2p5 is taken to be the desired intent, then
references and iterators remain valid after a call to swap, if they refer to
an element before the new end() of the vector into which they originally
pointed, in which case they refer to the element at the same index position.
Iterators and references that referred to an element whose index position
was beyond the new end of the vector are invalidated.

If the note to table 65 is taken as the desired intent, then there are two
possibilities with regard to iterators and references.

1) All Iterators and references into both vectors are invalidated.
2) Iterators and references into either vector remain valid, and remain
pointing to the same element. Consequently iterators and references that
referred to one vector now refer to the other, and vice-versa.

Proposed resolution:

I believe that table 65 should be taken as the desired intent - swap should
be constant time. I also believe that permitting iterators and references to
remain valid, but refer to elements in the other container would place undue
restriction on the implementation of vector iterators, though it may be
useful.

Therefore I propose modifying 23.2.4.2 [lib.vector.capacity] paragraph 5 as
follows:

add the following to the end of the final sentence "It is guaranteed that no
reallocation takes place...."

", unless the vector is passed as an argument (either directly, or as the
implied object) for a call to swap()."

Also, a description of swap() should be added to 23.2.4.3
[lib.vector.modifiers]:

"void swap(vector<T,Allocator>& x);

Effects: Swaps the contents of the vector with that of x. The new size() and
capacity() are the values held for x prior to the call to swap(), and vice
versa. Any guarantees on reallocation due to a call to reserve() are also
exchanged. All iterators and references into either vector are invalidated.

Complexity: Constant time"

Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optoelectronics
The opinions expressed in this message are not necessarily those of my
employer




[ 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.research.att.com/~austern/csc/faq.html                ]

"Anthony Williams" <anthwil@nortelnetworks.com> wrote in message
news:9ov5hi$fh52p$1@ID-49767.news.dfncis.de...
[snip]
> Therefore I propose modifying 23.2.4.2 [lib.vector.capacity] paragraph 5
as
> follows:
>
> add the following to the end of the final sentence "It is guaranteed that
no
> reallocation takes place...."
>
> ", unless the vector is passed as an argument (either directly, or as the
> implied object) for a call to swap()."
[rest cut]

I don't usually post to comp.std.c++, but seeing as I've been following the
related thread on clc++m....

Assuming that this modification is necessary, it is probably also not
sufficient. What I mean is, if you need to write an explicit exemption for
swap() in this case, then there may be other cases for which swap() is also
unusual. Furthermore, the assignment operator might need the same
exemption(s). This is because a vector must be Assignable in order to be
used itself in a container:

#include <vector>
#include <iostream>

using namespace std;

int main (void)
{
  vector<vector <int> > vv (1);

  vv[0].reserve (100);
  cout << vv[0].capacity() << endl;
  vv.reserve(1024);
  cout << vv[0].capacity() << endl;
}

The reserve(1024) is intended to cause copying of the vector at vv[0] (maybe
via the copy constructor, but there must be some cases where the
implementation is allowed to use the assignment operator - maybe an erase in
the middle of a sequence).

If the copied object doesn't have (at least) the same capacity as the
original, then the reserve() requirement has been broken. Actually, the
Assignable requirement has been broken, because the new vv[0] is not really
equivalent to the original.

[I'm pretty sure that STLport version 4.0 gets this example wrong. It should
output 100 and 100, but I get 100 and 0]

After thinking about it, maybe assignment is not relevant to the reserve()
requirement, because an increase in capacity is always allowed. On the other
hand, since the capacity is an observable feature, I would think assignment
should preserve it in all cases.

Regards,
Raoul Gough.

--
Don't bother trying the deja return address. You could try the same username
"at" knuut.de or via Hotmail if I've moved home address.



---
[ 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.research.att.com/~austern/csc/faq.html                ]

Anthony Williams wrote:
>
> It is a common idiom to reduce the capacity of a vector by swapping it with
> an empty one:
>
> std::vector<SomeType> vec;
> // fill vec with data
> std::vector<SomeType>().swap(vec);
> // vec is now empty, with minimal capacity
>
> However, the wording of 23.2.4.2 [lib.vector.capacity] paragraph 5 prevents
> the capacity of a vector being reduced, following a call to reserve(). This
> invalidates the idiom, as swap() is thus prevented from reducing the

The reservation is itself one of the properties of the vector that is
swapped. Therefore, the reservation is swapped along with the data.

---
[ 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.research.att.com/~austern/csc/faq.html                ]

"Raoul Gough" <RaoulGough@my-deja.com> wrote in message
news:3bb3996c$0$194$4d4ebb8e@read.news.de.uu.net...
> "Anthony Williams" <anthwil@nortelnetworks.com> wrote in message
> news:9ov5hi$fh52p$1@ID-49767.news.dfncis.de...
> [snip]
> > Therefore I propose modifying 23.2.4.2 [lib.vector.capacity] paragraph 5
> as
> > follows:
> >
> > add the following to the end of the final sentence "It is guaranteed
that
> no
> > reallocation takes place...."
> >
> > ", unless the vector is passed as an argument (either directly, or as
the
> > implied object) for a call to swap()."
> [rest cut]
>
> I don't usually post to comp.std.c++, but seeing as I've been following
the
> related thread on clc++m....
>
> Assuming that this modification is necessary, it is probably also not
> sufficient. What I mean is, if you need to write an explicit exemption for
> swap() in this case, then there may be other cases for which swap() is
also
> unusual. Furthermore, the assignment operator might need the same
> exemption(s). This is because a vector must be Assignable in order to be
> used itself in a container:
>
> #include <vector>
> #include <iostream>
>
> using namespace std;
>
> int main (void)
> {
>   vector<vector <int> > vv (1);
>
>   vv[0].reserve (100);
>   cout << vv[0].capacity() << endl;
>   vv.reserve(1024);
>   cout << vv[0].capacity() << endl;
> }
>
> The reserve(1024) is intended to cause copying of the vector at vv[0]
(maybe
> via the copy constructor, but there must be some cases where the
> implementation is allowed to use the assignment operator - maybe an erase
in
> the middle of a sequence).
>
> If the copied object doesn't have (at least) the same capacity as the
> original, then the reserve() requirement has been broken. Actually, the
> Assignable requirement has been broken, because the new vv[0] is not
really
> equivalent to the original.
>
> [I'm pretty sure that STLport version 4.0 gets this example wrong. It
should
> output 100 and 100, but I get 100 and 0]
>
> After thinking about it, maybe assignment is not relevant to the reserve()
> requirement, because an increase in capacity is always allowed. On the
other
> hand, since the capacity is an observable feature, I would think
assignment
> should preserve it in all cases.

The requirements on assignment are that a=b => a==b as a post condition.

a==b is defined as (a.size()==b.size() &&
equal(a.begin(),a.end(),b.begin(),b.end())) (23.1 Table 65)

Thus assignment only has to change capacity if the vector grows beyond the
current capacity, which IMO counts as an insertion, so the current wording
allows this.

For swap to happen in constant time, the capacity may have to _shrink_, even
if the size remains unchanged. This is not currently permitted. e.g.

std::vector<int> v1,v2;

v1.reserve(10);
v2.reserve(v1.capacity()*2);

for(unsigned i=0;i<10;++i)
{
    v1.push_back(i);
    v2.push_back(10*i);
}

v2.swap(v1);

Each vector has 10 elements. The capacity of v2 is at least twice that of v1
(i.e. not equal). For swap to happen in constant time, the memory blocks
must be exchanged, swapping the capacities. The current wording prevents the
capacity of v2 shrinking, so the elements must be copied, which implies
linear time.

Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optoelectronics
The opinions expressed in this message are not necessarily those of my
employer



---
[ 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.research.att.com/~austern/csc/faq.html                ]

"James Russell Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3BB3C899.F25E1EFB@wizard.net...
> Anthony Williams wrote:
> >
> > It is a common idiom to reduce the capacity of a vector by swapping it
with
> > an empty one:
> >
> > std::vector<SomeType> vec;
> > // fill vec with data
> > std::vector<SomeType>().swap(vec);
> > // vec is now empty, with minimal capacity
> >
> > However, the wording of 23.2.4.2 [lib.vector.capacity] paragraph 5
prevents
> > the capacity of a vector being reduced, following a call to reserve().
This
> > invalidates the idiom, as swap() is thus prevented from reducing the
>
> The reservation is itself one of the properties of the vector that is
> swapped. Therefore, the reservation is swapped along with the data.

That is the assumption, but no wording supports it. Hence the DR.

Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optoelectronics
The opinions expressed in this message are not necessarily those of my
employer



---
[ 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.research.att.com/~austern/csc/faq.html                ]

"Anthony Williams" <anthwil@nortelnetworks.com> wrote in message
news:9p1a47$fk76i$1@ID-49767.news.dfncis.de...
[cut]
> The requirements on assignment are that a=b => a==b as a post condition.
>
> a==b is defined as (a.size()==b.size() &&
> equal(a.begin(),a.end(),b.begin(),b.end())) (23.1 Table 65)
>
> Thus assignment only has to change capacity if the vector grows beyond the
> current capacity, which IMO counts as an insertion, so the current wording
> allows this.
>

Yes, that is the current requirement for containers. However, the general
requirement for something to be Assignable says that assignment makes the
two objects "equivalent". Lets put this another way: are you suggesting that
a vector which is itself stored in a container does not have to remember
it's capacity?

E.g.

vector< vector<int> > vv(1);   // line 1
vv[0].reserve(1024);
vv.push_back (vector<int>());

[Does this example worry anybody apart from me?]

If I understand what you are saying, line three of the example is allowed to
invalidate the reserve made in line two. Remembering that this is not just a
performance issue, as others have pointed out. I'm submitting that the
requirement of "equivalence" should also include a vector's capacity. I
would like to hear an argument as to why the capacity is allowed to be
ignored by the assignment operator (or copy constructor, for that matter).

My original point being, if you are going to start listing exceptions to the
reserve() requirement, and you think that swap needs to be included, then I
would say that you also have to include the assignment operator. I
personally think that a simple footnote would clear up the whole matter.
Maybe it would also help to avoid reference to the "last call of reserve()"
and refer instead to the vector's current capacity (actually elevating
capacity to a first-class attribute of vector :-)

Regards,
Raoul Gough.

--
Don't bother trying the deja return address. You could try the same username
"at" knuut.de or via Hotmail if I've moved home address.


---
[ 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.research.att.com/~austern/csc/faq.html                ]

Anthony Williams wrote:
>
> "James Russell Kuyper Jr." <kuyper@wizard.net> wrote in message
> news:3BB3C899.F25E1EFB@wizard.net...
> > Anthony Williams wrote:
> > >
> > > It is a common idiom to reduce the capacity of a vector by swapping it
> with
> > > an empty one:
> > >
> > > std::vector<SomeType> vec;
> > > // fill vec with data
> > > std::vector<SomeType>().swap(vec);
> > > // vec is now empty, with minimal capacity
> > >
> > > However, the wording of 23.2.4.2 [lib.vector.capacity] paragraph 5
> prevents
> > > the capacity of a vector being reduced, following a call to reserve().
> This
> > > invalidates the idiom, as swap() is thus prevented from reducing the
> >
> > The reservation is itself one of the properties of the vector that is
> > swapped. Therefore, the reservation is swapped along with the data.
>
> That is the assumption, but no wording supports it. Hence the DR.

Table 65 specifies that a.swap(b) has the effect swap(a,b). That doesn't
mean it has to call std::swap(a,b), but it does mean that it must have
the same effect as doing so.

25.2.2p2 specifies that for swap(a,b), "Effects: Exchanges values stored
in two locations."

Are you suggesting that the current reservation of a container is not
part of that container's value? I don't know how to argue that point -
it seems too obvious - so I hope that's not what you're saying. It's a
per-instance quantity, so it must be stored as part of the container
object, directly or indirectly.

---
[ 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.research.att.com/~austern/csc/faq.html                ]

"James Russell Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3BB5185A.65F32C8D@wizard.net...
> Table 65 specifies that a.swap(b) has the effect swap(a,b). That doesn't
> mean it has to call std::swap(a,b), but it does mean that it must have
> the same effect as doing so.
>
> 25.2.2p2 specifies that for swap(a,b), "Effects: Exchanges values stored
> in two locations."
>
> Are you suggesting that the current reservation of a container is not
> part of that container's value? I don't know how to argue that point -
> it seems too obvious - so I hope that's not what you're saying. It's a
> per-instance quantity, so it must be stored as part of the container
> object, directly or indirectly.

Yes, but assigment doesn't preserve it, so I see no requirement for swap to
do so, as the simplest implementation

template<typename T>
void swap(T& a,T& b)
{
    T temp(a);
    a=b;
    b=temp;
}

won't preserve it, yet fulfils all the swap requirements (IMO).

Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optoelectronics
The opinions expressed in this message are not necessarily those of my
employer



---
[ 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.research.att.com/~austern/csc/faq.html                ]

Anthony Williams wrote:
>
> "James Russell Kuyper Jr." <kuyper@wizard.net> wrote in message
> news:3BB5185A.65F32C8D@wizard.net...
> > Table 65 specifies that a.swap(b) has the effect swap(a,b). That doesn't
> > mean it has to call std::swap(a,b), but it does mean that it must have
> > the same effect as doing so.
> >
> > 25.2.2p2 specifies that for swap(a,b), "Effects: Exchanges values stored
> > in two locations."
> >
> > Are you suggesting that the current reservation of a container is not
> > part of that container's value? I don't know how to argue that point -
> > it seems too obvious - so I hope that's not what you're saying. It's a
> > per-instance quantity, so it must be stored as part of the container
> > object, directly or indirectly.
>
> Yes, but assigment doesn't preserve it, so I see no requirement for swap to
> do so, as the simplest implementation

I'd thought that Containers were required to be Assignable, which would
mean that the post condition on t=u is that t is equivalent to u. That
would imply that all features get copied, including the reservation.
However, I can't find any such requirement. There's only a requirement
that the value type of a container be Assignable. According to Table 65,
the post-condition on u=a for containers is weaker than Assignable; it
only says that u==a. The definition of u==a makes that a condition only
on the elements of u, and not on any other feature of the container. It
seems to neither require nor prohibit copying of the reservation.

The generic implementation of swap() must use assignment. I guess that
implies that vector<T>::swap() should use the same semantics as a
generic swap() implemented using assignment. It would certainly be
feasible for it to carry over the reservation, but I can't find anything
that says it has to. Therefore, I suppose you have a point.

I don't like this; it implies that portable code cannot assume that
containers can themselve be placed in other containers;
Container<Container<T> > is legal only for implementations that choose
to make Container<T> Assignable, something that is not required by the
standard.

Was this the intent of the committee?

---
[ 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.research.att.com/~austern/csc/faq.html                ]