非修改序列操作

for_each

1
2


template <class InputIterator, class Function>
   Function for_each (InputIterator first, InputIterator last, Function fn);

1
2
3
4
5
6
7
8
9


template<class InputIterator, class Function>
  Function for_each(InputIterator first, InputIterator last, Function fn)
{
  while (first!=last) {
    fn (*first);
    ++first;
  }
  return fn;      // or, since C++11: return move(fn);
}

all_of

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


// all_of example
#include <iostream>     // std::cout
#include <algorithm>    // std::all_of
#include <array>        // std::array

int main () {
  std::array<int,8> foo = {3,5,7,11,13,17,19,23};

  if ( std::all_of(foo.begin(), foo.end(), [](int i){return i%2;}) )
    std::cout << "All the elements are odd numbers.\n";

  return 0;
}

for_each

1
2


template <class InputIterator, class Function>
   Function for_each (InputIterator first, InputIterator last, Function fn);

find

1
2


template <class InputIterator, class T>
   InputIterator find (InputIterator first, InputIterator last, const T& val);

1
2
3
4
5
6
7
8
9


template<class InputIterator, class T>
  InputIterator find (InputIterator first, InputIterator last, const T& val)
{
  while (first!=last) {
    if (*first==val) return first;
    ++first;
  }
  return last;
}

find_if

1
2


template <class InputIterator, class UnaryPredicate>
   InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);

1
2
3
4
5
6
7
8
9


template<class InputIterator, class UnaryPredicate>
  InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred)
{
  while (first!=last) {
    if (pred(*first)) return first;
    ++first;
  }
  return last;
}

find_end

1
2
3
4
5
6
7


template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,
                              ForwardIterator2 first2, ForwardIterator2 last2);
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
   ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,
                              ForwardIterator2 first2, ForwardIterator2 last2,
                              BinaryPredicate pred);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


template<class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2)
{
  if (first2==last2) return last1;  // specified in C++11

  ForwardIterator1 ret = last1;

  while (first1!=last1)
  {
    ForwardIterator1 it1 = first1;
    ForwardIterator2 it2 = first2;
    while (*it1==*it2) {    // or: while (pred(*it1,*it2)) for version (2)
        ++it1; ++it2;
        if (it2==last2) { ret=first1; break; }
        if (it1==last1) return ret;
    }
    ++first1;
  }
  return ret;
}

find_first_of

1
2
3
4
5
6
7


template <class InputIterator, class ForwardIterator>
   InputIterator find_first_of (InputIterator first1, InputIterator last1,
                                   ForwardIterator first2, ForwardIterator last2);
template <class InputIterator, class ForwardIterator, class BinaryPredicate>
   InputIterator find_first_of (InputIterator first1, InputIterator last1,
                                   ForwardIterator first2, ForwardIterator last2,
                                   BinaryPredicate pred);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


template<class InputIterator, class ForwardIterator>
  InputIterator find_first_of ( InputIterator first1, InputIterator last1,
                                ForwardIterator first2, ForwardIterator last2)
{
  while (first1!=last1) {
    for (ForwardIterator it=first2; it!=last2; ++it) {
      if (*it==*first1)          // or: if (pred(*it,*first)) for version (2)
        return first1;
    }
    ++first1;
  }
  return last1;
}

adjacent_find

1
2
3
4
5


template <class ForwardIterator>
   ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
   ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last,
                                  BinaryPredicate pred);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


template <class ForwardIterator>
   ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last)
{
  if (first != last)
  {
    ForwardIterator next=first; ++next;
    while (next != last) {
      if (*first == *next)     // or: if (pred(*first,*next)), for version (2)
        return first;
      ++first; ++next;
    }
  }
  return last;
}

equal

1
2
3
4
5
6


template <class InputIterator1, class InputIterator2>
  bool equal (InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2);
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
  bool equal (InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, BinaryPredicate pred);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


template <class InputIterator1, class InputIterator2>
  bool equal ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
{
  while (first1!=last1) {
    if (!(*first1 == *first2))   // or: if (!pred(*first1,*first2)), for version 2
      return false;
    ++first1; ++first2;
  }
  return true;
}

