Again a simple question about std::vector

[ciccio]

Hi,

Again I am wondering about something.

If you use the swap function of an std::vector, what does it do?

Does it swap each element separately by means of copying to a tmp
variable, or does it just swap some pointers to memory blocks.

Regards

 

[Victor Bazarov]

Again I am wondering about something.

If you use the swap function of an std::vector, what does it do?

Does it swap each element separately by means of copying to a tmp
variable, or does it just swap some pointers to memory blocks.

In most implementations, the latter. Of course it also has to
swap the size if it's cached (and it probably is), and other data
members.

V

 

[Lionel B]

Hi,

Again I am wondering about something.

If you use the swap function of an std::vector, what does it do?

Did you mean std::vector::swap() or std::swap() as applied to std::vector
() ? (not that there is necessarily much difference - see below).

Does it swap each element separately by means of copying to a tmp
variable, or does it just swap some pointers to memory blocks.

I believe the C++ standard demands that std::swap() - and indeed the swap
() member for any container - must have constant time complexity, which
would rule out element-by-element swapping. If you have the source/docs
for your standard library you could have a look. My standard library
(GNU) documentation says:

"This exchanges the elements between two vectors in constant time. (Three
pointers, so it should be quite fast.) Note that the global std::swap()
function is specialized such that std::swap(v1,v2) will feed to this
function."

 

[Jerry Coffin]

Hi,

Again I am wondering about something.

If you use the swap function of an std::vector, what does it do?

Does it swap each element separately by means of copying to a tmp
variable, or does it just swap some pointers to memory blocks.

