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

1、检验是否形成heap

is_heap(), is_heap_until()

#include "algostuff.hpp"

using namespace std;

int main() {
    vector<int> coll1 = {9, 8, 7, 7, 7, 5, 4, 2, 1};
    vector<int> coll2 = {5, 3, 2, 1, 4, 7, 9, 8, 6};
    PRINT_ELEMENTS(coll1, "coll1: ");
    PRINT_ELEMENTS(coll2, "coll2: ");
    cout << boolalpha << "coll1 is heap: " << 
         is_heap(coll1.begin(), coll1.end()) << endl;
    cout << "coll2 is heap: " << is_heap(coll2.begin(), coll2.end()) << endl;
    auto pos = is_heap_until(coll2.begin(), coll2.end());
    if(pos != coll2.end()) {
        cout << "first non-heap element: " << *pos << endl;
    }
    return 0;
}
输出：
coll1: 9 8 7 7 7 5 4 2 1 
coll2: 5 3 2 1 4 7 9 8 6
coll1 is heap: true
coll2 is heap: false
first non-heap element: 4

2、检验all、any、none

all_of(), any_of(), none_of()

#include "algostuff.hpp"

using namespace std;

int main() {
    vector<int> coll;
    vector<int>::iterator pos;
    INSERT_ELEMENTS(coll, 1, 9);
    PRINT_ELEMENTS(coll,"coll: ");

    auto isEven = [](int elem){
        return elem % 2 == 0;
    };
    cout << boolalpha << "all even?: " << all_of(coll.begin(), coll.end(), isEven) << endl;;
    cout << "any even?: " << any_of(coll.begin(), coll.end(), isEven) << endl;
    cout << "none even?: " << none_of(coll.begin(), coll.end(), isEven) << endl;
    return 0;
}
输出：
coll: 1 2 3 4 5 6 7 8 9 
all even?: false
any even?: true
none even?: false

3、修改型算法

下面描述的算法会修改区间的内容，有两种方法，使用迭代器过程中修改元素，或者将元素从源区间复制到目标区间的过程中进行修改。但是需要注意的是，目标区间不可以是关联容器或者无序容器，因为他们的元素会被认为是常量。

（1）复制元素copy(), copy_if(),copy_n(),copy_backward()

copy()的destBeg不可以处于[sourceBeg,sorceEnd)区间内，copy_if()源区间和目标区间不可以重叠，copy_backward()，destEnd不可以处于(sourceBeg, sourceEnd]区间内。

copy()正向遍历，copy_backward()反向遍历，若要把一个子区间复制到前端，应该使用copy(),此时destBeg位置位于sourceBeg之前。若要把一个子区间复制到后端，应使用copy_backward()，此时destEnd位置位于sourceEnd之后。自C++11起，如果源端元素不再使用，就使用move()取代copy()，使用move_backward()取代copy_backward()。

#include "algostuff.hpp"

using namespace std;

int main() {
    vector<string> coll1 = {"Hello", "this", "is","an", "example"};
    list<string> coll2;
    copy(coll1.cbegin(), coll1.cend(), back_inserter(coll2));

    copy(coll2.cbegin(), coll2.cend(), ostream_iterator<string>(cout, " "));
    cout << endl;

    copy(coll1.crbegin(), coll1.crend(), coll2.begin());

    copy(coll2.cbegin(), coll2.cend(), ostream_iterator<string>(cout, " "));
    cout << endl;
    return 0;
}
输出：
Hello this is an example 
example an is this Hello

#include "algostuff.hpp"

using namespace std;

int main() {
    vector<char> source(10, '.');
    for (int c = 'a'; c <= 'f'; c++) {
        source.push_back(c);
    }
    source.insert(source.end(), 10, '.');
    PRINT_ELEMENTS(source, "source: ");
    vector<char> c1(source.begin(), source.end());
    copy(c1.cbegin()+10, c1.cbegin()+16, c1.begin()+7);
    PRINT_ELEMENTS(c1, "c1: ");
    vector<char> c2(source.begin(), source.end());
    copy_backward(c2.cbegin()+10, c2.cbegin()+16, c2.begin()+19);
    PRINT_ELEMENTS(c2, "c2: ");
    return 0;
}
输出：
source: . . . . . . . . . . a b c d e f . . . . . . . . . . 
c1: . . . . . . . a b c d e f d e f . . . . . . . . . .
c2: . . . . . . . . . . a b c a b c d e f . . . . . . .