count

1
2
3


template <class InputIterator, class T>
  typename iterator_traits<InputIterator>::difference_type
    count (InputIterator first, InputIterator last, const T& val);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


template <class InputIterator, class T>
  typename iterator_traits<InputIterator>::difference_type
    count (InputIterator first, InputIterator last, const T& val)
{
  typename iterator_traits<InputIterator>::difference_type ret = 0;
  while (first!=last) {
    if (*first == val) ++ret;
    ++first;
  }
  return ret;
}

count_if

1
2
3


template <class InputIterator, class UnaryPredicate>
  typename iterator_traits<InputIterator>::difference_type
    count_if (InputIterator first, InputIterator last, UnaryPredicate pred);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


template <class InputIterator, class UnaryPredicate>
  typename iterator_traits<InputIterator>::difference_type
    count_if (InputIterator first, InputIterator last, UnaryPredicate pred)
{
  typename iterator_traits<InputIterator>::difference_type ret = 0;
  while (first!=last) {
    if (pred(*first)) ++ret;
    ++first;
  }
  return ret;
}

mismatch

1
2
3
4
5
6
7
8


template <class InputIterator1, class InputIterator2>
  pair<InputIterator1, InputIterator2>
    mismatch (InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2);
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
  pair<InputIterator1, InputIterator2>
    mismatch (InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, BinaryPredicate pred);

1
2
3
4
5
6
7
8


template <class InputIterator1, class InputIterator2>
  pair<InputIterator1, InputIterator2>
    mismatch (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
{
  while ( (first1!=last1) && (*first1==*first2) )  // or: pred(*first1,*first2), for version 2
  { ++first1; ++first2; }
  return std::make_pair(first1,first2);
}

search

1
2
3
4
5
6
7


template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
                            ForwardIterator2 first2, ForwardIterator2 last2);
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
   ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
                            ForwardIterator2 first2, ForwardIterator2 last2,
                            BinaryPredicate pred);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


template<class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
                            ForwardIterator2 first2, ForwardIterator2 last2)
{
  if (first2==last2) return first1;  // specified in C++11

  while (first1!=last1)
  {
    ForwardIterator1 it1 = first1;
    ForwardIterator2 it2 = first2;
    while (*it1==*it2) {    // or: while (pred(*it1,*it2)) for version 2
        if (it2==last2) return first1;
        if (it1==last1) return last1;
        ++it1; ++it2;
    }
    ++first1;
  }
  return last1;
}

search_n

1
2
3
4
5
6


template <class ForwardIterator, class Size, class T>
   ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
                             Size count, const T& val);
template <class ForwardIterator, class Size, class T, class BinaryPredicate>
   ForwardIterator search_n ( ForwardIterator first, ForwardIterator last,
                              Size count, const T& val, BinaryPredicate pred );

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


template<class ForwardIterator, class Size, class T>
  ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
                            Size count, const T& val)
{
  ForwardIterator it, limit;
  Size i;

  limit=first; std::advance(limit,std::distance(first,last)-count);

  while (first!=limit)
  {
    it = first; i=0;
    while (*it==val)       // or: while (pred(*it,val)) for the pred version
      { ++it; if (++i==count) return first; }
    ++first;
  }
  return last;
}

修改序列操作

copy

1
2


template <class InputIterator, class OutputIterator>
  OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result);

1
2
3
4
5
6
7
8
9


template<class InputIterator, class OutputIterator>
  OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
{
  while (first!=last) {
    *result = *first;
    ++result; ++first;
  }
  return result;
}

copy_backward

1
2
3
4


template <class BidirectionalIterator1, class BidirectionalIterator2>
  BidirectionalIterator2 copy_backward (BidirectionalIterator1 first,
                                        BidirectionalIterator1 last,
                                        BidirectionalIterator2 result);

swap_ranges

1
2
3


template <class ForwardIterator1, class ForwardIterator2>
  ForwardIterator2 swap_ranges (ForwardIterator1 first1, ForwardIterator1 last1,
                                ForwardIterator2 first2);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


