Home > Archive > VC STL > March 2005 > vector swap
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
| Mycroft Holmes 2005-03-08, 8:59 am |
| Hi,
I have a small doubt here: does vector::swap swap the capacity?
according to MSDN docs, *literally* it should not ("exchanges the
elements"), but in practice I think the only way for swap to be O(1) is
to swap all the memory managed by the objects (and in fact VC71 does it
swapping firs/last/end).
Anyway my problem is this:
vector<T> v1;
vector<T> v2;
v1.reserve( BIG_NUMBER );
v2.swap(v1); // note that they are both empty!
assert( v2.capacity() >= BIG_NUMBER ); // will it ever assert?
thanks in advance
--
The set of solutions is never empty.
Two solutions together form a new problem
-- Mycroft Holmes
--
The set of solutions is never empty.
Two solutions together form a new problem.
-- Mycroft Holmes
| |
| Laura T. 2005-03-08, 4:05 pm |
| AFAIK, swap should size the resulting vector as small as possibile.
From guru of the w (http://www.gotw.ca/):
"
If you want to completely clear a vector, so that it has no contents and no
extra capacity at all, the code is nearly identical to the shrink-to-fit
code... you just initialize the temporary vector to be empty instead of
making it a copy of c:
vector<Customer>().swap( c ); // ...now c.capacity() == 0, unless the
// implementation happens to enforce a
// minimum size even for empty vectorsAgain, note that the vector
implementation you're using may choose to make even empty vectors have some
slight capacity, but now you're guaranteed that c's capacity will be the
smallest possible allowed by your implementation: it will be the same as the
capacity of an empty vector.
"
Laura
"Mycroft Holmes" <m.holmes@nospam.it> ha scritto nel messaggio
news:m.holmes-CC93E5.12163108032005@msnews.microsoft.com...
> Hi,
>
> I have a small doubt here: does vector::swap swap the capacity?
> according to MSDN docs, *literally* it should not ("exchanges the
> elements"), but in practice I think the only way for swap to be O(1) is
> to swap all the memory managed by the objects (and in fact VC71 does it
> swapping firs/last/end).
>
> Anyway my problem is this:
>
> vector<T> v1;
> vector<T> v2;
> v1.reserve( BIG_NUMBER );
>
> v2.swap(v1); // note that they are both empty!
>
> assert( v2.capacity() >= BIG_NUMBER ); // will it ever assert?
>
>
> thanks in advance
>
>
> --
> The set of solutions is never empty.
> Two solutions together form a new problem
> -- Mycroft Holmes
>
> --
> The set of solutions is never empty.
> Two solutions together form a new problem.
> -- Mycroft Holmes
| |
| Pete Becker 2005-03-08, 4:05 pm |
| Laura T. wrote:
> AFAIK, swap should size the resulting vector as small as possibile.
No, swap merely exchanges the contents of two vectors. That trick for
clearing a vector swaps with a default-constructed vector, which is
where you get the small size from.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
| |
| Pete Becker 2005-03-08, 4:05 pm |
| Mycroft Holmes wrote:
> Hi,
>
> I have a small doubt here: does vector::swap swap the capacity?
> according to MSDN docs, *literally* it should not ("exchanges the
> elements"), but in practice I think the only way for swap to be O(1) is
> to swap all the memory managed by the objects (and in fact VC71 does it
> swapping firs/last/end).
>
Sloppy documentation. Take a look at our online documentation for a
better explanation. Or look at what the C++ standard says:
> Effects: Exchanges the contents and capacity() of *this with that of x.
>
> Complexity: Constant time.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
| |
| Mycroft Holmes 2005-03-08, 4:05 pm |
| [color=darkred]
> better explanation. Or look at what the C++ standard says:
>
thanks. can you show me the reference to the standard?
I have the PDF version here, but I cannot find your sentence.
--
The set of solutions is never empty.
Two solutions together form a new problem.
-- Mycroft Holmes
| |
| Carl Daniel [VC++ MVP] 2005-03-08, 4:05 pm |
| Mycroft Holmes wrote:
>
>
> thanks. can you show me the reference to the standard?
> I have the PDF version here, but I cannot find your sentence.
AFAICT that standard contains no such verbiage, neither in the 1998 version
nor the 2003 revision incorporating TC1 (but that's based only on looking
where it ought to be - maybe it is hiddne in there somewhere!).
What the standard does say, however, clearly implies that capacity must be
swapped as well:
If a and b are objects of type std::vector<some_type>,
a.swap(b);
is the same as
std::swap(a,b);
The effects of std::swap are "exchanges the values of two variables".
Capacity is clearly part of the value representation of a std::vector
instance, so it must be swapped along with the content.
-cd
| |
| Pete Becker 2005-03-08, 4:05 pm |
| Mycroft Holmes wrote:
>
>
>
> thanks. can you show me the reference to the standard?
> I have the PDF version here, but I cannot find your sentence.
>
23.2.4.2/6-7. But that's the latest internal version, not the actual
standard. Changed by DR 341. Sorry about that.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
| |
| red floyd 2005-03-08, 4:05 pm |
| Pete Becker wrote:
> Mycroft Holmes wrote:
>
>
> 23.2.4.2/6-7. But that's the latest internal version, not the actual
> standard. Changed by DR 341. Sorry about that.
>
Let me guess, DR 341 said that 23.2.4.4/1 had meaningless content? My
copy of the Standard+TC1 (Wiley Press) has 23.2.4.4/1 reading literally
as follows:
-- begin quote
Effects:
x.swap(y);
-- end quote
| |
| Tom Widmer 2005-03-08, 4:05 pm |
| Pete Becker wrote:[color=darkred]
> Mycroft Holmes wrote:
>
>
> Sloppy documentation. Take a look at our online documentation for a
> better explanation. Or look at what the C++ standard says:
>
What if the containers have non-equal allocators? Does it swap the
allocators? Does the working paper say?
Tom
| |
| Pete Becker 2005-03-08, 4:05 pm |
| Tom Widmer wrote:
>
> What if the containers have non-equal allocators? Does it swap the
> allocators? Does the working paper say?
>
The standard doesn't impose any requirements for containers with
allocators that don't compare equal. Our implementation supports them,
and in that case vector::swap is linear in the number of elements. You
have to copy them into the other's memory block.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
| |
| Pete Becker 2005-03-08, 4:05 pm |
| red floyd wrote:
>
> Let me guess, DR 341 said that 23.2.4.4/1 had meaningless content?
Nope.
> My
> copy of the Standard+TC1 (Wiley Press) has 23.2.4.4/1 reading literally
> as follows:
>
> -- begin quote
> Effects:
> x.swap(y);
> -- end quote
That's typical of the global swap functions: they call the member
version. Some of the member functions aren't explicitly specified for a
particular container because the generic requirements tables give the
necessary details. For vector there was enough confusion about the
effect on capacity() that we made the effect explicit.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
| |
| Ken Alverson 2005-03-08, 9:02 pm |
| "Carl Daniel [VC++ MVP]" <cpdaniel_remove_this_and_nospam@mvps.org.nospam>
wrote in message news:uwA$cq$IFHA.3484@TK2MSFTNGP12.phx.gbl...
>
> The effects of std::swap are "exchanges the values of two variables".
> Capacity is clearly part of the value representation of a std::vector
> instance, so it must be swapped along with the content.
I would not consider capacity a part of the vector's "value", consider:
vector<int> a,b;
// fill "a"
b = a;
b.reserve(b.capacity()*2);
if (a == b) cout << "vectors are the same" << endl;
a and b have different capacities, yet compare equal, which in my book gives
them the same "value".
Ken
| |
| Mycroft Holmes 2005-03-09, 9:00 am |
|
> What the standard does say, however, clearly implies that capacity must be
> swapped as well:
>
well, if the standard states that swap must be O(1) everytime it can be
:) that should be enough to imply that capacity must be swapped (under
the hypothesis that vector has contiguous storage).
btw, is the TC1 downloadable?
--
The set of solutions is never empty.
Two solutions together form a new problem.
-- Mycroft Holmes
| |
| Tom Widmer 2005-03-09, 4:03 pm |
| Pete Becker wrote:
> Tom Widmer wrote:
>
>
> The standard doesn't impose any requirements for containers with
> allocators that don't compare equal.
It should impose semantics where non-equal allocators are supported -
there's enough experience with them to fix this for the next standard I
think.
> Our implementation supports them,
> and in that case vector::swap is linear in the number of elements. You
> have to copy them into the other's memory block.
Ahh, I had checked the VC7.1 implementation, but I assumed you were
going to change it so that it swapped allocators to avoid violating the
new capacity() swap guarantee. But I can see that this has some alarming
exception safety implications, since swapping allocators might throw.
For this to work, swapping allocators must have the strong exception
safety guarantee, since a half swapped allocator would spell doom.
I see Howard Hinnant and Dinkumware are in disagreement on container
swapping for unequal allocators. Why did you opt for an O(N) swap?
Tom
| |
| Tom Widmer 2005-03-09, 4:03 pm |
| Mycroft Holmes wrote:
>
>
> well, if the standard states that swap must be O(1) everytime it can be
> :) that should be enough to imply that capacity must be swapped (under
> the hypothesis that vector has contiguous storage).
>
> btw, is the TC1 downloadable?
Yup, I believe it has replaced the original standard at the ANSI
webstore. (It looks like it indeed has:
http://webstore.ansi.org/ansidocsto...EC+14882%2D2003
)
Tom
| |
|
|
|
|
|