C++相关闲碎记录(10)

1、search()

#include "algostuff.hpp"
using namespace std;

int main()
{
    deque<int> coll;
    list<int> subcoll;

    INSERT_ELEMENTS(coll,1,7);
    INSERT_ELEMENTS(coll,1,7);
    INSERT_ELEMENTS(subcoll,3,6);

    PRINT_ELEMENTS(coll,   "coll:    ");
    PRINT_ELEMENTS(subcoll,"subcoll: ");

    // search first occurrence of subcoll in coll
    deque<int>::iterator pos;
    pos = search (coll.begin(), coll.end(),         // range
                  subcoll.begin(), subcoll.end());  // subrange

    // loop while subcoll found as subrange of coll
    while (pos != coll.end()) { 
        // print position of first element
        cout << "subcoll found starting with element "
             << distance(coll.begin(),pos) + 1
             << endl;

        // search next occurrence of subcoll
        ++pos;
        pos = search (pos, coll.end(),                  // range
                      subcoll.begin(), subcoll.end());  // subrange
    }
}
输出：
coll:    1 2 3 4 5 6 7 1 2 3 4 5 6 7 
subcoll: 3 4 5 6
subcoll found starting with element 3
subcoll found starting with element 10

查找满足偶数、奇数、偶数排列的子序列。

#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> coll;

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

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

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

    // loop while subrange found
    while (pos != coll.end()) {
        // print position of first element
        cout << "subrange found starting with element "
             << distance(coll.begin(),pos) + 1
             << endl;

        // search next subrange in coll
        pos = search (++pos, coll.end(),              // range
                      checkEvenArgs, checkEvenArgs+3, // subr. values
                      checkEven);                     // subr. criterion
    }
}
输出：
coll: 1 2 3 4 5 6 7 8 9 
subrange found starting with element 2
subrange found starting with element 4
subrange found starting with element 6

2、find_end()

#include "algostuff.hpp"
using namespace std;

int main()
{
    deque<int> coll;
    list<int> subcoll;

    INSERT_ELEMENTS(coll,1,7);
    INSERT_ELEMENTS(coll,1,7);

    INSERT_ELEMENTS(subcoll,3,6);

    PRINT_ELEMENTS(coll,   "coll:    ");
    PRINT_ELEMENTS(subcoll,"subcoll: ");

    // search last occurrence of subcoll in coll
    deque<int>::iterator pos;
    pos = find_end (coll.begin(), coll.end(),         // range
                    subcoll.begin(), subcoll.end());  // subrange

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

        // search next occurrence of subcoll
        end = pos;
        pos = find_end (coll.begin(), end,               // range
                        subcoll.begin(), subcoll.end()); // subrange
    }
}
输出：
coll:    1 2 3 4 5 6 7 1 2 3 4 5 6 7 
subcoll: 3 4 5 6
subcoll found starting with element 10
subcoll found starting with element 3

3、find_first_of()

查找某些元素第一次出现的地点

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll;
    list<int> searchcoll;

    INSERT_ELEMENTS(coll,1,11);
    INSERT_ELEMENTS(searchcoll,3,5);

    PRINT_ELEMENTS(coll,      "coll:       ");
    PRINT_ELEMENTS(searchcoll,"searchcoll: ");

    // search first occurrence of an element of searchcoll in coll
    vector<int>::iterator pos;
    pos = find_first_of (coll.begin(), coll.end(),     // range
                         searchcoll.begin(),   // beginning of search set
                         searchcoll.end());    // end of search set
    cout << "first element of searchcoll in coll is element "
         << distance(coll.begin(),pos) + 1
         << endl;

    // search last occurrence of an element of searchcoll in coll
    vector<int>::reverse_iterator rpos;
    rpos = find_first_of (coll.rbegin(), coll.rend(),  // range
                          searchcoll.begin(),  // beginning of search set
                          searchcoll.end());   // end of search set
    cout << "last element of searchcoll in coll is element "
         << distance(coll.begin(),rpos.base())
         << endl;
}
输出：
coll:       1 2 3 4 5 6 7 8 9 10 11 
searchcoll: 3 4 5
first element of searchcoll in coll is element 3
last element of searchcoll in coll is element 5

4、adjacent_find()

