9 STL Algorithm

9.1 header files

使用C++標(biāo)準(zhǔn)庫的算法呢铆，須先#include <algorithm>。

該頭文件也包含一些輔助函數(shù)啊楚，
    如max()、min()、swap()砚尽，迭代器相關(guān)函數(shù)iter_swap()拆撼。

有些STL算法用于數(shù)值處理容劳，故須 #include <numeric>
functor及 function adapters，須 #include <functional>

9.2 算法概覽

9.2.1 簡介

• 所有STL算法都被設(shè)計有處理一個或多個iterator區(qū)間闸度。

第一個區(qū)間以起點(diǎn)終點(diǎn)表示竭贩，其它區(qū)間一般只提供終點(diǎn)即可，
  其終點(diǎn)由第一區(qū)間的元素數(shù)量推出莺禁。
調(diào)用這須確保區(qū)間有效性留量。

• STL算法采用overwrite而非insert模式。
  故調(diào)用者須確保目標(biāo)區(qū)間有足夠的元素空間哟冬。
  當(dāng)然可用特殊insert iterator將overwrite改變?yōu)閕nsert(p271)楼熄。
• 為提高靈活性和效率，某些STL算法允許傳遞自定義操作浩峡。

這些操作可以使一般函數(shù)可岂，或functor；若返回值為bool翰灾，則稱為predicate缕粹。
可用predicate完成以下工作：
1. 對于查找算法稚茅，用一元predicate作為查找準(zhǔn)則。
2. 對于排序算法平斩，用二元predicate作為排序準(zhǔn)則亚享，如p294姓氏排序。
3. 用一元predicate作為準(zhǔn)則判斷是否應(yīng)該對某元素做相應(yīng)操作绘面。
4. 可為某個數(shù)值算法指定一個數(shù)值運(yùn)算虹蒋。

note: predicate不應(yīng)在函數(shù)調(diào)用過程中改變自身狀態(tài)。

9.2.2 算法分類

nonmodifying algorithm(非變動性算法)
modifying algorithm(變動性算法)
removing algorithm(移除性算法)
mutating algorithm(變序性算法)
sorting algorithm(排序算法)
sorted range algorithm(已序區(qū)間算法)
numeric algorithm(數(shù)值算法)

• nonmodifying algorithm
  不改變元素次序飒货，不改變元素值魄衅，通過input iterator和forward iterator完成操作，故可作用于所有標(biāo)準(zhǔn)容器塘辅。
  

  t9-1.png
  
  for_each()傳遞的操作可改變元素值晃虫。
  string class和STL class是各自獨(dú)立發(fā)展設(shè)計的，故命名“一致性”有出入扣墩。
  
  t9-2.png

• modifying algorithm
  或直接改變元素值哲银，或在復(fù)制到目標(biāo)區(qū)間過程中改變元素值。
  

  t9-3.png

for_each()接受某操作呻惕，該操作可變動其參數(shù)荆责，故該參數(shù)須by reference傳遞。eg:
  void square(int& elem)  // call by reference
  {
      elem = elem*elem;  // assign processed value directly
   }
   // ...
  for_each(col1.begin(), col1.end(), square() );

transform()用某操作亚脆，該操作返回變動后的參數(shù)做院，關(guān)鍵在于可用于將結(jié)果復(fù)制給原元素。eg:
  int square(int elem)  // call by value
  {
    return elem*elem;  // return processed value
  }
  // ...
  transform(col1.begin(), col1.end(), col1.begin(), square);


transform()比for_each()速遞稍慢濒持，
  因?yàn)槠鋵⒎祷刂蒂x值給元素而不是直接變動元素键耕。

merge()可用于合并無序區(qū)間，當(dāng)然結(jié)果也是無序的柑营。
  最好只對已序區(qū)間調(diào)用merge()屈雄。

• removing algorithm
  移除性算法是一種特殊的變動性算法。和modifying algorithm類似官套，作用的區(qū)間不能是關(guān)聯(lián)式容器(關(guān)聯(lián)式容器key為常數(shù))酒奶。
  

  t9-4.png
  
  note: removing algorithm只是 邏輯上移除元素，即 將不需被移除的元素往前overwrite被移除的元素奶赔。故不改變操作區(qū)間元素的個數(shù)惋嚎，且返回邏輯上的新終點(diǎn)位置。(可見p111)

• mutating algorithm(變序算法)
  通過元素值的賦值和交換纺阔，改變元素順序瘸彤。
  

  t9-5.png

• sorting algorithm
  

  t9-6.png
  
  要對所有元素排序，可考慮：

1.sort()笛钝，內(nèi)部采用quicksort质况，故保證了很好的平均性能，
  復(fù)雜度n*lg(n)玻靡，但最差情況也可為二次復(fù)雜度结榄。

2. partial_sort()，內(nèi)部用heapsort囤捻，故任何情況為n*lg(n)臼朗，
  大多情況下heapsort比quicksort慢2-5倍，
  partial_sort()可對前n個元素排序后立即停止蝎土。

3. stable_sort()视哑，內(nèi)部用mergesort，
  只有內(nèi)存足夠時誊涯，才具有n*lg(n)挡毅，否則為n*lg(n)*lg(n)。是穩(wěn)定性排序暴构。

標(biāo)準(zhǔn)規(guī)范規(guī)定了算法復(fù)雜度跪呈，但未規(guī)定具體實(shí)現(xiàn)手法。
若只需要排序后的第n個元素取逾，可考慮：

