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

1、排序算法

（1）对所有元素排序sort(), stable_sort()

#include "algostuff.hpp"

using namespace std;

int main() {
    deque<int> coll;
    INSERT_ELEMENTS(coll, 1, 9);
    INSERT_ELEMENTS(coll, 1, 9);
    PRINT_ELEMENTS(coll, "on entry: ");
    sort(coll.begin(), coll.end());
    PRINT_ELEMENTS(coll, "sorted: ");
    sort(coll.begin(), coll.end(), greater<int>());
    PRINT_ELEMENTS(coll, "storted > ");
    return 0;
}
输出：
on entry: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 
sorted: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
storted > 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1

#include "algostuff.hpp"

using namespace std;

bool lessLength(const string& s1, const string& s2) {
    return s1.length() < s2.length();
}
int main() {
    vector<string> coll1 = {"1xxxx", "2x", "3x", "4x", "5xx", "6xxxx", "7xx", "8xxx", "9xx", "10xxx","11", "12", "13", "14xx", "15","16","17"};
    vector<string> coll2(coll1);
    PRINT_ELEMENTS(coll1, "on entry: ");
    sort(coll1.begin(), coll1.end(), lessLength);
    stable_sort(coll2.begin(), coll2.end(), lessLength);
    PRINT_ELEMENTS(coll1, "with sort(): \n");
    PRINT_ELEMENTS(coll2, "with stable_sort(): \n");
    return 0;
}
输出：
on entry: 1xxxx 2x 3x 4x 5xx 6xxxx 7xx 8xxx 9xx 10xxx 11 12 13 14xx 15 16 17 
with sort():
2x 17 16 15 13 12 11 4x 3x 9xx 7xx 5xx 8xxx 14xx 10xxx 6xxxx 1xxxx
with stable_sort():
2x 3x 4x 11 12 13 15 16 17 5xx 7xx 9xx 8xxx 14xx 1xxxx 6xxxx 10xxx

（2）局部排序partial_sort(), partial_sort()

#include "algostuff.hpp"

using namespace std;

int main() {
    deque<int> coll;
    INSERT_ELEMENTS(coll, 3, 7);
    INSERT_ELEMENTS(coll, 2, 6);
    INSERT_ELEMENTS(coll, 1, 5);
    PRINT_ELEMENTS(coll);
    partial_sort(coll.begin(), coll.begin()+5,
                 coll.end());
    PRINT_ELEMENTS(coll);
    partial_sort(coll.begin(), coll.begin()+5,
                 coll.end(),
                 greater<int>());
    PRINT_ELEMENTS(coll);
    partial_sort(coll.begin(), coll.end(),
                 coll.end());
    PRINT_ELEMENTS(coll);
    return 0;
}
输出：
3 4 5 6 7 2 3 4 5 6 1 2 3 4 5 
1 2 2 3 3 7 6 5 5 6 4 4 3 4 5
7 6 6 5 5 1 2 2 3 3 4 4 3 4 5
1 2 2 3 3 3 4 4 4 5 5 5 6 6 7

（3）partial_sort_copy()

#include "algostuff.hpp"

using namespace std;

int main() {
    deque<int> coll1;
    vector<int> coll6(6);
    vector<int> coll30(30);
    INSERT_ELEMENTS(coll1, 3, 7);
    INSERT_ELEMENTS(coll1, 2, 6);
    INSERT_ELEMENTS(coll1, 1, 5);
    PRINT_ELEMENTS(coll1);
    vector<int>::const_iterator pos6;
    pos6 = partial_sort_copy(coll1.cbegin(), coll1.cend(),
                             coll6.begin(), coll6.end());
    copy(coll6.cbegin(), pos6,
         ostream_iterator<int>(cout, " "));
    cout << endl;
    vector<int>::const_iterator pos30;
    pos30 = partial_sort_copy(coll1.cbegin(), coll1.cend(),
                              coll30.begin(), coll30.end(),
                              greater<int>());
    copy(coll30.cbegin(), pos30,
         ostream_iterator<int>(cout, " "));
    cout << endl;
    return 0;
}
输出：
3 4 5 6 7 2 3 4 5 6 1 2 3 4 5 
1 2 2 3 3 3
7 6 6 5 5 5 4 4 4 3 3 3 2 2 1

（4）根据第n个元素排序nth_element()

#include "algostuff.hpp"

using namespace std;