#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> coll;

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

   PRINT_ELEMENTS(coll,"coll: ");

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

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

   // search first two elements for which the second has double the value of the first
   pos = adjacent_find (coll.begin(), coll.end(),   // range
                        doubled);                   // criterion

   if (pos != coll.end()) {
       cout << "first two elements with second value twice the "
            << "first have pos. "
            << distance(coll.begin(),pos) + 1
            << endl;
   }
}
输出：
coll: 1 3 2 4 5 5 0 
first two elements with equal value have position 5
first two elements with second value twice the first have pos. 3

第一次调用，是寻找连续两个值相等的元素，第二次调用时寻找连续两个，后面的数是前面的两倍。

5、equal()

#include "algostuff.hpp"
using namespace std;

bool bothEvenOrOdd (int elem1, int elem2)
{
    return elem1 % 2 == elem2 % 2;
}

int main()
{
    vector<int> coll1;
    list<int> coll2;

    INSERT_ELEMENTS(coll1,1,7);
    INSERT_ELEMENTS(coll2,3,9);

    PRINT_ELEMENTS(coll1,"coll1: ");
    PRINT_ELEMENTS(coll2,"coll2: ");

    // check whether both collections are equal
    if (equal (coll1.begin(), coll1.end(),  // first range
               coll2.begin())) {            // second range
        cout << "coll1 == coll2" << endl;
    }
    else {
        cout << "coll1 != coll2" << endl;
    }

    // check for corresponding even and odd elements
    if (equal (coll1.begin(), coll1.end(),  // first range
               coll2.begin(),               // second range
               bothEvenOrOdd)) {            // comparison criterion
        cout << "even and odd elements correspond" << endl;
    }
    else {
        cout << "even and odd elements do not correspond" << endl;
    }
}
输出：
coll1: 1 2 3 4 5 6 7 
coll2: 3 4 5 6 7 8 9
coll1 != coll2
even and odd elements correspond

6、is_permutation()

#include "algostuff.hpp"
using namespace std;

bool bothEvenOrOdd (int elem1, int elem2)
{
    return elem1 % 2 == elem2 % 2;
}