1. nth_element()耗绿，傳入第一子集的元素個數(shù)(也就確定了第二子集元素個數(shù))，eg:
  // move the four lowest elements to the front
  nth_element(col1.begin(),  // beginning of range
            col1.begin()+3,  // position between first and second
            col1.end() );  // end of range
但調(diào)動后不知道第一子集和第二子集的區(qū)別砾隅，
  兩部分可能包含和第n個元素相等的元素误阻。

2. partition()，須傳入“將第一子集和第二子集區(qū)別開”的排序準(zhǔn)則晴埂。eg:
  // move all elements lee than seven to the front
  vector<int>::iterator pos;
  pos = partition(col1.begin(), col1.end(), bind2nd(less<int>(), 7) );
調(diào)用后不知道第一和第二子集各有多少元素堕绩。
  pos之處第二子集的起點(diǎn)，第二子集元素不滿足被傳入的準(zhǔn)則邑时。

3. stable_partition()奴紧，類似于partition()，但是穩(wěn)定性排序晶丘。

sorting algorithm需要調(diào)用random access iterator黍氮，故不可對List使用sorting algorithm，但List有sort()成員函數(shù)浅浮。

• sorted range algorithm
  

  t9-7.png

• numeric algorithm
  

  t9-8.png

9.3 輔助函數(shù)

本章后續(xù)部分對所有STL算法詳細(xì)討論沫浆，為簡化例子，使問題突出滚秩，定義了一些輔助函數(shù)：

// algo/algostuff.cpp

#ifndef ALGOSTUFF_HPP
#define ALGOSTUFF_HPP
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <functional>
#include <iterator>
#include <numeric>

/* PRINT_ELEMENTS()
 * - prints optional C-string optcstr followed by
 * - all elements of the collection col1
 * - separated by spaces
 */
template <class T>
inline void PRINT_ELEMENTS (const T& col1, const char* optcstr = "")
{
    typename T::const_iterator pos;
    std::cout << optcstr;
    for (pos = col1.begin(); pos != col1.end(); ++pos)
    {
        std::cout << *pos << ' ';
    }
    std::cout << std::endl;
}

/* INSERT_ELEMENTS (collection, first, last)
 * - fill values from first to last into the collection
 * - NOTE: no half-open range
 */
template <class T>
inline void INSERT_ELEMENTS (T& col1, int first, int last)
{
    for (int i = first; i <= last; ++i)
    {
        col1.insert(col1.end(), i);
    }
}

#endif  /* ALGOSTUFF_HPP */

9.4 for_each()

UnaryProc for_each(InputIterator beg, InputIterator end, UnaryProc op)
對區(qū)間 [beg,end)每個元素調(diào)用 op(elem)专执；返回op(在算法內(nèi)部變動過)的一個副本；
op可變動元素郁油；實(shí)現(xiàn)可見p126本股；op的返回值會被忽略攀痊；
復(fù)雜度：線性。調(diào)用op共numberOfElements次拄显。
eg:將print()傳給for_each()苟径，打印所有元素

// 將print()傳給for_each()，打印所有元素
// algo/foreach1.cpp

#include "algostuff.hpp"
using namespace std;

// function called for each element
void print (int elem)
{
    cout << elem << ' ';
}

int main()
{
    vector<int> col1;

    INSERT_ELEMENTS(col1, 1, 9);

    // call print() for each element
    for_each(col1.begin(), col1.end(), print);
    cout << endl;
}

foreach1.png

eg:用functor改變每個元素的內(nèi)容

// 用functor改變每個元素的內(nèi)容
// algo/foreach2.cpp

#include "algostuff.hpp"
using namespace std;

// function object that adds the value with which it is initialized 
template <class T>
class AddValue
{
    private:
        T theValue; // value to add
    public:
        // constructor initializes the value to add
        AddValue (const T& v) : theValue(v){}

        // the function call for the element adds the value
        void operator() (T& elem) const
        {
            elem += theValue;
        }
};

int main()
{
    vector<int> col1;
    INSERT_ELEMENTS(col1, 1, 9);

    // add ten to each element
    for_each (col1.begin(), col1.end(), AddValue<int>(10));
    PRINT_ELEMENTS(col1);

    // add value of first element to each element
    for_each (col1.begin(), col1.end(), AddValue<int>(*col1.begin()));
    PRINT_ELEMENTS(col1);
}

foreach2.png

eg:使用for_each()的返回值躬审。

// 使用for_each()返回值棘街，處理返回結(jié)果
// algo/foreach3.cpp

#include "algostuff.hpp"
using namespace std;

// function object to proccess the mena value
class MeanValue
{
    private:
        long num;   // number of elements
        long sum;   // sum of all element values
    public:
        // constructor
        MeanValue() : num(0), sum(0){}

        // function call
        // - process one more element of the sequence
        void operator() (int elem)
        {
            num++;  // increment count
            sum += elem;    // add value
        }

        // return mean value (implicit type conversion)
        operator double()
        {
            return static_cast<double>(sum)/static_cast<double>(num);
        }
};

int main()
{
    vector<int> col1;

    INSERT_ELEMENTS(col1, 1, 8);

    // process and print mean value
    double mv = for_each (col1.begin(), col1.end(), MeanValue());
    cout << "meaan value: " << mv << endl;
}

output:

foreach3.png

9.5 nonmodifying algorithm

9.5.1 元素計數(shù)

difference_type count (InputIterator beg, InputIterator end, const T& value)
difference_type count_if(InputIterator beg, InputIterator end, UnaryPredicate op)
返回值類型difference_type表示iterator距離：typename iterator_traitts<InputIterator>::difference_type
op不應(yīng)修改傳進(jìn)來的參數(shù)遭殉；關(guān)聯(lián)式容器提供了等效的成員函數(shù)count()。

