• 締切済み

STLを使わずに可変長配列を再現する方法

STLのlistが(配列に比べると)想像以上に遅かったので C++で可変長配列を再現したいのですけども 配列の拡張が思った以上に遅く困っています。 毎回newではオーバーヘッドが発生しますので、 現在は配列を一定数確保しておき 足りなくなったら配列を拡張(再確保)しています。 現在の配列のアドレスを一旦退避させてdeleteし、 新たにnewで生成して復帰させるといった感じです。 ただしこれでは、配列の要素数が増えるほど遅くなり、 オブジェクトの参照ならまだしも実体の場合は 全てコピーしなければならないので、 場合によってはSTLのlistよりも遅くなってしまいます。 newで生成してるのでできればreallocは使わずに 再現したいのですが、どうにか方法は無いでしょうか? よろしくおねがいします。 //----------------------------------------------- struct Test {   int val;   Test( int _val ){ val=_val; } }; Test obj1( 1 ); Test obj2( 2 ); Test obj3( 3 ); // 元のデータに代入 Test **ptr = new Test*[2]; ptr[0] = &obj1; ptr[1] = &obj2; // 退避させる Test **tmp = new Test*[2]; for( int i=0; i<2; i++ ) tmp[i] = ptr[i]; // 拡張する delete [] ptr; ptr = new Test*[4]; // 復帰させる for( int i=0; i<2; i++ ) ptr[i] = tmp[i]; delete [] tmp; ptr[2] = &obj3; //----------------------------------------------- ※NULLチェックなどはここでは省いています。

みんなの回答

  • mtaka2
  • ベストアンサー率73% (867/1179)
回答No.1

「配列」が必要な場合は、STLの std::vector を使ってください。 std::list は「連結リスト」のクラスですので、「○番目のデータ」に直接アクセスするのは非常に遅くなります。 なお、std::vector でも、内部的には、質問者が書かれているようなメモリの再確保処理ルーチンが組み込まれていますが、 高速化のために、多めにメモリを確保することで、再確保処理の頻度を減らしています。 (たとえば、最初に要素数が10個でも、メモリは20個ぐらい確保しておくとか、さらに、21個目が必要になったら、今度は40個確保するとか。) また、質問者さんのコードは「退避」の部分が無駄です。 ---ここから Test **ptr = new Test*[2]; ptr[0] = &obj1; ptr[1] = &obj2; Test **newptr = new Test*[4]; for (int i = 0; i < 2; i++) newptr[i] = ptr[i]; delete [] ptr; ptr = newptr; ptr[2] = &obj3; ---ここまで という処理で十分。

cikora
質問者

お礼

お返事ありがとうございます。 ソースの方は、たしかに退避は無駄ですね(苦笑) よくよく考えれば解ることですが newとdeleteをセットで使う概念に囚われていて 気づきませんでした・・・ vectorを使えばランダムアクセス等は早くアクセスできますが、 挿入と削除を繰り返す処理(イメージ的にはシューティングの弾みたいな)の場合は遅くなってしまうのが悩みどころです。 そのためにlistとvectorがあって使い分ける必要があるのでしょうけど、一長一短ですよね;; とりあえずですが回答者様の仰られるとおり、 20個生成して足りなくなったら40個・・・というvectorのような処理を色々と工夫してみようと思います。 ありがとうございました。

関連するQ&A