STL算法合集

1,简要描述迭代器的各种形式:
(1)InputIterator:向单个序列读入元素的输入迭代器,前向传递++和*,可以通过==和!=检测.
(2)OutIterator:写入元素的输出迭代器,前向传递++和*,假定连续不断向目的文件发送元素,不能用==和!=检测.
注:当(1),(2)作为某个STL算法的模版参数时,该算法可以使用任意"更复杂的迭代器".
(3)ForwardIterator:前向读写,++,可同时读写.
(4)BidirectionalIterator:双向读写,++和--.
(5)RandomAccessIterator:可以向前或向后双向跳跃移动.

2,算法头文件:<utility>,<numeric>,<algorithm>.

3,稳定排序和不稳定排序:
前者:保持相等元素的原始相对顺序,如:stable_sort(),底层是归并排序.
后者:不能保证,如:sort,底层是变种的快排.

4,
void fill(ForwardIterator first, ForwardIterator last, const T& value);
void fill_n(OutputIterator first, Size n, const T& value);
fill( ):assigns value to every element in the range [first, last).
fill_n( ):assigns value to n elements starting at first.

void generate(ForwardIterator first, ForwardIterator last, Generator gen);
void generate_n(OutputIterator first, Size n, Generator gen);
generate( ):makes a call to gen( ) for each element in the range [first, last), presumably to produce a different value for each element.
generate_n( ):calls gen( ) n times and assigns each result to n elements starting at first.
实例代码:

#include <vector>
#include <algorithm>
#include <iterator>
#include <set>
#include <iostream>
using namespace std;

class SkipGen
{
    int start,step;
public:
    SkipGen(int m=1,int n=3):start(m),step(n){}
    int operator()()
    {
        int temp=start;
        start+=step;
        return temp;
    }

};

template<typename ite> //打印任意迭代器类型限定的序列
void myPrint(ite first, ite last, const char* ss="", const char* ee=" ", ostream& os=cout)
{
    if(ss!=0&&*ss!='\0')
        os<<ss<<": "<<ee;
    typedef typename iterator_traits<ite>::value_type T;//这样就可以处理任意迭代器类型限定的序列
    copy(first,last,ostream_iterator<T>(os,ee));
    os<<endl;
}


int main()
{
    int const N=8;

    vector<string> v1(5);
    fill(v1.begin(), v1.end(), "howdy");
    myPrint(v1.begin(), v1.end(), "v1", " ");

    vector<string> v2;
    fill_n(back_inserter(v2), N, "bye");
    myPrint(v2.begin(), v2.end(), "v2");

    vector<int> v3(10);
    generate(v3.begin(), v3.end(), SkipGen(4,5));
    myPrint(v3.begin(), v3.end(), "v3", " ");

    vector<int> v4;
    generate_n(back_inserter(v4),N, SkipGen(5,3));
    myPrint(v4.begin(), v4.end(), "v4", " ");
}

5,
IntegralValue count(InputIterator first, InputIterator last, const EqualityComparable& value);
IntegralValue count_if(InputIterator first, InputIterator last, Predicate pred);
count:Produces the number of elements in [first, last) that are equivalent to value (when tested using operator==).
count_if:Produces the number of elements in [first, last) that each cause pred to return true.
实例代码:

#include <vector>
#include <algorithm>
#include <iterator>
#include <set>
#include <iostream>
using namespace std;

class CharGen
{
    static const char* charSet;
    static const int N;
public:
    char operator()()
    {
        return charSet[rand()%N];
    }

};
const char* CharGen::charSet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const int CharGen::N = strlen(charSet);

template<typename ite> //打印任意迭代器类型限定的序列
void myPrint(ite first, ite last, const char* ss="", const char* ee=" ", ostream& os=cout)
{
    if(ss!=0&&*ss!='\0')
        os<<ss<<": "<<ee;
    typedef typename iterator_traits<ite>::value_type T;//这样就可以处理任意迭代器类型限定的序列
    copy(first,last,ostream_iterator<T>(os,ee));
    os<<endl;
}


