Changeset 48282
 Timestamp:
 Aug 21, 2008, 3:23:14 PM (10 years ago)
 Location:
 sandbox/committee/concepts/stdlib
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

sandbox/committee/concepts/stdlib/clibalgorithms.tex
r48273 r48282 119 119 \tcode{sort}, \tcode{partition}), we specify the 120 120 \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}. 121 126 \end{itemize} 122 127 … … 190 195 namespace std { 191 196 @\textcolor{black}{// \ref{alg.nonmodifying}, nonmodifying 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 192 207 template<InputIterator Iter, Callable<auto, Iter::reference> Function> 193 208 requires CopyConstructible<Function> … … 199 214 requires CopyConstructible<Pred> 200 215 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}@); 201 219 template<ForwardIterator Iter1, ForwardIterator Iter2> 202 220 requires HasEqualTo<Iter1::value_type, Iter2::value_type> … … 280 298 OutIter copy(InIter @\farg{first}@, InIter @\farg{last}@, 281 299 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}@); 282 308 template<BidirectionalIterator InIter, BidirectionalIterator OutIter> 283 309 requires OutputIterator<OutIter, InIter::reference> … … 467 493 468 494 @\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 469 499 template<BidirectionalIterator Iter, Predicate<auto, Iter::value_type> Pred> 470 500 requires ShuffleIterator<Iter> … … 475 505 && CopyConstructible<Pred> 476 506 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}@); 477 517 478 518 @\textcolor{black}{// \ref{alg.sorting}, sorting and related operations:}@ … … 1063 1103 1064 1104 \rSec1[alg.nonmodifying]{Nonmodifying sequence operations} 1105 \rSec2[alg.all_of]{All of} 1106 1107 \index{all_of@\tcode{all_of}}% 1108 \color{addclr} 1109 \begin{itemdecl} 1110 template <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\ 1123 At 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} 1130 template <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\ 1143 At 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} 1150 template <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\ 1163 At most \tcode{last  first} applications of the predicate. 1164 \end{itemdescr} 1065 1165 1066 1166 \rSec2[alg.foreach]{For each} … … 1122 1222 requires CopyConstructible<Pred> 1123 1223 Iter find_if(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@); 1224 1225 template<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}@); 1124 1228 \end{itemdecl}\color{black} 1125 1229 … … 1133 1237 for which the following corresponding 1134 1238 conditions hold: 1135 \tcode{*i == \farg{value}, \farg{pred}(*i) != false }.1239 \tcode{*i == \farg{value}, \farg{pred}(*i) != false, \farg{pred}(*i) == false}. 1136 1240 Returns \farg{last}\ if no such iterator is found. 1137 1241 … … 1522 1626 \tcode{\farg{last}\  \farg{first}} 1523 1627 assignments. 1628 \end{itemdescr} 1629 1630 \color{addclr} 1631 \begin{itemdecl} 1632 template<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\ 1646 For each nonnegative 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\ 1654 Exactly \tcode{n} assignments. 1655 \end{itemdescr} 1656 1657 \color{addclr} 1658 \begin{itemdecl} 1659 template<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\ 1670 The ranges \tcode{[first,last)} and \tcode{[result,result + (last  first))} shall not overlap. 1671 1672 \pnum 1673 \effects\ 1674 Copies 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\ 1678 Exactly \tcode{last  first} applications of the corresponding predicate. 1679 1680 \pnum 1681 \notes\ 1682 Stable. 1524 1683 \end{itemdescr} 1525 1684 … … 2466 2625 \rSec2[alg.partitions]{Partitions} 2467 2626 2627 \index{is_partitioned@\tcode{is_partitioned}}% 2628 \color{addclr}\begin{itemdecl} 2629 template <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\ 2645 Linear. At most \tcode{last  first} applications of \tcode{pred}. 2646 \end{itemdescr} 2647 2468 2648 \index{partition@\tcode{partition}}% 2469 2649 \color{addclr}\begin{itemdecl} … … 2565 2745 \tcode{\farg{last}\  \farg{first}}\ 2566 2746 applications of the predicate. 2747 \end{itemdescr} 2748 2749 \index{partition_copy@\tcode{partition_copy}}% 2750 \color{addclr}\begin{itemdecl} 2751 template <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\ 2768 For 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\ 2773 A 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\ 2777 Exactly \tcode{last  first} applications of \tcode{pred}. 2778 \end{itemdescr} 2779 2780 \index{partition_point@\tcode{partition_point}}% 2781 \color{addclr}\begin{itemdecl} 2782 template<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\ 2795 An 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}. 2567 2800 \end{itemdescr} 2568 2801 … … 4318 4551 to determine which mutating algorithms required 4319 4552 \tcode{ShuffleIterator} and which required \tcode{HasSwap} on the 4320 iterator's reference types. 4553 iterator's reference types. Daniel Kr\"ugler provided conceptualized 4554 versions of the algorithms in N2666. 4321 4555 4322 4556 \bibliographystyle{plain} 
sandbox/committee/concepts/stdlib/clibnumerics.tex
r48273 r48282 81 81 require \tcode{FloatingPointType}, which more accurately 82 82 characterizes the actual requirements for the \tcode{complex} type. 83 \item Added \tcode{iota}, conceptualized by Daniel Kr\"ugler. 83 84 \end{itemize} 84 85 … … 3445 3446 OutIter @\farg{result}@, 3446 3447 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}@); 3447 3452 \end{codeblock} 3448 3453 \color{black} … … 3715 3720 \end{itemdescr} 3716 3721 3722 \rSec2[numeric.iota]{Iota} 3723 \index{iota@\tcode{iota}}% 3724 \color{addclr}\begin{itemdecl} 3725 template <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\ 3737 For 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\ 3741 Exactly \tcode{last  first} increments and assignments. 3742 \end{itemdescr} 3743 3717 3744 \end{paras} 3745 3746 \section*{Acknowledgments} 3747 Daniel Kr\"ugler provided conceptualized 3748 versions of \tcode{iota} in N2666. 3718 3749 3719 3750 \bibliographystyle{plain}
Note: See TracChangeset
for help on using the changeset viewer.