template<class ForwardIterator1, class ForwardIterator2>
  ForwardIterator2 swap_ranges (ForwardIterator1 first1, ForwardIterator1 last1,
                                ForwardIterator2 first2)
{
  while (first1!=last1) {
    swap (*first1, *first2);
    ++first1; ++first2;
  }
  return first2;
}

iter_swap

template <class ForwardIterator1, class ForwardIterator2>
  void iter_swap (ForwardIterator1 a, ForwardIterator2 b);

1
2
3
4
5


template <class ForwardIterator1, class ForwardIterator2>
  void iter_swap (ForwardIterator1 a, ForwardIterator2 b)
{
  swap (*a, *b);
}

1
2
3
4
5


template <class InputIterator1, class InputIterator2,
          class OutputIterator, class BinaryOperation>
  OutputIterator transform (InputIterator1 first1, InputIterator1 last1,
                            InputIterator2 first2, OutputIterator result,
                            BinaryOperation binary_op);

transform

1
2
3


template <class InputIterator, class OutputIterator, class UnaryOperation>
  OutputIterator transform (InputIterator first1, InputIterator last1,
                            OutputIterator result, UnaryOperation op);

replace

1
2
3


template <class ForwardIterator, class T>
  void replace (ForwardIterator first, ForwardIterator last,
                const T& old_value, const T& new_value);

1
2
3
4
5
6
7
8
9


template <class ForwardIterator, class T>
  void replace (ForwardIterator first, ForwardIterator last,
                const T& old_value, const T& new_value)
{
  while (first!=last) {
    if (*first == old_value) *first=new_value;
    ++first;
  }
}

preplace_if

1
2
3


template <class ForwardIterator, class UnaryPredicate, class T>
  void replace_if (ForwardIterator first, ForwardIterator last,
                   UnaryPredicate pred, const T& new_value );

1
2
3
4
5
6
7
8
9


template < class ForwardIterator, class UnaryPredicate, class T >
  void replace_if (ForwardIterator first, ForwardIterator last,
                   UnaryPredicate pred, const T& new_value)
{
  while (first!=last) {
    if (pred(*first)) *first=new_value;
    ++first;
  }
}

replace_copy_if

1
2
3
4


template <class InputIterator, class OutputIterator, class UnaryPredicate, class T>
  OutputIterator replace_copy_if (InputIterator first, InputIterator last,
                                  OutputIterator result, UnaryPredicate pred,
                                  const T& new_value);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


template <class InputIterator, class OutputIterator, class UnaryPredicate, class T>
  OutputIterator replace_copy_if (InputIterator first, InputIterator last,
                                  OutputIterator result, UnaryPredicate pred,
                                  const T& new_value)
{
  while (first!=last) {
    *result = (pred(*first))? new_value: *first;
    ++first; ++result;
  }
  return result;
}

replace_copy

1
2
3
4


template <class InputIterator, class OutputIterator, class T>
  OutputIterator replace_copy (InputIterator first, InputIterator last,
                               OutputIterator result,
                               const T& old_value, const T& new_value);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


template <class InputIterator, class OutputIterator, class T>
  OutputIterator replace_copy (InputIterator first, InputIterator last,
                               OutputIterator result, const T& old_value, const T& new_value)
{
  while (first!=last) {
    *result = (*first==old_value)? new_value: *first;
    ++first; ++result;
  }
  return result;
}

fill

template <class ForwardIterator, class T>
  void fill (ForwardIterator first, ForwardIterator last, const T& val);

将[first, last)内的所有元素改填新值。

1
2
3
4
5
6
7
8


template <class ForwardIterator, class T>
  void fill (ForwardIterator first, ForwardIterator last, const T& val)
{
  while (first != last) {
    *first = val;
    ++first;
  }
}

fill_n

template <class OutputIterator, class Size, class T>
  OutputIterator fill_n (OutputIterator first, Size n, const T& val);

将[first, last)内的前n个元素改填新值，返回的迭代器指向被填入的最后一个元素的下一位置。

1
2
3
4
5
6
7
8
9