#include "algostuff.hpp"
using namespace std;

int main() {
    copy(istream_iterator<string>(cin),
         istream_iterator<string>(),
         ostream_iterator<string>(cout, "\n"));
}

（2）移动元素move(), move_backward()

#include "algostuff.hpp"
using namespace std;

int main() {
    vector<string> coll1 = {"Hello", "this", "is", "an", "example"};
    list<string> coll2;
    copy(coll1.cbegin(), coll1.cend(), back_inserter(coll2));

    move(coll2.cbegin(), coll2.cend(), ostream_iterator<string>(cout, " "));
    cout << endl;

    move(coll1.crbegin(), coll1.crend(), coll2.begin());
    move(coll2.cbegin(), coll2.cend(), ostream_iterator<string>(cout, " "));
    cout << endl;
    return 0;
}
输出：
Hello this is an example 
example an is this Hello

（3）转换和结合元素transform()

#include "algostuff.hpp"

using namespace std;

int main() {
    vector<int> coll1;
    list<int> coll2;
    INSERT_ELEMENTS(coll1, 1, 9);
    PRINT_ELEMENTS(coll1, "coll1: ");

    transform(coll1.cbegin(), coll1.cend(), coll1.begin(), negate<int>());
    PRINT_ELEMENTS(coll1, "nageted: ");

    transform(coll1.cbegin(), coll1.cend(), 
              back_inserter(coll2), 
              std::bind(multiplies<int>(),
                        std::placeholders::_1, 10));
    PRINT_ELEMENTS(coll2, "coll2: ");
    transform(coll2.crbegin(), coll2.crend(),
              ostream_iterator<int>(cout, " "),
              [](int elem){
                return -elem;
              });
    cout << endl;
}
输出：
coll1: 1 2 3 4 5 6 7 8 9 
nageted: -1 -2 -3 -4 -5 -6 -7 -8 -9
coll2: -10 -20 -30 -40 -50 -60 -70 -80 -90
90 80 70 60 50 40 30 20 10

#include "algostuff.hpp"

using namespace std;

int main() {
    vector<int> coll1;
    list<int> coll2;
    INSERT_ELEMENTS(coll1, 1, 9);
    PRINT_ELEMENTS(coll1, "coll1: ");
    transform(coll1.cbegin(), coll1.cend(),
              coll1.cbegin(),
              coll1.begin(),
              multiplies<int>());
    PRINT_ELEMENTS(coll1, "squared: ");
    transform(coll1.cbegin(), coll1.cend(),
              coll1.crbegin(),
              back_inserter(coll2),
              plus<int>());
    PRINT_ELEMENTS(coll2, "coll2: ");
    transform(coll1.cbegin(), coll1.cend(),
              coll2.cbegin(),
              ostream_iterator<int>(cout, " "),
              minus<int>());
    cout << endl;
}
输出：
coll1: 1 2 3 4 5 6 7 8 9 
squared: 1 4 9 16 25 36 49 64 81
coll2: 82 68 58 52 50 52 58 68 82
-81 -64 -49 -36 -25 -16 -9 -4 -1

（4）互换元素swap_ranges()

#include "algostuff.hpp"

using namespace std;

int main() {
    vector<int> coll1;
    deque<int> coll2;
    INSERT_ELEMENTS(coll1, 1, 9);
    INSERT_ELEMENTS(coll2, 11, 23);
    PRINT_ELEMENTS(coll1, "coll1: ");
    PRINT_ELEMENTS(coll2, "coll2: ");
    cout << endl;
    deque<int>::iterator pos;
    pos= swap_ranges(coll1.begin(), coll1.end(),
                     coll2.begin());
    PRINT_ELEMENTS(coll1, "\ncoll1: ");
    PRINT_ELEMENTS(coll2, "coll2: ");
    if (pos != coll2.end()) {
        cout << "first element not midified: " << *pos << endl;
    }
    swap_ranges(coll2.begin(), coll2.begin()+3,
                coll2.rbegin());
    PRINT_ELEMENTS(coll2, "coll2: ");
    return 0;
}
输出：
coll1: 1 2 3 4 5 6 7 8 9 
coll2: 11 12 13 14 15 16 17 18 19 20 21 22 23


