Again a simple question about std::vector

Discussion in 'C++' started by ciccio, Apr 3, 2008.

  1. ciccio

    ciccio Guest

    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, Apr 3, 2008
    #1
    1. Advertising

  2. 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
    Victor Bazarov, Apr 3, 2008
    #2
    1. Advertising

  3. ciccio

    Lionel B Guest

    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
    Lionel B, Apr 3, 2008
    #3
  4. ciccio

    Jerry Coffin Guest

    In article <ft2ck5$2j4$>,
    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.
    Jerry Coffin, Apr 3, 2008
    #4
  5. ciccio

    Lionel B Guest

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

    > In article <ft2ck5$2j4$>,
    > 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
    Lionel B, Apr 3, 2008
    #5
  6. ciccio

    James Kanze Guest

    On 3 avr, 16:14, Jerry Coffin <> wrote:
    > In article <ft2ck5$>,
    > 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:
    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
    James Kanze, Apr 3, 2008
    #6
  7. ciccio

    Jerry Coffin Guest

    In article <63812246-421c-4c54-b5f7-
    >, 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.
    Jerry Coffin, Apr 4, 2008
    #7
  8. ciccio

    James Kanze Guest

    On Apr 4, 6:54 am, Jerry Coffin <> wrote:
    > In article <63812246-421c-4c54-b5f7-
    > >, 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:
    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
    James Kanze, Apr 4, 2008
    #8
  9. ciccio

    Jerry Coffin Guest

    In article <ae8a0320-d323-4efc-9433-
    >,
    says...
    > On Apr 4, 6:54 am, Jerry Coffin <> 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.
    Jerry Coffin, Apr 5, 2008
    #9
  10. ciccio

    James Kanze Guest

    On 5 avr, 02:10, Jerry Coffin <> wrote:
    > In article <ae8a0320-d323-4efc-9433-
    > >,
    > says...


    > > On Apr 4, 6:54 am, Jerry Coffin <> 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:
    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
    James Kanze, Apr 5, 2008
    #10
  11. ciccio

    Jerry Coffin Guest

    In article <98c82a92-ed6a-4cb9-916d-ca7132ba40e9
    @s50g2000hsb.googlegroups.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.
    Jerry Coffin, Apr 6, 2008
    #11
  12. ciccio

    Jerry Coffin Guest

    In article <ft2qiv$d07$>, 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.
    Jerry Coffin, Apr 7, 2008
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Peter Jansson
    Replies:
    5
    Views:
    6,271
    Ivan Vecerina
    Mar 17, 2005
  2. Anonymous
    Replies:
    20
    Views:
    4,274
    Pete Becker
    Mar 30, 2005
  3. Jason Heyes
    Replies:
    8
    Views:
    709
    Andrew Koenig
    Jan 15, 2006
  4. Replies:
    8
    Views:
    1,895
    Csaba
    Feb 18, 2006
  5. Rune Allnor
    Replies:
    4
    Views:
    928
    Rune Allnor
    Dec 11, 2008
Loading...

Share This Page