template <class OutputIterator, class Size, class T>
  OutputIterator fill_n (OutputIterator first, Size n, const T& val)
{
  while (n>0) {
    *first = val;
    ++first; --n;
  }
  return first;     // since C++11
}

generate

1
2


template <class ForwardIterator, class Generator>
  void generate (ForwardIterator first, ForwardIterator last, Generator gen);

1
2
3
4
5
6
7
8


template <class ForwardIterator, class Generator>
  void generate ( ForwardIterator first, ForwardIterator last, Generator gen )
{
  while (first != last) {
    *first = gen();
    ++first;
  }
}

generate_n

1
2


template <class OutputIterator, class Size, class Generator>
  OutputIterator generate_n (OutputIterator first, Size n, Generator gen);

1
2
3
4
5
6
7
8


template <class OutputIterator, class Size, class Generator>
  void generate_n ( OutputIterator first, Size n, Generator gen )
{
  while (n>0) {
    *first = gen();
    ++first; --n;
  }
}

remove

1
2


template <class ForwardIterator, class T>
  ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


template <class ForwardIterator, class T>
  ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator result = first;
  while (first!=last) {
    if (!(*first == val)) {
      *result = move(*first);
      ++result;
    }
    ++first;
  }
  return result;
}

remove_copy

1
2
3


template <class InputIterator, class OutputIterator, class T>
  OutputIterator remove_copy (InputIterator first, InputIterator last,
                              OutputIterator result, const T& val);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


template <class InputIterator, class OutputIterator, class T>
  OutputIterator remove_copy (InputIterator first, InputIterator last,
                              OutputIterator result, const T& val)
{
  while (first!=last) {
    if (!(*first == val)) {
      *result = *first;
      ++result;
    }
    ++first;
  }
  return result;
}

remove_if

1
2
3


template <class ForwardIterator, class UnaryPredicate>
  ForwardIterator remove_if (ForwardIterator first, ForwardIterator last,
                             UnaryPredicate pred);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


template <class ForwardIterator, class UnaryPredicate>
  ForwardIterator remove_if (ForwardIterator first, ForwardIterator last,
                             UnaryPredicate pred)
{
  ForwardIterator result = first;
  while (first!=last) {
    if (!pred(*first)) {
      *result = std::move(*first);
      ++result;
    }
    ++first;
  }
  return result;
}

remove_copy_if

1
2
3


template <class InputIterator, class OutputIterator, class UnaryPredicate>
  OutputIterator remove_copy_if (InputIterator first, InputIterator last,
                                 OutputIterator result, UnaryPredicate pred);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


template <class InputIterator, class OutputIterator, class UnaryPredicate>
  OutputIterator remove_copy_if (InputIterator first, InputIterator last,
                                 OutputIterator result, UnaryPredicate pred)
{
  while (first!=last) {
    if (!pred(*first)) {
      *result = *first;
      ++result;
    }
    ++first;
  }
  return result;
}

unique

1
2
3
4
5


