Являются ли издержки на использование вектора с insert () в качестве приоритетной очереди относительно использования кучи? (C ++)

Question

В настоящее время я работаю над проектом, в котором реализовал вектор структурных указателей для использования в качестве очереди с приоритетами. Я использую цикл for, чтобы определить положение в векторе (если не меньше, чем задний ход), а затем использую insert(), чтобы поместить указатель структуры в положение в очереди. Я использую back() в качестве начала очереди, чтобы я мог поддерживать функциональность pop вектора.

Я просто пытался определить, добавит ли использование библиотеки кучи увеличение скорости, так как этот проект зависит от времени. Если хотите, можете предоставить код, размер кучи / вектора может сильно возрасти, поскольку это алгоритм поиска Ханойской системы A *.

Подумал, что я бы попросил о будущих знаниях, чтобы сэкономить мне некоторые отладочные перестановки точек останова, если бы кто-нибудь знал об этом.

Answer 1

Я сделал простой тест, сначала вставив N random int s в очередь с приоритетами, а затем вытолкнув N верхних элементов.

Как и ожидалось, отсортировал std::vector с победами линейного поискакогда размер очереди маленький, и std::priority_queue, который реализован как max-heap с O(log N) наихудшим временем вставки, побеждает, когда размер очереди большой.

Код эталона можно найти здесь .