Issue 431: Swapping containers with unequal allocators

This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of Resolved status.

431. Swapping containers with unequal allocators

Section: 16.4.4.6 [allocator.requirements], 26 [algorithms] Status: Resolved Submitter: Matt Austern Opened: 2003-09-20 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [allocator.requirements].

View all other issues in [allocator.requirements].

View all issues with Resolved status.

Discussion:

Clause 16.4.4.6 [allocator.requirements] paragraph 4 says that implementations are permitted to supply containers that are unable to cope with allocator instances and that container implementations may assume that all instances of an allocator type compare equal. We gave implementers this latitude as a temporary hack, and eventually we want to get rid of it. What happens when we're dealing with allocators that don't compare equal?

In particular: suppose that v1 and v2 are both objects of type vector<int, my_alloc> and that v1.get_allocator() != v2.get_allocator(). What happens if we write v1.swap(v2)? Informally, three possibilities:

1. This operation is illegal. Perhaps we could say that an implementation is required to check and to throw an exception, or perhaps we could say it's undefined behavior.

2. The operation performs a slow swap (i.e. using three invocations of operator=, leaving each allocator with its original container. This would be an O(N) operation.

3. The operation swaps both the vectors' contents and their allocators. This would be an O(1) operation. That is:

    my_alloc a1(...);
    my_alloc a2(...);
    assert(a1 != a2);

    vector<int, my_alloc> v1(a1);
    vector<int, my_alloc> v2(a2);
    assert(a1 == v1.get_allocator());
    assert(a2 == v2.get_allocator());

    v1.swap(v2);
    assert(a1 == v2.get_allocator());
    assert(a2 == v1.get_allocator());

[Kona: This is part of a general problem. We need a paper saying how to deal with unequal allocators in general.]

[pre-Sydney: Howard argues for option 3 in N1599. ]

[ 2007-01-12, Howard: This issue will now tend to come up more often with move constructors and move assignment operators. For containers, these members transfer resources (i.e. the allocated memory) just like swap. ]

[ Batavia: There is agreement to overload the container swap on the allocator's Swappable requirement using concepts. If the allocator supports Swappable, then container's swap will swap allocators, else it will perform a "slow swap" using copy construction and copy assignment. ]

[ 2009-04-28 Pablo adds: ]

Fixed in N2525. I argued for marking this Tentatively-Ready right after Bellevue, but there was a concern that N2525 would break in the presence of the RVO. (That breakage had nothing to do with swap, but never-the-less). I addressed that breakage in in N2840 (Summit) by means of a non-normative reference:

[Note: in situations where the copy constructor for a container is elided, this function is not called. The behavior in these cases is as if select_on_container_copy_construction returned x — end note]

[ 2009-10 Santa Cruz: ]

~~NAD Editorial~~Resolved. Addressed by N2982.

Proposed resolution: