C++ Concepts Defect Report List (Revision C5)

Also see:

• Table of Contents for all concepts issues.
• Index by Section for all concepts issues.
• Index by Status for all concepts issues.
• Concepts Active Issues List
• Concepts Closed Issues List

This document contains only concepts issues which have been closed after being found to be defects in the proposal. That is, issues which have a status of WP. See the Concepts Closed Issues List for issues closed as non-defects. See the Concepts Active Issues List for active issues and more information. The introductory material in that document also applies to this document.

Revision History

• C5: Companion to the concepts proposals in the pre-San Francisco mailing. (25 August 2008)
• C4: Companion to the concepts proposals in the post-Antipolis mailing. (30 June 2008)
• C3: Companion to the concepts proposals in the pre-Sophia-Antipolis mailing. (19 May 2008)
• C2: Companion to the concepts proposals in the Post-Bellevue mailing. (25 Mar 2008)
• C1: Initial version. (3 Mar 2008)

Defect Reports

1. Naming and symmetry in EqualityComparable

Section: 20.1.2 [concept.comparison] Status: WP Submitter: LWG Date: 2008-02-27

View all issues with WP status.

Discussion:

Another way to characterize the problem with EqualityComparable: the name suggests that it's a concept with semantics, one that's based on some kind of mathematical notion. At the Bloomington discussion there was a different naming convention for concepts that are purely syntactic; e.g. HasPlus, as opposed to "Addable", for a concept that doesn't mean anything more than that a + exists. The two-parameter EqualityComparable really falls into that category, since all it really means is that there's some kind of operation spelled == and we're not saying what it does. The one-parameter version of EqualityComparable really is EqualityComparable, though, and it does have mathematical axioms.

General issue: do we accept the naming convention that purely syntactic concepts should be named Has*?

If we do have a two-parameter HasEqualTo, do we also want it to provide != ? In other words, does it have any kind of semantic coherency?

Can we make the two-parameter HasEqualTo symmetrical? That is: if we say that there is a HasEqualTo for types T and U, and if t and u are variables of the appropriate types, can we at least say that t == u and u == t are both allowed and both mean the same thing? Is there any way to write defaults in the concept definition that won't ever give us an infinite loop?

Proposed resolution:

Split the EqualityComparable and LessThanComparable concepts into purely syntactic concepts (HasEqualTo, HasLessThan) and semantic concepts that refine them (EqualityComparable, LessThanComparable). In [utility.concepts], update the <concepts> header synopsis as follows:

// 20.1.2, comparisons:
auto concept LessThanComparable<typename T, typename U = T> see below;
auto concept EqualityComparable<typename T, typename U = T> see below;
auto concept TriviallyEqualityComparable<typename T> see below; 

...
// 20.1.10, operator concepts:
...

auto concept HasNegate<typename T> see below;
auto concept HasLess<typename T, typename U = T> see below;
auto concept HasEqualTo<typename T, typename U = T> see below;
auto concept HasLogicalAnd<typename T, typename U = T> see below;
      

Change [concept.comparison] paragraph 1 as follows:

auto concept LessThanComparable<typename T, typename U = T> : HasLess<T> { 
  bool operator<(T const& a, U const& b);
  bool operator>(UT const& a, T const& b) { return b < a; } 
  bool operator<=(UT const& a, T const& b) { return !(b < a); } 
  bool operator>=(T const& a, UT const& b) { return !(a < b); } 

  axiom Consistency(T a, T b) {
    (a > b) == (b < a);
    (a <= b) == !(b < a);
    (a >= b) == !(a < b);
  }

  axiom Irreflexivity(T a) { (a < a) == false; }

  axiom Antisymmetry(T a, T b) { 
    if (a < b) (b < a) == false;
  }

  axiom Transitivity(T a, T b, T c) {
    if (a < b && b < c) (a < c) == true;
  }

  axiom TransitivityOfEquivalence(T a, T b, T c) {
    if (!(a < b) && !(b < a) && !(b < c) && !(c < b))
      (!(a < c) && !(c < a)) == true;
  } 
}
    

1.     Note: describes types whose values can be ordered via an inequality operator, where operator< is a strict weak ordering relation ([alg.sorting]).
2.     Requires: operator< is a strict weak ordering relation ([alg.sorting]).

Change [concept.comparison] paragraphs 3 and 4 as follows:

auto concept EqualityComparable<typename T, typename U = T> : HasEqualTo<T> { 
 bool operator==(T const& a, U const& b); 
 bool operator!=(T const& a, UT const& b) { return !(a == b); } 

  axiom Consistency(T a, T b) {
    (a == b) == !(a != b);
  }

  axiom Reflexivity(T a) { a == a; }

  axiom Symmetry(T a, T b) { if (a == b) b == a; }

  axiom Transitivity(T a, T b, T c) {
    if (a == b && b == c) a == c;
  }
}
      

3.     Note: describes types whose values can be compared for equality with operator==, which is an equivalence relation.
4.     Requires: when T and U are identical, operator== is an equivalence relation that is, it has the following properties:
   • For all a, a == a.
   • If a == b, then b == a.
   • If a == b and b == c, then a == c.

Add to [concept.operator]:

auto concept HasLess< typename T, typename U = T> {
  bool operator<(const T& a, const U& b);
}
      

8.     Note: describes types with an operator<

auto concept HasEqualTo< typename T, typename U = T> {
  bool operator==(const T& a, const U& b);
}
      

9.     Note: describes types with an operator==

Note that this change also requires renaming two-parameter uses of EqualityComparable and LessThanComparable to HasEqualTo and HasLess, respectively.

2. Requires clause for Destructible is unclear

Section: 20.1.3 [concept.destruct] Status: WP Submitter: LWG Date: 2008-02-27

View all issues with WP status.

Discussion:

