Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Again a simple question about std::vector

Reply
Thread Tools

Again a simple question about std::vector

 
 
ciccio
Guest
Posts: n/a
 
      04-03-2008
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
 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      04-03-2008
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


 
Reply With Quote
 
 
 
 
Lionel B
Guest
Posts: n/a
 
      04-03-2008
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
 
Reply With Quote
 
Jerry Coffin
Guest
Posts: n/a
 
      04-03-2008
In article <ft2ck5$2j4$(E-Mail Removed)>, http://www.velocityreviews.com/forums/(E-Mail Removed)
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.
 
Reply With Quote
 
Lionel B
Guest
Posts: n/a
 
      04-03-2008
On Thu, 03 Apr 2008 08:14:18 -0600, Jerry Coffin wrote:

> In article <ft2ck5$2j4$(E-Mail Removed)>, (E-Mail Removed)
> 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
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      04-03-2008
On 3 avr, 16:14, Jerry Coffin <(E-Mail Removed)> wrote:
> In article <ft2ck5$(E-Mail Removed)>, (E-Mail Removed)
> 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:(E-Mail Removed)
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
 
Reply With Quote
 
Jerry Coffin
Guest
Posts: n/a
 
      04-04-2008
In article <63812246-421c-4c54-b5f7-
(E-Mail Removed)>, (E-Mail Removed) 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.
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      04-04-2008
On Apr 4, 6:54 am, Jerry Coffin <(E-Mail Removed)> wrote:
> In article <63812246-421c-4c54-b5f7-
> (E-Mail Removed)>, (E-Mail Removed) 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:(E-Mail Removed)
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
 
Reply With Quote
 
Jerry Coffin
Guest
Posts: n/a
 
      04-05-2008
In article <ae8a0320-d323-4efc-9433-
(E-Mail Removed)>, (E-Mail Removed)
says...
> On Apr 4, 6:54 am, Jerry Coffin <(E-Mail Removed)> 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.
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      04-05-2008
On 5 avr, 02:10, Jerry Coffin <(E-Mail Removed)> wrote:
> In article <ae8a0320-d323-4efc-9433-
> (E-Mail Removed)>, (E-Mail Removed)
> says...


> > On Apr 4, 6:54 am, Jerry Coffin <(E-Mail Removed)> 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:(E-Mail Removed)
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Again??? AGAIN???? NYC XYZ Firefox 4 04-23-2006 12:23 PM
HttpSession gets generated again and again!! PLEASE HELP ME!!!! che Java 2 10-10-2005 10:20 PM
A simple question turns into badgering.....again Richard HTML 18 10-21-2003 06:27 AM
jserve booting again and again amit Java 0 10-02-2003 04:26 PM
IMPORTANT! Changes to your Cable Internet Service (again & again) Charlie Computer Support 4 07-17-2003 01:18 AM



Advertisments