kkogoro

几种不常用的STL
不常用的STL值得一提的是,下面的所有函数都是传入(第一个元素的位置,最后一个元素的下一个位置)或(begin()...
扫描右侧二维码阅读全文
25
2018/10

几种不常用的STL

不常用的STL

值得一提的是,下面的所有函数都是传入(第一个元素的位置,最后一个元素的下一个位置)或(begin(),end())

算法

stable_sort()

稳定排序

以下是测试程序:,注意 $n$ 要足够大

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <ctime>

const int MAXN = 1000007;

typedef std::pair<int, int> PII;
PII data[MAXN], tmp[MAXN];

bool cmp(const PII &a, const PII &b) {
    return a.first < b.first;
}
 
int main() {
    srand(time(NULL));
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; ++i) {
        data[i].first = rand();
        data[i].second = i;
        tmp[i] = data[i];
    }
    std::sort(data + 1, data + 1 + n, cmp);
    std::stable_sort(tmp + 1, tmp + 1 + n, cmp);
    
    bool flag = true;
    for (int i = 1; i < n; ++i) {
        if (data[i].first == data[i + 1].first) {
             if (data[i].second > data[i + 1].second) {
                 flag = false;
                 break;
             }
        }
    }
    if (flag) {
        std::cout << "sort is stable\n";
    }
    else {
        std::cout << "sort isn't stable\n";
    }
    
    flag = true;
    for (int i = 1; i < n; ++i) {
        if (tmp[i].first == tmp[i + 1].first) {
             if (tmp[i].second > tmp[i + 1].second) {
                 flag = false;
                 break;
             }
        }
    }
    if (flag) {
        std::cout << "stable_sort is stable\n";
    }
    else {
        std::cout << "stable_sort isn't stable\n";
    }
    return 0;
}

nth_element()

$O(n)$ 求序列第 $k$ 大,传入(数组起始位置的指针,数组第k个位置的指针,数组末尾位置的下一个位置的指针),当然如果换作是STL容器(如vector)配合迭代器也是可以的。执行结束后数组第 $k$ 个位置的元素就是整个序列的第 $k$ 大元素。

#include <cstdio>
#include <algorithm>
#include <iostream>


const int MAXN = 100007;


int data[MAXN];


int main() {    
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; ++i) {
        std::cin >> data[i];
    }
    for (int i = 1; i <= n; ++i) {
        std::nth_element(data + 1, data + i, data + 1 + n);
        std::cout << data[i] << " ";
    }
    return 0;
}

random_shuffle()

随机打散序列

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <ctime>


const int MAXN  = 100007;
int data[MAXN];


int main() {
    srand(time(NULL));    
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; ++i) {
        data[i] = rand();
    }
    for (int i = 1; i <= n; ++i) {
        std::cout << data[i] << " ";
    }
    std::cout << std::endl;
    int m;
    std::cin >> m;
    while (m--) {
        std::random_shuffle(data + 1, data + 1 + n);
        for (int i = 1; i <= n; ++i) {
            std::cout << data[i] << " ";
        }
        std::cout << std::endl;
    }    
    return 0;
}

next_permutation()

下一个排列,如果没有返回 $false$

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <ctime>


const int MAXN  = 100007;
int data[MAXN];


int main() {
    srand(time(NULL));    
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; ++i) {
        data[i] = rand();
    }
    for (int i = 1; i <= n; ++i) {
        std::cout << data[i] << " ";
    }
    std::cout << std::endl;
    int m;
    std::cin >> m;
    while (m--) {
        std::next_permutation(data + 1, data + 1 + n);
        for (int i = 1; i <= n; ++i) {
            std::cout << data[i] << " ";
        }
        std::cout << std::endl;
    }    
    return 0;
}

prev_permutation()

上一个排列

可以看出来与next_permutation是一个相反的函数

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <ctime>


const int MAXN  = 100007;
int data[MAXN];


int main() {
    srand(time(NULL));    
    int n, m;
    std::cin >> n >> m;
    while (m--) {
        for (int i = 1; i <= n; ++i) {
            data[i] = rand();
        }
        for (int i = 1; i <= n; ++i) {
            std::cout << data[i] << " ";
        }
        std::cout << std::endl;
        
        std::next_permutation(data + 1, data + 1 + n);
        for (int i = 1; i <= n; ++i) {
            std::cout << data[i] << " ";
        }
        std::cout << std::endl;
        
        std::prev_permutation(data + 1, data + 1 + n);
        for (int i = 1; i <= n; ++i) {
            std::cout << data[i] << " ";
        }
        std::cout << std::endl;
    }    
    return 0;
}

数据结构

multiset

可重集,包含在set库中

需要注意 $erase()$ 函数

#include <iostream>
#include <cstdio>
#include <set>


std::multiset<int> s;


typedef std::multiset<int> PII;


inline void print() {
    for (PII::iterator it = s.begin(); it != s.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    return;
}


int main() {
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; ++i) {
        int opt, x;
        std::cin >> opt >> x;
        if (opt == 1) {
            s.insert(x);
            print();
        }
        else if (opt == 2) {
            s.erase(x);
            print();
        }
        else if (opt == 3) {
            s.erase(s.find(x));
            print();
        }
        else if (opt == 4) {
            int y;
            std::cin >> y; //delete[x, y)
            s.erase(s.lower_bound(x), s.lower_bound(y));
            print();
        }
        else {
            std::cout << s.count(x) << std::endl;    
        }
    }
    return 0;
}

