= operator: vector

[KS]

Hello,

I have a loop in which I need to keep two vectors, oldVector and
newVector. The elements of oldVector are processed and new elements are
added to newVector. At the end of the loop I simply do "oldVector =
newVector" for the next iteration. My question is does is assignment
destroy the contents of the oldVector and copy the new elements of
newVector? Its good if thats whats happenning, but if not, it is a huge
memory leak.

I looked at the source of vector and its not very clear what happens in
this case. (There are two functions copy and uninitialized copy which
are not available for viewing).

KS

 

[peter koch]

Hello,

I have a loop in which I need to keep two vectors, oldVector and
newVector. The elements of oldVector are processed and new elements are
added to newVector. At the end of the loop I simply do "oldVector =
newVector" for the next iteration. My question is does is assignment
destroy the contents of the oldVector and copy the new elements of
newVector? Its good if thats whats happenning, but if not, it is a huge
memory leak.

I looked at the source of vector and its not very clear what happens in
this case. (There are two functions copy and uninitialized copy which
are not available for viewing).

KS

Yes. Assignment in the std::library is intuitive and does what is
intuitively expected.

/Peter

 

[Philip Potter]

Hello,

I have a loop in which I need to keep two vectors, oldVector and
newVector. The elements of oldVector are processed and new elements are
added to newVector. At the end of the loop I simply do "oldVector =
newVector" for the next iteration. My question is does is assignment
destroy the contents of the oldVector and copy the new elements of
newVector? Its good if thats whats happenning, but if not, it is a huge
memory leak.

Yes, you are correct. After the assignment, the objects which were contained
in oldVector will have been destructed properly, and oldVector will contain
copies of the elements of newVector.

Philip

 

[Heinz Ozwirk]

Hello,

I have a loop in which I need to keep two vectors, oldVector and
newVector. The elements of oldVector are processed and new elements are
added to newVector. At the end of the loop I simply do "oldVector =
newVector" for the next iteration. My question is does is assignment
destroy the contents of the oldVector and copy the new elements of
newVector? Its good if thats whats happenning, but if not, it is a huge
memory leak.

I looked at the source of vector and its not very clear what happens in
this case. (There are two functions copy and uninitialized copy which
are not available for viewing).

As Peter and Philip already wrote, it works. But if you clear the contents
of newVector after assigning it to oldVector, swapping those vectors might
be more efficient than assignment. So if you do something like

oldVector = newVector;
newVector.clear();

it might be better to do

oldVector.swap(newVector);
newVector.clear();

This would not create copies of elements in newVector but would move
existing elements from newVector to oldVector (and elements from oldVector
to newVector).

HTH
Heinz

 

[Jerry Coffin]

Hello,

I have a loop in which I need to keep two vectors, oldVector and
newVector. The elements of oldVector are processed and new elements are
added to newVector. At the end of the loop I simply do "oldVector =
newVector" for the next iteration. My question is does is assignment
destroy the contents of the oldVector and copy the new elements of
newVector? Its good if thats whats happenning, but if not, it is a huge
memory leak.

Yes, it does what it should and you shouldn't be leaking memory.

It's not entirely clear what your intent is though. After you assign
oldVector=newVector, do you continue to use the elements in newVector?

If you don't care about the contents of newVector after that assignment,
it's almost certainly faster to do:

oldVector.swap(newVector);
// and optionally:
newVector.clear();

At least in the usual case (oldVector and newVector both use the same
Allocator) swapping is much faster. Instead of making a copy of each
element (linear time) it simply swaps the pointers to the data (constant
time).

 

[Philip Potter]

If you don't care about the contents of newVector after that assignment,
it's almost certainly faster to do:

oldVector.swap(newVector);
// and optionally:
newVector.clear();

At least in the usual case (oldVector and newVector both use the same
Allocator) swapping is much faster. Instead of making a copy of each
element (linear time) it simply swaps the pointers to the data (constant
time).

