[GeekBand] STL与泛型编程-3

本篇笔记主要列出各个算法的函数模板。
非变异算法

---

for_each

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

find

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

find_if

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

adjacent_find

// equality version
template <class ForwardIterator>
    ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last);

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

find_first_of

// equality version
template <class ForwardIterator1, class ForwardIterator2>
    ForwardIterator1 find_first_of (ForwardIterator1 first1, ForwardIterator1 last1,
                                    ForwardIterator2 first2, ForwardIterator2 last2);

// predicate version
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
    ForwardIterator1 find_first_of (ForwardIterator1 first1, ForwardIterator1 last1,
                                    ForwardIterator2 first2, ForwardIterator2 last2,
                                    BinaryPredicate pred);

count

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

count_if

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

mismatch

// equality version
template <class InputIterator1, class InputIterator2>
    pair<InputIterator1, InputIterator2>
    mismatch (InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, InputIterator2 last2);

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

equal

// equality version
template <class InputIterator1, class InputIterator2>
    bool equal (InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, InputIterator2 last2);

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

search

// equality version
template <class ForwardIterator1, class ForwardIterator2>
    ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2);

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

变异算法

copy

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

// copy_n
template <class InputIterator, class Size, class OutputIterator>
    OutputIterator copy_n (InputIterator first, Size n, 
                           OutputIterator result);

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

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

swap

// swap
template <class T> void swap (T& a, T& b);

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

transform

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

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

replace

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

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

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

// replace_copy_if
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);

fill

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

generate

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

remove

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

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

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

unique

// equality 
template <class ForwardIterator>
    ForwardIterator unique (ForwardIterator first, ForwardIterator last);

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

reverse

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

rotate

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

random_shuffle

// generator by default 
template <class RandomAccessIterator>
    void random_shuffle (RandomAccessIterator first, RandomAccessIterator last);

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

partition

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

排序

• 冒泡排序
• 插入排序：直接插入排序、希尔排序
• 选择排序(const)：直接选择排序、堆排序
• 快速排序
• 归并排序(const)
• 桶排序
• 基数排序(const)
• 计数排序

内存分配器

内存分配器需要满足一下接口：

• 一组 typedef：

allocator::value_type
allocator::pointer
allocator::const_pointer
allocator::reference
allocator::const_reference
allocator::size_type
allocator::difference_type

• allocator::rebind：allocator 的内嵌模板，需要定义 other 成员
• allocator::allocator()：构造函数