构造堆函数

可以利用vector数组来直接构造堆(按照一定规则安排元素的位置,并按照一定规则访问其中元素从而把它变成堆)

make_heap()

传入数组首位置,末位置的下一个位置,比较函数

将目标构造成堆,数组(或vector)的第一个元素是堆顶,如代码中的tmp[1](即data[1])

pop_heap()

将堆顶弹出,实际上是整体左旋,堆顶放在了数组最后一位

push_heap()

将一个元素入堆,入堆的元素必须放在数组的末位置

sort_heap()

将一个已经成为堆的数组变成有序的,此操作会使原数组失去堆的性质,值得注意的是排序后的数组与堆的优先级相反,即如果是大根堆,你得到的会是一个不降的序列

在不传入比较函数的情况下,默认构造为大根堆,需要注意的是对于同一个堆的所有操作所用的比较函数含义都必须一致

如果传入 std::less则是大根堆

如果传入 std::greater则是小根堆

如果传入

inline bool cmp(const int &a, const int &b) {
    return a < b;
}

则是大根堆

如果传入

inline bool cmp(const int &a, const int &b) {
    return a > b;
}

则是小根堆

push_heap()pop_heap()的演示
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>


const int MAXN  = 100007;
int data[MAXN], tmp[MAXN];


int main() {
    int n, tot = 0;
    std::cin >> n;
    for (int i = 1; i <= n; ++i) {
        int opt, x;
        std::cin >> opt;
        if (opt == 1) {
            std::cin >> x;
            data[++tot] = x;
            std::push_heap(data + 1, data + 1 + tot);
        }
        else {
            if (tot > 0) {
                std::pop_heap(data + 1, data + 1 + tot);
                --tot;
            }
        }
        
        int t = tot;
        memcpy(tmp, data, sizeof(int) * (tot + 1));
        while (t) {
            std::cout << tmp[1] << " ";
            std::pop_heap(tmp + 1, tmp + 1 + t);
            --t;
        }
        std::cout << std::endl;
    }
    return 0;
}
make_heap()的演示
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>


const int MAXN  = 100007;
int data[MAXN], tmp[MAXN];


inline bool cmp(const int &a, const int &b) {
    return a < b;
}


int main() {
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; ++i) {
        std::cin >> data[i];
    }
    std::random_shuffle(data + 1, data + 1 + n);
    

    std::make_heap(data + 1, data + 1 + n);
    memcpy(tmp, data, sizeof(int) * (n + 1));
    int t = n;
    while (t) {
        std::cout << tmp[1] << " ";
        std::pop_heap(tmp + 1, tmp + 1 + t);
        --t;
    }
    std::cout << std::endl;
        
    
    std::random_shuffle(data + 1, data + 1 + n);
    
    
    std::make_heap(data + 1, data + 1 + n, std::less<int>());
    memcpy(tmp, data, sizeof(int) * (n + 1));
    t = n;
    while (t) {
        std::cout << tmp[1] << " ";
        std::pop_heap(tmp + 1, tmp + 1 + t, std::less<int>());
        --t;
    }
    std::cout << std::endl;
    
    
    std::random_shuffle(data + 1, data + 1 + n);
    
    
    std::make_heap(data + 1, data + 1 + n, std::greater<int>());
    memcpy(tmp, data, sizeof(int) * (n + 1));
    t = n;
    while (t) {
        std::cout << tmp[1] << " ";
        std::pop_heap(tmp + 1, tmp + 1 + t, std::greater<int>());
        --t;
    }
    std::cout << std::endl;
    
    
    std::random_shuffle(data + 1, data + 1 + n);
    
    
    std::make_heap(data + 1, data + 1 + n, cmp);
    memcpy(tmp, data, sizeof(int) * (n + 1));
    t = n;
    while (t) {
        std::cout << tmp[1] << " ";
        std::pop_heap(tmp + 1, tmp + 1 + t,  cmp);
        --t;
    }
    std::cout << std::endl;
    return 0;
}
sort_heap()的演示
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>


const int MAXN  = 100007;
int data[MAXN], tmp[MAXN];


int main() {
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; ++i) {
        std::cin >> data[i];
    }
    std::random_shuffle(data + 1, data + 1 + n);
    

    std::make_heap(data + 1, data + 1 + n);
    memcpy(tmp, data, sizeof(int) * (n + 1));
    int t = n;
    while (t) {
        std::cout << tmp[1] << " ";
        std::pop_heap(tmp + 1, tmp + 1 + t);
        --t;
    }
    std::cout << std::endl;
    
    std::random_shuffle(data + 1, data + 1 + n);
    std::make_heap(data + 1, data + 1 + n);
    std::sort_heap(data + 1, data + 1 + n);
    for (int i = 1; i <= n; ++i) {
        std::cout << data[i] << " ";
    }
    return 0;
}

使用构造堆函数需要注意的地方

1.一定要保证同一个堆的比较函数相同

2.构造出来的数组直接访问没有实际意义

3.sort_heap()使用前要先make_heap()

4.sort_heap()会破坏堆的性质


技巧

set启发式合并

typedef std::set<int> PII;
PII *merge(PII *a, PII *b) {
    if (a->size() > b->size()) {
        std::swap(a, b);
    }
    PII::iterator it;
    for (it = a->begin(); it != a->end(); ++it) {
        b->insert(*it);
    }
    a->clear();
    return b;
}
Last modification:October 25th, 2018 at 03:03 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment