平衡
SortedSet
SortedMultiset
BucketList
使用例
ソート済み列をいくつかのバケット (list) に分割して管理します。このとき、(バケットの個数) : (バケット内の個数)
ほとんどの操作が (要素数を
iterable から SortedSet を作ります。ソートされていれば
SortedSet の中身です。list の list になっていて、中には要素が昇順に並んでいます。各バケットには要素が存在することが保証されます。
要素を昇順に走査するイテレータです。走査の途中で要素の追加・削除をしてはいけません。
要素を降順に走査するイテレータです。走査の途中で要素の追加・削除をしてはいけません。
x が s に含まれていなければ x を追加し、True を返します。含まれている場合は False を返します。
償却
x が s に含まれていれば x を削除し、True を返します。含まれていない場合は False を返します。
償却
x より小さい / 以下 / より大きい / 以上 で 最小 / 最大 の要素を返します。存在しなければ None を返します。
下から i 番目 / 上から ~i 番目 の要素を返します。存在しない場合は IndexError を返します。
abs(i) が小さいと高速に動作します。
下から i 番目 / 上から ~i 番目 の要素を削除するとともに返します。存在しない場合は IndexError を返します。
abs(i) が小さいと高速に動作します。
x より小さい要素の数を返します。x が s に含まれている場合は list(s).index(x) に相当します。
x 以下の要素の数を返します。
集合として同一かどうかを判定します。
SortedSet の多重集合版です。同じ要素を複数入れることができます。SortedSet からの変更点は以下の通りです。
x が s に含まれているかどうかに関わらず x を追加します。償却
x が s に含まれていれば x を 1 個 削除し、True を返します。含まれていない場合は False を返します。
償却
(C++ の std::multiset::erase には x を全て削除してしまうという罠があります。)
s に含まれる x の個数を返します。
SortedMultiset のソートしないバージョンです。list と同様に扱えます。
スライスは実装していません。
コンセプトや中身の簡単な解説が書いてあります (昔は偏ったら rebuild していましたが、今は split しています)