int main()
{
    vector<char> vc;
    generate_n(back_inserter(vc), 30, CharGen());
    myPrint(vc.begin(), vc.end(), "vc","");

    //set结合count,统计单词的个数
    set<char> cs(vc.begin(), vc.end());
    for(set<char>::iterator it = cs.begin(); it != cs.end(); it++)
    {
        int n = count(vc.begin(), vc.end(), *it);
        cout << *it << ": " << n << ", ";
    }

    int lNum = count_if(vc.begin(), vc.end(),bind2nd(greater<char>(), 'a'));
    cout << "\nLowercase letters: " << lNum << endl;
    sort(vc.begin(), vc.end());
    myPrint(vc.begin(), vc.end(), "sorted", "");
}

6,
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator destination);
注:使用赋值,复制序列到destination,每次赋值后都增加destination,原序列不能包含目的序列.
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 destinationEnd);
注:第一个目的元素是destinationEnd-1,同样原序列不能包含目的序列.

void reverse(BidirectionalIterator first, BidirectionalIterator last);
OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator destination);
reverse( ):reverses the range in place
reverse_copy( ):leaves the original range alone and copies the reversed elements into destination, returning the past-the-end iterator of the resulting range.

ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
swap_ranges:Exchanges the contents of two ranges of equal size by swapping corresponding elements.
注:范围的大小必须完全相等.

void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator destination);
Moves the contents of [first, middle) to the end of the sequence, and the contents of [middle, last) to the beginning.
实例代码:

#include <vector>
#include <algorithm>
#include <iterator>
#include <set>
#include <iostream>
using namespace std;

class SkipGen
{
    int start,step;
public:
    SkipGen(int m=1,int n=3):start(m),step(n){}
    int operator()()
    {
        int temp=start;
        start+=step;
        return temp;
    }

};

template<typename ite> //打印任意迭代器类型限定的序列
void myPrint(ite first, ite last, const char* ss="", const char* ee=" ", ostream& os=cout)
{
    if(ss!=0&&*ss!='\0')
        os<<ss<<": "<<ee;
    typedef typename iterator_traits<ite>::value_type T;//这样就可以处理任意迭代器类型限定的序列
    copy(first,last,ostream_iterator<T>(os,ee));
    os<<endl;
}


int main()
{
    vector<int> v1(10);
    generate(v1.begin(), v1.end(), SkipGen(1,1));
    myPrint(v1.begin(), v1.end(), "v1", " ");

    vector<int> v2(v1.size());
    copy_backward(v1.begin(), v1.end(), v2.end());
    myPrint(v2.begin(), v2.end(), "copy_backward", " ");

    reverse_copy(v1.begin(), v1.end(), v2.begin());
    myPrint(v2.begin(), v2.end(), "reverse_copy", " ");
    reverse(v1.begin(), v1.end());
    myPrint(v1.begin(), v1.end(), "reverse", " ");

    swap_ranges(v1.begin(), v1.begin() + 4, v1.begin() + 1);
    myPrint(v1.begin(), v1.end(), "swap_ranges", " ");

    generate(v1.begin(), v1.end(), SkipGen(1,1));
    myPrint(v1.begin(), v1.end(), "v1", " ");

    rotate(v1.begin(), v1.begin() + 3, v1.end());
    myPrint(v1.begin(), v1.end(), "rotate", " ");

}

7,
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering binary_pred);
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering binary_pred);
"排列"是一个序列第一无二的排序,返回"前驱"和"后继".

void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last RandomNumberGenerator& rand);
function: randomly rearranges the elements in the range.

BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
function: move elements that satisfy pred to the beginning of the sequence.

#include <vector>
#include <algorithm>
#include <iterator>
#include <set>
#include <iostream>
#include <ctime>
using namespace std;

class SkipGen
{
    int start,step;
public:
    SkipGen(int m=1,int n=3):start(m),step(n){}
    int operator()()
    {
        int temp=start;
        start+=step;
        return temp;
    }

};

class CharGen
{
    static const char* charSet;
    static const int N;
public:
    char operator()()
    {
        return charSet[rand()%N];
    }

};
const char* CharGen::charSet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const int CharGen::N = strlen(charSet);

