標準ライブラリに重複した型を取り除くuniqueifyが入るかもしれないっていうからuniqueの実装について
本の虫: 2014-10-pre-Urbanaのレビュー: N4142-N4149
曰く重複した型を取り除くuniqueify が追加されるかもらしい
そこで実装の話
俺俺ライブラリOTMPよりunique
uniqueはタイプリストを受け取り重複した型を取り除き返す
unique_t<List<char,int,long,int>>;//List<char,int,long>
この処理は「二つのユニークなリストL Rを受け取り、RからLの中に含まれているものを除いたリストをLの結合させ返す」メタ関数unique_concatと2分割統治するfoldがあれば実装できる
template<class L,class R> unique_concat=concat<L, remove_if< R, rcarry<lift<is_in>,to_set<L>> >> fold<map<List,self<List>>,unique_concat>
unique_concatのイメージ
(char,int,long),(long,char,void)
(char,int,long),(void)
(char,int,long,void)
畳み込みのイメージ
(char,int,lomg,int,long,char,void)
こーして(map< List,self< List>>)
( (char),(int),(lomg),(int),(long),(char),(void))
foldで二分木にして処理して
[[[(char),(int)],[(long),(int)]],[(long),(char),(void)]]
unique_concatで畳み込んでいく
[[(char,int),(lomg,int)],[(long,char),(void)]]
[(char,int,long),(long,char,void)]
[(char,int,long,void)]
unique_concatについてはis_inで検索しやすいように集合に直しておくと良い(to_set< L>)
O(1)で要素を探すことができるのでO(n^2)だったunique_concatがO(N)になる
集合に実装については要素をすべてwrapして多重継承
検索時にはis_base_ofすればいいだろう
/*こんなイメージ。実際は同じ型があった時対策でもうちょっと色々ある*/ template<class...T> struct set:wrap<T>...{};