2

私はpriority_queue<unsigned long,vector<unsigned long>,greater<unsigned long> >C++ で を使用しており、16MB のメモリ制限があります。私のプログラムは 10MB しか必要としませんが、8653464 バイトになるとすぐに容量を 2 倍にしようとし、bad_alloc.

現在の実装を使用してこれを停止する方法はありますか? [a から]priority_queueに切り替えた場合でも、log(n) 時間は保持できますか?dequevector

4

3 に答える 3

5

への切り替えdequeは非常に賢明なアプローチです。のように x2 ではなく、固定数だけ成長しvectorます。そして、複雑さは維持されるべきですO(log N)。

于 2012-12-24T19:47:09.110 に答える
1

vectorは よりも複雑でありdeque、dequeの成長ははるかに予測可能で制御可能です。神の緑の大地といくつかの青の大地 (または C 配列との互換性) で絶対に最速の反復を必要としない場合は、dequeすべての用途に優れたコンテナーです。

于 2012-12-24T19:50:25.447 に答える
1

もちろん。 priority_queueはコンテナ アダプタであり、デフォルトでは に基づいていvectorます。あなたの問題を解決する最も簡単な方法は、大きくなりすぎず、限界に近づいても2倍にならず、限界に達するだけのベクトルのサブクラスを作成することだと思います。通常のベクター クラスを使用することもできますが、代わりにカスタム アロケーターを使用することもできますが、おそらくより多くの作業が必要になります。

于 2012-12-24T19:44:03.550 に答える