// 根據(jù)不同準(zhǔn)則對元素計數(shù)
// algo/count1.cpp

#include "algostuff.hpp"
using namespace std;

bool isEven (int elem)
{
    return elem % 2 == 0;
}

int main()
{
    vector<int> col1;
    int num;

    INSERT_ELEMENTS(col1, 1, 9);
    PRINT_ELEMENTS(col1, "col1: ");

    // count and print elements with value 4
    num = count (col1.begin(), col1.end(), 4);
    cout << "number of elements equal to 4: " << num << endl;

    // cout elements with even value
    num = count_if(col1.begin(), col1.end(), isEven);
    cout << "number of elements with even value: " << num << endl;

    // count elements that are greater than value 4
    num = count_if (col1.begin(), col1.end(), bind2nd(greater<int>(), 4));
    cout << "number of elements greater than 4: " << num << endl;
}

count1.png

當(dāng)然也可不必使用上述isEven函數(shù)博助，可用not1(bind2nd(modules<int>(), 2))

9.5.2 最大值和最小值

InputIterator min_element (InputIterator beg, InputIterator end)
InputIterator min_element(InputIterator beg, InputIterator end, CompFunc op)
max_element()參數(shù)類似险污。
無op參數(shù)版本，以operator<進(jìn)行元素比較翔始；op用于比較兩元素罗心，op(elem1,elem2)，若op(elem1)<op(elem2)則應(yīng)返回true城瞎。有多個最小或最大值渤闷，返回第一個最小或最大值。

// 輸出集合內(nèi)最小元素和最大元素脖镀，并輸出絕對值的最小最大值
// algo/minmax1.cpp

#include <cstdlib>
#include "algostuff.hpp"
using namespace std;

bool absLess (int elem1, int elem2)
{
    return abs (elem1) < abs (elem2);
}

int main()
{
    deque<int> col1;

    INSERT_ELEMENTS(col1, 2, 8);
    INSERT_ELEMENTS(col1, -3, 5);

    PRINT_ELEMENTS(col1);

    // process and print minimum and maximum
    cout << "minimum: " << *min_element(col1.begin(), col1.end()) << endl;

    cout << "maximum: " << *max_element(col1.begin(), col1.end()) << endl;

    // process and print minimum and maximum of absolute values
    cout << "minimum of absolute values: " 
        << *min_element(col1.begin(),col1.end(),absLess) << endl;

    cout << "maximum 0f absolute value: "
        << *max_element(col1.begin(), col1.end(), absLess) << endl;
}

minmax1.png

9.5.3 查找元素

• 查找第一個匹配的元素
  InputIterator find (InputIterator beg, InputIterator end, const T& value)
  InputIterator find_if(InputIterator beg, InputIterator end, UnaryPredicate op)
  返回元素值等于value或使op(elem)為true的第一個元素的位置飒箭；若無匹配元素，返回參數(shù)end蜒灰；
  若是已序區(qū)間弦蹂，應(yīng)使用lower_bound()、upper_bound()强窖、equal_range()凸椿、binary_search()獲取更高性能。
  關(guān)聯(lián)式容器提供等效的成員函數(shù)find()翅溺，但為對數(shù)復(fù)雜度而非線性復(fù)雜度脑漫。最多比較次數(shù)numberOfElement。

// 用find()查找一個子區(qū)間：
//  以元素值為4的第一個元素開始咙崎，以元素值為4的第二個元素結(jié)束
// algo/find1.cpp

#include "algostuff.hpp"
using namespace std;

int main()
{
    list<int> col1;

    INSERT_ELEMENTS(col1, 1, 9);
    INSERT_ELEMENTS(col1, 1, 9);

    PRINT_ELEMENTS(col1, "col1: ");

    // find first element with value 4
    list<int>::iterator pos1;
    pos1 = find(col1.begin(), col1.end(), 4);

    /* find second element with value 4
     * - note: continue the search behind the first 4 (if any)
     */
    list<int>::iterator pos2;
    if (pos1 != col1.end())
    {
        pos2 = find(++pos1, col1.end(), 4);
    }
    
    /* print all elements from first to second 4 (both included)
     * - note: now we need the position of the first 4 again (if any)
     * - note: we have to pass the position behind the second 4 (if any)
     */
    if (pos1 != col1.end() && pos2 != col1.end())
    {
        copy (--pos1, ++pos2, ostream_iterator<int>(cout, " "));
        cout << endl;
    }
}

find1.png

// algo/find2.cpp

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> col1;
    vector<int>::iterator pos;

    INSERT_ELEMENTS(col1, 1, 9);
    PRINT_ELEMENTS(col1, "col1: ");

    // find first element greater than 3
    pos = find_if(col1.begin(), col1.end(), bind2nd(greater<int>(), 3));

    // print its position
    cout << "the " << distance(col1.begin(), pos) + 1
        << " . element is the first greater than 3" << endl;

    // find first element divisible by 3
    pos = find_if (col1.begin(), col1.end(), not1(bind2nd(modulus<int>(),3)));

    // print its position
    cout << "the " << distance(col1.begin(), pos) + 1
        << ". element is the first divisible by 3" << endl;
}

find2.png

• 查找前n個連續(xù)匹配值
  InputIterator search_n (InputIterator beg, InputIterator end, Size count, const T& value)
  InputIterator search_n (InputIterator beg, InputIterator end, Size count, const T& value, BinaryPredicate op)
  返回第一組”連續(xù)count個元素值等于value或使op(elem,value)為true“的元素位置优幸。若無匹配元素，返回參數(shù)end褪猛。(note:調(diào)用predicate的函數(shù)很多都是調(diào)用op()网杆。)
  最多比較次數(shù)numberOfElement*count。