template<typename ite> //打印任意迭代器类型限定的序列
void myPrint(ite first, ite last, const char* ss="", const char* ee=" ", ostream& os=cout)
{
    if(ss!=0&&*ss!='\0')
        os<<ss<<": "<<ee;
    typedef typename iterator_traits<ite>::value_type T;//这样就可以处理任意迭代器类型限定的序列
    copy(first,last,ostream_iterator<T>(os,ee));
    os<<endl;
}


int main()
{
    vector<int> v1(5);
    generate(v1.begin(), v1.end(), SkipGen(1,1));
    myPrint(v1.begin(), v1.end(), "v1", " ");
    for(int i=0;i<3;i++)
    {
        next_permutation(v1.begin(), v1.end());
        myPrint(v1.begin(), v1.end(), "next_permutation", " ");
    }
    for(int i=0;i<3;i++)
    {
        prev_permutation(v1.begin(), v1.end());
        myPrint(v1.begin(), v1.end(), "prev_permutation", " ");
    }

    srand(time(0));
    random_shuffle(v1.begin(), v1.end());
    myPrint(v1.begin(), v1.end(), "random_shuffle", " ");

    vector<char> vc;
    generate_n(back_inserter(vc), 15, CharGen());
    myPrint(vc.begin(), vc.end(), "vc","");
    partition( vc.begin(), vc.end(), bind2nd(less<char>(),'a'));
    myPrint(vc.begin(), vc.end(), "partition","");

    generate_n(back_inserter(vc), 15, CharGen());
    myPrint(vc.begin(), vc.end(), "vc","");
    stable_partition( vc.begin(), vc.end(), bind2nd(less<char>(),'a'));
    myPrint(vc.begin(), vc.end(), "stable_partition","");
}