template <class ForwardIterator>
  ForwardIterator unique (ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
  ForwardIterator unique (ForwardIterator first, ForwardIterator last,
                          BinaryPredicate pred);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


template <class InputIterator, class OutputIterator>
  OutputIterator unique_copy (InputIterator first, InputIterator last,
                              OutputIterator result)
{
  if (first==last) return result;

  *result = *first;
  while (++first != last) {
    typename iterator_traits<InputIterator>::value_type val = *first;
    if (!(*result == val))   // or: if (!pred(*result,val)) for version (2)
      *(++result)=val;
  }
  return ++result;
}

unique_copy

1
2
3
4
5
6


template <class InputIterator, class OutputIterator>
  OutputIterator unique_copy (InputIterator first, InputIterator last,
                              OutputIterator result);
template <class InputIterator, class OutputIterator, class BinaryPredicate>
  OutputIterator unique_copy (InputIterator first, InputIterator last,
                              OutputIterator result, BinaryPredicate pred);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


template <class InputIterator, class OutputIterator>
  OutputIterator unique_copy (InputIterator first, InputIterator last,
                              OutputIterator result)
{
  if (first==last) return result;

  *result = *first;
  while (++first != last) {
    typename iterator_traits<InputIterator>::value_type val = *first;
    if (!(*result == val))   // or: if (!pred(*result,val)) for version (2)
      *(++result)=val;
  }
  return ++result;
}

reverse

1
2


template <class BidirectionalIterator>
  void reverse (BidirectionalIterator first, BidirectionalIterator last);

1
2
3
4
5
6
7
8


template <class BidirectionalIterator>
  void reverse (BidirectionalIterator first, BidirectionalIterator last)
{
  while ((first!=last)&&(first!=--last)) {
    std::iter_swap (first,last);
    ++first;
  }
}

reverse_copy

1
2
3


template <class BidirectionalIterator, class OutputIterator>
  OutputIterator reverse_copy (BidirectionalIterator first,
                               BidirectionalIterator last, OutputIterator result);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


template <class BidirectionalIterator, class OutputIterator>
  OutputIterator reverse_copy (BidirectionalIterator first,
                               BidirectionalIterator last, OutputIterator result)
{
  while (first!=last) {
    --last;
    *result = *last;
    ++result;
  }
  return result;
}

rotate

1
2
3


template <class ForwardIterator>
  ForwardIterator rotate (ForwardIterator first, ForwardIterator middle,
                          ForwardIterator last);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


template <class ForwardIterator>
  void rotate (ForwardIterator first, ForwardIterator middle,
               ForwardIterator last)
{
  ForwardIterator next = middle;
  while (first!=next)
  {
    swap (*first++,*next++);
    if (next==last) next=middle;
    else if (first==middle) middle=next;
  }
}

rotate_copy

1
2
3


template <class ForwardIterator, class OutputIterator>
  OutputIterator rotate_copy (ForwardIterator first, ForwardIterator middle,
                              ForwardIterator last, OutputIterator result);

1
2
3
4
5
6
7


template <class ForwardIterator, class OutputIterator>
  OutputIterator rotate_copy (ForwardIterator first, ForwardIterator middle,
                              ForwardIterator last, OutputIterator result)
{
  result=std::copy (middle,last,result);
  return std::copy (first,middle,result);
}

random_shuffle

1
2
3
4
5


template <class RandomAccessIterator>
  void random_shuffle (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class RandomNumberGenerator>
  void random_shuffle (RandomAccessIterator first, RandomAccessIterator last,
                       RandomNumberGenerator&& gen);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


template <class RandomAccessIterator, class RandomNumberGenerator>
  void random_shuffle (RandomAccessIterator first, RandomAccessIterator last,
                       RandomNumberGenerator& gen)
{
  iterator_traits<RandomAccessIterator>::difference_type i, n;
  n = (last-first);
  for (i=n-1; i>0; --i) {
    swap (first[i],first[gen(i+1)]);
  }
}

Partitions

partition

1
2
3


template <class ForwardIterator, class UnaryPredicate>
  ForwardIterator partition (ForwardIterator first,
                             ForwardIterator last, UnaryPredicate pred);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


template <class BidirectionalIterator, class UnaryPredicate>
  BidirectionalIterator partition (BidirectionalIterator first,
                                   BidirectionalIterator last, UnaryPredicate pred)
{
  while (first!=last) {
    while (pred(*first)) {
      ++first;
      if (first==last) return first;
    }
    do {
      --last;
      if (first==last) return first;
    } while (!pred(*last));
    swap (*first,*last);
    ++first;
  }
  return first;
}

Sorting

partial_sort

1
2
3
4
5
6


template <class RandomAccessIterator>
  void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,
                     RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
  void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,
                     RandomAccessIterator last, Compare comp);

partial_sort_copy

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


template <class InputIterator, class RandomAccessIterator>
  RandomAccessIterator
    partial_sort_copy (InputIterator first,InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last);
template <class InputIterator, class RandomAccessIterator, class Compare>
  RandomAccessIterator
    partial_sort_copy (InputIterator first,InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last, Compare comp);

sort

1
2
3
4


template <class RandomAccessIterator>
  void sort (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

nth_element

1
2
3
4
5
6


template <class RandomAccessIterator>
  void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
                    RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
  void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
                    RandomAccessIterator last, Compare comp);

Binary search

lower_bound

1
2
3
4
5
6


template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                               const T& val);
template <class ForwardIterator, class T, class Compare>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                               const T& val, Compare comp);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; advance (it,step);
    if (*it<val) {                 // or: if (comp(*it,val)), for version (2)
      first=++it;
      count-=step+1;
    }
    else count=step;
  }
  return first;
}