// 查找連續(xù)4個“數(shù)值大于等于3”的元素
// algo/searchn1.cpp

#include "algostuff.hpp"
using namespace std;

int main()
{
    deque<int> col1;

    INSERT_ELEMENTS(col1, 1, 9);
    PRINT_ELEMENTS(col1);

    // find four consecutive elements with value 3
    deque<int>::iterator pos;
    pos = search_n (col1.begin(), col1.end(), 4, 3);

    // print result
    if (pos != col1.end())
    {
        cout << "four consecutive elements with value 3 "
            << "start with " << distance(col1.begin(), pos) + 1 
            << ". element" << endl;
    }
    else
    {
        cout << "no four consecutive elements with value 3 found" << endl;
    }

    // find four consecutive elements with value greater than 3
    pos = search_n (col1.begin(), col1.end(), 4, 3, greater<int>());

    // print result
    if (pos != col1.end())
    {
        cout << "four consecutive elements with value > 3 "
            << "start with " << distance(col1.begin(), pos) + 1
            << ". element " << endl;
    }
    else
    {
        cout << "no four consecutive elements with value > 3 found" << endl;
    }
}

search1.png

• 查找第一個子區(qū)間
  ForwardIterator1 search (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)
  ForwardIterator1 search(ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd, BinaryPredicate op)
  返回區(qū)間[beg, end)內(nèi)”和[searchBeg, searchEnd)完全吻合“的第一個子區(qū)間的第一個元素的位置，吻合條件：子區(qū)間元素和[searchBeg,searchEnd)全對應(yīng)相等 或使得op(elem,searchElem)為true碳却。最多比較次數(shù)numbeOfElements*numberOfSearchElements队秩。

// 在一個序列中查找一個子序列
// algo/search1.cpp

#include "algostuff.hpp"
using namespace std;

int main()
{
    deque<int> col1;
    list<int> subcol1;

    INSERT_ELEMENTS(col1, 1, 7);
    INSERT_ELEMENTS(col1, 1, 7);

    INSERT_ELEMENTS(subcol1, 3, 6);

    PRINT_ELEMENTS(col1, "col1: ");
    PRINT_ELEMENTS(subcol1, "subcol1: ");

    // search first occurence of subcol1 in col1
    deque<int>::iterator pos;
    pos = search(col1.begin(), col1.end(), subcol1.begin(), subcol1.end());

    // loop while subcol1 found as subrange of col1
    while (pos != col1.end())
    {
        // print position of first element
        cout << "subcol1 found starting with element "
            << distance(col1.begin(), pos) + 1 << endl;
        //search next occurence of subcol1
        ++pos;
        pos = search (pos, col1.end(), subcol1.begin(), subcol1.end());
    }
}

search1.png

// 查找“偶數(shù)、奇數(shù)追城、偶數(shù)”排列而成子序列
// algo/search2.cpp

#include "algostuff.hpp"
using namespace std;

// checks whether an element is even or odd
bool checkEven (int elem , bool even)
{
    if (even)
    {
        return elem % 2 == 0;
    }
    else
    {
        return elem % 2 == 1;
    }
}

int main()
{
    vector<int> col1;

    INSERT_ELEMENTS(col1, 1, 9);
    PRINT_ELEMENTS(col1, "col1: ");

    /* arguments for checkEven()
     * - check for: "even odd even"
     */
    bool checkEvenArgs[3] = {true, false, true};

    // search first subrange in col1
    vector<int>::iterator pos;
    pos = search(col1.begin(), col1.end(), 
            checkEvenArgs, checkEvenArgs + 3, checkEven);

    // loop while subrange found
    while (pos != col1.end())
    {
        // print position of first element
        cout << "subrange found starting with element "
            << distance(col1.begin(), pos) + 1 << endl;
        
        // search next subrange in col1
        pos = search( ++pos, col1.end(),
                checkEvenArgs, checkEvenArgs + 3, checkEven);
    }
}

search2.png

• 查找最后一個子區(qū)間
  ForwardIterator find_end(ForwardIterator beg, ForwardIterator end, ForwardIterator searchBeg, ForwardIterator searchEnd)
  ForwardIterator find_end(ForwardIterator beg, ForwardIterator end, Forward searchBeg,ForwardIterator searchEnd, BinaryPredicate op)
  返回匹配的最后一個子區(qū)間的第一個元素位置刹碾；匹配成功指 子區(qū)間元素對應(yīng)相等或子區(qū)間元素使得op(elem, searchElem)為true燥撞。最多比較次數(shù)numberOfElements*numberOfSearchElements座柱。

// 在一個序列中查找“與某序列相匹配”的最后一個子序列
// algo/findend1.cpp

#include "algostuff.hpp"
using namespace std;

int main()
{
    deque<int> col1;
    list<int> subcol1;

    INSERT_ELEMENTS(col1, 1, 7);
    INSERT_ELEMENTS(col1, 1, 7);

    INSERT_ELEMENTS(subcol1, 3, 6);

    PRINT_ELEMENTS(col1, "col1: ");
    PRINT_ELEMENTS(subcol1, "subcol1: ");

    // search last occurence of subcol1 in col1
    deque<int>::iterator pos;
    pos = find_end(col1.begin(), col1.end(), subcol1.begin(), subcol1.end());

    // loop while subcol1 found as subrange of col1
    deque<int>::iterator end(col1.end());
    while (pos != end)
    {
        // print position of first element
        cout << "subcol1 found starting with element "
            << distance(col1.begin(), pos) + 1 << endl;

        // search next occurence of subcol1
        end = pos;
        pos = find_end (col1.begin(), end, subcol1.begin(),subcol1.end());
    }
}

