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

1、移除型算法

（1）移除某些元素remove(), remove_if()

#include "algostuff.hpp"

using namespace std;

int main() {
    vector<int> coll;
    INSERT_ELEMENTS(coll, 2, 6);
    INSERT_ELEMENTS(coll, 4, 9);
    INSERT_ELEMENTS(coll, 1, 7);
    PRINT_ELEMENTS(coll, "coll: ");
    vector<int>::iterator pos;
    pos = remove(coll.begin(), coll.end(), 5);
    PRINT_ELEMENTS(coll, "size not changed: ");
    coll.erase(pos, coll.end());
    PRINT_ELEMENTS(coll, "size changed: ");
    coll.erase(remove_if(coll.begin(), coll.end(), 
                        [](int elem) {
                            return elem<4;
                        }),
                        coll.end());
    PRINT_ELEMENTS(coll, "<4 removed: ");
    return 0;
}
输出：
coll: 2 3 4 5 6 4 5 6 7 8 9 1 2 3 4 5 6 7 
size not changed: 2 3 4 6 4 6 7 8 9 1 2 3 4 6 7 5 6 7
size changed: 2 3 4 6 4 6 7 8 9 1 2 3 4 6 7
<4 removed: 4 6 4 6 7 8 9 4 6 7

（2）复制时一并移除元素，remove_copy(), remove_copy_if()

#include "algostuff.hpp"

using namespace std;
using namespace std::placeholders;

int main() {
    list<int> coll1;
    INSERT_ELEMENTS(coll1, 1, 6);
    INSERT_ELEMENTS(coll1, 1, 9);
    PRINT_ELEMENTS(coll1);
    remove_copy(coll1.cbegin(), coll1.cend(), 
                ostream_iterator<int>(cout, " "),
                3);
    cout << endl;
    remove_copy_if(coll1.cbegin(), coll1.cend(),
                   ostream_iterator<int>(cout, " "),
                   [](int elem){
                        return elem > 4;
                   });
    cout << endl;
    multiset<int> coll2;
    remove_copy_if(coll1.cbegin(), coll1.cend(),
                  inserter(coll2, coll2.end()),
                  bind(less<int>(), _1, 4));
    PRINT_ELEMENTS(coll2);
}
输出：
1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 
1 2 4 5 6 1 2 4 5 6 7 8 9
1 2 3 4 1 2 3 4
4 4 5 5 6 6 7 8 9

（3）移除重复元素unique(),需先经过排序

#include "algostuff.hpp"

using namespace std;

int main() {
    int source[] = {1, 4, 4, 6, 1, 2, 2, 3, 1, 6, 6, 5, 7, 5, 4, 4};
    list<int> coll;
    copy(begin(source), end(source), back_inserter(coll));
    PRINT_ELEMENTS(coll);

    auto pos = unique(coll.begin(), coll.end());
    copy(coll.begin(), pos, ostream_iterator<int>(cout, " "));
    cout << "\n\n";
    copy(begin(source), end(source), coll.begin());
    PRINT_ELEMENTS(coll);
    coll.erase(unique(coll.begin(), coll.end(), greater<int>()), coll.end());
    PRINT_ELEMENTS(coll);
    return 0;
}
输出：
1 4 4 6 1 2 2 3 1 6 6 5 7 5 4 4 
1 4 6 1 2 3 1 6 5 7 5 4

1 4 4 6 1 2 2 3 1 6 6 5 7 5 4 4
1 4 4 6 6 6 7

第一次调用unique是为了删除连续的重复元素，第二次调用是为了将前面的值大于自身值时，将自身删掉。

（4）复制过程中移除重复元素unique_copy(), unique_copy()

#include "algostuff.hpp"

using namespace std;

bool differenceOne(int elem1, int elem2) {
    return elem1 + 1 == elem2 || elem1 - 1 == elem2;
}

int main() {
    int source[] = {1, 4, 4, 6, 1, 2, 2, 3, 1, 6, 6, 6, 5, 7, 5, 4, 4};
    list<int> coll;
    copy(begin(source), end(source), back_inserter(coll));
    PRINT_ELEMENTS(coll);
    unique_copy(coll.cbegin(), coll.cend(),ostream_iterator<int>(cout, " "));
    cout << endl;
    unique_copy(coll.cbegin(), coll.cend(), ostream_iterator<int>(cout, " "),
                differenceOne);
    cout << endl;
    return 0;
}
输出：
1 4 4 6 1 2 2 3 1 6 6 6 5 7 5 4 4 
1 4 6 1 2 3 1 6 5 7 5 4
1 4 4 6 1 3 1 6 6 6 4 4

