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

ciccio wrote:
> 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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

On Thu, 03 Apr 2008 12:47:32 +0200, ciccio wrote:

> 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."

--
Lionel B

In article <ft2ck5$2j4$1@ikaria.belnet.be>, no_valid_email@spam.com
says...
> 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).

--
Later,
Jerry.

The universe is a figment of its own imagination.

On Thu, 03 Apr 2008 08:14:18 -0600, Jerry Coffin wrote:

> In article <ft2ck5$2j4$1@ikaria.belnet.be>, no_valid_email@spam.com
> says...
>> 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).

--
Lionel B

On 3 avr, 16:14, Jerry Coffin <jcof...@taeus.com> wrote:
> In article <ft2ck5$2j...@ikaria.belnet.be>, no_valid_em...@spam.com
> says...
> > 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).

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?

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

In article <63812246-421c-4c54-b5f7-
5429442cca7b@b5g2000pri.googlegroups.com>, james.kanze@gmail.com says...

[ ... ]

> 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.

--
Later,
Jerry.

The universe is a figment of its own imagination.

On Apr 4, 6:54 am, Jerry Coffin <jcof...@taeus.com> wrote:
> In article <63812246-421c-4c54-b5f7-
> 5429442cc...@b5g2000pri.googlegroups.com>, james.ka...@gmail.com says...

> [ ... ]

> > 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."

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

> > 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.

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
probably go with the second, that vector<>::swap might throw if
the allocators are unequal and swapping them throws.)

> > 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.

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

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

In article <ae8a0320-d323-4efc-9433-
b76e17b4bc4f@u69g2000hse.googlegroups.com>, james.kanze@gmail.com
says...
> On Apr 4, 6:54 am, Jerry Coffin <jcof...@taeus.com> wrote:

[ ... ]

> > 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.

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


> > 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.

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).

--
Later,
Jerry.

The universe is a figment of its own imagination.

On 5 avr, 02:10, Jerry Coffin <jcof...@taeus.com> wrote:
> In article <ae8a0320-d323-4efc-9433-
> b76e17b4b...@u69g2000hse.googlegroups.com>, james.ka...@gmail.com
> says...

> > On Apr 4, 6:54 am, Jerry Coffin <jcof...@taeus.com> wrote:

> [ ... ]
> > > 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.

> 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 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.

> 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.

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

In article <98c82a92-ed6a-4cb9-916d-ca7132ba40e9
@s50g2000hsb.googlegroups.com>, james.kanze@gmail.com says...

[ 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.

[ ... ]

> > 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.

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

--
Later,
Jerry.

The universe is a figment of its own imagination.

In article <ft2qiv$d07$2@south.jnrs.ja.net>, me@privacy.net says...

[ ... ]

> > 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).

I believe that's correct, yes.

--
Later,
Jerry.

The universe is a figment of its own imagination.