findend1.png

• 查找某些元素第一次出現(xiàn)的位置
  ForwardIterator find_first_of(ForwardIterator1 beg,ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)
  ForwardIterator find_first_of(ForwardIterator1 beg,ForwardIterator1 end, ForwardIteartor2 searchBeg,ForwardIterator2 searchEnd,BinaryPredicate op)
  note:
  第一種形式，返回第一個”既在[beg,end)又在[searchBeg,searchEnd)中出現(xiàn)“的元素的位置物舒；第二種形式返回區(qū)間[beg,end)中第一個這樣的元素色洞，該元素和區(qū)間[searchBeg,searchEnd)的每個元素的op(elem,searchElem)都為true。
  最多比較次數(shù)numberOfElements*numberOfSearchElements冠胯。

// algo/findof1.cpp

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> col1;
    list<int> searchcol1;

    INSERT_ELEMENTS(col1, 1, 11);
    INSERT_ELEMENTS(searchcol1, 3, 5);

    PRINT_ELEMENTS(col1, "col1: ");
    PRINT_ELEMENTS(searchcol1, "searchcol1: ");
    
    // search first occurence of an element of searchcol1 in col1
    vector<int>::iterator pos;
    pos = find_first_of (col1.begin(), col1.end(),
            searchcol1.begin(),
            searchcol1.end());

    cout << "first element of searchcol1 in col1 is element "
        << distance(col1.begin(), pos) + 1 << endl;

    // search last occurence of an element of searchcol1 in col1
    vector<int>::reverse_iterator rpos;
    rpos = find_first_of (col1.rbegin(), col1.rend(),
            searchcol1.begin(),
            searchcol1.end());
    cout << "last element of searchcol1 in col1 is element "
        << distance(col1.begin(), rpos.base()) << endl;
}

output:

findof1.png

• 查找兩個連續(xù)且相等的元素
  InputIterator adjacent_find(InputIterator beg, InputIterator end)
  InputIterator adjacent_find(InputIterator beg, InputIterator end, BinaryPredicate op)
  返回區(qū)間中第一對”連續(xù)兩個相等元素“或”連續(xù)兩個使得op(elem,nextElem)為true的元素“的第一元素位置置蜀。
  最多比較次數(shù)numberOfElements。

// algo/adjfind1.cpp

#include "algostuff.hpp"
using namespace std;

// return whether the second object has double the value  of the first
bool doubled(int elem1, int elem2)
{
    return elem1 * 2 == elem2;
}

int main()
{
    vector<int> col1;

    col1.push_back(1);
    col1.push_back(3);
    col1.push_back(2);
    col1.push_back(4);
    col1.push_back(5);
    col1.push_back(5);
    col1.push_back(0);

    PRINT_ELEMENTS(col1, "col1: ");

    // search first two elements with equal value
    vector<int>::iterator pos;
    pos = adjacent_find (col1.begin(), col1.end());

    if (pos != col1.end())
    {
        cout << "first two elements with equal value have position "
            << distance (col1.begin(), pos) + 1 << endl;
    }

    // search first two element for which the second has double the value of the first
    pos = adjacent_find(col1.begin(), col1.end(), doubled);

    if (pos != col1.end())
    {
        cout << "first two elements with second value twice the first have pos.  " 
            << distance(col1.begin(), pos) + 1 << endl;
    }
}

adjfind1.png

9.5.4 區(qū)間的比較

• 檢驗(yàn)相等性

bool equal (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg)
bool equal (InputIterator1 beg, InputIterator1 end, 
            InputIterator2 cmpBeg, BinaryPredicate op)

• 查找第一處不同點(diǎn)

pair<InputIterator1, InputIterator2> 
      mismatch(InputIterator1 beg, InputIterator1 end, InputIterator2 cmp)

pair<InputIterator1, InputIterator2> 
      mismatch (InputIterator1 beg, InputIterator1 end, 
                 InputIterator2 cmpBeg, BinaryPredicate op)
返回第一對兩兩相異的對應(yīng)元素悉盆。
  若沒找到不同點(diǎn)盯荤，則返回一個pair，以end和第二序列對應(yīng)元素組成焕盟。
(這不意味著兩序列相等秋秤，因?yàn)榈诙蛄锌赡馨嘣亍?

• 檢驗(yàn) “<”

bool lexicongraphical_compare (InputIterator1 beg1, InputIterator1 end1, 
                               InputIterator2 beg2, InputIterator2 end2)
bool lexicongraphical_compare (InputIterator1 beg1, InputIterator1 end1, 
                               InputIterator2 beg2, InputIterator2 end2, 
                               CompFunc op)

9.6 modifying algorithm

• copy (p363)

OutputIterator copy(InputIterator sourceBeg, InputIterator sourceEnd,
                     OutputIterator destBeg)

BidirectionalIterator copy_backward(BidirectionalIterator1 sourceBeg, 
                                    BidirectionalIterator1 sourceEnd,
                                    BidirectionalIterator2 destEnd)
note:destEnd或destBeg不能位于[sourceBeg,sourceEnd)區(qū)間內(nèi)。
    copy()正向遍歷脚翘，copy_backward()反向遍歷灼卢。

• transforming and combinng(p366)