It's pretty much required to do the latter. It's required to have
constant complexity, and it's can't throw an exception (a swap() can
only throw an exception if the container's Compare() function throws the
exception, and a vector doesn't have a Compare() function).

Contrary to the implication elsethread, there's no real difference
between std::swap<vector, vector> and vector::swap(vector). According to
section 23.2.4.4, the standard library is required to contain a
specialization of std::swap for vector so that if v1 and v2 both refer
to vectors, std:swap(v1, v2) is equivalent to v1.swap(v2).

 

[Lionel B]

Hi,

Again I am wondering about something.

If you use the swap function of an std::vector, what does it do?

Does it swap each element separately by means of copying to a tmp
variable, or does it just swap some pointers to memory blocks.

[...]

Contrary to the implication elsethread, there's no real difference
between std::swap<vector, vector> and vector::swap(vector). According to
section 23.2.4.4, the standard library is required to contain a
specialization of std::swap for vector so that if v1 and v2 both refer
to vectors, std:swap(v1, v2) is equivalent to v1.swap(v2).

Right, I wasn't aware that it was actually a requirement. I guess that
applies to every container, then (I can't think why it shouldn't).

 

[James Kanze]

It's pretty much required to do the latter. It's required to have
constant complexity, and it's can't throw an exception (a swap() can
only throw an exception if the container's Compare() function throws the
exception, and a vector doesn't have a Compare() function).

I've been wondering about this. What about the allocators? If
I understand the philosophy behind them, all memory that was
allocated must be freed by an allocator of the same type, which
compares equal to the one used to allocate. The same type is
automatic, since the type of the allocator is part of the type
of the template specialization. But maintaining the second
condition means somehow swapping the allocators as well, at
least if they don't compare equal. And off hand, I don't see
any requirement that allocators are "Swappable", nor that they
cannot throw if you attempt to swap them with std::swap.

Is this an oversight in the standard, or is there something I've
missed?

 

[Jerry Coffin]

[ ... ]

I've been wondering about this. What about the allocators?

Good question.

If I understand the philosophy behind them, all memory that was
allocated must be freed by an allocator of the same type, which
compares equal to the one used to allocate.

I believe that's correct. In fact, table 32 specifies equality for
Allocators in exactly those terms: "a1 == a2 ... returns true iff
storage allocated from each can be deallocated via the other."

The same type is
automatic, since the type of the allocator is part of the type
of the template specialization. But maintaining the second
condition means somehow swapping the allocators as well, at
least if they don't compare equal. And off hand, I don't see
any requirement that allocators are "Swappable", nor that they
cannot throw if you attempt to swap them with std::swap.

Section 20.1.5/4 says:

Implementations of containers described in this International
Standard are permitted to assume that their Allocator
template parameter meets the following two additional
requirements beyond those in Table 32.

— All instances of a given allocator type are required to be
interchangeable and always compare equal to each other.

It goes on to say:

Implementors are encouraged to supply libraries that can accept
allocators that encapsulate more general memory models and that
support non-equal instances. In such implementations, any
requirements imposed on allocators by containers beyond those
requirements that appear in Table 32, and the semantics of con-
tainers and algorithms when allocator instances compare non-
equal, are implementation-defined.

As such, I'd say non-equal allocators leads to undefined behavior as a
rule, though it might only be implementation defined behavior instead --
but if so, there may also be implementation defined requirements to get
the implementation defined behavior (e.g. swap of containers won't throw
-- but swapping allocators can't throw either).

Is this an oversight in the standard, or is there something I've
missed?

If I understand your question correctly, I think the section above
covers it.

 

[James Kanze]

[ ... ]

I've been wondering about this. What about the allocators?

Good question.

I believe that's correct. In fact, table 32 specifies equality for
Allocators in exactly those terms: "a1 == a2 ... returns true iff
storage allocated from each can be deallocated via the other."

Which supposes that if it returns false, they probably can't be.

Section 20.1.5/4 says:

Implementations of containers described in this International
Standard are permitted to assume that their Allocator
template parameter meets the following two additional
requirements beyond those in Table 32.

? All instances of a given allocator type are required to be
interchangeable and always compare equal to each other.

It goes on to say:

Implementors are encouraged to supply libraries that can accept
allocators that encapsulate more general memory models and that
support non-equal instances. In such implementations, any
requirements imposed on allocators by containers beyond those
requirements that appear in Table 32, and the semantics of con-
tainers and algorithms when allocator instances compare non-
equal, are implementation-defined.

Which is pretty weasely, if you ask me. Does == on an allocator
mean anything, or not? The answer is an unqualified and
decisive maybe.

As such, I'd say non-equal allocators leads to undefined
behavior as a rule, though it might only be implementation
defined behavior instead -- but if so, there may also be
implementation defined requirements to get the implementation
defined behavior (e.g. swap of containers won't throw -- but
swapping allocators can't throw either).

In sum, if an implementation decides to support non-equal
allocators, it is free to choose: require them to support swap
(possibly by having a no-throw copy constructor and assignment
operator, so that std::swap will work), accept that swap might
throw if the allocators are not equal (along the lines of
Compare), or accept that swap is not constant time if the
allocators are not equal.

It's a shame we don't hear much from Plauger any more. I know
that his implementation does support non-equal allocators; I'd
be interesting in hearing which option he chose, and why. (I'd

If I understand your question correctly, I think the section
above covers it.

In other words, the standard has intentionally decided to duck
the issue.

 

[Jerry Coffin]

(e-mail address removed)>, (e-mail address removed)
says...

On Apr 4, 6:54 am, Jerry Coffin <[email protected]> wrote:

[ ... ]

Which supposes that if it returns false, they probably can't be.

I think it does more than suppose -- 'iff' (at least normally) means "if
and only if"...

Which is pretty weasely, if you ask me. Does == on an allocator
mean anything, or not? The answer is an unqualified and
decisive maybe.

It means exactly what's said above, nothing more.

[ ... ]

In sum, if an implementation decides to support non-equal
allocators, it is free to choose: require them to support swap
(possibly by having a no-throw copy constructor and assignment
operator, so that std::swap will work), accept that swap might
throw if the allocators are not equal (along the lines of
Compare), or accept that swap is not constant time if the
allocators are not equal.

Right -- your last point (possible O(N) swap) comes back to a
fundamental question of what it means to swap containers: does it just
mean swapping their contents, or does it also mean swapping their
allocators?

If it just means swapping their contents, I don't think the possibility
of non-constant time is an "or" -- I think it's linear time AND you face
the possibility of an exception (if either allocator throws).

[ ... ]

In other words, the standard has intentionally decided to duck
the issue.

Yes, mostly. As it stands right now, an Allocator is really more like a
namespace than an object. For most practical purposes, it doesn't
(portably) have any per-object state, just a set of names (with
functions to implement some of them, of course).

 

[James Kanze]

(e-mail address removed)>, (e-mail address removed)
says...

[ ... ]

Which supposes that if it returns false, they probably can't be.

I think it does more than suppose -- 'iff' (at least normally) means "if
and only if"...

Yep. I missed the second f in iff.

It means exactly what's said above, nothing more.

If == must return true, then it doesn't mean anything. If an
implementation doesn't use it, always assuming it returns true,
then it doesn't mean anything.

At least the implementation must document its choice (good luck
finding that documentation, though), and it's not unlimited.

[ ... ]

In sum, if an implementation decides to support non-equal
allocators, it is free to choose: require them to support swap
(possibly by having a no-throw copy constructor and assignment
operator, so that std::swap will work), accept that swap might
throw if the allocators are not equal (along the lines of
Compare), or accept that swap is not constant time if the
allocators are not equal.

Right -- your last point (possible O(N) swap) comes back to a
fundamental question of what it means to swap containers: does it just
mean swapping their contents, or does it also mean swapping their
allocators?

If it just means swapping their contents, I don't think the
possibility of non-constant time is an "or" -- I think it's
linear time AND you face the possibility of an exception (if
either allocator throws).

Exactly. That's why I tend to favor the idea that swapping
containers means swapping their allocators as well.

 

[Jerry Coffin]

[ Allocator instances ]

If == must return true, then it doesn't mean anything. If an
implementation doesn't use it, always assuming it returns true,
then it doesn't mean anything.

Yes and no. A container implementation is free to assume that it returns
true, in which case you're right, at least for use with the standard
containers in that implementation, it's basically pointless.

OTOH, you can use non-equal allocators, as long as you don't care about
portability to implementations that don't support it. You can also
create your own container classes that support non-equal allocators,
even if the ones supplied by your standard library vendor don't.

OTOH, if your interest is exclusively in writing code that will work
with essentially any standard library implementation, then operator== is
pretty well pointless, because it's always going to return true.

[ ... ]

Exactly. That's why I tend to favor the idea that swapping
containers means swapping their allocators as well.

That certainly seems like what I'd do in any case.

 

[Jerry Coffin]

Right, I wasn't aware that it was actually a requirement. I guess that
applies to every container, then (I can't think why it shouldn't).

I believe that's correct, yes.