並行linked listの話と、linked listの存在意義

くまぎ @kumagi

@SubaruG ロックしてから一貫性取るならスレッドごとにコピーを作る必要すら無くて万々歳ですね。スケーラビリティを除いて。

普通のC++使い、銀天すばる @SubaruG

shared_ptr のコストって結構バカにならないからにゃー。サイズもそうだしコピーコストもそう。参照外しは高速だけど。

普通のC++使い、銀天すばる @SubaruG

@kumagi まぁそうですよねー。あくまで「僕がやるなら」の話です。頭よくないので最低限のロックで済むならそうするな、と。

くまぎ @kumagi

@SubaruG 並行処理の世界でmapの代用となる予定のskip listや、クローズアドレス式のhash mapはリンクリストをベースにしているので、あんまり嫌っても居られないんですこれが。

普通のC++使い、銀天すばる @SubaruG

@kumagi そりゃそうでしょう。好きじゃない言いつつも、僕も普通に使ってますし。＞リンクリスト

くまぎ @kumagi

@SubaruG いわれてみたらstd::list<T>はまともに使ったことがないかも…！順序を保ちたい以外の理由で途中の位置に挿入したい場面が無くて！

普通のC++使い、銀天すばる @SubaruG

@kumagi リンクリストの用途としては Boost.Intrusive の方がいろいろと便利なので、最近は専らそっちですね僕は。

Fadis @fadis_

std::listは 途中で中止される可能性がある キューで使う。ただ削除対象を検索しなければならない場合はリスト構造だと線形探索になるからmulti_index使う

Fadis @fadis_

そうか、ここでBoost.PropertyMapが出てくるのか！こいつなら要素にアクセスする時にコンテナも渡すから安全にアクセス出来る状況かどうかのチェックなんて楽勝ぢゃん！

普通のC++使い、銀天すばる @SubaruG

std::list さんは ls.erase(iter++); 以外にメリットってあるんだろうか。

普通のC++使い、銀天すばる @SubaruG

まぁ ls.erase(iter++); は普通に便利なので、利点がそれだけでも十分に価値はあるんだけど、でも list っていう一番抽象的な名前にふさわしいコンテナとは言えない気がするんだよにゃ。

普通のC++使い、銀天すばる @SubaruG

あーあと splice もあるか。 list の利点。

普通のC++使い、銀天すばる @SubaruG

メモリ管理しなくていい線形リンクリストって点では、流石STLだけあって、なんだかんだで普通に便利だよにゃ。

SHOO @mono_shoo

@SubaruG insertとかも利点じゃない？

普通のC++使い、銀天すばる @SubaruG

@mono_shoo insert はぶっちゃけ deque でもいい気がしてます。

普通のC++使い、銀天すばる @SubaruG

@mono_shoo イテレータ無効化しないのは魅力的ですけど、もちろん。

SHOO @mono_shoo

@SubaruG dequeでinsertって効率よくできるんだ？

普通のC++使い、銀天すばる @SubaruG

個人的には constant_time_size じゃない std::list もあっていい（つまりコンテナサイズを保存しないので splice 操作がイテレータのみで完結する）

普通のC++使い、銀天すばる @SubaruG

@mono_shoo オーダは Ο(N) ですけど vector に比べたら倍で、メモリ確保コストとのトレードオフで考えたら要素数が大きくないうちは普通に勝ちますね。

普通のC++使い、銀天すばる @SubaruG

insert もイテレータだけ指定すればそれでおっけー。 RT @SubaruG: 個人的には constant_time_size じゃない std::list もあっていい（つまりコンテナサイズを保存しないので splice 操作がイテレータのみで完結する）

SHOO @mono_shoo

dequeってリングバッファつかってる印象があって、中間点にinsertで効率よく挿入できない気がするんだよなぁ。O(n)的な

普通のC++使い、銀天すばる @SubaruG

erase も。

SHOO @mono_shoo

対して、listはO(1)なのが魅力かなぁと。

普通のC++使い、銀天すばる @SubaruG

ま、アレだ。 boost::intrusive::list 使えばいいんだけどな。

SHOO @mono_shoo

というか、listって要素数が1万とか半端なくでかくなる可能性があって、かつ中間要素への操作が頻繁に行われるとかそういう用途で初めて有用になる代物でしょ？