OutputIterator transform (InputIterator sourceBeg, InputIterator sourceEnd, 
                          OutputIterator destBeg, UnaryFunc op)
OutputIterator transform (InputIterator1 source1Beg,
                          InputIterator1 source1End, 
                          InputIterator2 source2Beg, 
                          OutputIterator destBeg, BinaryFunc op)

• swapping(page370)

ForwardIterator2 swap_ranges (ForwardIterator1 beg1, 
                              ForwardIterator1 end1, 
                              ForwardIterator2 beg2)
返回第二區(qū)間中“最后一個被交換元素”的下一個位置。

• assigning(p372)

void fill (ForwardIterator beg, ForwardIterator end, const T& newValue)
void fill_n (OutputIterator beg, Size num, const T& newValue)

void generate(ForwardIterator beg, ForwardIterator end, Func op)
void generate_n(OutputIterator beg, Size num, Func op)

• replacing(p375)

void replace (ForwardIterator beg, ForwaredIterator end, 
              const T& oldValue, const T& newValue)

void replace_if(ForwardIterator beg, ForwardIterator end, 
                UnaryPredicate op, const T& newValue)

OutputIterator replace_copy (InputIterator sourceBeg,
                             InputIterator sourceEnd, 
                             OutputIterator destBeg, 
                             const T& oldValue,const T& newValue)
OutputIterator replace_copy_if (InputIterator sourceBeg, 
                                InputIterator sourceEnd, 
                                OutputIterator destBeg,
                                UnaryPredicate op, const T& newValue)
返回目標(biāo)區(qū)間中“最后一個被復(fù)制元素”的下一位置来农。

9.7 removing algorithm

不改變元素數(shù)量：這些算法不改變元素的數(shù)量鞋真，只是邏輯上的思考，將原本置于后面的“不移除元素”向前移動沃于，覆蓋被移除的元素而已涩咖。

• 移除特定元素

ForwardIterator remove (ForwardIterator beg, ForwardIterator end,
                        const T& value)
ForwardIterator remove_if (ForwardIterator beg, ForwardIterator end, 
                        UnaryPredicate op)
返回新的邏輯終點(diǎn)(即最后一個未被移除元素的下一位置)

• 復(fù)制并移除

OutputIterator remove_copy (InputIterator sourceBeg, InputIterator sourceEnd, 
                            OutputIterator destBeg,
                            const T& value)
OutputIterator remove_copy_if(InputIterator sourceBeg,InputIterator sourceEnd,
                            OutputIterator destBeg,
                            UnaryPredicate op)
返回目標(biāo)區(qū)間中最后一個被復(fù)制元素的下一位置(即第一個未被覆蓋的元素)
是copy非移除的元素。

• 移除重復(fù)元素

ForwardIterator unique (ForwardIterator beg,
                        ForwardIterator end)
ForwardIterator unique (ForwardIterator beg,
                        ForwardIterator end,
                        BinaryPredicate op)
將*pos == *(pos-1)的pos元素移除揽涮，若要移除所有重復(fù)元素抠藕，區(qū)間須是已序。
note:pos移除后蒋困，下次則是判斷*(pos+1)==*(pos-1)盾似，同理op( *(pos-1), *pos)。
返回變動后的序列的新終點(diǎn)(邏輯終點(diǎn)，同remove()系列)零院。

• 復(fù)制并移除重復(fù)元素

OutputIterator unique_copy(InputIterator sourceBeg,
                        InputIterator sourceEnd,
                        OutputIterator destBeg)
OutputIterator unique_copy(InputIterator sourceBeg,
                        InputIterator sourceEnd,
                        OutputIterator destBeg,
                        BinaryPredicate op)
類似remove_copy()溉跃，先remove()再copy(),
  但并不改變原群集。

9.8 mutating algorithm(變序算法)

mutable意義是 “即使const object內(nèi)仍可變動”

• reversing

void reverse(BidirectionalIterator beg, BidirectionalIterator end,)
void reverse_copy(BidirectionalIterator beg, BidirectionalIterator end,
                    OutputIterator destBeg)
返回目標(biāo)區(qū)間內(nèi)左后一個被復(fù)制元素的下一位置告抄。

• rotating

void rotate(ForwardIterator beg, ForwardIterator newBeg,
                    ForwardIterator end)
將[beg,end)區(qū)間內(nèi)元素旋轉(zhuǎn)撰茎，執(zhí)行后 *newBeg成為新的第一元素。
即將[newBeg,end) 移到[beg,end-beg+newBeg),
  [beg,newBeg)移到[end-beg+newBeg,end)打洼。

• rotate and copy

OutputIterator rotate_copy(ForwardIterator sourceBeg, ForwardIterator newBeg,
                    ForwardIterator sourceEnd,
                    OutputIterator destBeg)

• Permutaing(排序)

bool next_permutation (BidirectionalIterator beg, BidirectionalIterator end)
bool prev_permutation (BidirectionaIterator beg, BidirectionalIterator end)

上兩個函數(shù)不是很懂(應(yīng)用場景龄糊？)，看下可能的實(shí)現(xiàn)代碼：

next_permutation_possible_code.png

prev_permutation_possible_code.png

• shuffling(重排)

void random_shuffle(RandomAccessIterator beg,
                    RandomAccessIterator end)
void random_shuffle(RandomAccessIterator beg,
                    RandomAccessIterator end,
                    RandomFunc& op)

• 元素前移

BidirectioanlIterator partition(BidirectionalIterator beg,
                    BidirectionalIterator end,
                    UnaryPredicate op)
BidirectionalIterator stable_partition(BidirectionalIterator beg,
                    BidirectionalIterator end,
                    UnaryPredicate op)
