読者です 読者をやめる 読者になる 読者になる

標準ライブラリに重複した型を取り除く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>...{};