settest.cxx

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
#include <set>
#include <random>
#include <chrono>

std::vector<int> unique_vec(int min, int max, std::size_t n, std::mt19937& gen) {
        std::vector<int> vec(n);
	std::uniform_int_distribution<int> dist{min, max};
	while(vec.size() < n) {
		const auto tmp = dist(gen);
		if(std::find(vec.begin(), vec.end(), tmp) == vec.end()) {
			vec.push_back(tmp);
		}
	}
	return vec;
}

std::vector<int> oversized_unique_vec(int min, int max, std::size_t n, std::mt19937& gen) {
        std::vector<int> vec(n * 2);
	std::uniform_int_distribution<int> dist{min, max};
        for (int i = 0; i < n * 2; i++) {
            vec.push_back(dist(gen));
	}
        std::unique(vec.begin(), vec.end());
        std::cerr << "# new size: " << vec.size() << " # ";
        vec.resize(n);
	return vec;
}

std::set<int> unique_set(int min, int max, std::size_t n, std::mt19937 gen) {
	std::set<int> set;
	std::uniform_int_distribution<int> dist{min, max};
	while(set.size() < n) {
		set.insert(dist(gen));
	}
	return set;
}


int main() {
	const auto seed = std::random_device{}();
	for(std::size_t n: {10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000}) {
		for(auto i = 0u; i < 5; ++i) { // five runs each
			std::cout << n << "  ";
			{
				std::mt19937 gen{seed};
				const auto start = std::chrono::steady_clock::now();
				unique_vec(0, 1000000, n, gen);
				const auto end = std::chrono::steady_clock::now();
				const auto dur = end - start;
				std::cout << dur.count() << "  ";
			}
			{
				std::mt19937 gen{seed};
				const auto start = std::chrono::steady_clock::now();
				unique_set(0, 1000000, n, gen);
				const auto end = std::chrono::steady_clock::now();
				const auto dur = end - start;
				// std::cout << dur.count() << ' ';
				std::cout << dur.count() << '\n';
			}
			// {
			// 	std::mt19937 gen{seed};
			// 	const auto start = std::chrono::steady_clock::now();
			// 	oversized_unique_vec(0, 1000000, n, gen);
			// 	const auto end = std::chrono::steady_clock::now();
			// 	const auto dur = end - start;
			// 	std::cout << dur.count() << '\n';
			// }
		}
	}
}