將op(elem)為true的元素前移募疮，
返回“令op()結(jié)果為false”的第一個元素的位置炫惩。

9.9 sorting algorithm(p397)

可以使用關(guān)聯(lián)式容器讓元素自動排序，但對全體元素進(jìn)行一次性排序阿浓，通常比始終維護(hù)它們保持已序狀態(tài)更高效他嚷。(詳見p228：關(guān)聯(lián)式容器每插入一個元素都要進(jìn)行一次排序)

• full sorting

void sort(RandomAccessIterator beg, RandomAccessIterator end)
void sort(RandomAccessIterator beg, RandomAccessIterator end,
                    BinaryPredicate op)

void stable_sort(RandomAccessIterator beg, RandomAccessIterator end)
void stable_sort(RandomAccessIterator beg, RandomAccessIterator end,
                    BinaryPredicate op)

sort: n*log(n)
stable_sort(): 內(nèi)存夠則同sort()，否則n*log(n)*log(n)芭毙。

• partial sorting

void partial_sort(RandomAccessIterator beg, RandomAccessIterator sortEnd,
                    RandomAccessIterator end)
void partial_sort(RandomAccessIterator beg, RandomAccessIterator sortEnd,
                    RandomAccessIterator end,
                    BinaryPredicate op)

RandomAccessIterator partial_sort_copy(InputIterator sourceBeg,
                    InputIterator sourceEnd,
                    RandomAccessIterator destBeg,
                    RandomAccessIterator destEnd)
RandomAccessIterator partial_sort_copy(InputIterator sourceBeg,
                    InputIterator sourceEnd,
                    RandomAccessIterator destBeg,
                    RandomAccessIterator destEnd,
                    BinaryPredicate op)
copy()并partial_sort()筋蓖，
返回目標(biāo)區(qū)間內(nèi)“最后一個被復(fù)制元素”的下一位置(目標(biāo)區(qū)間可能大于源區(qū)間)

• 根據(jù)第n個元素排序

void nth_element(RandomAccessIterator beg, 
                    RandomAccessIterator nth,
                    RandomAccessIterator end)
void nth_element(RandomAccessIterator beg, 
                    RandomAccessIterator nth,
                    RandomAccessIterator end
                    BinaryPredicate op)
是nth之前元素小于nth元素，或使op(element)為true的元素置于nth之前退敦。

• heap algorithm

void make_heap(RandomAccess Iterator beg, RandomAccessIterator end)
void make_heap(RandomAccessIterator beg, RandomAccessIterator end,
           BinaryPredicate op)         
將某區(qū)間轉(zhuǎn)化為heap粘咖，
線性：最多3**numberOfElements次比較

void push_heap(RandomAccessIterator beg,
                    RandomAccessIterator end)
void push_heap(RandomAccessIterator beg,
                    RandomAccessIterator end,
                    BinaryPredicate op)
將end之前的最后一個元素加入 原本就是heap的[beg,end-1)區(qū)間，使[beg,end)稱為heap苛聘。

void pop_heap(RandomAccessIterator beg,  RandomAccessIterator end)
void pop_heap(RandomAccessIterator beg,  RandomAccessIterator end,
                    BinarryPredicate op)
將[beg,end)內(nèi)第一個元素移到最后涂炎，并將[beg,end-1)組織成一個heap。

void sort_heap(RandomAccessIterator beg, RandomAccessIterator end)
void sort_heap(RandomAccessIterator beg, RandomAccessIterator end,
                    BinaryPredicate op)
將heap區(qū)間[beg,end)轉(zhuǎn)化為一個sorted序列设哗。

9.10 sorted range algorithm(p409)

• searching

bool binary_serach(ForwardIterator beg,
                    ForwardIterator end,
                    const T& value)
bool binary_search(ForwardIterator beg,
                    ForwardIterator end,
                    const T& value,
                    BinaryPredicate op)

bool includes(InputIterator1 beg, InputIterator1 end,
                    InputIterator2 searchBeg, InputIterator2 searchEnd)
bool includes(InputIterator1 beg,InputIterator1 end,
                    InputIterator2 searchBeg,InputIterator2 searchEnd,
                    BinaryPredicate op)
判斷已序區(qū)間[beg,end)是否包含已序區(qū)間[searchBeg,searchEnd)的所有元素唱捣，
[searchBeg,searchEnd)在[beg,end)中不一定要連續(xù)

ForwardIterator lower_bound(ForwardIterator beg,
                    ForwardIterator end,
                    const T& value)
ForwardIterator lower_bound(ForwardIterator beg,
                    ForwardIteartor end,
                  const T& value,
                  BinaryPredicate op)

ForwardIterator upper_bound(ForwardIterator beg,
                    ForwardIterator end,
                    const T& value)
ForwardIterator upper_bound(ForwardIterator beg,
                    ForwardIteartor end,
                  const T& value,
                  BinaryPredicate op)

pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator beg,
                      ForwardIterator end,
                    const T& value)
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator beg,
                      ForwardIterator end,
                    const T& value,
                    BinaryPredicate op)

• merging(p416)

OutputIterator merge(InputIterator source1Beg, InputIterator source1End,
                InputIterator source2Beg,InputIterator source2End,
                OutputIterator destBeg)
OutputIterator merge(InputIterator source1Beg, InputIterator source1End,
                InputIterator source2Beg,InputIterator source2End,
                OutputIterator destBeg,
                BinaryPredicate op)
返回目標(biāo)區(qū)間內(nèi)“最后一個被復(fù)制元素”的下一位置。