What does the Requires clause for Destructible actually mean? "All resources owned by the object" is either false (what about a type with a pointer member variable that doesn't call delete in the destructor?) or vacuous (if you define "owned" resources precisely as the resources that are relinquished in the destructor). This is probably another purely syntactic concept: a type that you can use as the target of a pseudo destructor call, or something like that. If we do believe that this is a purely syntactic construct then we might want to consider renaming it as HasDestructor.

Doug Gregor: the requirements on the destructor come directly from the corresponding table in the pre-concepts Working Paper, so this issue wasn't introduced by concepts.

Proposed resolution:

The vacuous sentence has been removed.

3. Naming of Constructible/DefaultConstructible concepts

Section: 20.1.4 [concept.construct] Status: WP Submitter: LWG Date: 2008-02-27

View all other issues in [concept.construct].

View all issues with WP status.

Discussion:

Constructible and DefaultConstructible don't have any semantics, so they should have the prefix Has.

Doug Gregor: DefaultConstructible does have some (admittedly weak) semantics regarding what it does, and the name itself is part of the vocabulary of generic programming, so I suggest we keep it.

Proposed resolution:

Rename Constructible to HasConstructor.

In [concept.construct], change paragraph 2 as follows:

2.     Note: describes types that can be default-constructedfor which an object can be constructed without initializing the object to any particular value.

4. MoveConstructible should refine Constructible

Section: 20.1.5 [concept.copymove] Status: WP Submitter: LWG Date: 2008-02-27

View all other issues in [concept.copymove].

View all issues with WP status.

Discussion:

We should consider saying that MoveConstructible is a refinement of an appropriate specialization of Constructible, not just Destructible. Specifically, one would think that MoveConstructible<T> is a refinement of Constructible<T, T&&>. In that case, the body of MoveConstructible would go away.

Proposed resolution:

In [concept.copymove] paragraph 1, change as follows:

auto concept MoveConstructible<typename T> : Constructible<T, T&&>, Destructible<T> { 
  T::T(T&&);
} 

In [concept.copymove] paragraph 3, change as follows:

  auto concept CopyConstructible<typename T> : MoveConstructible<T>, Constructible<T, const T&> { 
  T::T(const T&);

  axiom CopyPreservation(T x) { 
    T(x) == x; 
  } 
}

5. Inconsistent naming between concepts and type traits

Section: 20.1 [utility.concepts] Status: WP Submitter: LWG Date: 2008-02-27

View all other issues in [utility.concepts].

View all issues with WP status.

Discussion:

General issue: many of these core concepts, including CopyConstructible, TriviallyCopyConstructible, and ObjectType, mirror existing type traits names. Essentially, type traits are a mechanism used in unconstrained templates and concepts express something very similar in constrained code. We should consider a uniform naming convention, in places where the correspondence exists, to make the connection clearer. This is one motivation for using Has* and Is* uniformly.

Proposed resolution:

The table provides the mapping between type traits and concepts. Any insertions or deletions indicate changes proposed as part of this issue.

6. MoveAssignable assignment operator is incorrect

Section: 20.1.5 [concept.copymove] Status: WP Submitter: LWG Date: 2008-02-27

View all other issues in [concept.copymove].

View all issues with WP status.

Discussion:

Editorial issue in MoveAssignable: the function signature is different in the concept synopsis than it is in paragraph 6, and inconsistent with CopyAssignable

Proposed resolution:

Update the definition of MoveAssignable in paragraph 6 of N2502 as follows:

auto concept MoveAssignable<typename T, typename U = T> { 
  typename result_type; 
  result_type T::operator=(T&, U&&); 
}

9. Memory-allocation concepts are too fine-grained

Section: 20.1.6 [concept.memory] Status: WP Submitter: LWG Date: 2008-02-27

View all issues with WP status.

Discussion:

Newable and Deletable and HeapAllocatable are awfully fine grained and low level. Can we get rid of them, or at least consolidate them? Yes, it's possible to write types that can be created on the stack but not with new, but do our library algorithms really need to distinguish between constructable, new-able, and heap-allocatable?

Proposed resolution:

In [concept.memory], remove paragraphs 1-4 (describing the Newable, Deletable, ArrayNewable, and ArrayDeletable concepts). Change the HeapAllocatable concept as follows:

auto concept HeapAllocatable<typename T>
  : Newable<T>, Deletable<T>, ArrayNewable<T>, ArrayDeletable<T> { 
  void* T::operator new(size_t size);
  void* T::operator new(size_t size, void*);
  void* T::operator new[](size_t size);
  void T::operator delete(void*);
  void T::operator delete[](void*);
}
  

10. Remarks should be notes

Section: 20.1 [utility.concepts] Status: WP Submitter: LWG Date: 2008-02-27

View all other issues in [utility.concepts].

View all issues with WP status.

Discussion:

General semi-editorial issue: almost all of the "Remarks" are actually notes. This is obviously true in the case of Semiregular, for example. Note: this was due to a misunderstanding of the LaTeX macros, because these were all intended to be notes. Considered an editorial issue.

Proposed resolution:

Replace all "Remark"s in the paper with "Note"s.

12. Update operator concepts based on "Option #2" change in language specification

Section: 20.1.10 [concept.operator] Status: WP Submitter: LWG Date: 2008-02-27

View all other issues in [concept.operator].

View all issues with WP status.

Discussion:

In light of Tuesday night's "option 2" change, all of the operator concepts in 20.1.10 need to have three of the four signatures removed.

Proposed resolution:

Change all of the operator concepts in the same way as we're changing HasPlus, as follows:

auto concept HasPlus<typename T, typename U = T> { 
  typename result_type; 
  result_type operator+(T const&, U const&); 
  result_type operator+(T const&, U &&); 
  result_type operator+(T &&, U const&); 
  result_type operator+(T &&, U &&); 
}

13. Naming consistency in [concept.operator]

Section: 20.1.10 [concept.operator] Status: WP Submitter: LWG Date: 2008-02-27

View all other issues in [concept.operator].

View all issues with WP status.

Discussion:

Slightly substantive issue: we should consider reviewing the names in 20.1.10 for consistent style. One suggestion is making them consistent with the names of the function objects in 20.5. (Except that some people would like HasModulus to have a different name, since x%y isn't strictly speaking the mathematical mod operation, even though the current name is consistent with the 20.5 name std::modulus. So either that would be an exception to the goal of consistency with 20.5, or it means we need to look for a different naming convention.)

Proposed resolution:

The following table provides the names of operators, the function objects associated with that name in the <functional> header, and the proposed concept name.

14. Addressable and const types

Section: 20.1.10 [concept.operator] Status: WP Submitter: LWG Date: 2008-02-27

View all other issues in [concept.operator].

View all issues with WP status.

Discussion:

What does Addressable mean for const types? e.g. what happens if you have a constrained template with requires Addressable<const T>? Is the answer just "don't do that"? Perhaps there should only be one typedef here, not two, and it should be called result_type. Ditto for Dereferenceable.

Proposed resolution:

auto concept Addressable<typename T> { 
  typename pointer; 
  typename const_pointer;
  pointer operator&(T&); 
  const_pointer operator&(const T&); 
}

15. Can Callable's function object be an rvalue?

Section: 20.1.10 [concept.operator] Status: WP Submitter: LWG Date: 2008-02-27

View all other issues in [concept.operator].

View all issues with WP status.

Discussion:

In Callable: can the F, the first argument of operator(), be an rvalue? If so, what's the language rule that gives us a yes answer? If not, is it ok to rule that out? (General theme for many of our questions: what is the criterion we use, when we define a concept, to decide whether the concept's functions should take their argument by value, by const reference, by non-const reference, by rvalue reference, or whatever?)

Note: The function object cannot be an rvalue.

Proposed resolution:

Modify the definition of the Callable concept as follows:

auto concept Callable<typename F, typename... Args> { 
  typename result_type; 
  result_type operator()(F&&, Args...); 
} 
  

17. Errors in Allocator concept

Section: 20.1.13 [concept.allocator] Status: WP Submitter: LWG Date: 2008-02-27

View all issues with WP status.

Discussion:

Allocator, since pointer is required to be convertible to value_type*, the required convertibility to void* is superfluous. Ditto for const_pointer to const void *. Also, there is a typo in requires Convertible<const_pointer, const value_type&>. Should be requires Convertible<const_pointer, const value_type*>.

In specification of Allocator::construct just above 20.1.3 para 11, error requires Constructible<value_type, V&&> should be requires Convertible<V, value_type> as in the synopsis.

Proposed resolution:

In [concept.allocator] paragraph 2, change the associated requirements of the Allocator concept as follows:

concept Allocator<typename X> : DefaultConstructible<X>, CopyConstructible<X> {
  // ...
  requires Convertible<pointer, const_pointer> && 
    Convertible<pointer, void*> &&
    Convertible<pointer, value_type*> && 
    SameType<pointer::value_type, value_type> && 
    SameType<pointer::reference, value_type&> && 
    SameType<pointer::reference, reference>; 
  requires Convertible<const_pointer, const void*> &&
    Convertible<const_pointer, const value_type&*;> && 
    SameType<const_pointer::value_type, value_type> && 
    SameType<const_pointer::reference, const value_type&> && 
    SameType<const_pointer::reference, const_reference>;
}
    

Change [concept.allocator] paragraph 11 as follows:

template<typename V>
  requires Constructible<value_type, V&&>
  void X::construct(pointer p, V&&);
    

18. Consistent naming for concepts headers

Section: 24.1 [iterator.concepts] Status: WP Submitter: LWG Date: 2008-02-28

View all other issues in [iterator.concepts].

View all issues with WP status.

Discussion:

Should <iterator_concepts> and <iterator> be different headers? Probably. It's nice to be able to write constrained templates without pulling in all of <iostream>, for example. On the other hand, which header should things like std::iterator and std::forward_iterator_tag go in? Also, at a higher level, some consistent naming or locating policy should be firmly established so that random number concepts, iterator concepts, and other concepts all are coherent.

Proposed resolution:

Use the header <foo_concepts> for the concepts relating to a particular part of the library (iterators, containers, etc).

19. IteratorBase is an implementation detail

Section: 24.1 [iterator.concepts] Status: WP Submitter: LWG Date: 2008-02-28

View all other issues in [iterator.concepts].

View all issues with WP status.

Discussion:

We're not very happy about IteratorBase. It doesn't seem like anything that anyone would ever want to constrain a template on; there's no text following its definition to say what it is and what it's for; it appears unused except as, well, a base; it seems more like a macro to save a few lines of typing in the real concepts. Can we get rid of it? Or can we strengthen it into TrivialIterator and base all other iterator concepts on TrivialIterator instead?

Proposed resolution:

In [iterator.concepts], remove the IteratorBase concept from the synopsis (in paragraph 1) and from paragraph 2.

In [input.iterators], change the InputIterator concept as follows:

concept InputIterator<typename X> : IteratorBase<X>, Semiregular<X>, EqualityComparable<X> { 
  typename value_type = typename X::value_type;
  MoveConstructible reference = typename X::reference; 
  MoveConstructible pointer = typename X::pointer;

  // ...
}
  

In [output.iterators], change the BasicOutputIterator concept as follows:

concept BasicOutputIterator<typename X> : IteratorBase<X>, CopyConstructible<X> { 
  typename value_type = typename X::value_type;
  MoveConstructible reference = typename X::reference; 

  // ...
}
  

In [forward.iterators], modify the MutableForwardIterator concept definition as follows:

concept MutableForwardIterator<typename X> : ForwardIterator<X>, BasicOutputIterator<X> { 
  requires SameType<ForwardIterator<X>::value_type, BasicOutputIterator<X>::value_type> &&
           SameType<ForwardIterator<X>::reference, BasicOutputIterator<X>::reference>;
} 
  

22. Oddly-placed and missing InputIterator requirements

Section: 24.1.1 [input.iterators] Status: WP Submitter: LWG Date: 2008-02-28

View all other issues in [input.iterators].

View all issues with WP status.

Discussion:

24.1.1 paragraphs 8 and 9 seem very oddly placed. They seem to be discussing the semantics of operator==, but textually they appear to be underneath the signature for operator->. This is probably a purely editorial issue. Another purely editorial issue: "any" should be capitalized at the beginning of the second sentence of paragraph 11.

There's something missing in 24.1.1. The semantics of *r++ has gotten lost in the shuffle. The old requirements table said that *r++ gave us the value we would have gotten before the increment, but the n2500 version doesn't say that. Based on the words in n2500, all we really know about *r++ is that it returns some unspecified value that's convertible to value_type. Similar issues apply in OutputIterator.

Proposed resolution:

Add the following at the beginning of [input.iterators]p8:

bool operator==(X const& a, X const& b); // inherited from EqualityComparable<X>
  

Change [input.iterators]p12 as follows:

12.     Effects: ++requivalent to { T tmp = *r; ++r; return tmp; }

23. Output iterators without value types

Section: 24.1.2 [output.iterators] Status: WP Submitter: LWG Date: 2008-02-28

View all issues with WP status.

Discussion:

24.1.2 preserves the C++03 notion that output iterators don't actually have value types (see, for example, 24.1.2 paragraph 3, saying that an output iterator may permit output of many different value types). Is this something we really want to preserve for conceptized C++09? There are a few real-world output iterators that support multiple output types, but very few. For most users, the fact that we don't have a specific output types is much more a nuisance than anything else. This is another issue where we have a choice between rationalizing the current requirements or preserving them in every last corner case, and we should consider doing the former. Concretely, in terms of the n2500 notation: most users probably want to use the BasicOutputIterator concept, not OutputIterator. We should consider renaming BasicOutputIterator to OutputIterator, and either getting rid of the concept that n2500 calls OutputIterator or renaming it to BackwardCompatibilityOutputIteratorWithoutValueType.

Doug Gregor: Note that the output iterator without a value type (currently called OutputIterator) is used by many of the algorithms in chapter 25. In fact, none of these algorithms use BasicOutputIterator (the one that has a value type). It would be a shame for all of our algorithms to have a name like BackwardCompatibilityOutputIteratorWithoutValueType in their requires clauses. Changing these algorithms to use the output iterator with a value type (currently called BasicOutputIterator) would break backward compatibility significantly, and is therefore probably not feasible.

Proposed resolution:

BasicOutputIterator has been removed with the latest refactoring of the iterator taxonomy.

25. Lost normative semantics of ForwardIterator

Section: 24.1.3 [forward.iterators] Status: WP Submitter: LWG Date: 2008-02-28

View all issues with WP status.

Discussion:

We seem to have lost all normative text that describes the semantics of forward iterators. Some of the semantics from table 98 have just disappeared, and the n2500 text has very little to say about substantive ways in which constant forward iterators differ from input iterators. We've lost the requirement that r == s implies ++r == ++s. (It now appears only in nonnormative text.) There's nothing saying that forward iterators are allowed to be multipass. Forward iterators are a good use case for the axiom feature.

One of the other important axioms for forward iterators is that a == b iff *a and *b are the same object. This axiom got moved to input iterators (but not using the axiom feature), where it does not belong. That assertion is not true for input iterators in general, or for some of the specific input iterators in the standard. What's novel about forward iterators, as opposed to input iterators, is that a forward iterator points to a specific memory location.

Proposed resolution:

In [forward.iterators], add the following new paragraph:

    X::X(); // inherited from Regular<X>
  

1.     Note: the constructed object might have a singular value.

In [input.iterators], remove paragraph 9:

9.     If two iterators a and b of the same type are both dereferenceable, then a == b if and only if *a and *b are the same object.

In [forward.iterators], add the following axiom to the definition of the ForwardIterator concept:

    axiom MultiPass(X a, X b) {
      if (a == b) *a == *b;
      if (a == b) ++a == ++b;
      &a == &++a;
    }
  

Add the following paragraph to [forward.iterators]:

  reference operator*(X&);
  reference operator*(X const&);
  

2.     Requires: If two iterators a and b of the same type are both dereferenceable, then a == b if and only if *a and *b are the same object.

In [bidirectional.iterators], add the following axiom to the Bidireciotnal iterator concept:

    axiom BackwardTraversal(X a, X b) {
      --(++a) == a;
      if (--a == --b) a == b;
      &a == &--a;
    }
  

5.     Effects: --(++r) == r.
   --r == --s implies r == s.
   &r == &--r.

26. Transition of Clause 17, Library introduction

Section: 17 [library] Status: WP Submitter: Beman Dawes Date: 2008-03-03

View all issues with WP status.

Discussion:

N2037, Concepts for the C++0x Standard Library: Introduction, removes current requirements based wording from chapter 17 and replaces it with concepts based wording.

That's fine if we uniformly replace all requirements with concepts. But if we choose to leave even a single requirement in place, then the WP is in an inconsistent state since that requirement is no longer supported by the wording in 17.

Even if we do remove all uses of requirements, that is unlikely to occur at a single point in time. Thus the WP will be in an inconsistent state until each and every chapter has been converted to concepts.

Proposed resolution:

Break N2037 into two papers. One adds the wording to support concepts. The other removes wording supporting requirements (and does any rewording of the concepts wording needed to reflect a concepts only approach.)

Vote the "add concepts to the introduction" paper into the WP whenever the first of the other library chapters concepts are voted in.

Vote the "remove requirements from the introduction" paper into the WP whenever the last old-style requirement is removed from the WP (if ever).

27. Missing core concept for polymorphic types

Section: 20.1.1 [concept.support] Status: WP Submitter: Alisdair Meredith Date: 2008-03-25

View all other issues in [concept.support].

View all issues with WP status.

Discussion:

There is no core concept for Polymorphic types in n2572. This seems to be a useful concept where we expect dynamic_cast to return something useful.

Proposed resolution:

Add to the synopsis of the header <concepts>:

concept ClassType<typename T> see below; 
concept Class<typename T> see below; 
concept PolymorphicClass<typename T> see below;
concept Union<typename T> see below;
  

Add the following to [concept.support], after the description of concept Class:

concept PolymorphicClass<typename T> : Class<T> { }
  

16. Note: describes polymorphic types ([class.virtual]).
17. Requires: for every type T that is a polymorphic class, a concept map PolymorphicClass<T> shall be implicitly defined in namespace std.

28. Abstract classes should not be VariableTypes

Section: 20.1.1 [concept.support] Status: WP Submitter: Thomas Witt Date: 2008-03-25

View all other issues in [concept.support].

View all issues with WP status.

Discussion:

Since one cannot create an instance of an abstract class, an abstract class type T should not have an implicitly-defined concept map VariableType<T>.

Proposed resolution:

Modify [concept.support]p9 as follows:

9. Requires: for every type T that is an object type or reference type, but not an abstract class type ([class.abstract]), a concept map VariableType<T> shall be implicitly defined in namespace std.

29. Concepts on mutating algorithms are confusing

Section: 25 [algorithms] Status: WP Submitter: Christopher Jefferson Date: 2008-04-29

View all other issues in [algorithms].

View all issues with WP status.

Discussion:

The concepts on the mutating algorithms are confusing and leak too much about the implementation. For example push_heap requires MoveConstructible and MoveAssignable, but pop_heap also requires Swappable. These arise from the functions used in practical implementations, but mean using them in constrained templates requires looking up the exact concepts required. At the cost of a slightly less efficient implementation, all of the following algorithms can be implemented using just IteratorSwappable, along with a predicate or LessThanComparable:

reverse, rotate, random_shuffle, partition, stable_partition, sort, stable_sort, partial_sort, nth_element, inplace_merge, push_heap, pop_heap, make_heap, sort_heap, next_permutation, prev_permutation

Further, partial_sort_copy can be implemented requiring only SwappableIterator on the result array. All of these changes have been tested with a modification of libstdc++. Of course implementations can implement optimised versions of these methods when MoveConstructable and MoveAssignable are available.

Proposed resolution:

Replace any references to MoveConstructible, MoveAssignable and Swappable in the requires section of reverse, rotate, random_shuffle, partition, stable_partition, sort, stable_sort, partial_sort, nth_element, inplace_merge, push_heap, pop_heap, make_heap, sort_heap, next_permutation, prev_permutation with SwappableIterator, remove all references to SameType and remove Mutable from any iterator requirements. Further, replace the concepts:

      SameType<RAIter::value_type&, RAIter::reference> && Swappable<RAIter::value_type> &&
      MoveConstructible<RAIter::value_type> && MoveAssignable<RAIter::value_type> &&
  

with SwappableIterator<RAIter> in both copies if partial_sort_copy

Updated: the post-Sophia mailing contains changes to address this issue using HasSwap, OutputIterator, and the new MovableIterator.

30. Should Predicates be on Iter::value_type or Iter::reference?

Section: 25 [algorithms] Status: WP Submitter: Christopher Jefferson Date: 2008-05-18

View all other issues in [algorithms].

View all issues with WP status.

Discussion:

Some algorithms, such as prev_permutation and next_permutation, are predicated on Iter::reference. Others, such as sort_heap, are predicated on Iter::value_type. I am not sure which is correct, but it the inconsistency seems strange. The choice should only affect proxy references.

Proposed resolution:

Predicates operator on the value types, because predicates aren't supposed to change the actual value. This change has been made throughout the concepts proposals.

31. Which specifiers are legal for associated functions?

Section: 14.9.1.1 [concept.fct] Status: WP Submitter: Daniel Kruegler Date: 2008-05-28

View all issues with WP status.

Discussion:

[concept.fct] describes some explicit exclusions for function specifiers on associated functions, but can we conclude from this that all other specifiers are feasible? Can we declare functions as constexpr, virtual, and pure?

Proposed resolution:

The virtual specifier doesn't make sense for associated functions (especially now that one can adapt the syntax of member functions a concept map), so it should be banned. Syntactically, a pure-specifier cannot occur in an associated function, so it need not be mentioned. constexpr is permitted, as are any other specifiers (like explicit) that aren't banned, so it doesn't need to be mentioned either. Suggested change to [concept.fct]p2:

An associated-function shall declare a function or function template. If the declarator-id of the declaration is a qualified-id, its nested-name-specifier shall name a template parameter of the enclosing concept; the declaration declares a member function or member function template. An associated function shall not be extern([dcl.stc]), inline or virtual ([dcl.fct.spec]), explicitly-defaulted or deleted ([dcl.fct.def]), or a friend function ([class.friend]). An associated function shall not contain an exception-specification ([except.spec]).

32. Missing definition of TriviallyDefaultConstructible

Section: 20.1.4 [concept.construct] Status: WP Submitter: Daniel Kruegler Date: 2008-05-29

View all other issues in [concept.construct].

View all issues with WP status.

Discussion:

A missing concept in [concept.construct]: Although (and rightly) declared in [utility.concepts], header <concepts> synopsis, the description and definition of TriviallyDefaultConstructible is missing.

Proposed resolution:

Add the following to [concept.construct]:

    concept TriviallyDefaultConstructible<typename T> : DefaultConstructible<T> {}
  

3. Note: describes types whose default constructor is trivial.
4. Requires: for every type T that is a trivial type ([basic.types]) or a class type with a trivial default constructor ([class.ctor]), a concept map TriviallyDefaultConstructible<T> shall be implicitly defined in namespace std.

33. ArithmeticLike should have construction from an unsigned integral type

Section: 20.1.11 [concept.arithmetic] Status: WP Submitter: Daniel Kruegler Date: 2008-05-29

View all other issues in [concept.arithmetic].

View all issues with WP status.

Discussion:

It is necessary to add the associated c'tor signature T::T(uintmax_t) to concept ArithmeticLike as well, because otherwise uintmax_t itself would be excluded and ArithmeticLike itself is not restricted on signed types (uintmax_t -> intmax_t can lead to overflow), e.g HasNegate > is part of all arithmetic types.

Proposed resolution:

Add the following to concept ArithmeticLike:

    T::T(intmax_t);
    T::T(uintmax_t);
    T::T(long double);
  

34. Copy/move requirements on container members

Section: 23 [containers] Status: WP Submitter: Howard Hinnant Date: 2008-05-22

View all other issues in [containers].

View all issues with WP status.

Discussion:

In N2623 I note that the requirements on each container assignment look like:

requires ConstructibleAsElement<Alloc, T, const T&>
 vector<T,Allocator>& operator=(const vector<T,Allocator>& x);

Why is T not required to be CopyAssignable? We have a history of wanting to reuse capacity/nodes whatever, whenever we can. This is a tremendous performance advantage over a clear()/push_back() algorithm.

I'm aware that a container could always overload each assignment member for types that are CopyAssignable, and make the optimization. I'm greatly concerned about doubling the size of the entire std::library by doing such overloading in so many places where this philosophy is currently proposed. Concepts are already going to extract a very significant compile-time penalty (no one knows how much at this point, conceptgcc is a worst (and unacceptable) case). I don't want to further aggravate that very real problem.

These requirements have an interesting history. In the following, CA=CopyAssignable, CC=CopyConstructible, MA=MoveAssignable, and MC=MoveAssignable. The library "move papers" were written in 2005. At that time we had a blanket CA/CC requirement on the containers. Howard wrote the move papers against that, mechanically substituting in MA/MC for CA/CC.

After the move papers were written, and before they were accepted, LWG 276 was settled, removing the CA requirement for all the node-based containers except list::assign. It was still required for all of vector and deque (if I recall correctly). Then the move papers were accepted, subsequently accidently reversing LWG 276.

The addition of scoped allocators (N2554) removed the blanket MA/MC requirement, added by the move papers, using ConstructibleAsElement without CA/CC/MA/MC. LWG 704 (submitted prior to pre-scoped allocators and emplace) attempts to straighten out the message. This issue includes the minimum requirements for each container member at the time the issue was written (May 20, 2007). The table doesn't specifically mention C::operator=(const C&) because those requirements should be identical to c1.assign(c2.begin(), c2.end()) which is listed.

Proposed resolution:

(Proposed resolution by Doug Gregor)

In [deque], change the definition of class template deque as follows:

template <ObjectType T, RandomAccessAllocator Alloc = allocator<T> >
requires Destructible<T>
class deque { 
public: 
  // ...

  requires ConstructibleAsElement<Alloc, T, const T&> && CopyAssignable<T>
    deque<T,Allocator>& operator=(const deque<T,Allocator>& x); 
  requires ConstructibleAsElement<Alloc, T, T&&>
    deque<T,Allocator>& operator=(const deque<T,Allocator>&& x); 
  template <InputIterator Iter> 
    requires ConstructibleAsElement<Alloc, T, Iter::reference> && HasCopyAssign<T, Iter::reference>
    void assign(Iter first, Iter last); 
  requires ConstructibleAsElement<Alloc, T, const T&> && CopyAssignable<T>
    void assign(size_type n, const T& t); 

  // ...
  requires DefaultConstructible<T> && MoveAssignable<T>
    void resize(size_type sz); 
  requires ConstructibleAsElement<Alloc, T, const T&> && MoveAssignable<T>
    void resize(size_type sz, const T& c); 
};
  

In [forwardlist], change the definition of class template forward_list as follows:

template <ObjectType T, Allocator Alloc = allocator<T> > 
requires Destructible<T> 
class forward_list { 
public: 
  // ...
  requires ConstructibleAsElement<Alloc, T, const T&> && CopyAssignable<T>
    forward_list<T,Alloc>& operator=(const forward_list<T,Alloc>& x); 
  forward_list<T,Alloc>& operator=(forward_list<T,Alloc>&& x); 
  template <class InputIteratorInputIterator Iter> 
    requires ConstructibleAsElement<Alloc, T, Iter::reference> && HasCopyAssign<T, Iter::reference>
    void assign(Iter first, Iter last); 
  ConstructibleAsElement<Alloc, T, const T&> && CopyAssignable<T>
    void assign(size_type n, const T& t); 
};
  

In [list], change the definition of class template list as follows:

template <ObjectType T, Allocator Alloc = allocator<T> > 
requires Destructible<T> 
class list { 
public: 
  // ...
  requires ConstructibleAsElement<Alloc, T, const T&> && CopyAssignable<T>
    list<T,Alloc>& operator=(const list<T,Alloc>& x ); 
  list<T,Alloc>& operator=(list<T,Alloc>&& x); 
  template <InputIterator Iter> 
    requires ConstructibleAsElement<Alloc, T, Iter::reference> && HasCopyAssign<T, Iter::reference>
    void assign(Iter first, Iter last); 
  requires ConstructibleAsElement<Alloc, T, const T&> && CopyAssignable<T>
    void assign(size_type n, const T& t); 
};
  

In [vector], change the definition of class template vector as follows:

template <ObjectType T, RandomAccessAllocator Alloc = allocator<T> > 
requires Destructible<T> 
class vector { 
public: 
  // ...
  template <InputIterator Iter> 
    requires ConstructibleAsElement<Alloc, T, Iter::reference> && ConstructibleAsElement<Alloc, T, T&&>
    vector(Iter first, Iter last, 
           const Alloc& = Alloc()); 

  // ...
  requires ConstructibleAsElement<Alloc, T, const T&> && CopyAssignable<T> 
    vector<T,Alloc>& operator=(const vector<T,Alloc>& x); 
  vector<T,Alloc>& operator=(vector<T,Alloc>&& x); 
  template <InputIterator Iter> 
    requires ConstructibleAsElement<Alloc, T, Iter::reference> 
          && HasCopyAssign<T, Iter::reference> && ConstructibleAsElement<Alloc, T, T&&>
    void assign(Iter first, Iter last); 
  requires ConstructibleAsElement<Alloc, T, const T&> && CopyAssignable<T> 
    void assign(size_type n, const T& u);  

  // ...
  requires DefaultConstructible<T> && ConstructibleAsElement<Alloc, T, T&&>
    void resize(size_type sz); 
  requires ConstructibleAsElement<Alloc, T, const T&> && ConstructibleAsElement<Alloc, T, T&&>
    void resize(size_type sz, const T& c);

  // ...
  requires ConstructibleAsElement<Alloc, T, T&&>
    void reserve(size_type n); 

  // ...
  template <class... Args> 
    requires ConstructibleAsElement<Alloc, T, Args&&...> && ConstructibleAsElement<Alloc, T, T&&>
    void push_back(Args&&... args); 
  void pop_back(); 
  template <class... Args> 
    requires ConstructibleAsElement<Alloc, T, Args&&...> && ConstructibleAsElement<Alloc, T, T&&>
    iterator emplace(const_iterator position, Args&&... args); 
  requires ConstructibleAsElement<Alloc, T, const T&> && MoveAssignable<T> && ConstructibleAsElement<Alloc, T, T&&>
    iterator insert(const_iterator position, const T& x); 
  requires ConstructibleAsElement<Alloc, T, T&&> && MoveAssignable<T>
    void insert(const_iterator position, T&& x); 
  requires ConstructibleAsElement<Alloc, T, const T&> && MoveAssignable<T> && ConstructibleAsElement<Alloc, T, T&&>
    void insert(const_iterator position, size_type n, const T& x);
  template <InputIterator Iter> 
    requires ConstructibleAsElement<Alloc, T, Iter::reference> 
        && HasCopyAssign<T, Iter::reference>
        && ConstructibleAsElement<Alloc, T, T&&> && MoveAssignable<T> 
    void insert(const_iterator position, 
                Iter first, Iter last);
};
  

35. Swappable should be usable with proxy iterator references

Section: 20.1.5 [concept.copymove] Status: WP Submitter: LWG Date: 2008-05-29

View all other issues in [concept.copymove].

View all issues with WP status.

Discussion:

The Swappable concept cannot currently be used with proxy iterator references, because they aren't necessarily lvalues. Moreover, its swap can't be applied to values of different types. For example, it couldn't be used for the proxy references coming from two different iterator types in the swap_ranges algorithm.

Proposed resolution:

Add a new paragraph to [concept.operator] after paragraph 23:

auto concept HasSwap<typename T, typename U> {
  void swap(T, U);
}
  

24. Note: describes types for which values of those types can be swapped.

Modify the definition of Swappable in [concept.copymove] as follows:

auto concept Swappable<typename T> : HasSwap<T, T> { } 
  

11. Note: describes types for which values of that type can be swapped.
12. Postconditions: after executing swap(s, t), t has the value originally held by s and s has the value originally held by t.

The synopsis in [utility.concepts] will need to be updated accordingly.

Note: the proposed resolution changed at Sophia-Antipolis, to create a new two-argument HasSwap and make Swappable refine that concept. Also, we have removed the reference from swap's arguments; the appropriate kind of reference will be provided by the user of HasSwap or Swappable.

36. HasCopyAssign should be named HasAssign

Section: 20.1.10 [concept.operator] Status: WP Submitter: Howard Hinnant Date: 2008-05-29

View all other issues in [concept.operator].

View all issues with WP status.

Discussion:

In:

template <InputIterator Iter>
     requires ConstructibleAsElement<Alloc, T, Iter::reference> && HasCopyAssign<T, Iter::reference>
     void assign(Iter first, Iter last);

Is "HasCopyAssign" a good name for this concept? I'm thinking more along the lines of "HasAssign". Rationale: Iter can be a move_iterator<T>. It's reference type is T&&. I strongly suspect that the HasCopyAssign concept will work just fine for move_iterator<T>. I'm just thinking that the name may be misleading because the code may end up doing a move assign.

38. Container move constructor/assignment operators don't account for scoped allocators

Section: 23 [containers] Status: WP Submitter: Pablo Halpern Date: 2008-05-29

View all other issues in [containers].

View all issues with WP status.

Discussion:

The requirements for extended move construction are correct table 91, but missing in the requires clauses in N2623. The requirements on the normal move constructor and the move assignment operator are missing.

Proposed resolution:

39. Some uses of the MutableXXXIterator concepts are unnecessary

Section: 25 [algorithms] Status: WP Submitter: LWG Date: 2008-06-09

View all other issues in [algorithms].

View all issues with WP status.

Discussion:

Some algorithms that use the MutableXXXIterator concepts (e.g., MutableForwardIterator) don't actually need the Mutable variant of the concept, because they don't depend on that form of assignability. Generally, these algorithms output some other type, and don't move elements within the sequence. For example, this is the replace algorithm:

template<MutableForwardIterator Iter, class T> 
  requires HasEqualTo<Iter::reference, T> && HasCopyAssign<Iter::reference, T> 
  void replace(Iter first, Iter last, 
               const T& old_value, const T& new_value); 
  

The MutableForwardIterator concept requirement could be changed to ForwardIterator without breaking any code. This makes it possible, for example, to pass a sequence of move-only types into replace.

swap_ranges has the same issue.

Proposed resolution:

All of the MutableXXXIterator concepts have now been removed.

40. HasXXX concepts should not default second parameter when there is an XXXable concept

Section: 20.1 [utility.concepts] Status: WP Submitter: LWG Date: 2008-06-09

View all other issues in [utility.concepts].

View all issues with WP status.

Discussion:

In several cases, we have two-parameter HasXXX concepts that detect the presence of a binary operator or function (e.g., <, swap, ==) along with a semantic version XXXable that is a single-parameter refinement of that concept. For example, the pair of concepts HasEqualTo and EqualityComparable. Since we know of no cases where one would need to use the HasXXX form of the concept with only one parameter (all such cases use the XXXable form), we should remove the default argument in the HasXXX version to discourage its use with symmetric types.

Proposed resolution:

In [concept.comparison], modify paragraph 1 as follows:

auto concept LessThanComparable<typename T> : HasLess<T, T> { 
  bool operator>(T const& a, T const& b) { return b < a; } 
  bool operator<=(T const& a, T const& b) { return !(b < a); } 
  bool operator>=(T const& a, T const& b) { return !(a < b); } 
  // ...
}
  

In [concept.comparison], modify paragraph 2 as follows:

auto concept EqualityComparable<typename T> : HasEqualTo<T, T> { 
  bool operator!=(T const& a, T const& b) { return !(a == b); } 
  // ...
}
  

In [concept.copymove], modify paragraph 7 as follows:

auto concept MoveAssignable<typename T> : HasMoveAssign<T, T> { } 
  

In [concept.operator], modify paragraph 8 as follows:

auto concept HasLess<typename T, typename U = T> { 
  bool operator<(T const& a, U const& b); 
} 
  

In [concept.operator], modify paragraph 9 as follows:

auto concept HasEqualTo<typename T, typename U = T> { 
  bool operator==(T const& a, U const& b); 
} 
  

In [concept.operator], modify paragraph 22 as follows:

auto concept HasMoveAssign<typename T, typename U = T> { 
  typename result_type; 
  result_type T::operator=(U&&); 
} 
  

In [concept.operator], modify paragraph 23 as follows:

auto concept HasCopyAssign<typename T, typename U = T> : HasMoveAssign<T, U> { 
  result_type T::operator=(const U&); 
} 
  

Modify the synopsis in [utility.concepts] accordingly.

43. Using Swappable for all swapping

Section: 25 [algorithms] Status: WP Submitter: LWG Date: 2008-06-09

View all other issues in [algorithms].

View all issues with WP status.

Discussion:

The current description of the algorithms uses a mix of SameType && Swappable and SwappableIterator concept requirements to handle swapping. These should all be replaced with uses of the two-parameter HasSwap (issue 35) or the current Swappable concept that (typically) work on the reference types of iterators. As part of this, the SwappableIterator concept should be eliminated.

Proposed resolution:

HasSwap is now used throughout.

44. unique_copy requirements don't account for move semantics

Section: 25.2.9 [alg.unique] Status: WP Submitter: LWG Date: 2008-06-09

View all issues with WP status.

Discussion:

The unique_copy algorithm uses iterator value_types in a few places that preclude the use of move iterators.

Proposed resolution:

unique_copy requirements have been updated to cope with move semantics.

45. move and move_backward rely too heavily on the iterator's value_type

Section: 25.2.2 [alg.move] Status: WP Submitter: LWG Date: 2008-06-09

View all issues with WP status.

Discussion:

The move and move_backward algorithms use the iterator's value_type rather than reference type in several places, which may cause problems for certain iterators (e.g., proxy iterators).

Proposed resolution:

The latest proposal contains requirements that properly support proxy iterators.

47. ArithmeticLike conversions from integral, floating-point types should be explicit

Section: 20.1.11 [concept.arithmetic] Status: WP Submitter: Howard Hinnant Date: 2008-08-25

View all other issues in [concept.arithmetic].

View all issues with WP status.

Discussion:

We would like to use the ArithmeticLike concept in places where the user types might only have explicit conversions from the built-in arithmetic types, e.g., in class duration. For example, the user may have created an arithmetic emulator type but wanted to keep conversions to a minimum to make the type safer to use.

Proposed resolution:

In [concept.arithmetic], update the three constructor requirements in ArithmeticLike as follows:

concept ArithmeticLike<typename T>
  : ... {
  explicit T::T(intmax_t);
  explicit T::T(uintmax_t);
  explicit T::T(long double); 
}
  

48. Missing iterator to const_iterator conversion

Section: 23.1.4 [container.concepts] Status: WP Submitter: LWG Date: 2008-06-09

View all issues with WP status.

Discussion:

The Container and MemberContainer concepts are missing the conversion from iterator to const_iterator.

Proposed resolution:

In [concept.concepts.free], modify the Container concept as follows:

concept Container<typename C> {
  // ...
  requires Convertible<iterator, const_iterator>;
}
  

In [container.concepts.member], modify the MemberContainer concept as follows:

concept MemberContainer<typename C> {
  // ...
  requires Convertible<iterator, const_iterator>;
}