中文字幕无码黄色大片,午夜福利午夜,韩国少妇99

9 STL Algorithm

9.1 header files

使用C++標準庫的算法，須先#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算法都被設計有處理一個或多個iterator區(qū)間。

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

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

這些操作可以使一般函數(shù)，或functor；若返回值為bool，則稱為predicate。
可用predicate完成以下工作：
1. 對于查找算法，用一元predicate作為查找準則。
2. 對于排序算法，用二元predicate作為排序準則，如p294姓氏排序。
3. 用一元predicate作為準則判斷是否應該對某元素做相應操作。
4. 可為某個數(shù)值算法指定一個數(shù)值運算。

note: predicate不應在函數(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完成操作，故可作用于所有標準容器。

t9-1.png

for_each()傳遞的操作可改變元素值。
string class和STL class是各自獨立發(fā)展設計的，故命名“一致性”有出入。

t9-2.png
modifying algorithm
或直接改變元素值，或在復制到目標區(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é)果復制給原元素。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()速遞稍慢，
  因為其將返回值賦值給元素而不是直接變動元素。

merge()可用于合并無序區(qū)間，當然結(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ù)，且返回邏輯上的新終點位置。(可見p111)
mutating algorithm(變序算法)
通過元素值的賦值和交換，改變元素順序。

t9-5.png
sorting algorithm

t9-6.png

要對所有元素排序，可考慮：

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

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)定性排序。

標準規(guī)范規(guī)定了算法復雜度，但未規(guī)定具體實現(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ū)別開”的排序準則。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之處第二子集的起點，第二子集元素不滿足被傳入的準則。

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算法詳細討論，為簡化例子，使問題突出，定義了一些輔助函數(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可變動元素；實現(xiàn)可見p126；op的返回值會被忽略；
復雜度：線性。調(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;
}

output:

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);
}

output:

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

note:程序中operator double()函數(shù)，原理暫不懂后續(xù)補充。

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不應修改傳進來的參數(shù)；關(guān)聯(lián)式容器提供了等效的成員函數(shù)count()。

// 根據(jù)不同準則對元素計數(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;
}

output:

count1.png

當然也可不必使用上述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<進行元素比較；op用于比較兩元素，op(elem1,elem2)，若op(elem1)<op(elem2)則應返回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;
}

output:

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ū)間，應使用lower_bound()、upper_bound()、equal_range()、binary_search()獲取更高性能。
關(guān)聯(lián)式容器提供等效的成員函數(shù)find()，但為對數(shù)復雜度而非線性復雜度。最多比較次數(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;
    }
}

output:

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;
}

output:

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;
    }
}

output:

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)全對應相等或使得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());
    }
}

output:

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);
    }
}

output:

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ū)間元素對應相等或子區(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());
    }
}

output:

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

note:rpos.base()部分的distance()不用加一，因為base()改變iterator所指數(shù)值位置，詳見p269。

查找兩個連續(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;
    }
}

output:

adjfind1.png

9.5.4 區(qū)間的比較

檢驗相等性

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

查找第一處不同點

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

pair<InputIterator1, InputIterator2> 
      mismatch (InputIterator1 beg, InputIterator1 end, 
                 InputIterator2 cmpBeg, BinaryPredicate op)
返回第一對兩兩相異的對應元素。
  若沒找到不同點，則返回一個pair，以end和第二序列對應元素組成。
(這不意味著兩序列相等，因為第二序列可能包含更多元素。)

檢驗 “<”

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)
返回目標區(qū)間中“最后一個被復制元素”的下一位置。

9.7 removing algorithm

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

移除特定元素

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

復制并移除

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

移除重復元素

ForwardIterator unique (ForwardIterator beg,
                        ForwardIterator end)
ForwardIterator unique (ForwardIterator beg,
                        ForwardIterator end,
                        BinaryPredicate op)
將*pos == *(pos-1)的pos元素移除，若要移除所有重復元素，區(qū)間須是已序。
note:pos移除后，下次則是判斷*(pos+1)==*(pos-1)，同理op( *(pos-1), *pos)。
返回變動后的序列的新終點(邏輯終點，同remove()系列)。

復制并移除重復元素

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)
返回目標區(qū)間內(nèi)左后一個被復制元素的下一位置。

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ù)不是很懂(應用場景？)，看下可能的實現(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)式容器讓元素自動排序，但對全體元素進行一次性排序，通常比始終維護它們保持已序狀態(tài)更高效。(詳見p228：關(guān)聯(liá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()，
返回目標區(qū)間內(nèi)“最后一個被復制元素”的下一位置(目標區(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)
返回目標區(qū)間內(nèi)“最后一個被復制元素”的下一位置。

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ū)間中就存在重復元素，則目標區(qū)間也會存在重復元素。
返回“最后一個被復制元素”的下一位置。

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ū)間就存在重復元素，
  則目標區(qū)間中對應重復元素的個數(shù)是兩源區(qū)間內(nèi)重復個數(shù)的較小值。
返回目標區(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ū)間。
返回目標區(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)  
目標區(qū)間中元素，只存在于第一或第二區(qū)間，但不同時存在于兩個源區(qū)間。
返回目標區(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>

加工運算后產(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, ...
返回目標區(qū)間內(nèi)“最后一個被寫入的值”的 下一位置。
源區(qū)間和目標區(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, ...
返回目標區(qū)間“最后一個被寫入的值”的下一位置。
同partial_sum()源區(qū)間可與目標區(qū)間相同。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

The C++ standard library(侯捷/孟巖譯) 09--algorithm

The C++ standard library(侯捷/孟巖譯) 09--algorithm

9 STL Algorithm

9.1 header files

9.2 算法概覽

9.2.1 簡介

9.2.2 算法分類

9.3 輔助函數(shù)

9.4 for_each()

9.5 nonmodifying algorithm

9.5.1 元素計數(shù)

9.5.2 最大值和最小值

9.5.3 查找元素

9.5.4 區(qū)間的比較

9.6 modifying algorithm

9.7 removing algorithm

9.8 mutating algorithm(變序算法)

9.9 sorting algorithm(p397)

9.10 sorted range algorithm(p409)

9.11 Numeric Algorithm(p425)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

The C++ standard library(侯捷/孟巖 譯) 09--algorithm

9 STL Algorithm

9.1 header files

9.2 算法概覽

9.2.1 簡介

9.2.2 算法分類

9.3 輔助函數(shù)

9.4 for_each()

9.5 nonmodifying algorithm

9.5.1 元素計數(shù)

9.5.2 最大值和最小值

9.5.3 查找元素

9.5.4 區(qū)間的比較

9.6 modifying algorithm

9.7 removing algorithm

9.8 mutating algorithm(變序算法)

9.9 sorting algorithm(p397)

9.10 sorted range algorithm(p409)

9.11 Numeric Algorithm(p425)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

The C++ standard library(侯捷/孟巖譯) 09--algorithm