8,
InputIterator find(InputIterator first, InputIterator last, const EqualityComparable& value);
功能:Searches for value within a range of elements. Returns an iterator in the range [first, last) that points to the first occurrence of value. If value isn’t in the range, find( ) returns last.
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
注:线性查找,依次对每个元素进行检查.

ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
功能:Like find( ), performs a linear search through the range, but it searches for two adjacent elements that are equivalent.

ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred);
功能:在第二个范围内查找与第一个范围内某个元素相等的元素.

ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 BinaryPredicate binary_pred);
功能:检查第二个序列是否在第一个序列的范围内.返回第一个序列在第二个范围序列第一次出现的位置.
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred);
功能:同search,返回最后出现的位置.

ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate binary_pred);
功能:Looks for a group of count consecutive values in [first, last) that are all equal to value

ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
ForwardIterator min_element(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
功能:Returns an iterator pointing to the first occurrence of the “smallest” value in the range
ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
ForwardIterator max_element(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
功能:返回最下第一次出现的迭代器.

void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value);
OutputIterator replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
实例代码:

#include <algorithm>
#include <functional>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;

template<typename ite> //打印任意迭代器类型限定的序列
void myPrint(ite first, ite last, const char* ss="", const char* ee=" ", ostream& os=cout)
{
    if(ss!=0&&*ss!='\0')
        os<<ss<<": "<<ee;
    typedef typename iterator_traits<ite>::value_type T;//这样就可以处理任意迭代器类型限定的序列
    copy(first,last,ostream_iterator<T>(os,ee));
    os<<endl;
}

struct PlusOne
{
    bool operator()(int i, int j) { return j == i + 1; }
};

class MulMoreThan
{
    int value;
public:
    MulMoreThan(int val) : value(val) {}
    bool operator()(int v, int m) { return v * m > value; }
};

int main()
{
    int a[] = { 1, 2, 3, 4, 5, 6, 6, 7, 7, 7,8, 8, 8, 8, 11, 11, 11, 11, 11 };
    const int ASZ = sizeof a / sizeof *a;

    vector<int> v(a, a + ASZ);
    myPrint(v.begin(), v.end(), "v", " ");

    vector<int>::iterator it = find(v.begin(), v.end(), 4);
    cout << "find: " << *it << endl;

    it = find_if(v.begin(), v.end(),
    bind2nd(greater<int>(), 8));
    cout << "find_if: " << *it << endl;

    it = adjacent_find(v.begin(), v.end());
    while(it != v.end())
    {
        cout << "adjacent_find: " << *it << ", " << *(it + 1) << endl;
        it = adjacent_find(it + 1, v.end());
    }
    it = adjacent_find(v.begin(), v.end(), PlusOne());
    while(it != v.end())
    {
        cout << "adjacent_find PlusOne: " << *it << ", " << *(it + 1) << endl;
        it = adjacent_find(it + 1, v.end(), PlusOne());
    }

    int b[] = { 8, 11 };
    const int BSZ = sizeof b / sizeof *b;
    myPrint(b, b + BSZ, "b", " ");

    it = find_first_of(v.begin(), v.end(), b, b + BSZ);
    cout<<"find_first_of: "<<*it<<endl;;

    it = find_first_of(v.begin(), v.end(),b, b + BSZ, PlusOne());
    cout<<"find_first_of PlusOne: "<<*it<<endl;;


    it = search(v.begin(), v.end(), b, b + BSZ);
    if(it!=v.end())
        myPrint(it, it + BSZ, "search", " ");

    int c[] = { 5, 6, 7 };
    const int CSZ = sizeof c / sizeof *c;
    myPrint(c, c + CSZ, "c", " ");
    it = search(v.begin(), v.end(), c, c + CSZ, PlusOne());
    myPrint(it, it + CSZ,"search PlusOne", " ");

    int d[] = { 11, 11, 11 };
    const int DSZ = sizeof d / sizeof *d;
    myPrint(d, d + DSZ, "d", " ");
    it = find_end(v.begin(), v.end(), d, d + DSZ);
    myPrint(it, v.end(),"find_end", " ");
    int e[] = { 9, 9 };
    myPrint(e, e + 2, "e", " ");
    it = find_end(v.begin(), v.end(), e, e + 2, PlusOne());
    myPrint(it, v.end(),"find_end PlusOne"," ");

    it = search_n(v.begin(), v.end(), 3, 7);
    myPrint(it, it + 3, "search_n 3, 7", " ");
    it = search_n(v.begin(), v.end(), 6, 15, MulMoreThan(100));
    myPrint(it, it + 6,"search_n 6, 15, MulMoreThan(100)", " ");

    cout << "min_element: "<< *min_element(v.begin(), v.end()) << endl;
    cout << "max_element: "<< *max_element(v.begin(), v.end()) << endl;

    vector<int> v2;
    replace_copy(v.begin(), v.end(),back_inserter(v2), 8, 47);
    myPrint(v2.begin(), v2.end(), "replace_copy 8 -> 47", " ");

    replace_if(v.begin(), v.end(),bind2nd(greater_equal<int>(), 7), -1);
    myPrint(v.begin(), v.end(), "replace_if >= 7 -> -1", " ");
}

9,
bool equal(InputIterator first1, InputIterator last1, InputIterator first2);
bool equal(InputIterator first1, InputIterator last1, InputIterator first2 BinaryPredicate binary_pred);
功能:returns true if both ranges are exactly the same (the same elements in the same order).

bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate binary_pred);
功能:"字典顺序"比较,第一个"<".

pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);
功能:equal( ) just tells you whether the two ranges are the same, mismatch( ) tells you where they begin to differ.
实例代码:

#include <algorithm>
#include <functional>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;

template<typename ite> //打印任意迭代器类型限定的序列
void myPrint(ite first, ite last, const char* ss="", const char* ee=" ", ostream& os=cout)
{
    if(ss!=0&&*ss!='\0')
        os<<ss<<": "<<ee;
    typedef typename iterator_traits<ite>::value_type T;//这样就可以处理任意迭代器类型限定的序列
    copy(first,last,ostream_iterator<T>(os,ee));
    os<<endl;
}

