- 506 名前：デフォルトの名無しさん [2021/11/28(日) 21:47:47.53 ID:tN4i8A7m.net]
- >>494
>Rust で insert, remove 操作を O(1) で実装可能かどうかが論点ですよね？
そうじゃない。
Rustでも、insert, remove 自体は、標準実装でも O(1)で行える。
ところが、アクセスが、標準実装では、借用規則のために複数の
読み書きポインタを永続的に保持することが出来ないので、ノードの位置を
先頭からの通し番号で覚えておいて、アクセスするたびに毎回先頭から
辿る必要があるため、O(N)かかる。
特殊な独自実装をすると、アクセスがオーダー的にはO(1)で出来るが、
特殊実装な故に、>>493 の後半のようになってしまい、
20〜50クロック位かかる。