upper_bound

1
2
3
4
5
6


template <class ForwardIterator, class T>
  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                               const T& val);
template <class ForwardIterator, class T, class Compare>
  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                               const T& val, Compare comp);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


template <class ForwardIterator, class T>
  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = std::distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; std::advance (it,step);
    if (!(val<*it))                 // or: if (!comp(val,*it)), for version (2)
      { first=++it; count-=step+1;  }
    else count=step;
  }
  return first;
}

equal_range

1
2
3
4
5
6
7


template <class ForwardIterator, class T>
  pair<ForwardIterator,ForwardIterator>
    equal_range (ForwardIterator first, ForwardIterator last, const T& val);
template <class ForwardIterator, class T, class Compare>
  pair<ForwardIterator,ForwardIterator>
    equal_range (ForwardIterator first, ForwardIterator last, const T& val,
                  Compare comp);

1
2
3
4
5
6
7


template <class ForwardIterator, class T>
  pair<ForwardIterator,ForwardIterator>
    equal_range (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it = std::lower_bound (first,last,val);
  return std::make_pair ( it, std::upper_bound(it,last,val) );
}

binary_search

1
2
3
4
5
6


template <class ForwardIterator, class T>
  bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val);
template <class ForwardIterator, class T, class Compare>
  bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val, Compare comp);

1
2
3
4
5
6


template <class ForwardIterator, class T>
  bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
{
  first = std::lower_bound(first,last,val);
  return (first!=last && !(val<*first));
}

Merge

merge

1
2
3
4
5
6
7
8
9


template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator2 last2,
                        OutputIterator result);
template <class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
  OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator2 last2,
                        OutputIterator result, Compare comp);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator2 last2,
                        OutputIterator result)
{
  while (true) {
    if (first1==last1) return std::copy(first2,last2,result);
    if (first2==last2) return std::copy(first1,last1,result);
    *result++ = (*first2<*first1)? *first2++ : *first1++;
  }
}

inplace_merge

1
2
3
4
5
6


template <class BidirectionalIterator>
  void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
                      BidirectionalIterator last);
template <class BidirectionalIterator, class Compare>
  void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
                      BidirectionalIterator last, Compare comp);

includes

1
2
3
4
5
6
7


template <class InputIterator1, class InputIterator2>
  bool includes ( InputIterator1 first1, InputIterator1 last1,
                  InputIterator2 first2, InputIterator2 last2 );

template <class InputIterator1, class InputIterator2, class Compare>
  bool includes ( InputIterator1 first1, InputIterator1 last1,
                  InputIterator2 first2, InputIterator2 last2, Compare comp );

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


template <class InputIterator1, class InputIterator2>
  bool includes (InputIterator1 first1, InputIterator1 last1,
                 InputIterator2 first2, InputIterator2 last2)
{
  while (first2!=last2) {
    if ( (first1==last1) || (*first2<*first1) ) return false;
    if (!(*first1<*first2)) ++first2;
    ++first1;
  }
  return true;
}

Heap

push_heap

1
2
3
4
5