int main()
{
    string s1("This is a test");
    string s2("This is a Test");
    cout << "s1: " << s1 << endl << "s2: " << s2 << endl;

    cout << "compare s1 & s1: "<< equal(s1.begin(), s1.end(), s1.begin()) << endl;
    cout << "compare s1 & s2: "<< equal(s1.begin(), s1.end(), s2.begin()) << endl;

    cout << "lexicographical_compare s1 & s1: "<< lexicographical_compare(s1.begin(), s1.end(),s1.begin(), s1.end()) <<  endl;
    cout << "lexicographical_compare s1 & s2: "<< lexicographical_compare(s1.begin(), s1.end(),s2.begin(), s2.end()) << endl;
    cout << "lexicographical_compare s2 & s1: "<< lexicographical_compare(s2.begin(), s2.end(),s1.begin(), s1.end()) << endl;
    cout << "lexicographical_compare shortened ""s1 & full_length s2: "<< lexicographical_compare(s1.begin(), s1.begin()+4,s2.begin(), s2.end()) << endl;
    string s3(s1);
    while(s3.length() != 0)
    {
        bool result = lexicographical_compare(s3.begin(), s3.end(), s2.begin(),s2.end());
        cout << s3 << endl << s2 << ", result = "<< result << endl;
        if(result == true) break;
        s3 = s3.substr(0, s3.length() - 1);
    }

    pair<string::iterator, string::iterator> p =mismatch(s1.begin(), s1.end(), s2.begin());
    myPrint(p.first, s1.end(), "p.first", "");
    myPrint(p.second, s2.end(), "p.second","");
}

10,
ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
注:remove并不是真正的删除元素,只是把需要删除的放在了序列的最后.
想要真正删除,可以使用c.erase( remove(c.begin(),c.end(),value), c.end() )

ForwardIterator unique(ForwardIterator first, ForwardIterator last);
ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result);
OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred);
功能:删除相邻相同的元素,最好结合sort使用.

#include <algorithm>
#include <functional>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;

template<typename ite> //打印任意迭代器类型限定的序列
void myPrint(ite first, ite last, const char* ss="", const char* ee=" ", ostream& os=cout)
{
    if(ss!=0&&*ss!='\0')
        os<<ss<<": "<<ee;
    typedef typename iterator_traits<ite>::value_type T;//这样就可以处理任意迭代器类型限定的序列
    copy(first,last,ostream_iterator<T>(os,ee));
    os<<endl;
}

struct IsUpper
{
    bool operator()(char c)
    {
        return isupper(c);
    }
};

class CharGen
{
    static const char* charSet;
    static const int N;
public:
    char operator()()
    {
        return charSet[rand()%N];
    }
};
const char* CharGen::charSet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const int CharGen::N = strlen(charSet);

int main()
{

    string v;
    v.resize(25);
    generate(v.begin(), v.end(), CharGen());
    myPrint(v.begin(), v.end(), "v original", "");

    string us(v.begin(), v.end());
    sort(us.begin(), us.end());
    string::iterator uend = unique(us.begin(), us.end());
    myPrint(us.begin(), uend, "sort+unique", " ");

    generate(v.begin(), v.end(), CharGen());
    myPrint(v.begin(), v.end(), "v", "");
    string::iterator cit = remove_if(v.begin(), v.end(), IsUpper());
    myPrint(v.begin(), cit, "v after remove_if IsUpper", " ");

    sort(v.begin(), cit);
    myPrint(v.begin(), cit, "sorted", " ");
    string v2;
    v2.resize(cit - v.begin());
    unique_copy(v.begin(), cit, v2.begin());
    myPrint(v2.begin(), v2.end(), "unique_copy", " ");

    cit = unique(v.begin(), cit, equal_to<char>());
    myPrint(v.begin(), cit, "unique equal_to<char>", " ");

    return 0;
}

11,
void sort(RandomAccessIterator first, RandomAccessIterator last);
void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering binary_pred);
功能:Sorts [first, last) into ascending order.

void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering binary_pred);
功能:Sorts [first, last) into ascending order, preserving the original ordering of equivalent elements.

void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, StrictWeakOrdering binary_pred);
功能:Sorts the number of elements from [first, last) that can be placed in the range [first, middle). The rest of the elements end up in [middle, last) and have no guaranteed order.

RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last);
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, StrictWeakOrdering binary_pred);
功能:Sorts the number of elements from [first, last) that can be placed in the range [result_first, result_last) and copies those elements into [result_first, result_last).

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, StrictWeakOrdering binary_pred);
功能:All the elements in the range [first, nth) will pair-wise satisfy the binary predicate (operator< by default, as usual), and all the elements in the range (nth, last] will not. However, neither subrange is in any particular order, unlike partial_sort( ) which has the first range in sorted order.
注:只是保证n前面的比n小,n后面的比n大.

下面算法为在已经排序的范围中找出指定元素.
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);
功能:Tells you whether value appears in the sorted range [first, last).

ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);
功能:Returns an iterator indicating the first occurrence of value in the sorted range [first, last). If value is not present, an iterator to where it would fit in the sequence is returned.

ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);
功能:Returns an iterator indicating one past the last occurrence of value in the sorted range [first, last).

pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value);
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering binary_pred);
功能:Essentially combines lower_bound( ) and upper_bound( ) to return a pair indicating the first and one-past-the-last occurrences of value in the sorted range [first, last). Both iterators indicate the location where value would fit if it is not found.
实例代码:

#include <algorithm>
#include <functional>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;

template<typename ite> //打印任意迭代器类型限定的序列
void myPrint(ite first, ite last, const char* ss="", const char* ee=" ", ostream& os=cout)
{
    if(ss!=0&&*ss!='\0')
        os<<ss<<": "<<ee;
    typedef typename iterator_traits<ite>::value_type T;//这样就可以处理任意迭代器类型限定的序列
    copy(first,last,ostream_iterator<T>(os,ee));
    os<<endl;
}

int main()
{

    typedef vector<string>::iterator sit;
    srand(time(0));
    cout.setf(ios::boolalpha);

    string str[]={"f","a","f","d","A","G","f","d","F","a","A","F","h","f","A","d","f","f","a","a"};
    vector<string> original(str,str+sizeof(str)/sizeof(str[0]) );
    vector<string> v(original.begin(), original.end());
    vector<string> w(original.size() / 2);

    sort(v.begin(), v.end());
    myPrint(v.begin(), v.end(), "sort");

    v = original;
    stable_sort(v.begin(), v.end());
    myPrint(v.begin(), v.end(), "stable_sort");

    v = original;
    sit it = v.begin(), it2;
    for(size_t i = 0; i < v.size() / 2; i++)
        ++it;

    partial_sort(v.begin(), it, v.end());
    cout << "middle = " << *it << endl;
    myPrint(v.begin(), v.end(), "partial_sort");

    v = original;
    it = v.begin();
    for(size_t i = 0; i < v.size() / 4; i++)
        ++it;
    partial_sort_copy(v.begin(), it, w.begin(), w.end());
    myPrint(w.begin(), w.end(), "partial_sort_copy");//??????????
    // Not enough room in destination
    partial_sort_copy(v.begin(), v.end(), w.begin(),w.end());
    myPrint(w.begin(), w.end(), "w partial_sort_copy");

    // v remains the same through all this process
    assert(v == original);
    nth_element(v.begin(), it, v.end());
    cout << "The nth_element = " << *it << endl;
    myPrint(v.begin(), v.end(), "nth_element");

    string f = original[rand() % original.size()];
    cout << "binary search: " << binary_search(v.begin(), v.end(), f) << endl;

    sort(v.begin(), v.end());
    it = lower_bound(v.begin(), v.end(), f);
    it2 = upper_bound(v.begin(), v.end(), f);
    myPrint(it, it2, "found range");

    pair<sit, sit> ip = equal_range(v.begin(), v.end(), f);
    myPrint(ip.first, ip.second, "equal_range");
    return 0;
}

12,合并已排序的序列.
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
功能:Copies elements from [first1, last1) and [first2, last2) into result, such that the resulting range is sorted in ascending order. This is a stable operation.

void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, StrictWeakOrdering binary_pred);
功能:This assumes that [first, middle) and [middle, last) are each sorted ranges in the same sequence. The two ranges are merged so that the resulting range [first, last) contains the combined ranges in sorted order.
实例代码:

#include <algorithm>
#include <functional>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;

