クラス名・変数名に迷ったら書き込むスレ。Part9

リスト構造の名前で悩んでいます。

あらかじめ動的に配列を確保しておき、
・要素を追加するときは、空きを探して追加します。
・要素を削除するときは、フラグを立てるだけ。

特徴は、順列無視。要素の追加、削除が比較的高速にできるという
配列型リスト（ArrayListの変形）です。
（最大要素数以上に、追加した場合は、自動的にリストの拡大が行われます）

イメージ的には、こんな感じです。
□……空き
■……要素有り

■■■□□■■□□

追加：
→→→↓ここに突っ込む
■■■□□■■□□
↓
■■■■□■■□□

削除：
　↓ここを消したい
■■■□□■■□□
↓
■□■□□■■□□
フラグを立てるだけ

ObjectPoolとか、
ParkingList(車庫をイメージしている)とか考えましたが、
一般的な名前ってないですか？

> 順列無視
分かりにくいですね。
追加順番の無視といいますか。

っていうか、そのアルゴリズムのどこが高速なのかと小一時間w
それが高速なんて絶対にありえないと思う。

追加するときに逐一スキャンしなきゃダメじゃんそんなの

久々にわろた。

削除が非常に遅いデバイスなんじゃね？

OrderIgnoral

空きが無くなったらどうするんだろうな

>（最大要素数以上に、追加した場合は、自動的にリストの拡大が行われます）

RecycleBin

>>115
実際には、配列分オブジェクトをあらかじめ確保しておいて使うのです。
頻繁にオブジェクトを追加、削除する場合に、
メモリ確保、開放を一切行わずに行えるため、比較的高速なんです。

ちなみに、考えたらわかると思いますが、常に頭からスキャンはしませんｗ

ゲームなんかだとよく使われるんですよ・・・。

実際に、高速化どうかってのは、なんだったらベンチマーク出しますよ？

でもねえ・・・。
今時、ゲームとはいえ、小さなメモリ確保を1フレーム数百回、一秒間に数千回やったくらいだと
たいした差は出ないんですけどね('A`)

あー、やっぱりタスクか。
いまはもう、スタック使ったほうが早いよ。

タスク？って擬似タスクですか？まあ近いですけど

スタックですか？いまいちスタックで代用できるように思えないのですが・・・

スタックって、基本は、最後に入れたものを先に出すという構造と記憶しているのですが、
途中で破棄されたオブジェクトを削除する場合は、どうするんですか？
削除して、詰める、だと普通のArrayListなんかと同じだと思うのですが、
あえて、スタックを持ち出す意味はなんですか？
ちょっと、頭が悪いせいか想像力が働きません。

ごめんなさい。
なんか、突っかかったような言い方になってますけど、
現場の方っぽいので、いろいろ意見聞いてみたいんです。

ウザかったら、ゲーム製作技術板にでも行きますので言ってください。

>>113
segregated storage 使え。確保時のスキャンを不要にできる。
実際は memory pool みたいなクラスにラップして使うといい。

その前に、普通に new して本当に速度が問題になるか
確認したほうがいいが。

>>127
Pool Concepts
http://boost.cppll.jp/HEAD/libs/pool/doc/concepts.html

boostのこれですかね？

同じメモリ幅（例えば、同じ型のオブジェクト）の追加削除に利用できて、
Linked List(連結リスト)のメモリ配置をArrayList(配列リスト)でやった様な感じで、
両方のいいとこどりをしたようなデータ構造なんですね。
うまいことやれば、追加の順番も維持できそうですね（イテレータを使えば）。

俺が、勉強不足なのはわかるんですけど、
ところで、segregated storage とかの単語とか知識って、
こういうのってどこで仕入れてくるものなのか・・・。

そういや、こういうのを語るスレはどこが適切なんだろう・・・

>>128
boost のそれと同じなので参考にするといい。っていうか、 boost::pool 使えば？

自分の言葉で理解したいのは分かるが、 segregated storage 自体には
Linked List も ArrayList も関係ない。 segregated storage を使えば
「両方のいいとこどりをしたような」コンテナを作ることが出来るということ。
「追加の順番を維持」ってのもよく分からんな。

メモリ確保について、適当に google で調べていればすぐに見つかる。
数年前は英語も含めて検索して無いとほとんど無理だったけど、今なら
そのリンク先のような日本語の文書もあるんで日本語だけでもなんとか
たどり着けるんじゃないかな？

確かにスレ違いなんだけど、適切なスレも思い当たらない。
C/C++ に特有の話だろうから C/C++ のスレで適当に話せばいいかもしれない。

どっかいいスレがあれば誘導よろしく。

>>129
>>128は能力はあるんだろうけど、まだ駆け出しっぽいから今のム板のスレにはよさげなスレなさそうだ。
C++スレがいいんだろうがboostの話が出ると専門スレ行けって話になるのに、boost自体の位置づけに不案内っぽいから難しいね。
かといって初心者スレってわけでもなさげ（つか初心者スレがレベル低すぎるってのもあるが）

ゲーム前提な設計ということで、こちらでよろしいでしょうか・・・
こちらにも現役の方がいらっしゃるようですので、

ゲームにおけるデータ構造・クラス設計・パターン
http://pc10.2ch.net/test/read.cgi/gamedev/1155209226/

で、聞いている肝心の俺が、C++使いではないと言う罠・・・(笑）
Delphi使いはいつも肩身が・・・。

>>131
そこなら文句無いだろう。「データ構造」ってあるしな。
問題は板自体の人口が少な目ってことだが、まぁしょうがないだろう。