int main()
{
    vector<int> coll1;
    list<int> coll2;
    deque<int> coll3;

    coll1 = { 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    coll2 = { 1, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    coll3 = { 11, 12, 13, 19, 18, 17, 16, 15, 14, 11 };

    PRINT_ELEMENTS(coll1,"coll1: ");
    PRINT_ELEMENTS(coll2,"coll2: ");
    PRINT_ELEMENTS(coll3,"coll3: ");

    // check whether both collections have equal elements in any order
    if (is_permutation (coll1.cbegin(), coll1.cend(), // first range
                        coll2.cbegin())) {            // second range
        cout << "coll1 and coll2 have equal elements" << endl;
    }
    else {
        cout << "coll1 and coll2 don't have equal elements" << endl;
    }

    // check for corresponding number of even and odd elements
    // 这里是按照奇数和偶数的个数来判断是否为真
    if (is_permutation (coll1.cbegin(), coll1.cend(), // first range
                        coll3.cbegin(),               // second range
                        bothEvenOrOdd)) {             // comparison criterion
        cout << "numbers of even and odd elements match" << endl;
    }
    else {
        cout << "numbers of even and odd elements don't match" << endl;
    }
}
输出：
coll1: 1 1 2 3 4 5 6 7 8 9 
coll2: 1 9 8 7 6 5 4 3 2 1
coll3: 11 12 13 19 18 17 16 15 14 11
coll1 and coll2 have equal elements
numbers of even and odd elements match

7、mismatch()

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll1 = { 1, 2, 3, 4, 5, 6 };
    list<int>   coll2 = { 1, 2, 4, 8, 16, 3 };

    PRINT_ELEMENTS(coll1,"coll1: ");
    PRINT_ELEMENTS(coll2,"coll2: ");

    // find first mismatch
    auto values = mismatch (coll1.cbegin(), coll1.cend(),  // first range
                            coll2.cbegin());               // second range
    if (values.first == coll1.end()) {
        cout << "no mismatch" << endl;
    }
    else {
        cout << "first mismatch: "
             << *values.first  << " and "
             << *values.second << endl;
    }

    // find first position where the element of coll1 is not
    // less than the corresponding element of coll2
    values = mismatch (coll1.cbegin(), coll1.cend(),       // first range
                       coll2.cbegin(),                     // second range
                       less_equal<int>());                 // criterion
    if (values.first == coll1.end()) {
        cout << "always less-or-equal" << endl;
    }
    else {
        cout << "not less-or-equal: "
             << *values.first << " and "
             << *values.second << endl;
    }
}
输出：
coll1: 1 2 3 4 5 6 
coll2: 1 2 4 8 16 3
first mismatch: 3 and 4
not less-or-equal: 6 and 3

第一次调用mismatch()是查找第一个互异的对应元素，返回类型是

pair<vector<int>::const_iterator, list<int>::const_iterator>

判断pair第一个元素是否是终点，就知道最终的结果是否存在，第二次查找是为了找第一个元素比第二个元素大的位置。

8、lexicographical_compare()

#include "algostuff.hpp"
using namespace std;

void printCollection(const list<int>& l) {
    PRINT_ELEMENTS(l);
}

bool lessForCollection(const list<int>& l1, const list<int>& l2) {
    return lexicographical_compare(l1.begin(), l1.end(),
                                   l2.begin(), l2.end());
}

int main() {
    list<int> c1, c2, c3, c4;
    INSERT_ELEMENTS(c1, 1, 5);

    c4 = c3 = c2 = c1;
    c1.push_back(7);
    c3.push_back(2);
    c3.push_back(0);
    c4.push_back(2);

    vector<list<int>> cc;
    cc.insert(cc.begin(), {c1, c2, c3, c4, c3, c1, c4, c2});
    for_each(cc.begin(), cc.end(), printCollection);
    cout << endl;
    sort(cc.begin(), cc.end(), lessForCollection);
    for_each(cc.begin(), cc.end(), printCollection);
}
输出：
1 2 3 4 5 7 
1 2 3 4 5
1 2 3 4 5 2 0
1 2 3 4 5 2
1 2 3 4 5 2 0
1 2 3 4 5 7
1 2 3 4 5 2
1 2 3 4 5

1 2 3 4 5
1 2 3 4 5
1 2 3 4 5 2
1 2 3 4 5 2
1 2 3 4 5 2 0
1 2 3 4 5 2 0
1 2 3 4 5 7
1 2 3 4 5 7

9、检验是否排序

is_sorted(), is_sorted_until()函数

#include "algostuff.hpp"
using namespace std;
int main() {
    vector<int> coll1 = {1, 1, 2, 3, 4, 5, 6, 7, 8};
    PRINT_ELEMENTS(coll1, "coll1: ");
    if (is_sorted(coll1.begin(), coll1.end())) {
        cout << "coll1 is sorted" << endl;
    } else {
        cout << "coll1 is not sorted" << endl;
    }
    map<int, string> coll2;
    coll2 = {{1, "Bill"}, {2, "Jim"}, {3, "Nico"}, {4, "Liu"}, {5, "Ai"}};
    PRINT_MAPPED_ELEMENTS(coll2, "coll2: ");

    auto compareName = [](const pair<int,string>& e1, const pair<int, string>& e2) {
                            return e1.second < e2.second;
                        };
    if (is_sorted(coll2.begin(), coll2.end(), compareName)) {
        cout << "names in coll2 are sorted" << endl;
    } else {
        cout << "names in coll2 are not sorted" << endl;
    }
    auto pos = is_sorted_until(coll2.cbegin(), coll2.cend(), compareName);
    if (pos != coll2.end()) {
        cout << "the first unsorted name : " << pos->second << endl;
    }
}
输出：
coll1: 1 1 2 3 4 5 6 7 8 
coll1 is sorted
coll2: [1,Bill] [2,Jim] [3,Nico] [4,Liu] [5,Ai]
names in coll2 are not sorted
the first unsorted name : Liu

10、检验是否分割

is_partitioned(), partition_point()

#include "algostuff.hpp"

using namespace std;

int main() {
    vector<int> coll = {5, 3, 9, 1, 3, 4, 8, 2, 6};
    PRINT_ELEMENTS(coll, "coll: ");
    auto isOdd = [](int elem) {
        return elem % 2 == 1;
    };
    if(is_partitioned(coll.begin(), coll.end(), isOdd)) {
        cout << "coll is partitioned" << endl;
        auto pos = partition_point(coll.begin(), coll.end(), isOdd);
        cout << "first even element :" << *pos << endl;
    } else {
        cout << "coll is not partitioned" << endl;
    }
    return 0;
}
输出：
coll: 5 3 9 1 3 4 8 2 6 
coll is partitioned
first even element :4