int main() {
    deque<int> coll;
    INSERT_ELEMENTS(coll, 3, 7);
    INSERT_ELEMENTS(coll, 2, 6);
    INSERT_ELEMENTS(coll, 1, 5);
    PRINT_ELEMENTS(coll);
    
    nth_element(coll.begin(), coll.begin()+3, coll.end());
    cout << "the four lowest elements are: ";
    copy(coll.cbegin(), coll.cbegin()+4, ostream_iterator<int>(cout, " "));
    cout << endl;
    nth_element(coll.begin(), coll.end()-4, coll.end());
    cout << "the four highest elements are: ";
    copy(coll.cend()-4, coll.cend(), ostream_iterator<int>(cout, " "));
    cout << endl;
    nth_element(coll.begin(), coll.begin()+3,
                coll.end(), greater<int>());
    cout << "the four highest elements are: ";
    copy(coll.cbegin(), coll.cbegin()+4,
         ostream_iterator<int>(cout, " "));
    cout << endl;
    return 0;
}
输出：
3 4 5 6 7 2 3 4 5 6 1 2 3 4 5 
the four lowest elements are: 2 1 2 3
the four highest elements are: 5 6 6 7
the four highest elements are: 6 7 6 5

（5）make_heap()、push_heap()、pop_heap()、sort_heap()

#include "algostuff.hpp"

using namespace std;

int main() {
    vector<int> coll;
    INSERT_ELEMENTS(coll, 3, 7);
    INSERT_ELEMENTS(coll, 5, 9);
    INSERT_ELEMENTS(coll, 1, 4);
    PRINT_ELEMENTS(coll, "on entry: ");
    make_heap(coll.begin(), coll.end());
    PRINT_ELEMENTS(coll, "after make_heap(): ");
    pop_heap(coll.begin(), coll.end());
    coll.pop_back();
    PRINT_ELEMENTS(coll, "after pop_heap(): ");
    coll.push_back(17);
    push_heap(coll.begin(), coll.end());
    PRINT_ELEMENTS(coll, "after push_heap(): ");
    sort_heap(coll.begin(), coll.end());
    PRINT_ELEMENTS(coll, "after sort_heap(): ");
    
    return 0;
}
输出：
on entry: 3 4 5 6 7 5 6 7 8 9 1 2 3 4 
after make_heap(): 9 8 6 7 7 5 5 3 6 4 1 2 3 4
after pop_heap(): 8 7 6 7 4 5 5 3 6 4 1 2 3
after push_heap(): 17 7 8 7 4 5 6 3 6 4 1 2 3 5
after sort_heap(): 1 2 3 3 4 4 5 5 6 6 7 7 8 17

调用make_heap之后，元素被排序为9 8 6 7 7 5 5 3 6 4 1 2 3 4

?转换为二叉树如下：

?2、已排序区间算法

（1）binary_search()

#include "algostuff.hpp"

using namespace std;

int main() {
    list<int> coll;
    INSERT_ELEMENTS(coll, 1, 9);
    PRINT_ELEMENTS(coll);
    if(binary_search(coll.begin(), coll.end(), 5)) {
        cout << "5 is present" << endl;
    } else {
        cout << "5 is not present" << endl;
    }
    if(binary_search(coll.begin(), coll.end(), 42)) {
        cout << "42 is present" << endl;
    } else {
        cout << "42 is not present" << endl;
    }
    return 0;
}
输出：
1 2 3 4 5 6 7 8 9 
5 is present
42 is not present

（2）检查数个元素是否存在includes()

#include "algostuff.hpp"

using namespace std;

int main() {
    list<int> coll;
    vector<int> search;
    INSERT_ELEMENTS(coll, 1, 9);
    PRINT_ELEMENTS(coll, "coll: ");
    search.push_back(3);
    search.push_back(4);
    search.push_back(7);
    PRINT_ELEMENTS(search, "search: ");
    if(includes(coll.cbegin(), coll.cend(),
                search.cbegin(), search.cend())) {
        cout << "all elements of search are also in coll" << endl;
    } else {
        cout << "not all elements of search are also in coll" << endl;
    }
    return 0;
}
输出：
coll: 1 2 3 4 5 6 7 8 9 
search: 3 4 7
all elements of search are also in coll

（3）查找第一个或者最后一个可能的位置lower_bound()、upper_bound()

#include "algostuff.hpp"

using namespace std;

int main() {
    list<int> coll;
    INSERT_ELEMENTS(coll, 1, 9);
    INSERT_ELEMENTS(coll, 1, 9);
    coll.sort();
    PRINT_ELEMENTS(coll);
    auto pos1 = lower_bound(coll.cbegin(), coll.cend(), 5);
    auto pos2 = upper_bound(coll.cbegin(), coll.cend(), 5);
    cout << "5 could get position "
         << distance(coll.cbegin(), pos1) + 1
         << " up to " 
         << distance(coll.cbegin(), pos2) + 1
         << " without breaking the sorting" << endl;
    coll.insert(lower_bound(coll.begin(), coll.end(), 3), 3);
    coll.insert(upper_bound(coll.begin(), coll.end(), 7), 7);
    PRINT_ELEMENTS(coll);
    return 0;
}
输出：
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 
5 could get position 9 up to 11 without breaking the sorting
1 1 2 2 3 3 3 4 4 5 5 6 6 7 7 7 8 8 9 9

