ceph/src/boost/libs/range/doc/reference/algorithm/set_intersection.qbk

   1 [/
   2     Copyright 2010 Neil Groves
   3     Distributed under the Boost Software License, Version 1.0.
   4     (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   5 /]
   6 [section:set_intersection set_intersection]
   7
   8 [heading Prototype]
   9
  10 ``
  11 template<
  12     class SinglePassRange1,
  13     class SinglePassRange2,
  14     class OutputIterator
  15     >
  16 OutputIterator set_intersection(const SinglePassRange1& rng1,
  17                                 const SinglePassRange2& rng2,
  18                                 OutputIterator          out);
  19
  20 template<
  21     class SinglePassRange1,
  22     class SinglePassRange2,
  23     class OutputIterator,
  24     class BinaryPredicate
  25     >
  26 OutputIterator set_intersection(const SinglePassRange1& rng1,
  27                                 const SinglePassRange2& rng2,
  28                                 OutputIterator          out,
  29                                 BinaryPredicate         pred);
  30 ``
  31
  32 [heading Description]
  33
  34 `set_intersection` constructs a sorted range that is the intersection of the sorted ranges `rng1` and `rng2`. The return value is the end of the output range.
  35
  36 The ordering relationship is determined by using `operator<` in the non-predicate versions, and by evaluating `pred` in the predicate versions.
  37
  38 [heading Definition]
  39
  40 Defined in the header file `boost/range/algorithm/set_algorithm.hpp`
  41
  42 [heading Requirements]
  43
  44 [*For the non-predicate versions:]
  45
  46 * `SinglePassRange1` is a model of the __single_pass_range__ Concept.
  47 * `SinglePassRange2` is a model of the __single_pass_range__ Concept.
  48 * `OutputIterator` is a model of the `OutputIteratorConcept`.
  49 * `SinglePassRange1` and `SinglePassRange2` have the same value type.
  50 * `SinglePassRange1`'s value type is a model of the `LessThanComparableConcept`.
  51 * `SinglePassRange2`'s value type is a model of the `LessThanComparableConcept`.
  52 * The ordering of objects of type `SinglePassRange1`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
  53 * The ordering of objects of type `SinglePassRange2`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
  54
  55 [*For the predicate versions:]
  56
  57 * `SinglePassRange1` is a model of the __single_pass_range__ Concept.
  58 * `SinglePassRange2` is a model of the __single_pass_range__ Concept.
  59 * `OutputIterator` is a model of the `OutputIteratorConcept`.
  60 * `SinglePassRange1` and `SinglePassRange2` have the same value type.
  61 * `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
  62 * `SinglePassRange1`'s value type is convertible to `BinaryPredicate`'s first argument type.
  63 * `SinglePassRange2`'s value type is convertible to `BinaryPredicate`'s second argument types.
  64
  65 [heading Precondition:]
  66
  67 [*For the non-predicate versions:]
  68
  69 `rng1` and `rng2` are sorted in ascending order according to `operator<`.
  70
  71 [*For the predicate versions:]
  72
  73 `rng1` and `rng2` are sorted in ascending order according to `pred`.
  74
  75 [heading Complexity]
  76
  77 Linear. `O(N)`, where `N` is `distance(rng1) + distance(rng2)`.
  78
  79 [endsect]
  80
  81