Changeset 48282


Ignore:
Timestamp:
Aug 21, 2008, 3:23:14 PM (10 years ago)
Author:
Douglas Gregor
Message:

Add the algorithms from N2666, from Daniel Kruegler

Location:
sandbox/committee/concepts/stdlib
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • sandbox/committee/concepts/stdlib/clib-algorithms.tex

    r48273 r48282  
    119119  \tcode{sort}, \tcode{partition}), we specify the
    120120  \tcode{ShuffleIterator} requirement.
     121\item Added conceptualized versions of the algorithms in N2666, from
     122  Daniel Kr\"ugler: \tcode{all_of}, \tcode{any_of}, \tcode{none_of},
     123  \tcode{find_if_not}, \tcode{copy_n}, \tcode{copy_if},
     124  \tcode{partition_copy}, \tcode{is_partitioned}, and
     125  \tcode{partition_point}.
    121126\end{itemize}
    122127
     
    190195namespace std {
    191196  @\textcolor{black}{// \ref{alg.nonmodifying}, non-modifying sequence operations:}@
     197  template <InputIterator Iter, Predicate<auto, Iter::value_type> Pred>
     198    requires CopyConstructible<Pred>
     199    bool all_of(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
     200  template <InputIterator Iter, Predicate<auto, Iter::value_type> Pred>
     201    requires CopyConstructible<Pred>
     202    bool any_of(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
     203  template <InputIterator Iter, Predicate<auto, _Iter::value_type> Pred>
     204    requires CopyConstructible<Pred>
     205    bool none_of(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
     206
    192207  template<InputIterator Iter, Callable<auto, Iter::reference> Function>
    193208    requires CopyConstructible<Function>
     
    199214    requires CopyConstructible<Pred>
    200215    Iter find_if(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
     216  template<InputIterator Iter, Predicate<auto, Iter::value_type> Pred>
     217    requires CopyConstructible<Pred>
     218    Iter find_if_not(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
    201219  template<ForwardIterator Iter1, ForwardIterator Iter2>
    202220    requires HasEqualTo<Iter1::value_type, Iter2::value_type>
     
    280298    OutIter copy(InIter @\farg{first}@, InIter @\farg{last}@,
    281299                 OutIter @\farg{result}@);
     300  template<InputIterator InIter, OutputIterator<auto, InIter::reference> OutIter>
     301    OutIter copy_n(InIter @\farg{first}@, InIter::difference_type @\farg{n}@,
     302                   OutIter @\farg{result}@);
     303  template<InputIterator InIter, OutputIterator<auto, InIter::reference> OutIter,
     304           Predicate<auto, InIter::value_type> Pred>
     305    requires CopyConstructible<Pred>
     306    OutIter copy_if(InIter @\farg{first}@, InIter @\farg{last}@,
     307                    OutIter @\farg{result}@, Pred @\farg{pred}@);
    282308  template<BidirectionalIterator InIter, BidirectionalIterator OutIter>
    283309    requires OutputIterator<OutIter, InIter::reference>
     
    467493
    468494  @\textcolor{black}{// \ref{alg.partitions}, partitions:}@
     495  template <InputIterator Iter, Predicate<auto, Iter::value_type> Pred>
     496    requires CopyConstructible<Pred>
     497    bool is_partitioned(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
     498
    469499  template<BidirectionalIterator Iter, Predicate<auto, Iter::value_type> Pred>
    470500    requires ShuffleIterator<Iter>
     
    475505          && CopyConstructible<Pred>
    476506    Iter stable_partition(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
     507  template <InputIterator InIter, OutputIterator<auto, InIter::reference> OutIter1,
     508            OutputIterator<auto, InIter::reference> OutIter2, Predicate<auto, InIter::value_type> Pred>
     509    requires CopyConstructible<Pred>
     510    pair<OutIter1, OutIter2>
     511    partition_copy(InIter @\farg{first}@, InIter @\farg{last}@,
     512                   OutIter1 @\farg{out_true}@, OutIter2 @\farg{out_false}@,
     513                   Pred @\farg{pred}@);
     514  template<ForwardIterator Iter, Predicate<auto, Iter::value_type> Pred>
     515    requires CopyConstructible<Pred>
     516    Iter partition_point(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
    477517
    478518  @\textcolor{black}{// \ref{alg.sorting}, sorting and related operations:}@
     
    10631103
    10641104\rSec1[alg.nonmodifying]{Non-modifying sequence operations}
     1105\rSec2[alg.all_of]{All of}
     1106
     1107\index{all_of@\tcode{all_of}}%
     1108\color{addclr}
     1109\begin{itemdecl}
     1110template <InputIterator Iter, Predicate<auto, Iter::value_type> Pred>
     1111  requires CopyConstructible<Pred>
     1112  bool all_of(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
     1113\end{itemdecl}
     1114\color{black}
     1115
     1116\begin{itemdescr}
     1117\pnum
     1118\returns\
     1119\tcode{true} if \tcode{pred(*i)} is \tcode{true} for every iterator \tcode{i} in the range \tcode{[first,last)}, and \tcode{false} otherwise.
     1120
     1121\pnum
     1122\complexity\
     1123At most \tcode{last - first} applications of the predicate.
     1124\end{itemdescr}
     1125
     1126\rSec2[alg.any_of]{Any of}
     1127\index{any_of@\tcode{any_of}}%
     1128\color{addclr}
     1129\begin{itemdecl}
     1130template <InputIterator Iter, Predicate<auto, Iter::value_type> Pred>
     1131  requires CopyConstructible<Pred>
     1132  bool any_of(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
     1133\end{itemdecl}
     1134\color{black}
     1135
     1136\begin{itemdescr} 
     1137\pnum
     1138\returns\
     1139\tcode{true} if there exists an iterator \tcode{i} in the range \tcode{[first,last)} such that \tcode{pred(*i)} is \tcode{true}, and \tcode{false} otherwise.
     1140
     1141\pnum
     1142\complexity\
     1143At most \tcode{last - first} applications of the predicate.
     1144\end{itemdescr}
     1145
     1146\rSec2[alg.none_of]{None of}
     1147\index{none_of@\tcode{none_of}}%
     1148\color{addclr}
     1149\begin{itemdecl}
     1150template <InputIterator Iter, Predicate<auto, _Iter::value_type> Pred>
     1151  requires CopyConstructible<Pred>
     1152  bool none_of(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
     1153\end{itemdecl}
     1154\color{black}
     1155
     1156\begin{itemdescr}
     1157\pnum
     1158\returns\
     1159\tcode{true} if \tcode{pred(*i)} is \tcode{false} for every iterator \tcode{i} in the range \tcode{[first,last)}, and \tcode{false} otherwise.
     1160
     1161\pnum
     1162\complexity\
     1163At most \tcode{last - first} applications of the predicate.
     1164\end{itemdescr}
    10651165
    10661166\rSec2[alg.foreach]{For each}
     
    11221222  requires CopyConstructible<Pred>
    11231223  Iter find_if(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
     1224
     1225template<InputIterator Iter, Predicate<auto, Iter::value_type> Pred>
     1226  requires CopyConstructible<Pred>
     1227  Iter find_if_not(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
    11241228\end{itemdecl}\color{black}
    11251229
     
    11331237for which the following corresponding
    11341238conditions hold:
    1135 \tcode{*i == \farg{value}, \farg{pred}(*i) != false}.
     1239\tcode{*i == \farg{value}, \farg{pred}(*i) != false, \farg{pred}(*i) == false}.
    11361240Returns \farg{last}\ if no such iterator is found.
    11371241
     
    15221626\tcode{\farg{last}\ - \farg{first}}
    15231627assignments.
     1628\end{itemdescr}
     1629
     1630\color{addclr}
     1631\begin{itemdecl}
     1632template<InputIterator InIter, OutputIterator<auto, InIter::reference> OutIter>
     1633  OutIter copy_n(InIter @\farg{first}@, InIter::difference_type @\farg{n}@,
     1634                 OutIter @\farg{result}@);
     1635\end{itemdecl}
     1636\color{black}
     1637
     1638\editorial{As with \tcode{fill_n}, we have eliminated the \tcode{Size}
     1639  parameter and instead have used the \tcode{difference_type} of the
     1640  input iterator, which is a better choice for measuring distances
     1641  within the input iterator sequence.}
     1642
     1643\begin{itemdescr}
     1644\pnum
     1645\effects\
     1646For each non-negative integer \tcode{i < n}, performs \tcode{*(result + i)} = \tcode{*(first + i)}.
     1647
     1648\pnum
     1649\returns\
     1650\tcode{result + n}.
     1651
     1652\pnum
     1653\complexity\
     1654Exactly \tcode{n} assignments.
     1655\end{itemdescr}
     1656
     1657\color{addclr}
     1658\begin{itemdecl}
     1659template<InputIterator InIter, OutputIterator<auto, InIter::reference> OutIter,
     1660         Predicate<auto, InIter::value_type> Pred>
     1661  requires CopyConstructible<Pred>
     1662  OutIter copy_if(InIter @\farg{first}@, InIter @\farg{last}@,
     1663                  OutIter @\farg{result}@, Pred @\farg{pred});
     1664\end{itemdecl}
     1665\color{black}
     1666
     1667\begin{itemdescr}
     1668\pnum
     1669\requires\
     1670The ranges \tcode{[first,last)} and \tcode{[result,result + (last - first))} shall not overlap.
     1671
     1672\pnum
     1673\effects\
     1674Copies all of the elements referred to by the iterator \tcode{i} in the range \tcode{[first,last)} for which \tcode{pred(*i)} is \tcode{true}.
     1675
     1676\pnum
     1677\complexity\
     1678Exactly \tcode{last - first} applications of the corresponding predicate.
     1679
     1680\pnum
     1681\notes\
     1682Stable.
    15241683\end{itemdescr}
    15251684
     
    24662625\rSec2[alg.partitions]{Partitions}
    24672626
     2627\index{is_partitioned@\tcode{is_partitioned}}%
     2628\color{addclr}\begin{itemdecl}
     2629template <InputIterator Iter, Predicate<auto, Iter::value_type> Pred>
     2630  requires CopyConstructible<Pred>
     2631  bool is_partitioned(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
     2632\end{itemdecl}\color{black}
     2633
     2634\begin{itemdescr}
     2635\pnum
     2636\removedConcepts{\requires
     2637\mbox{\tcode{InputIterator}}'s value type shall be convertible to \mbox{\tcode{Predicate}}'s argument type.}
     2638
     2639\pnum
     2640\returns\
     2641\tcode{true} if \tcode{[first,last)} is partitioned by \tcode{pred}, i.e. if all elements that satisfy \tcode{pred} appear before those that do not.
     2642
     2643\pnum
     2644\complexity\
     2645Linear. At most \tcode{last - first} applications of \tcode{pred}.
     2646\end{itemdescr}
     2647
    24682648\index{partition@\tcode{partition}}%
    24692649\color{addclr}\begin{itemdecl}
     
    25652745\tcode{\farg{last}\ - \farg{first}}\
    25662746applications of the predicate.
     2747\end{itemdescr}
     2748
     2749\index{partition_copy@\tcode{partition_copy}}%
     2750\color{addclr}\begin{itemdecl}
     2751template <InputIterator InIter, OutputIterator<auto, InIter::reference> OutIter1,
     2752          OutputIterator<auto, InIter::reference> OutIter2, Predicate<auto, InIter::value_type> Pred>
     2753  requires CopyConstructible<Pred>
     2754  pair<OutIter1, OutIter2>
     2755  partition_copy(InIter @\farg{first}@, InIter @\farg{last}@,
     2756                 OutIter1 @\farg{out_true}@, OutIter2 @\farg{out_false}@,
     2757                 Pred @\farg{pred}@);
     2758\end{itemdecl}
     2759\color{black}
     2760
     2761\begin{itemdescr}
     2762\pnum
     2763\removedConcepts{\requires
     2764\mbox{\tcode{InputIterator}}'s value type shall be \mbox{\tcode{Assignable}}, and shall be writable to the \mbox{\tcode{out_true}} and \mbox{\tcode{out_false}} \mbox{\tcode{OutputIterator}}s, and shall be convertible to \mbox{\tcode{Predicate}}’s argument type. The input range shall not overlap with either of the output ranges.}
     2765
     2766\pnum
     2767\effects\
     2768For each iterator \tcode{i} in \tcode{[first,last)}, copies \tcode{*i} to the output range beginning with \tcode{out_true} if \tcode{pred(*i)}
     2769   is \tcode{true}, or to the output range beginning with \tcode{out_false} otherwise.
     2770
     2771\pnum
     2772\returns\
     2773A pair \tcode{p} such that \tcode{p.first} is the end of the output range beginning at \tcode{out_true} and \tcode{p.second} is the end of the output range beginning at \tcode{out_false}.
     2774
     2775\pnum
     2776\complexity\
     2777Exactly \tcode{last - first} applications of \tcode{pred}.
     2778\end{itemdescr}
     2779
     2780\index{partition_point@\tcode{partition_point}}%
     2781\color{addclr}\begin{itemdecl}
     2782template<ForwardIterator Iter, Predicate<auto, Iter::value_type> Pred>
     2783  requires CopyConstructible<Pred>
     2784  Iter partition_point(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
     2785\end{itemdecl} 
     2786\color{black}
     2787
     2788\begin{itemdescr}
     2789\pnum
     2790\removedConcepts{\requires
     2791\mbox{\tcode{ForwardIterator}}'s value type shall be convertible to \mbox{\tcode{Predicate}}'s argument type. \mbox{\tcode{[first,last)}} shall be partitioned by \mbox{\tcode{pred}}, i.e. all elements that satisfy \mbox{\tcode{pred}} shall appear before those that do not.}
     2792
     2793\pnum
     2794\returns\
     2795An iterator \tcode{mid} such that \tcode{all_of(first, mid, pred)} and \tcode{none_of(mid, last, pred)} are both \tcode{true}.
     2796
     2797\pnum
     2798\complexity\
     2799${\cal O}(log(last - first))$ applications of \tcode{pred}.
    25672800\end{itemdescr}
    25682801
     
    43184551to determine which mutating algorithms required
    43194552\tcode{ShuffleIterator} and which required \tcode{HasSwap} on the
    4320 iterator's reference types.
     4553iterator's reference types. Daniel Kr\"ugler provided conceptualized
     4554versions of the algorithms in N2666.
    43214555
    43224556\bibliographystyle{plain}
  • sandbox/committee/concepts/stdlib/clib-numerics.tex

    r48273 r48282  
    8181  require \tcode{FloatingPointType}, which more accurately
    8282  characterizes the actual requirements for the \tcode{complex} type.
     83\item Added \tcode{iota}, conceptualized by Daniel Kr\"ugler.
    8384\end{itemize}
    8485
     
    34453446                                OutIter @\farg{result}@,
    34463447                                BinaryOperation @\farg{binary_op}@);
     3448
     3449  template <ForwardIterator Iter, HasPreincrement T>
     3450    requires OutputIterator<Iter, const T&>
     3451    void iota(Iter @\farg{first}@, Iter @\farg{last}@, T @\farg{value}@);
    34473452\end{codeblock}
    34483453\color{black}
     
    37153720\end{itemdescr}
    37163721
     3722\rSec2[numeric.iota]{Iota}
     3723\index{iota@\tcode{iota}}%
     3724\color{addclr}\begin{itemdecl}
     3725template <ForwardIterator Iter, HasPreincrement T>
     3726  requires OutputIterator<Iter, const T&>
     3727  void iota(Iter @\farg{first}@, Iter @\farg{last}@, T @\farg{value}@);
     3728\end{itemdecl}\color{black}
     3729
     3730\begin{itemdescr}
     3731\pnum
     3732\removedConcepts{\requires
     3733\mbox{\tcode{T}} shall meet the requirements of \mbox{\tcode{CopyConstructible}} and \mbox{\tcode{Assignable}} types, and shall be convertible to \mbox{\tcode{ForwardIterator}}'s value type. The expression \mbox{\tcode{++val}}, where \mbox{\tcode{val}} has type \mbox{\tcode{T}}, shall be well formed.}
     3734
     3735\pnum
     3736\effects\
     3737For each element referred to by the iterator \tcode{i} in the range \tcode{[first,last)}, assigns \tcode{*i = value} and increments value as if by \tcode{++value}.
     3738
     3739\pnum
     3740\complexity\
     3741Exactly \tcode{last - first} increments and assignments.
     3742\end{itemdescr}
     3743
    37173744\end{paras}
     3745
     3746\section*{Acknowledgments}
     3747Daniel Kr\"ugler provided conceptualized
     3748versions of \tcode{iota} in N2666.
    37183749
    37193750\bibliographystyle{plain}
Note: See TracChangeset for help on using the changeset viewer.