（4）查找第一个和最后一个可能位置equal_range()

#include "algostuff.hpp"

using namespace std;

int main() {
    list<int> coll;
    INSERT_ELEMENTS(coll, 1, 9);
    INSERT_ELEMENTS(coll, 1, 9);
    coll.sort();
    PRINT_ELEMENTS(coll);
    pair<list<int>::const_iterator, list<int>::const_iterator> range;
    range = equal_range(coll.cbegin(), coll.cend(), 5);
    cout << "5 could get position " 
         << distance(coll.cbegin(), range.first) + 1
         << " up to " 
         << distance(coll.cbegin(), range.second) + 1
         << " without breaking the sorting" << endl;
    return 0;
}
输出：
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 
5 could get position 9 up to 11 without breaking the sorting

（5）合并元素merge()

#include "algostuff.hpp"

using namespace std;

int main() {
    list<int> coll1;
    set<int> coll2;
    INSERT_ELEMENTS(coll1, 1, 6);
    INSERT_ELEMENTS(coll2, 3, 8);
    PRINT_ELEMENTS(coll1, "coll1: ");
    PRINT_ELEMENTS(coll2, "coll2: ");
    cout << "merged: ";
    merge(coll1.cbegin(), coll1.cend(),
          coll2.cbegin(), coll2.cend(),
          ostream_iterator<int>(cout, " "));
    cout << endl; 
    return 0;
}
输出：
coll1: 1 2 3 4 5 6 
coll2: 3 4 5 6 7 8
merged: 1 2 3 3 4 4 5 5 6 6 7 8

（6）两个已排序集合的并集set_union(),set_intersection(),set_difference(), set_symmetric_difference()

#include "algostuff.hpp"
using namespace std;

int main() {
    vector<int> c1 = {1, 2, 2, 4, 6, 7, 7, 9};
    deque<int> c2 = {2, 2, 2, 3, 6, 6, 8, 9};
    cout << "c1: ";
    copy(c1.cbegin(), c1.cend(), ostream_iterator<int>(cout, " "));
    cout << endl;
    cout << "c2: ";
    copy(c2.cbegin(), c2.cend(), ostream_iterator<int>(cout, " "));
    cout << endl << endl;
    cout << "merged: ";
    merge(c1.cbegin(), c1.cend(),
         c2.cbegin(), c2.cend(),
         ostream_iterator<int>(cout, " "));
    cout << endl;
    cout << "set_union: ";
    set_union(c1.cbegin(), c1.cend(),
              c2.cbegin(), c2.cend(),
              ostream_iterator<int>(cout, " "));
    cout << endl;
    cout << "set_intersection()";
    set_intersection(c1.cbegin(), c1.cend(),
                     c2.cbegin(), c2.cend(),
                     ostream_iterator<int>(cout, " "));
    cout << endl;
    cout << "set_difference()";
    set_difference(c1.cbegin(), c1.cend(),
                   c2.cbegin(), c2.cend(),
                   ostream_iterator<int>(cout, " "));
    cout << endl;
    cout << "set_symmetric_difference(): ";
    set_symmetric_difference(c1.cbegin(), c1.cend(),
                             c2.cbegin(), c2.cend(),
                             ostream_iterator<int>(cout, " "));
    cout << endl;
    return 0;
}
输出：
c1: 1 2 2 4 6 7 7 9 
c2: 2 2 2 3 6 6 8 9

merged: 1 2 2 2 2 2 3 4 6 6 6 7 7 8 9 9
set_union: 1 2 2 2 3 4 6 6 7 7 8 9
set_intersection()2 2 6 9
set_difference()1 4 7 7
set_symmetric_difference(): 1 2 3 4 6 7 7 8

（7）合并连贯之已排序区间inplace_merge()

#include "algostuff.hpp"

using namespace std;

int main() {
    list<int> coll;
    INSERT_ELEMENTS(coll, 1, 7);
    INSERT_ELEMENTS(coll, 1, 8);
    PRINT_ELEMENTS(coll);
    list<int>::iterator pos;
    pos = find(coll.begin(), coll.end(), 7);
    ++pos;
    inplace_merge(coll.begin(), pos, coll.end());
    PRINT_ELEMENTS(coll);
    return 0;
}
输出：
1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8