Simple priority queue benchmark: std::priority_queue vs std::vector+std::lower_bound vs std::vector+std::find

priority_queue_benchmark.cpp

#include <benchmark/benchmark.h>

#include <algorithm>
#include <queue>
#include <random>
#include <string>
#include <vector>

template<typename T>
class Vector_priority_queue
{
public:
	using value_type = T;

	const T& top() const
	{
		return queue_.back();
	}

	void pop()
	{
		queue_.pop_back();
	}

protected:
	std::vector<T> queue_;
};

template<typename T>
class Vector_priority_queue1 : public Vector_priority_queue<T>
{
public:
	void push(const T& value)
	{
		const auto pos = std::lower_bound(this->queue_.begin(), this->queue_.end(), value);
		this->queue_.insert(pos, value);
	}
};

template<typename T>
class Vector_priority_queue2 : public Vector_priority_queue<T>
{
public:
	void push(const T& value)
	{
		const auto pos = std::find_if(
			this->queue_.begin(), this->queue_.end(), [value](auto v) { return v >= value; });
		this->queue_.insert(pos, value);
	}
};

template<typename Priority_queue>
void func(benchmark::State& state)
{
	using T = typename Priority_queue::value_type;

	std::mt19937 gen;
	std::uniform_int_distribution<T> dist;
	const std::size_t n = state.range(0);

	Priority_queue pq;
	for (auto _ : state)
	{
		for (std::size_t i = 0; i < n; ++i)
			pq.push(dist(gen));

		for (std::size_t i = 0; i < n; ++i)
		{
			const auto top = pq.top();
			benchmark::DoNotOptimize(top);
			pq.pop();
		}
	}

	state.SetItemsProcessed(state.iterations() * n);
	state.SetLabel(std::to_string(n * sizeof(T)));
}

BENCHMARK_TEMPLATE(func, std::priority_queue<int>)->RangeMultiplier(2)->Range(1L << 6, 1L << 19);
BENCHMARK_TEMPLATE(func, Vector_priority_queue1<int>)->RangeMultiplier(2)->Range(1L << 6, 1L << 19);
BENCHMARK_TEMPLATE(func, Vector_priority_queue2<int>)->RangeMultiplier(2)->Range(1L << 6, 1L << 19);

BENCHMARK_MAIN();