deque is ring-buffer?

りんご @aomoriringo

えーと、C++のstd::dequeは複数個の固定長配列で、リングバッファでdequeを実装する方法もあるけど別ですよ、ってことでいいのですかね

Akso de la Malbono @Cryolite

@kikairoya std::vector<std::array<T, PageSize> *> をリングバッファ化してしまえば良いじゃない．ぷぇ～．

若年寄(もう若くない) @kikairoya

@Cryolite vectorの代わりにリングバッファを使うってこと？それは元の論旨から大きく外れてるような [宮崎産を食べよう]

Akso de la Malbono @Cryolite

@kikairoya 「元の論旨」というのがどれを指しているかがイマイチ明確ではないのですが，少なくとも http://bit.ly/cdcvqO の「実装」のところに書いてある「動的配列による実装」の2つの bullet にある選択肢は両方とも C++ でも取れますよね？

SKS rep @repeatedly

気が付けばC(ry先生がやはりdequeについて噛み付いておられた．

Akso de la Malbono @Cryolite

@kikairoya kikairoya さんが主張されている実装は，前者の選択肢に要素の参照・ポインタ安定性を維持するべく memory indirection を導入しているわけなんですが，そうすると後者に memory indirection を導入したものもアリですよね？

SKS rep @repeatedly

C(ry先生が通り過ぎた後には何も残らないという…

若年寄(もう若くない) @kikairoya

@Cryolite 元々の話が、std::dequeはリングバッファだよ( http://ufcpp.net/study/stl/deque.html )、いやそれじゃstd::dequeにならないよ、ということで、 [宮崎産を食べよう]

若年寄(もう若くない) @kikairoya

@Cryolite 先頭・末尾挿入時の参照の有効性の問題でいくつかのメモリブロックに小分けになってないと要件を満たせないよね、というのが論旨 [宮崎産を食べよう]

Akso de la Malbono @Cryolite

@kikairoya あ，それは理解しています．そこで主張されている「std::deque はリングバッファだよ」というのに対して私は「リングバッファ以外の実装も取れる」と異議を申し立てます．ただ，「リングバッファでは実装できない」という主張には違和感を覚えます．

若年寄(もう若くない) @kikairoya

@Cryolite えーと、リングバッファ一つで実装が可能なんですか？リングバッファをいくつか使う、ということなら一応 https://twitter.com/kikairoya/status/18887910453 想定はしてあります [宮崎産を食べよう]

Akso de la Malbono @Cryolite

@kikairoya push_[front|back] に対して要素の参照・ポインタが安定であることの根源は，配列に値を直接乗せず，配列と寿命の異なる別の領域に値を確保して間接参照しているところですよね．この視点で見れば，リングバッファも同様なことが可能なのでは？

若年寄(もう若くない) @kikairoya

@Cryolite それはリングバッファ自体にはT *を格納しておくという理解でいいですか？ [宮崎産を食べよう]

Akso de la Malbono @Cryolite

@kikairoya 少なくとも， http://bit.ly/cdcvqO の「リングバッファに両端キューの内容を格納し、バッファが満杯になったときだけサイズを拡大する」という記述内容に memory indirection を導入した実装は規格上の困難があるように思えません．

Akso de la Malbono @Cryolite

http://twitter.com/kinaba/status/18894201292 http://twitter.com/kikairoya/status/18894178807 はい，そーです．実際この実装もありますし，こうすることで有益になる文脈もありますし．

若年寄(もう若くない) @kikairoya

@Cryolite 理解しました。 [宮崎産を食べよう]

若年寄(もう若くない) @kikairoya

@Cryolite ただ、 http://ufcpp.net/study/stl/deque.html に関しては、要素をリングバッファに直接載せているのでstd::dequeの解説としては不適切と思いますがどうでしょう [宮崎産を食べよう]

Akso de la Malbono @Cryolite

@kikairoya あ，要素を直接乗せる実装は言うまでもなくまずいです．

若年寄(もう若くない) @kikairoya

ん、というかあれかそれってvector<array<T, PageSize> *>のvectorをringbufferにして、PageSizeを1にしただけじゃん [宮崎産を食べよう]

若年寄(もう若くない) @kikairoya

というか逆だな、元がvectorって言ってるのがそもそも要件に合ってないんだ [宮崎産を食べよう]

若年寄(もう若くない) @kikairoya

しかし要件に合うコンテナを選択すると当然dequeしか残らないわけでぬるぽ [宮崎産を食べよう]

Akso de la Malbono @Cryolite

「ring_buffer<T> だと要素のポインタ・参照安定性が満たせない => ringu_buffer<T *> で間接参照を導入 => allocation の効率化のために chunk 化」という考え方を暗黙に仮定しているからダメダメな説明になっているのかorz

若年寄(もう若くない) @kikairoya

@Cryolite あ、そもそもの発祥がそっちなんですか…vectorの伸長の最大時間を削るためにchunk化したのかとばかり^q^ [宮崎産を食べよう]

若年寄(もう若くない) @kikairoya

何見てもvectorに似てるっていうからvectorの変形から進化したのかと思ってた [宮崎産を食べよう]

若年寄(もう若くない) @kikairoya

@Cryolite C++のstd::dequeをring_buffer<T *>で実装している実例はどこかで見られますか？ [宮崎産を食べよう]