第二次调用unique_copy() 是移除如果某个元素，它和它前面的元素相差1，则将其移除掉。

#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

bool bothSpaces (char elem1, char elem2) {
    return elem1 == ' ' && elem2 == ' ';
}

int main() {
    // don't skip leading whitespaces by default
    cin.unsetf(ios::skipws);
    unique_copy(istream_iterator<char>(cin),
                istream_iterator<char>(),
                ostream_iterator<char>(cout),
                bothSpaces);
}
输入：hello,   heare aer  asdjk jkewj   jwkerj   jakej    jkaew f
输出：hello, heare aer asdjk jkewj jwkerj jakej jkaew f

?2、变序算法

（1）反转元素次序reverse(), reverse_copy()

#include "algostuff.hpp"
using namespace std;

int main() {
    vector<int> coll;
    INSERT_ELEMENTS(coll, 1, 9);
    PRINT_ELEMENTS(coll, "coll: ");
    reverse(coll.begin(), coll.end());
    PRINT_ELEMENTS(coll, "coll: ");
    reverse(coll.begin()+1, coll.end()-1);
    PRINT_ELEMENTS(coll, "coll: ");
    reverse_copy(coll.begin(), coll.end(), 
                 ostream_iterator<int>(cout, " "));
    cout << endl;
    return 0;
}
输出：
coll: 1 2 3 4 5 6 7 8 9 
coll: 9 8 7 6 5 4 3 2 1
coll: 9 2 3 4 5 6 7 8 1
1 8 7 6 5 4 3 2 9

（2）旋转元素rotate()

#include "algostuff.hpp"
using namespace std;

int main() {
    vector<int> coll;
    INSERT_ELEMENTS(coll, 1, 9);
    PRINT_ELEMENTS(coll, "coll: ");
    // rotate one element to the left
    rotate(coll.begin(), coll.begin()+1, coll.end());  
    PRINT_ELEMENTS(coll, "one left: ");
    // rotate two elements to the right
    rotate(coll.begin(), coll.end()-2, coll.end());
    PRINT_ELEMENTS(coll, "two right: ");
    rotate(coll.begin(), find(coll.begin(), coll.end(), 4), 
           coll.end());
    PRINT_ELEMENTS(coll, "4 first: ");
    return 0;   
}
输出：
coll: 1 2 3 4 5 6 7 8 9 
one left: 2 3 4 5 6 7 8 9 1
two right: 9 1 2 3 4 5 6 7 8
4 first: 4 5 6 7 8 9 1 2 3

只有针对随机访问迭代器才可以使用加减操作，否则要使用advance()。?

（3）复制并同时旋转元素rotate_copy()

#include "algostuff.hpp"

using namespace std;

int main() {
    set<int> coll;
    INSERT_ELEMENTS(coll, 1, 9);
    PRINT_ELEMENTS(coll, "coll: ");
    set<int>::const_iterator pos = next(coll.begin());
    rotate_copy(coll.cbegin(),
                pos,
                coll.end(),
                ostream_iterator<int>(cout, " "));
    cout << endl;
    pos = coll.cend();
    advance(pos, -2);
    rotate_copy(coll.cbegin(),
                pos,
                coll.cend(),
                ostream_iterator<int>(cout, " "));
    cout << endl;
    rotate_copy(coll.cbegin(),
                coll.find(4),
                coll.cend(),
                ostream_iterator<int>(cout, " "));
    cout << endl;
    return 0;
}
输出：
coll: 1 2 3 4 5 6 7 8 9 
2 3 4 5 6 7 8 9 1
8 9 1 2 3 4 5 6 7
4 5 6 7 8 9 1 2 3

（4）排列元素next_permutation(), prev_permutation()

#include "algostuff.hpp"

using namespace std;

int main() {
    vector<int> coll;
    INSERT_ELEMENTS(coll, 1, 3);
    PRINT_ELEMENTS(coll, "on entry: ");
    while(next_permutation(coll.begin(), coll.end())) {
        PRINT_ELEMENTS(coll, " ");
    }
    PRINT_ELEMENTS(coll, "afterward: ");
    while(prev_permutation(coll.begin(), coll.end())) {
        PRINT_ELEMENTS(coll, " ");
    }
    PRINT_ELEMENTS(coll, "now: ");
    while(prev_permutation(coll.begin(), coll.end())) {
        PRINT_ELEMENTS(coll, " ");
    }
    PRINT_ELEMENTS(coll, "afterward: ");
    return 0;
}
输出：
on entry: 1 2 3  
 1 3 2 
 2 1 3 
 2 3 1 
 3 1 2 
 3 2 1 
