Подготовиться к собеседованию
Меню
  • website icon
    •  
  • website icon
Задачи для подготовки к собеседованию

В каком из контейнеров поиск будет работать быстрее и почему?

C++ 
void generate_vector(std::vector<ssize_t>& vector, size_t size)
{
		for (size_t i = 0u; i < size; ++i) {
				vector.push_back(i);
		}
}

void generate_set(std::set<ssize_t>& set, size_t size)
{
		for (size_t i = 0u; i < size; ++i) {
				set.insert(i);
		}
}

int main(int argc, char** argv)
{
    using std::chrono::high_resolution_clock;
    using std::chrono::duration_cast;
    using std::chrono::duration;
    using std::chrono::nanoseconds;

		constexpr size_t SIZE = 10000u;
		std::cout << "SIZE: " << SIZE << std::endl;

		std::set<ssize_t> set;
		generate_set(set, SIZE);
		std::vector<ssize_t> vector;
		generate_vector(vector, SIZE);

		{
				std::cout << "Vector: ";
				auto t1 = high_resolution_clock::now();

				std::binary_search(begin(vector), end(vector), SIZE / 2u + 3); // O(log(N))

				auto t2 = high_resolution_clock::now();
				std::cout << duration_cast<nanoseconds>(t2 - t1).count() << " ns" << std::endl;
		}
		{
				std::cout << "Set: ";
				auto t1 = high_resolution_clock::now();

				set.find(SIZE / 2u + 3); // O(log(N))

				auto t2 = high_resolution_clock::now();
				std::cout << duration_cast<nanoseconds>(t2 - t1).count() << " ns" << std::endl;
		}
	
		return EXIT_SUCCESS;
}