OutputIterator set_union(InputIterator source1Beg, InputIterator source1End,
                  InputIterator source2Beg, InputIterator source2End,
                  OutputIterator destBeg)

OutputIterator set_union(InputIterator source1Beg, InputIterator source1End,
                  InputIterator source2Beg, InputIterator source2End,
                  OutputIterator destBeg,
                  BinaryPredicate op)
與merge()不同网梢，set_union()會使同時在兩源區(qū)間出現(xiàn)的元素在并集中只出現(xiàn)一次震缭。
  但若 某源區(qū)間中就存在重復(fù)元素，則目標(biāo)區(qū)間也會存在重復(fù)元素战虏。
返回“最后一個被復(fù)制元素”的下一位置拣宰。

OutputIterator set_intersection(InputIterator source1Beg,InputIterator source1End,
                InputIterator source2Beg, InputIterator sourcce2End,
                OutputIterator destBeg)
set_intersection(InputIterator source1Beg,InputIterator source1End,
                InputIterator source2Beg, InputIterator sourcce2End,
                OutputIterator destBeg,
                BinaryPredicate op)
求交集，同set_union()烦感，若某源區(qū)間就存在重復(fù)元素巡社，
  則目標(biāo)區(qū)間中對應(yīng)重復(fù)元素的個數(shù)是兩源區(qū)間內(nèi)重復(fù)個數(shù)的較小值。
返回目標(biāo)區(qū)間中“最后一個被合并元素”的下一位置

OutputIterator set_difference(InputIterator source1Beg,InputIterator source1End,
                  InputIterator2Beg,InputIterator source2End,
                  OutputIterator destBeg)
OutputIterator set_difference(InputIterator source1Beg,InputIterator source1End,
                  InputIterator2Beg,InputIterator source2End,
                  OutputIterator destBeg,
                  BinaryPredicate op)
差集：元素只存在于第一區(qū)間手趣，不存在于第二區(qū)間晌该。
返回目標(biāo)區(qū)間內(nèi)“最后一個被合并元素”的下一位置。

OutputIterator set_symmetric_difference(InputIterator source1Beg, InputIterator source1End,
                InputIterator source2Beg,InputIterator source2End,
                OutputIterator destBeg)
OutputIterator set_symmetric_difference(InputIterator source1Beg, InputIterator source1End,
                InputIterator source2Beg,InputIterator source2End,
                OutputIterator destBeg,
                BinaryPredicate op)  
目標(biāo)區(qū)間中元素，只存在于第一或第二區(qū)間朝群，但不同時存在于兩個源區(qū)間燕耿。
返回目標(biāo)區(qū)間內(nèi)“最后一個被合并元素”的下一位置。

void inplace_merge(BidirectionalIterator beg1, 
                BidirectionalIterator end1beg2,
                BidirectionalIterator end2)
void inplace_merge(BidirectionalIterator beg1, 
                BidirectionalIterator end1beg2,
                BidirectionalIterator end2,
                BinaryPredicate op)
將已序區(qū)間[beg1,end1beg2)和[end1beg2,end2)合并姜胖，使[beg1,end2)成為二者總和并已序誉帅。

9.11 Numeric Algorithm(p425)

#include <numeric>

• 加工運(yùn)算后產(chǎn)生結(jié)果

T accumulate (InputIterator beg, InputIterator end, T initValue)
T accumulate(InputIterator beg, T initValue, BinaryPredicate op)
對每個元素 initValue = initValue + elem 或initValue = op(initValue, elem)
返回 initValue + a1+a2+...
  或 initValue op a1 op a2 op ...
若beg==end，則返回initValue右莱。

T inner_product(InputIterator1 beg1, InputIterator1 end1,
                  InputIterator2 beg2,
                  T initValue)

T inner_product(InputIterator1 beg1, InputIterator1 end1,
                  InputIterator2 beg2,
                  T initValue,
                  BinaryFunc op1,
                  BinaryFunc op2)
兩區(qū)間對用元素：initValue = initValue + elem1*elem2
  或 initValue = op1(initValue, op2(elem1,elem2) )
返回 initValue +(a1*b1)+(a2*b2)+...
  或 initValue op1 (a1 op2 b1) op1 (a2 op2 b2) op1 ...

• 相對值和絕對值的轉(zhuǎn)換

將相對值 轉(zhuǎn)換為絕對值
OutputIterator partial_sum(InputIterator sourceBeg,
                InputIterator sourceEnd,
                OutputIterator destBeg)

OutputIterator partial_sum(InputIterator sourceBeg,
                InputIterator sourceEnd,
                OutputIterator destBeg,
                BinaryFunc op)
分別計算 a1, a1+a2, a1+a2+a3, ...
  或 a1, a1 op a2, a1 op a2 op a3, ...
返回目標(biāo)區(qū)間內(nèi)“最后一個被寫入的值”的 下一位置蚜锨。
源區(qū)間和目標(biāo)區(qū)間可以形同。

將絕對值轉(zhuǎn)換為相對值
OutputIterator adjacent_difference(InputIterator sourceBeg,
                InputIterator sourceEnd,
                OutputIterator destBeg)
OutputIterator adjacent_difference(InputIterator sourceBeg,
                InputIterator sourceEnd,
                OutputIterator destBeg,
                BinaryFunc op)
分別計算 a1, a2-a1, a3-a2, ...
  或 a1, a2 op a1, a3 op a2, ...
返回目標(biāo)區(qū)間“最后一個被寫入的值”的下一位置隧出。
同partial_sum()源區(qū)間可與目標(biāo)區(qū)間相同踏志。