2019-01-07-01-forward_listからsizeメソッドを削除 - project-enigma

2019-01-07-01-forward_listからsizeメソッドを削除

>> Site top >> weblog >> 月別アーカイブ >> 2019年01月のlog >> 2019-01-07-01-forward_listからsizeメソッドを削除

最終更新日付:2019/01/07 07:18:11


forward_listからsizeメソッドを削除

2019 年 01 月 07 日

今回は、どう考えても間違っていた自分の判断を修正する作業。forward_list からの size メソッドの削除だ。

元々、STL の forward_list には size メンバ関数はない。要素数をカウントするのに線形時間がかかるからだ。これは、要素数をキャッシュするデータメンバも保有しないことを意味している。splice 系メンバ関数との兼ね合いもあるのだろう。C++98 から存在していた list でも、当初は size メンバ関数は定数時間処理とは限らなかった。たしか C++11 で定数時間と定められたと記憶しているが、その結果 splice (の一部)は線形時間になった。

当時の自分がどういうつもりだったのか、イマイチ覚えていないのだけれど、cl-stl の forward_list でも size を使えるようにしてしまった。しかし、あれば使ってしまうものだし、その時線形コストだという意識は持たないものだ。だから削除した。ひょっとしたら、Common Lisp 使いにとっては cons list の長さを調べるのに線形時間を要するのは当たり前で、そこを間違えたりはしないよ、と言われてしまうかもしれない。しかし、だとしてもひとまずは STL に合わせる、ということで。

 

コメント

このページにコメントする

 

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

 

 


Copyright(C) 2005-2019 project-enigma.
Generated by CL-PREFAB.