afterward: 1 2 3 
now: 3 2 1       
 3 1 2 
 2 3 1 
 2 1 3 
 1 3 2 
 1 2 3 
afterward: 3 2 1

（5）对元素重新洗牌shuffle(), random_shuffle()

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

int main() {
    vector<int> coll;
    INSERT_ELEMENTS(coll, 1, 9);
    PRINT_ELEMENTS(coll, "coll: ");
    random_shuffle(coll.begin(), coll.end());
    PRINT_ELEMENTS(coll, "shuffled: ");
    sort(coll.begin(), coll.end());
    PRINT_ELEMENTS(coll, "sorted: ");
    default_random_engine dre;
    shuffle(coll.begin(), coll.end(), dre);
    PRINT_ELEMENTS(coll, "shuffled: ");
    return 0;
}
输出：
coll: 1 2 3 4 5 6 7 8 9 
shuffled: 9 2 7 3 1 6 8 4 5
sorted: 1 2 3 4 5 6 7 8 9
shuffled: 4 1 5 8 6 2 9 7 3

自定义随机数生成器传递给random_shuffle()以对元素重新洗牌。

#include <cstdlib>
#include "algostuff.hpp"

using namespace std;

class MyRandom {
public:
    ptrdiff_t operator() (ptrdiff_t max) {
        double tmp;
        tmp = static_cast<double>(rand()) / static_cast<double>(RAND_MAX);
        return static_cast<ptrdiff_t>(tmp*max);
    }
};

int main() {
    vector<int> coll;
    INSERT_ELEMENTS(coll, 1, 9);
    PRINT_ELEMENTS(coll,"coll:");
    MyRandom rd;
    random_shuffle(coll.begin(), coll.end(), rd);
    PRINT_ELEMENTS(coll, "shuffled: ");
    return 0;
}
输出：
coll:1 2 3 4 5 6 7 8 9 
shuffled: 4 3 8 7 5 2 6 1 9

（6）将元素向前搬partition(), stable_partition()

#include "algostuff.hpp"
using namespace std;

int main() {
    vector<int> coll1;
    vector<int> coll2;
    INSERT_ELEMENTS(coll1, 1, 9);
    INSERT_ELEMENTS(coll2, 1, 9);
    PRINT_ELEMENTS(coll1, "coll1: ");
    PRINT_ELEMENTS(coll2, "coll2: ");
    vector<int>::iterator pos1, pos2;
    pos1 = partition(coll1.begin(), coll1.end(),
                     [](int elem) {
                        return elem%2 == 0;
                     });
    pos2 = stable_partition(coll2.begin(), coll2.end(),
                     [](int elem) {
                        return elem%2== 0;
                     });
    PRINT_ELEMENTS(coll1, "coll1: ");
    cout << "first odd element: " << *pos1 << endl;
    PRINT_ELEMENTS(coll2, "coll2: ");
    cout << "first odd element: " << *pos2 << endl;
    return 0;
}
输出：
coll1: 1 2 3 4 5 6 7 8 9 
coll2: 1 2 3 4 5 6 7 8 9
coll1: 8 2 6 4 5 3 7 1 9
first odd element: 5
coll2: 2 4 6 8 1 3 5 7 9
first odd element: 1

（7）划分两个区间partition_copy()

#include "algostuff.hpp"

using namespace std;

int main() {
    vector<int> coll = {1, 6, 33, 7, 22, 4, 11, 33, 2, 7, 0, 42, 5};
    PRINT_ELEMENTS(coll, "coll: ");
    vector<int> evenColl;
    vector<int> oddColl;
    partition_copy(coll.cbegin(), coll.cend(),
                   back_inserter(evenColl),
                   back_inserter(oddColl),
                   [](int elem) {
                    return elem%2 == 0;
                   });
    PRINT_ELEMENTS(evenColl, "evenColl:");
    PRINT_ELEMENTS(oddColl, "oddColl:");

    return 0;
}
输出：
coll: 1 6 33 7 22 4 11 33 2 7 0 42 5 
evenColl:6 22 4 2 0 42
oddColl:1 33 7 11 33 7 5