I'm not in favour of this, because it makes the code harder to read unless
you're aware of the idiom; it also gains nothing on implementations use
copy-on-write semantics for vectors. (Does the Standard say anything about
this?)

Philip

 

[KS]

If you don't care about the contents of newVector after that assignment,
it's almost certainly faster to do:

oldVector.swap(newVector);
// and optionally:
newVector.clear();

At least in the usual case (oldVector and newVector both use the same
Allocator) swapping is much faster. Instead of making a copy of each
element (linear time) it simply swaps the pointers to the data (constant
time).

newVector will be populated from the contents of oldVector in each
iteration. So I suppose I could do swap. But will swap take care of
destroying the contents of oldVector?

 

[Jerry Coffin]

[ using x.swap(y) ]

I'm not in favour of this, because it makes the code harder to read unless
you're aware of the idiom; it also gains nothing on implementations use
copy-on-write semantics for vectors. (Does the Standard say anything about
this?)

First of all, C+++ programmers should be aware of the idiom in any case
-- for example, one of the few clean implememtations of exception-safe
assignment uses swap.

Second, I'm not aware of anybody ever having even made a serious attempt
at implementing a COW vector. I'm not sure it's impossible, but I'm
pretty sure it's very difficult at best. Even though the committee made
an attempt at allowing COW implementations of std::string, that's quite
difficult to do well. Early implementations of the standard library
mostly used COW strings. Most no longer do (e.g. neither Dinkumware nor
STLPort does at the present time).

