ceph/src/boost/libs/mpl/doc/src/refmanual/sort.rst

   1 .. Algorithms/Transformation Algorithms//sort |95
   2
   3 sort
   4 ====
   5
   6 Synopsis
   7 --------
   8
   9 .. parsed-literal::
  10
  11     template<
  12           typename Seq
  13         , typename Pred = less<_1,_2>
  14         , typename In = |unspecified|
  15         >
  16     struct sort
  17     {
  18         typedef |unspecified| type;
  19     };
  20
  21
  22 Description
  23 -----------
  24
  25 Returns a new sequence of all elements in the range |begin/end<Seq>| sorted according
  26 to the ordering relation ``Pred``.
  27
  28 |transformation algorithm disclaimer|
  29
  30
  31 Header
  32 ------
  33
  34 .. parsed-literal::
  35
  36     #include <boost/mpl/sort.hpp>
  37
  38
  39 Model of
  40 --------
  41
  42 |Reversible Algorithm|
  43
  44
  45 Parameters
  46 ----------
  47
  48 +-------------------+-----------------------------------+-------------------------------+
  49 | Parameter         | Requirement                       | Description                   |
  50 +===================+===================================+===============================+
  51 | ``Seq``           | |Forward Sequence|                | An original sequence.         |
  52 +-------------------+-----------------------------------+-------------------------------+
  53 | ``Pred``          | Binary |Lambda Expression|        | An ordering relation.         |
  54 +-------------------+-----------------------------------+-------------------------------+
  55 | ``In``            | |Inserter|                        | An inserter.                  |
  56 +-------------------+-----------------------------------+-------------------------------+
  57
  58
  59 Expression semantics
  60 --------------------
  61
  62 |Semantics disclaimer...| |Reversible Algorithm|.
  63
  64 For any |Forward Sequence| ``s``, a binary |Lambda Expression| ``pred``, and an
  65 |Inserter| ``in``:
  66
  67
  68 .. parsed-literal::
  69
  70     typedef sort<s,pred,in>::type r;
  71
  72 :Return type:
  73     A type.
  74
  75 :Semantics:
  76     If ``size<s>::value <= 1``, equivalent to
  77
  78     .. parsed-literal::
  79
  80         typedef copy<s,in>::type r;
  81
  82
  83     otherwise equivalent to
  84
  85     .. parsed-literal::
  86
  87         typedef back_inserter< vector<> > aux_in;
  88         typedef lambda<pred>::type p;
  89
  90         typedef begin<s>::type pivot;
  91         typedef partition<
  92               iterator_range< next<pivot>::type, end<s>::type >
  93             , apply_wrap2<p,_1,deref<pivot>::type>
  94             , aux_in
  95             , aux_in
  96             >::type partitioned;
  97
  98         typedef sort<partitioned::first,p,aux_in >::type part1;
  99         typedef sort<partitioned::second,p,aux_in >::type part2;
 100
 101         typedef copy<
 102               joint_view<
 103                   joint_view<part1,single_view< deref<pivot>::type > >
 104                 , part2
 105                 >
 106             , in
 107             >::type r;
 108
 109
 110 Complexity
 111 ----------
 112
 113 Average *O(n log(n))* where *n* == ``size<s>::value``, quadratic at worst.
 114
 115 Example
 116 -------
 117
 118 .. parsed-literal::
 119
 120     typedef vector_c<int,3,4,0,-5,8,-1,7> numbers;
 121     typedef vector_c<int,-5,-1,0,3,4,7,8> expected;
 122     typedef sort<numbers>::type result;
 123
 124     BOOST_MPL_ASSERT(( equal< result, expected, equal_to<_,_> > ));
 125
 126
 127 See also
 128 --------
 129
 130 |Transformation Algorithms|, |Reversible Algorithm|, |partition|
 131
 132
 133 .. copyright:: Copyright ©  2001-2009 Aleksey Gurtovoy and David Abrahams
 134    Distributed under the Boost Software License, Version 1.0. (See accompanying
 135    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)