2076. Bad CopyConstructible requirement in set constructors

Section: 26.4.6.2 [set.cons] Status: C++17 Submitter: Jens Maurer Opened: 2011-08-20 Last modified: 2017-07-30

Priority: 3

View all issues with C++17 status.

Discussion:

26.4.6.2 [set.cons] paragraph 4 says:

Requires: If the iterator's dereference operator returns an lvalue or a non-const rvalue, then Key shall be CopyConstructible.

I'm confused why a "non-const rvalue" for the return value of the iterator would require CopyConstructible; isn't that exactly the situation when you'd want to apply the move constructor?

The corresponding requirement for multimap seems better in that regard ([multimap.cons] paragraph 3):

Requires: If the iterator's dereference operator returns an lvalue or a const rvalue pair<key_type, mapped_type>, then both key_type and mapped_type shall be CopyConstructible.

Obviously, if I have a const rvalue, I can't apply the move constructor (which will likely attempt modify its argument).

Dave Abrahams:

I think you are right. Proposed resolution: drop "non-" from 26.4.6.2 [set.cons] paragraph 3.

[2012, Kona]

The wording is in this area will be affected by Pablo's paper being adopted at this meeting. Wait for that paper to be applied before visiting this issue - deliberately leave in New status until the next meeting.

Proposed resolution from Kona 2012:

This wording is relative to the FDIS.

Change 26.4.6.2 [set.cons] p3 as follows:

template <class InputIterator>
  set(InputIterator first, InputIterator last,
    const Compare& comp = Compare(), const Allocator& = Allocator());

-3- Effects: Constructs an empty set using the specified comparison object and allocator, and inserts elements from the range [first,last).

-4- Requires: If the iterator's dereference operator returns an lvalue or a non-const rvalue, then Key shall be CopyConstructible.

-5- Complexity: Linear in N if the range [first,last) is already sorted using comp and otherwise N logN, where N is last - first.

[2014-05-18, Daniel comments]

According to Pablo, the current P/R correctly incorporates the changes from his paper (which was adopted in Kona)

[2014-06-10, STL comments and suggests better wording]

N1858 was voted into WP N2284 but was "(reworded)", introducing the "non-const" damage.

N1858 wanted to add this for map:

Requires: Does not require CopyConstructible of either key_type or mapped_type if the dereferenced InputIterator returns a non-const rvalue pair<key_type, mapped_type>. Otherwise CopyConstructible is required for both key_type and mapped_type.

And this for set:

Requires: Key must be CopyConstructible only if the dereferenced InputIterator returns an lvalue or const rvalue.

(And similarly for multi.)

This was reworded to N2284 23.3.1.1 [map.cons]/3 and N2284 23.3.3.1 [set.cons]/4, and it slightly changed over the years into N3936 23.4.4.2 [map.cons]/3 and N3936 23.4.6.2 [set.cons]/4.

In 2005/2007, this was the best known way to say "hey, we should try to move this stuff", as the fine-grained element requirements were taking shape.

Then in 2010, N3173 was voted into WP N3225, adding the definition of EmplaceConstructible and modifying the container requirements tables to make the range constructors require EmplaceConstructible.

After looking at this history and double-checking our implementation (where map/set range construction goes through emplacement, with absolutely no special-casing for map's pairs), I am convinced that N3173 superseded N1858 here. (Range-insert() and the unordered containers are unaffected.)

Previous resolution [SUPERSEDED]:

This wording is relative to the N3936.

Change 26.4.6.2 [set.cons] p4 as follows:

template <class InputIterator>
  set(InputIterator first, InputIterator last,
    const Compare& comp = Compare(), const Allocator& = Allocator());

-3- Effects: Constructs an empty set using the specified comparison object and allocator, and inserts elements from the range [first,last).

-4- Requires: If the iterator's indirection operator returns an lvalue or a non-const rvalue, then Key shall be CopyInsertible into *this.

-5- Complexity: Linear in N if the range [first,last) is already sorted using comp and otherwise N logN, where N is last - first.

[2015-02 Cologne]

GR: Do requirements supersede rather than compose [container requirements and per-function requirements]? AM: Yes, they supersede.

AM: This looks good. Ready? Agreement.

Proposed resolution:

This wording is relative to the N4296.

  1. Remove 26.4.4.2 [map.cons] p3:

    template <class InputIterator>
      map(InputIterator first, InputIterator last,
          const Compare& comp = Compare(), const Allocator& = Allocator());
    

    -3- Requires: If the iterator's indirection operator returns an lvalue or a const rvalue pair<key_type, mapped_type>, then both key_type and mapped_type shall be CopyInsertible into *this.

    […]

  2. Remove 26.4.5.2 [multimap.cons] p3:

    template <class InputIterator>
      multimap(InputIterator first, InputIterator last,
               const Compare& comp = Compare(), 
               const Allocator& = Allocator());
    

    -3- Requires: If the iterator's indirection operator returns an lvalue or a const rvalue pair<key_type, mapped_type>, then both key_type and mapped_type shall be CopyInsertible into *this.

    […]

  3. Remove 26.4.6.2 [set.cons] p4:

    template <class InputIterator>
      set(InputIterator first, InputIterator last,
          const Compare& comp = Compare(), const Allocator& = Allocator());
    

    […]

    -4- Requires: If the iterator's indirection operator returns an lvalue or a non-const rvalue, then Key shall be CopyInsertible into *this.

  4. Remove 26.4.7.2 [multiset.cons] p3:

    template <class InputIterator>
      multiset(InputIterator first, InputIterator last,
               const Compare& comp = Compare(), 
               const Allocator& = Allocator());
    

    -3- Requires: If the iterator's indirection operator returns an lvalue or a const rvalue, then Key shall be CopyInsertible into *this.

    […]