16

基礎となるコンテナとしてベクトルでpriority_queueを使用しています。ただし、ヒープのサイズは非常に大きくなると思います。動的ベクトル容量のサイズ変更に関する問題を認識しています。そのため、priority_queue の基礎となるベクターに十分なスペースを最初に割り当てる方法を探しています。これを達成するための提案はありますか？

ありがとう

4

5 に答える 5

26

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

于 2010-09-08T10:53:38.783 に答える
3

基になるコンテナーに直接アクセスして容量を変更することはできません。ただし、内部で使用されるコンテナをstd::deque. std::dequeコンテナーは、ベクトルよりも若干遅くなる可能性がありますが (Big-O 表記ではありません)、既存のすべての要素を再配置する必要がないため、コンテナーの成長ははるかに高速です。

于 2010-09-08T10:58:44.983 に答える
0

デビッドが示唆するように、 std::deque を使用することはおそらく良い解決策です。メモリ チャンクは十分に小さいため、通常、キューが増大している間、ほとんどのメモリを予約できます。ただし、これはより安全なソリューションであり、安全なソリューションではありません。

効率をあまり気にしない場合は、特大データ セット用の標準テンプレート ライブラリの実装であるstlxxlを使用できます。このようにして、割り当て可能なメモリはハード ドライブ全体になります (ライブラリは複数のハード ドライブまたはネットワーク ドライブもサポートします)。

于 2010-09-08T12:17:13.010 に答える
0

使用reserve機能:

std::vector<Type>::reserve(size_t size)

サンプル：

std::vector<int> vec;
vec.reserve(10000);
std::priority_queue<int> q (std::less<int>(), vec);
于 2010-09-08T09:46:19.267 に答える
0

デビッドは、アレクセイの答えに対する彼のコメントで正しいです。ベクトルの実装がコピーに予約されているものを割り当てる可能性はあまりありません。したがって、これを行う独自のコンテナーを提供するか、priority_queue から継承して、基礎となるコンテナーで遊ぶメンバーをいくつか提供します。

于 2010-09-08T10:56:31.793 に答える