template<typename ite> //打印任意迭代器类型限定的序列
void myPrint(ite first, ite last, const char* ss="", const char* ee=" ", ostream& os=cout)
{
    if(ss!=0&&*ss!='\0')
        os<<ss<<": "<<ee;
    typedef typename iterator_traits<ite>::value_type T;//这样就可以处理任意迭代器类型限定的序列
    copy(first,last,ostream_iterator<T>(os,ee));
    os<<endl;
}

class SkipGen
{
    int start,step;
public:
    SkipGen(int m=1,int n=3):start(m),step(n){}
    int operator()()
    {
        int temp=start;
        start+=step;
        return temp;
    }
};

int main()
{
    const int SZ = 15;
    int a[SZ*2] = {0};
    // Both ranges go in the same array:
    generate(a, a + SZ, SkipGen(0, 2));
    a[3] = 4;
    a[4] = 4;
    generate(a + SZ, a + SZ*2, SkipGen(1, 3));
    myPrint(a, a + SZ, "range1", " ");
    myPrint(a + SZ, a + SZ*2, "range2", " ");

    int b[SZ*2] = {0}; // Initialize all to zero
    merge(a, a + SZ, a + SZ, a + SZ*2, b);
    myPrint(b, b + SZ*2, "merge", " ");

    // Reset b
    for(int i = 0; i < SZ*2; i++)
        b[i] = 0;
    inplace_merge(a, a + SZ, a + SZ*2);
    myPrint(a, a + SZ*2, "inplace_merge", " ");

    return 0;
}

13,在已排序的序列上进行集合运算.
bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, StrictWeakOrdering binary_pred);
功能:Returns true if [first2, last2) is a subset of [first1, last1). Neither range is required to hold only unique elements, but if [first2, last2) holds n elements of a particular value, [first1, last1) must also hold at least n elements if the result is to be true.

OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, <p align="center"></p>StrictWeakOrdering binary_pred);
功能:Creates the mathematical union of two sorted ranges in the result range, returning the end of the output range. Neither input range is required to hold only unique elements, but if a particular value appears multiple times in both input sets, the resulting set will contain the larger number of identical values.

OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
功能:Produces, in result, the intersection of the two input sets, returning the end of the output range—that is, the set of values that appear in both input sets. Neither input range is required to hold only unique elements, but if a particular value appears multiple times in both input sets, the resulting set will containthe smaller number of identical values.

OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
功能:Produces, in result, the mathematical set difference, returning the end of the output range. All the elements that are in [first1, last1) but not in [first2, last2) are placed in the result set. Neither input range is required to hold only unique elements, but if a particular value appears multiple times in both input sets (n times in set 1 and m times in set 2), the resulting set will contain max(n-m, 0) copies of that value.

OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
功能:
Constructs, in result, the set containing:
1.All the elements in set 1 that are not in set 2.
2.All the elements in set 2 that are not in set 1.
Neither input range is required to hold only unique elements, but if a particular value appears multiple times in both input sets (n times in set 1 and m times in set 2), the resulting set will contain abs(n-m) copies of that value, where abs( ) is the absolute value. The return value is the end of the output range.
实例代码:

#include <algorithm>
#include <functional>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;

template<typename ite> //打印任意迭代器类型限定的序列
void myPrint(ite first, ite last, const char* ss="", const char* ee=" ", ostream& os=cout)
{
    if(ss!=0&&*ss!='\0')
        os<<ss<<": "<<ee;
    typedef typename iterator_traits<ite>::value_type T;//这样就可以处理任意迭代器类型限定的序列
    copy(first,last,ostream_iterator<T>(os,ee));
    os<<endl;
}

class CharGen
{
    static const char* charSet;
    static const int N;
public:
    char operator()()
    {
        return charSet[rand()%N];
    }
};
const char* CharGen::charSet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const int CharGen::N = strlen(charSet);