template <class RandomAccessIterator>
  void push_heap (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
  void push_heap (RandomAccessIterator first, RandomAccessIterator last,
                   Compare comp);

pop_heap

1
2
3
4
5


template <class RandomAccessIterator>
  void pop_heap (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
  void pop_heap (RandomAccessIterator first, RandomAccessIterator last,
                 Compare comp);

sort_heap

1
2
3
4
5


template <class RandomAccessIterator>
  void sort_heap (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
  void sort_heap (RandomAccessIterator first, RandomAccessIterator last,
                  Compare comp);

Min/Max

min

1
2
3
4
5
6


template <class T> const T& min (const T& a, const T& b);
template <class T, class Compare>
  const T& min (const T& a, const T& b, Compare comp);
template <class T> T min (initializer_list<T> il);
template <class T, class Compare>
  T min (initializer_list<T> il, Compare comp);

取两个对象的较小值.

1
2
3


template <class T> const T& min (const T& a, const T& b) {
  return !(b<a)?a:b;     // or: return !comp(b,a)?a:b; for version (2)
}

max

1
2
3
4
5
6


template <class T> const T& max (const T& a, const T& b);
template <class T, class Compare>
const T& max (const T& a, const T& b, Compare comp);
template <class T> T max (initializer_list<T> il);
template <class T, class Compare>
  T max (initializer_list<T> il, Compare comp);

取两个对象中的较大值。

1
2
3


template <class T> const T& max (const T& a, const T& b) {
  return (a<b)?b:a;     // or: return comp(a,b)?b:a; for version (2)
}

max_element

1
2
3
4
5


template <class ForwardIterator>
  ForwardIterator max_element (ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class Compare>
  ForwardIterator max_element (ForwardIterator first, ForwardIterator last,
                               Compare comp);

这个算法返回一个迭代器,指向序列之中数值最大的元素.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


template <class ForwardIterator>
  ForwardIterator max_element ( ForwardIterator first, ForwardIterator last )
{
  if (first==last) return last;
  ForwardIterator largest = first;

  while (++first!=last)
    if (*largest<*first)    // or: if (comp(*largest,*first)) for version (2)
      largest=first;
  return largest;
}

min_element

1
2
3
4
5


template <class ForwardIterator>
  ForwardIterator min_element (ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class Compare>
  ForwardIterator min_element (ForwardIterator first, ForwardIterator last,
                               Compare comp);

这个算法返回一个迭代器,指向序列之中数值最小的元素.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


template <class ForwardIterator>
  ForwardIterator min_element ( ForwardIterator first, ForwardIterator last )
{
  if (first==last) return last;
  ForwardIterator smallest = first;

  while (++first!=last)
    if (*first<*smallest)    // or: if (comp(*first,*smallest)) for version (2)
      smallest=first;
  return smallest;
}

其他

lexicographical_compare

1
2
3
4
5
6
7


template <class InputIterator1, class InputIterator2>
  bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2);
template <class InputIterator1, class InputIterator2, class Compare>
  bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                Compare comp);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


template <class InputIterator1, class InputIterator2>
  bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2)
{
  while (first1!=last1)
  {
    if (first2==last2 || *first2<*first1) return false;
    else if (*first1<*first2) return true;
    ++first1; ++first2;
  }
  return (first2!=last2);
}

next_permutation

1
2
3
4
5
6


template <class BidirectionalIterator>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);
template <class BidirectionalIterator, class Compare>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);

prev_permutation

1
2
3
4
5
6


template <class BidirectionalIterator>
  bool prev_permutation (BidirectionalIterator first,
                         BidirectionalIterator last );
template <class BidirectionalIterator, class Compare>
  bool prev_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);

文章目录

非修改序列操作

for_each

all_of

for_each

find

find_if

find_end

find_first_of

adjacent_find

equal

count

count_if

mismatch

search

search_n

修改序列操作

copy

copy_backward

swap_ranges

iter_swap

transform

replace

preplace_if

replace_copy_if

replace_copy

fill

fill_n

generate

generate_n

remove

remove_copy

remove_if

remove_copy_if

unique

unique_copy

reverse

reverse_copy

rotate

rotate_copy

random_shuffle

Partitions

partition

Sorting

partial_sort

partial_sort_copy

sort

nth_element

Binary search

lower_bound

upper_bound

equal_range

binary_search

Merge

merge

inplace_merge

includes

Heap

push_heap

pop_heap

sort_heap

Min/Max

min

max

max_element

min_element

其他

lexicographical_compare

next_permutation

prev_permutation