Changeset 54702


Ignore:
Timestamp:
Jul 6, 2009, 4:19:53 AM (9 years ago)
Author:
Douglas Gregor
Message:

Fixes for both concepts papers

Location:
sandbox/committee/LWG/proposals
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • sandbox/committee/LWG/proposals/explicit-refinement.rst

    r54662 r54702  
    55:Authors: Doug Gregor <doug.gregor@gmail.com> and Dave Abrahams <dave@boostpro.com>
    66:Number:  xxxx=xx-xxxx
    7 :Date: 2009-07-04
     7:Date: 2009-07-05
    88
    99This paper describes a significant type-safety problem with explicit
     
    1818In N2831_, we described a type-safety problem with the (then current)
    1919rvalue-reference binding rules, wherein an rvalue reference could bind
    20 to an lvalue, silently stealing resources from the lvalue. The
    21 rvalue-references problem highlighted an important principle of type
    22 safety:
     20to an lvalue, silently stealing resources from the lvalue. The only
     21way to avoid this problem was to provide an lvalue-reference overload
     22that attracted lvalues more strongly than the rvalue-reference
     23overload. This rvalue-references problem highlighted an important
     24principle of type safety:
    2325
    2426.. Admonition:: Principle of Type-safe Overloading (PTO)
     
    3638separation in different headers.
    3739
    38 This principle is certainly not new. Back when overloading was
    39 introduced into C++, various uses of the "overload" keyword were tried
    40 (and subsequently removed). Bjarne Stroustrup summarizes the issue
    41 with the "overload" keyword succinctly (from c++std-lib-23985):
    42 
    43     In particular, we *must* pick the right version of an algorithm
    44     without a single point of definition of all versions.
    45 
    46 The principle of type-safe overloading is based on that same idea.
    47 
    4840Explicit Refinement
    4941===================
     
    5345refinement, *explicit refinement*, that limits when a concept map can
    5446be implicitly generated. In particular, when a concept ``B``
    55 explicitly refines a concept ``A``, a type ``X`` that meets the syntactic
    56 requirements of both ``B`` and ``A`` will be considered a ``B`` unless
    57 we are performing some kind of partial ordering (of class template
    58 partial specialization, concept map templates, or function
     47explicitly refines a concept ``A``, a type ``X`` that meets the
     48syntactic requirements of both ``B`` and ``A`` will be considered a
     49``B`` unless we are performing some kind of partial ordering (of class
     50template partial specialization, concept map templates, or function
    5951templates). In these partial-ordering cases, ``X`` will only be
    6052considered a ``B`` when there is an explicit concept map ``B<X>`` or
    61 when the other candidates in the ordering do not involve ``A<X>``.
     53when the other candidates in the ordering do not involve ``A<X>``. 
    6254
    6355Explicit refinement can best be understood through examples. N2906_
     
    6658iterators. The two constrained templates are::
    6759
    68   // #1
     60  // #1: from the Standard Library; safe for all input/output iterators
    6961  template<InputIterator InIter, OutputIterator<auto, InIter::reference> OutIter>
    7062    OutIter copy(InIter first, InIter last, OutIter result) {
     
    7769    }
    7870
    79   // #2
     71  // #2: possibly in a 3rd-party library; safe and fast for contiguous regions of PODs
    8072  template<ContiguousIterator InIter, ContiguousIterator OutIter>
    8173    requires SameType<InIter::value_type, OutIter::value_type>
     
    9183value types. The second ``copy()`` implementation uses ``memmove()``
    9284for far greater performance with both iterators point to contiguous
    93 blocks with the same POD data type.
    94 
    95 Next, we consider two calls to ``copy()``::
    96 
    97   void test_copy(deque<int>::iterator di, int* ip, int n, int *result) {
    98     copy(di, di + n, result);
    99     copy(ip, ip + n, result);
    100   }
    101 
    102 Ideally, the first call should invoke the ``copy()`` marked #1, since a deque
    103 does not store its contents in contiguous memory. The second call
    104 should invoke the ``copy())`` marked #2, providing the ``memmove()``
    105 optimization automatically. Any other solution either misses an
    106 optimization opportunity or leads to run-time errors.
     85blocks with the same POD data type. The second ``copy()`` is
     86considered to be *more specialized*, because it operates on a subset
     87of the input types that the first ``copy()`` operates on.
    10788
    10889With explicit refinement, one would express the iterator concepts
    109 hierarchy using implicit concepts and some explicit refinement as::
     90hierarchy using implicit concepts and some explicit refinement as, e.g.::
    11091
    11192  /*auto*/ concept InputIterator<typename T> { /* ... */ }
     
    11798  }
    11899
    119 Now, consider the call to ``copy()`` that provides ``deque<int>``
    120 iterator arguments. Both versions of ``copy()`` could be called,
    121 because ``deque<int>::iterator`` syntactically meets the requirements
    122 of both ``InputIterator`` and ``ContiguousIterator``. However, the
     100Next, we consider two calls to ``copy()``::
     101
     102  void test_copy(deque<int>::iterator di, int* ip, int n, int *result) {
     103    copy(di, di + n, result);
     104    copy(ip, ip + n, result);
     105  }
     106
     107Ideally, the first call should invoke the ``copy()`` marked #1, since a deque
     108does not store its contents in contiguous memory. The second call
     109should invoke the ``copy()`` marked #2, providing the ``memmove()``
     110optimization automatically. Any other solution either misses an
     111optimization opportunity or leads to run-time errors.
     112
     113Now, consider the call to ``copy(di, di + n, result)``. Syntactically,
     114the dequee iterators meet all of the requirements of the
     115``ContiguousIterator`` concept (along with all of the other
     116concepts), so the compiler could implicitly generate a concept map
     117``ContiguousIterator<deque<int>::iterator>`` to satisfy the
     118requirements of both ``copy()`` algorithms. However, the
    123119explicit refinement of ``ContiguousIterator`` from
    124120``RandomAccessIterator`` (which, transitively, refines
    125121``InputIterator``) prevents ``copy()`` #2 from being selected by
    126 partial ordering. That's good: if we called ``copy()`` #2, the result
     122partial ordering (N2906_). That's good: if we called ``copy()`` #2, the result
    127123would be a run-time failure as the code attempts to ``memmove()`` the
    128124contents of a deque.
     
    192188behavior for the deque.
    193189
    194 What happened? The optimized ``copy()`` violates the principle of
     190What happened? Due to the use of explicit refinement in the iterator
     191concepts hierarchy, the optimized ``copy()`` violates the principle of
    195192type-safe overloading, because it only properly rejects iterators that
    196193syntactically meet the requirements of ``ContiguousIterator`` (but
  • sandbox/committee/LWG/proposals/taxonomy-of-concepts-and-maps.rst

    r54701 r54702  
    333333    concept_map Swappable<pair<T,U> >
    334334    {
    335         swap(pair<T,U>& lhs, pair<T,U>& rhs)
     335        void swap(pair<T,U>& lhs, pair<T,U>& rhs)
    336336        {
    337337            swap(lhs.first,rhs.first);
     
    362362
    363363    template <LessThanComparable T, class A>
    364     bool operator< (const list<T,A>& x, const list<T,A>& y);
     364      bool operator< (const list<T,A>& x, const list<T,A>& y);
    365365    template <LessThanComparable T, class A>
    366     bool operator> (const list<T,A>& x, const list<T,A>& y);
     366      bool operator> (const list<T,A>& x, const list<T,A>& y);
    367367    template <LessThanComparable T, class A>
    368     bool operator>=(const list<T,A>& x, const list<T,A>& y);
     368      bool operator>=(const list<T,A>& x, const list<T,A>& y);
    369369    template <LessThanComparable T, class A>
    370     bool operator<=(const list<T,A>& x, const list<T,A>& y);
     370      bool operator<=(const list<T,A>& x, const list<T,A>& y);
    371371
    372372  which can be simplified, using an exported concept map, to::
     
    375375    export concept_map LessThanComparable<list<T,A> >
    376376    {
    377         bool operator<(const list<T,A>& x, const list<T,A>& y);
     377        bool operator<(const list<T,A>& x, const list<T,A>& y) { /*...*/ }
    378378    };
    379379
     
    409409----------------
    410410
    411 Adaptative mapping is used to fulfill a concept's requirements that
     411Adaptive mapping is used to fulfill a concept's requirements that
    412412are already expressed, but in a different form.  For example, one can
    413413use adaptive mapping to represent the edge connectivity of a graph
Note: See TracChangeset for help on using the changeset viewer.