Third, even if vector does implement COW, swap is often more efficient
anyway. If you're sure your code will only ever be used an single-
threaded environement, COW assignment and swap are both essentially the
same speed. In a multi-threaded environment, access to the reference
count has to be synchronized across threads. This makes COW more
expensive (e.g. see: http://www.gotw.ca/gotw/045.htm).

You can count on efficiency if you use swap. You can hope for efficiency
if you use assignment, but if you do, you'll usually be disappointed.

 

[Jerry Coffin]

[ ... ]

newVector will be populated from the contents of oldVector in each
iteration. So I suppose I could do swap. But will swap take care of
destroying the contents of oldVector?

By itself, no, it doesn't do anything to the contents. Just as with the
assignment previously discussed, however, when you populate newVector
from oldVector, that will destroy the previous contents. As mentioned,
one alternative is to use clear() to empty the vector, and this also
takes care of destroying the contents properly.

 

[Howard]

Yes, you are correct. After the assignment, the objects which were
contained
in oldVector will have been destructed properly, and oldVector will
contain
copies of the elements of newVector.

Well, that assumes that the vector stores objects. If it stores raw
pointers, then that's not the case. When it holds pointers, the objects
pointed to may need to be destroyed first (depending on whether the vector
"owns" the objects pointed to by those).

-Howard

 

[KS]

You can count on efficiency if you use swap. You can hope for efficiency
if you use assignment, but if you do, you'll usually be disappointed.

swap works flawlessly.. Thanks for the reply.

 

[Philip Potter]

[ using x.swap(y) ]

I'm not in favour of this, because it makes the code harder to read unless
you're aware of the idiom; it also gains nothing on implementations use
copy-on-write semantics for vectors. (Does the Standard say anything about
this?)

First of all, C+++ programmers should be aware of the idiom in any case
-- for example, one of the few clean implememtations of exception-safe
assignment uses swap.

Second, I'm not aware of anybody ever having even made a serious attempt
at implementing a COW vector. I'm not sure it's impossible, but I'm
pretty sure it's very difficult at best. Even though the committee made
an attempt at allowing COW implementations of std::string, that's quite
difficult to do well. Early implementations of the standard library
mostly used COW strings. Most no longer do (e.g. neither Dinkumware nor
STLPort does at the present time).

Third, even if vector does implement COW, swap is often more efficient
anyway. If you're sure your code will only ever be used an single-
threaded environement, COW assignment and swap are both essentially the
same speed. In a multi-threaded environment, access to the reference
count has to be synchronized across threads. This makes COW more
expensive (e.g. see: http://www.gotw.ca/gotw/045.htm).

You can count on efficiency if you use swap. You can hope for efficiency
if you use assignment, but if you do, you'll usually be disappointed.

It's always nice to be disagreed with so educationally.

Does the Standard provide complexity-guarantees for swap() and operator=()?
Or is "you can count on efficiency if you use swap" only true for every
implementation you've seen?

Philip

 

[Kai-Uwe Bux]

[ using x.swap(y) ]

I'm not in favour of this, because it makes the code harder to read unless
you're aware of the idiom; it also gains nothing on implementations use
copy-on-write semantics for vectors. (Does the Standard say anything about
this?)

First of all, C+++ programmers should be aware of the idiom in any case
-- for example, one of the few clean implememtations of exception-safe
assignment uses swap.

Second, I'm not aware of anybody ever having even made a serious attempt
at implementing a COW vector. I'm not sure it's impossible, but I'm
pretty sure it's very difficult at best. Even though the committee made
an attempt at allowing COW implementations of std::string, that's quite
difficult to do well. Early implementations of the standard library
mostly used COW strings. Most no longer do (e.g. neither Dinkumware nor
STLPort does at the present time).

Third, even if vector does implement COW, swap is often more efficient
anyway. If you're sure your code will only ever be used an single-
threaded environement, COW assignment and swap are both essentially the
same speed. In a multi-threaded environment, access to the reference
count has to be synchronized across threads. This makes COW more
expensive (e.g. see: http://www.gotw.ca/gotw/045.htm).

You can count on efficiency if you use swap. You can hope for efficiency
if you use assignment, but if you do, you'll usually be disappointed.

It's always nice to be disagreed with so educationally.

Does the Standard provide complexity-guarantees for swap() and
operator=()? Or is "you can count on efficiency if you use swap" only true
for every implementation you've seen?

The standard says that the member function swap() for containers "should
have constant complexity" for every container. This is the same wording as
for the member function size(), which in some implementations has linear
complexity for std::list. However, the standard clearly sends a signal that
swap() is supposed to be constant time if this can be done without
compromising the efficiency of other operations. Thus, I would be very
surprised to find an implementation that has linear complexity for the
member function swap() in a standard container.

Copy constructor and assignment operators are supposed to have no worse than
linear complexity. [23.1/table 65]


Best

Kai-Uwe Bux

 

[Philip Potter]

The standard says that the member function swap() for containers "should
have constant complexity" for every container. This is the same wording as
for the member function size(), which in some implementations has linear
complexity for std::list. However, the standard clearly sends a signal that
swap() is supposed to be constant time if this can be done without
compromising the efficiency of other operations. Thus, I would be very
surprised to find an implementation that has linear complexity for the
member function swap() in a standard container.

Copy constructor and assignment operators are supposed to have no worse than
linear complexity. [23.1/table 65]

Thanks, that's exactly what I needed to know. In which case, I take back
what I said upthread

Philip

 

[Jerry Coffin]

[ ... ]

Does the Standard provide complexity-guarantees for swap() and operator=()?

Technically, the swap member function doesn't provide a guarantee on
complexity -- but the standard says it "should be constant".

OTOH, it does require that vector::swap can't throw any exceptions.
Nearly any operation on the contents such as assignment or copy
construction could throw an exception, so you can't do anything with the
contents. That leaves only the data in the vector structure itself,
which will normally be a pointer plus two size_t's. It'd be hard to
spend much time on them.

Or is "you can count on efficiency if you use swap" only true for every
implementation you've seen?

In theory, I suppose it's possible that somebody _could_ implement it in
a way that was arbitrarily inefficient. For example, you could add calls
to sleep (or Sleep, as applicable) to nearly anything and make it too
slow to be useful without violating requirements.