20

私は次のようなクラスを持っています：

typedef std::list<char*> PtrList;
class Foo
{
public:
   void DoStuff();
private:
   PtrList m_list;
   PtrList::iterator m_it;
};

この関数DoStuff()は基本的に、要素を追加m_listまたは消去し、その中の特別な要素へのイテレータを見つけて、に格納しm_itます。m_itの各値は、以降のすべての呼び出しで使用されることに注意してくださいDoStuff()。

だから問題は何ですか？プロファイリングが、からnew呼び出されたためにオペレーターが呼び出されすぎていることを 示していることを除いて、すべてが機能します。list::push_back()DoStuff()

パフォーマンスを向上させるためm_listに、の初期化でメモリを事前に割り当てたいとFoo思いstd::vectorます。問題は、これにより次のような新しい問題が発生することです。

  1. 効率が悪くinsert、erase要素があります。
  2. m_itベクトルが1つの呼び出しからDoStuff()次の呼び出しに変更されるとすぐに無効になります。編集： Alan Stokesは、この問題を解決するために、イテレータの代わりにインデックスを使用することを提案しました。

私の解決策：私が考えることができる最も簡単な解決策は、リンクリスト機能も備えたオブジェクトのプールを実装することです。このようにして、リンクリストを取得し、そのためのメモリを事前に割り当てることができます。

私は何かが足りないのですか、それとも本当に最も簡単な解決策ですか？「車輪の再発明」をしたくはありません。代わりに、標準ソリューションが存在する場合はそれを使用します。

任意の考え、回避策、または啓発的なコメントをいただければ幸いです。

4

5 に答える 5

9

間違った容器を使用していると思います。

高速プッシュバックが必要な場合は、リンクリストが必要であると自動的に想定しないでください。リンクリストは低速のコンテナであり、基本的に並べ替えに適しています。

より良いコンテナはstd::dequeです。dequeは、基本的に配列の配列です。それはメモリのブロックを割り当て、あなたが押し戻すとそれを占有し、それがなくなると別のブロックを割り当てます。これは、割り当てが非常にまれであり、std::vectorや。のように効率を上げるために事前にコンテナのサイズを知る必要がないことを意味しますreserver。

于 2012-05-20T14:57:33.510 に答える
4

spliceの関数を使用してstd::list、プールを実装できます。新しいメンバー変数を追加しますPtrList m_Pool。新しいオブジェクトを追加する必要があり、プールが空でない場合は、プールの最初の要素に値を割り当ててから、それをリストに接続します。要素を消去するには、リストからプールに要素を接続します。

ただし、要素の順序を気にしない場合は、aのdeque方がはるかに高速です。途中の要素を消去したい場合は、最後の要素を削除したい要素にコピーしてから、最後の要素を消去します。

于 2012-05-21T18:52:40.607 に答える
3

私のアドバイスはと同じです。重要なコードを書く前にに111111切り替えてみてください。deque

ただし、質問に直接答えるにstd::listは、カスタムアロケータを使用できます。少し面倒なので、ここではすべての詳細を説明するつもりはありませんが、その要点は、リストノードのメモリ割り当て戦略を表すクラスを作成することです。によって割り当てられるノードは、listよりも大きい実装定義の小さな量char*になりますが、すべて同じサイズになります。つまり、そのサイズ（オブジェクトのプールではなくメモリブロックのプール）に合わせて最適化されたアロケータを作成できます。また、アロケータ内の任意のスペースを必要なときに予約できる関数を追加できます。その後、リストはすばやく割り当て/解放できます。これにより、実際のlist機能を再実装する必要がなくなります。

（何らかの理由で）リスト機能を備えたオブジェクトのプールを実装する場合は、から始めることができますboost::intrusive。これは、空きブロックのリストを追跡するために、独自のアロケータを作成するときにも役立つ場合があります。

于 2012-05-20T16:21:54.110 に答える
3

リストとベクトルは、オブジェクトの管理方法がまったく異なります。

ベクターは、指定された容量の割り当てられたバッファーに要素を配置します。容量がなくなると、新しい割り当てが発生します。割り当て要素を1つずつリストし、それぞれを個別に割り当てられたスペースに入れます。

ベクトル要素は、何かが挿入/削除されるとシフトするため、ベクトルインデックスと要素アドレスは安定していません。リスト要素は、何かが挿入/削除されるときに再リンクされるため、リストイテレータと要素アドレスは安定しています。

ベクトルと同様に動作するリストを作成する方法は、デフォルトのアロケータ（呼び出されるたびにシステムから割り当てられる）を別のアロケータに置き換え、オブジェクトをより大きなチャンクに割り当て、呼び出すときにサブチャンクをリストにディスパッチすることです。それ。これは、標準ライブラリがデフォルトで提供するものではありません。

于 2012-05-20T15:09:04.083 に答える
1

を使用する可能性がありますlist::get_allocator().allocate()。Afaik、デフォルトの動作は、sの非連続性（listしたがって不足）のためにメモリを取得することですreserve()が、このメソッドを使用することによる大きな欠点はallocatorすぐには発生しません。プログラムにクリティカルでないセクションがある場合、開始時など、少なくともその時点でダメージを受けることを選択できます。

于 2012-05-20T14:42:22.543 に答える