coll1: 11 12 13 14 15 16 17 18 19
coll2: 1 2 3 4 5 6 7 8 9 20 21 22 23
first element not midified: 20
coll2: 23 22 21 4 5 6 7 8 9 20 3 2 1

（5）赋值fill()，fill_n()

#include "algostuff.hpp"

using namespace std;

int main() {
    fill_n(ostream_iterator<float>(cout, " "),
           10,
           7.7);
    cout << endl;
    list<string> coll;
    fill_n(back_inserter(coll),
           9,
           "hello");
    PRINT_ELEMENTS(coll, "coll: ");
    fill(coll.begin(), coll.end(), "again");
    PRINT_ELEMENTS(coll, "coll: ");
    fill_n(coll.begin(), coll.size() - 2, "hi");
    PRINT_ELEMENTS(coll, "coll: ");
    list<string>::iterator pos1, pos2;
    pos1 = coll.begin();
    pos2 = coll.end();
    fill(++pos1, --pos2, "hmmm");
    PRINT_ELEMENTS(coll, "coll: ");
    return 0;
}
输出：
7.7 7.7 7.7 7.7 7.7 7.7 7.7 7.7 7.7 7.7 
coll: hello hello hello hello hello hello hello hello hello
coll: again again again again again again again again again
coll: hi hi hi hi hi hi hi again again
coll: hi hmmm hmmm hmmm hmmm hmmm hmmm hmmm again

（6）赋予新生值generate(), generate_n()

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

using namespace std;

int main() {
    list<int> coll;
    generate_n(back_inserter(coll),
               5,
               rand);
    PRINT_ELEMENTS(coll, "coll: ");
    generate(coll.begin(), coll.end(), rand);
    PRINT_ELEMENTS(coll);
}
输出：
coll: 41 18467 6334 26500 19169 
15724 11478 29358 26962 24464

（7）赋予一系列递增的值iota()

#include "algostuff.hpp"

using namespace std;

int main() {
    array<int, 10> coll;
    iota(coll.begin(), coll.end(), 42);
    PRINT_ELEMENTS(coll, "coll: ");
    return 0;
}
输出：
coll: 42 43 44 45 46 47 48 49 50 51

（7）替换元素replace(), replace_if()

#include "algostuff.hpp"

using namespace std;
int main() {
    list<int> coll;
    INSERT_ELEMENTS(coll, 2, 7);
    INSERT_ELEMENTS(coll, 4, 9);
    PRINT_ELEMENTS(coll, "coll: ");
    replace(coll.begin(), coll.end(), 6, 42);
    PRINT_ELEMENTS(coll, "coll: ");
    replace_if(coll.begin(), coll.end(), 
              [](int elem) {
                return elem < 5;
              },
              0);
    PRINT_ELEMENTS(coll, "coll: ");
}
输出：
coll: 2 3 4 5 6 7 4 5 6 7 8 9 
coll: 2 3 4 5 42 7 4 5 42 7 8 9
coll: 0 0 0 5 42 7 0 5 42 7 8 9

（8）复制并替换元素replace_copy(), replace_copy_if()

#include "algostuff.hpp"

using namespace std;

int main() {
    list<int> coll;
    INSERT_ELEMENTS(coll, 2, 6);
    INSERT_ELEMENTS(coll, 4, 9);
    PRINT_ELEMENTS(coll);
    replace_copy(coll.begin(), coll.end(),
                 ostream_iterator<int>(cout, " "),
                 5,
                 55);
    cout << endl;
    replace_copy_if(coll.cbegin(), coll.cend(),
                    ostream_iterator<int>(cout, " "),
                    bind(less<int>(), std::placeholders::_1, 5),
                    42);
    cout << endl;
    replace_copy_if(coll.cbegin(), coll.cend(),
                    ostream_iterator<int>(cout, " "),
                    [](int elem) {
                        return elem%2 ==1;
                    }, 
                    0);
    cout << endl;
}
输出：
2 3 4 5 6 4 5 6 7 8 9 
2 3 4 55 6 4 55 6 7 8 9
42 42 42 5 6 42 5 6 7 8 9
2 0 4 0 6 4 0 6 0 8 0