except test (habr)

#include <ctime>
#include <iostream>
#include <vector>
#include <unordered_set>
#include <set>
#include <cstdlib>
#include <algorithm>
#include <bitset>
#include <climits>

using namespace std;

int sort_second(vector<int> a, vector<int> b) {
    sort(b.begin(), b.end());
    int result = 0;
    for (const auto &i : a) {
        result += binary_search(b.begin(), b.end(), i);
    }
    return result;
}

int sort_both(vector<int> a, vector<int> b) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int result = 0;
    for (vector<int>::const_iterator ap = a.begin(), bp = b.begin(); ap != a.end() && bp != b.end(); ) {
        if (*ap > *bp) {
            ++bp;
        }
        else {
            if (*bp > *ap) {
                ++ap;
            }
            else {
                ++result;
                ++ap;
                ++bp;
            }
        }
    }
    return result;
}

int std_set(vector<int> a, vector<int> b) {
    set<int> s(b.begin(), b.end());
    int result = 0;
    for (const auto &i : a) {
        result += s.count(i);
    }
    return result;
}

int std_unordered_set(vector<int> a, vector<int> b) {
    unordered_set<int> s(b.begin(), b.end());
    int result = 0;
    for (const auto &i : a) {
        result += s.count(i);
    }
    return result;
}

int std_bitset(vector<int> a, vector<int> b) {
    bitset<INT_MAX> *bs = new bitset<INT_MAX>;
    for (const auto &i : b) {
        (*bs)[i] = true;
    }
    int result = 0;
    for (const auto &i : a) {
        result += !((*bs)[i]);
    }
    delete bs;
    return result;
}

const int ROUNDS = 5;

vector<double> test(const vector<int> &a, const vector<int> &b, const vector<int> &tests, int f(vector<int> a, vector<int> b)) {
    vector<double> result;
    result.reserve(tests.size());
    for (const auto &test : tests) {
        vector<int> _a(a.begin(), a.begin() + test), _b(b.begin(), b.begin() + test);
        clock_t time = clock();
        int r(0);
        for (int i = 0; i < ROUNDS; ++i) {
            r += f(_a, _b);
        }
        time = clock() - time;
        result.push_back(static_cast<double> (time) / CLOCKS_PER_SEC / ROUNDS);
        cerr << test << ' ' << r << ' ' << result.back() << '\n';
    }
    return result;
}

int main(void) {
    const int N = 10000000;
    vector<int> a(N), b(N);

    vector<int> tests;

    for (int i = 0; i < N; ++i) {
        a[i] = rand();
        b[i] = rand();
    }
    for (int i = 1; i < N; i *= 2) {
        tests.push_back(i);
    }

    vector<double> r;

    cout << "sort_second\n";
    r = test(a, b, tests, sort_second);
    for (auto i: r) {
        cout << i << ' ';
    }
    cout << '\n';

    cout << "sort_both\n";
    r = test(a, b, tests, sort_both);
    for (auto i: r) {
        cout << i << ' ';
    }
    cout << '\n';

    cout << "std_set\n";
    r = test(a, b, tests, std_set);
    for (auto i: r) {
        cout << i << ' ';
    }
    cout << '\n';

    cout << "std_unordered_set\n";
    r = test(a, b, tests, std_unordered_set);
    for (auto i: r) {
        cout << i << ' ';
    }
    cout << '\n';

    cout << "std_bitset\n";
    r = test(a, b, tests, std_bitset);
    for (auto i: r) {
        cout << i << ' ';
    }
    cout << '\n';

    return 0;
}