Я использую priority_queue с вектором в качестве базового контейнера. Однако я ожидаю, что размер кучи будет очень большим. Я знаю о проблемах с изменением размера динамической векторной емкости. Поэтому я ищу способы изначально выделить достаточное пространство для базового вектора в моем priority_queue. Есть ли какие-либо предложения для этого?C++ priority_queue базовый размер контейнера для контейнера
Благодаря
STDLIB контейнерные адаптеры обеспечивают "заднюю дверь", чтобы получить доступ к основной контейнер: контейнер представляет собой защищенный член c.
Поэтому вы можете наследовать от адаптера, чтобы получить доступ к контейнеру:
#include <queue>
#include <iostream>
template <class T>
class reservable_priority_queue: public std::priority_queue<T>
{
public:
typedef typename std::priority_queue<T>::size_type size_type;
reservable_priority_queue(size_type capacity = 0) { reserve(capacity); };
void reserve(size_type capacity) { this->c.reserve(capacity); }
size_type capacity() const { return this->c.capacity(); }
};
int main()
{
reservable_priority_queue<int> q;
q.reserve(10000);
std::cout << q.capacity() << '\n';
}
Если вы чувствуете себя плохо о наследовании от класса STDLIB, использовать закрытое наследование и сделать все методы priority_queue доступных с using деклараций ,
Использование reserve функции:
std::vector<Type>::reserve(size_t size)
Пример:
std::vector<int> vec;
vec.reserve(10000);
std::priority_queue<int> q (std::less<int>(), vec);
Я не думаю, что это решение. Стандарт требует только, чтобы внутренний контейнер инициализировался вторым аргументом этого конкретного конструктора. Это означает, что конструктор экземпляра 'std :: vector' будет называться' 'vec' 'как аргумент, и тогда все это сводится к тому, что требуется' std :: vector
Хм, кажется, ты прав. –
Дэвид прав в своем комментарии к ответу Алексея: не так много шансов, что векторная реализация выделит то, что зарезервировано на копии. Поэтому либо предоставляйте свой собственный контейнер, который это делает, либо наследует от priority_queue и предоставляет некоторым членам возможность играть с базовым контейнером.
Вы не можете напрямую обращаться к базовому контейнеру, чтобы изменить емкость. Однако вы можете изменить контейнер, который используется внутренне, на std::deque. Контейнер std::deque может быть немного медленнее (не в примечании с большим О), чем вектор, но его рост намного быстрее, так как ему не нужно перемещать все существующие элементы.
Я думаю, что в последнем предложении есть опечатка. s/std :: queue/std :: deque/no? В противном случае я согласен. Это решение делает использование приоритета более безопасным. Элементы в deque выделяются кусками. – log0
@Ugo: Верно, спасибо! –
+1 для того, чтобы не наследовать из контейнера STL. –
Как полагают Дэвид, использование std :: deque, вероятно, является хорошим решением. Колонки памяти достаточно малы, чтобы обычно оставлять большую часть вашей памяти, пока очередь растет. Однако это просто более безопасное решение, но не безопасное решение.
Если вы не слишком заботитесь об эффективности, вы можете использовать stlxxl, который представляет собой реализацию стандартной библиотеки шаблонов для сверхбольших наборов данных. Таким образом, выделяемая память будет вашим полным жестким диском (библиотека также поддерживает несколько жестких дисков или сетевых дисков).
+1 Я обычно был против наследования стандартного контейнера по теоретическим соображениям, но в этом случае техника во мне говорит мне, что это может быть лучшим решением. –
Мне не нравится это решение по двум причинам: 1/наследование от класса, у которого есть публичный не виртуальный деструктор, плохо себя чувствует, очень плохо, 2/этот бэкдор не упоминается ни на cplusplus.com, ни на http://www.sgi.com/tech/stl ... У меня плохое ощущение, что это специфичный для реализации и НЕ стандартный. –
@Matthiew M. Бэкдор в стандарте, так что это технически правильно. Я согласен с тем, что наследование из контейнера не является лучшим советом в целом ... –