int main()
{
    const int SZ = 30;
    char v[SZ + 1], v2[SZ + 1];
    CharGen g;
    generate(v, v + SZ, g);
    generate(v2, v2 + SZ, g);
    sort(v, v + SZ);
    sort(v2, v2 + SZ);
    myPrint(v, v + SZ, "v", "");
    myPrint(v2, v2 + SZ, "v2", "");

    bool b = includes(v, v + SZ, v + SZ/2, v + SZ);
    cout.setf(ios::boolalpha);
    cout << "includes: " << b << endl;

    char v3[SZ*2 + 1], *end;
    end = set_union(v, v + SZ, v2, v2 + SZ, v3);
    myPrint(v3, end, "set_union", "");

    end = set_intersection(v, v + SZ, v2, v2 + SZ, v3);
    myPrint(v3, end, "set_intersection", "");

    end = set_difference(v, v + SZ, v2, v2 + SZ, v3);
    myPrint(v3, end, "set_difference", "");

    end = set_symmetric_difference(v, v + SZ,v2, v2 + SZ, v3);
    myPrint(v3, end, "set_symmetric_difference","");

    return 0;
}

14,数值算法(都在<numeric>头文件中)
T accumulate(InputIterator first, InputIterator last, T result);
T accumulate(InputIterator first, InputIterator last, T result, BinaryFunction f);
功能:The first form is a generalized summation; for each element pointed to by an iterator i in [first, last), it performs the operation result = result + *i, where result is of type T. However, the second form is more general; it applies the function f(result, *i) on each element *i in the range from beginning to end.

T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init);
功能:init+(1*1) + (1*2) + (2*3) + (2*4)
T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init, BinaryFunction1 op1, BinaryFunction2 op2);
功能:op2代替"*"运算,op1代替"+"运算

OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result);
OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryFunction op);
功能:Calculates a generalized partial sum.
例: {1, 1, 2, 2, 3}.The generated sequence is {1, 1 + 1, 1 + 1 + 2, 1 + 1 + 2 + 2, 1 + 1 + 2 + 2 + 3}, that is, {1, 2, 4, 6, 9}.

OutputIterator adjacent_difference(InputIterator first,   InputIterator last, OutputIterator result);
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryFunction op);
功能:Calculates the differences of adjacent elements throughout the range [first, last).
例:{1, 1, 2, 2, 3}, the resulting sequence is {1, 1 – 1, 2 – 1, 2 – 2, 3 – 2}, that is: {1, 0, 1, 0, 1}.
实例代码:

#include <algorithm>
#include <functional>
#include <vector>
#include <iterator>
#include <iostream>
#include <numeric>
using namespace std;

template<typename ite> //打印任意迭代器类型限定的序列
void myPrint(ite first, ite last, const char* ss="", const char* ee=" ", ostream& os=cout)
{
    if(ss!=0&&*ss!='\0')
        os<<ss<<": "<<ee;
    typedef typename iterator_traits<ite>::value_type T;//这样就可以处理任意迭代器类型限定的序列
    copy(first,last,ostream_iterator<T>(os,ee));
    os<<endl;
}

int main()
{
    int a[] = { 1, 1, 2, 2, 3, 5, 7, 9, 11, 13 };
    const int ASZ = sizeof a / sizeof a[0];
    myPrint(a, a + ASZ, "a", " ");

    int r = accumulate(a, a + ASZ, 0);
    cout << "accumulate 1: " << r << endl;
    // Should produce the same result:
    r = accumulate(a, a + ASZ, 0, plus<int>());
    cout << "accumulate 2: " << r << endl;

    int b[] = { 1, 2, 3, 4, 1, 2, 3, 4, 1, 2 };
    myPrint(b, b + sizeof b / sizeof b[0], "b", " ");
    r = inner_product(a, a + ASZ, b, 0);
    cout << "inner_product 1: " << r << endl;
    // Should produce the same result:
    r = inner_product(a, a + ASZ, b, 0,
    plus<int>(), multiplies<int>());
    cout << "inner_product 2: " << r << endl;

    int* it = partial_sum(a, a + ASZ, b);
    myPrint(b, it, "partial_sum 1", " ");
    // Should produce the same result:
    it = partial_sum(a, a + ASZ, b, plus<int>());
    myPrint(b, it, "partial_sum 2", " ");

    it = adjacent_difference(a, a + ASZ, b);
    myPrint(b, it, "adjacent_difference 1"," ");
    // Should produce the same result:
    it = adjacent_difference(a, a + ASZ, b, minus<int>());
    myPrint(b, it, "adjacent_difference 2"," ");

    return 0;
}