C/C++ 拡張は Python の機能のひとつなので当然 C++ は Python

この記事は何

この間の記事のすごくはやい set を真面目に使いやすくした

真面目ではない使い方説明

これを見ると大体わかる

colab.research.google.com

(20/9/14追記) C 側でクラスも作ってちょっと速くなったけど絶対バグあるだろバージョン

colab.research.google.com

(21/09/05追記) 最新版はこのあたりを見て snippet/wrap_cpp_set.py at master · Lgeu/snippet · GitHub

割と真面目な使い方説明

↑のひとつめのセルの中身をコピペすれば、普通に Python のクラスとして使えるようになる

長過ぎると思ったときは、下の方のセルに圧縮する方法を書いたのでそれを使うと良いかもしれない

CppSet オブジェクトひとつにつき C++ 側では set オブジェクトひとつとイテレータをひとつ保持する
イテレータは基本的に最後に操作を行った位置を指し、これによって一部の操作を高速に行えることがある

g++ 拡張で高速になるメソッドを使わない場合、C++ のコードの 3 行目くらいのコメントアウトを外すと定数倍高速になる

以下各メソッドの説明（計算量の説明で、 $n$ は要素数とする）

CppSet (コンストラクタ)

引数無しで呼ぶと、空の CppSet オブジェクトを作る
リストまたはタプルを引数に入れると、その要素が入った CppSet オブジェクトを作る
計算量は
- リストがソート済みの場合は $\mathcal{O}(n)$
イテレータは最小の要素を指す

add

要素を追加して True を返す
ただし、既に同じ要素が入っていた場合、要素を追加せず False を返す
計算量は $\mathcal{O}(\log n)$
イテレータは追加した要素（または既に入っていた要素）を指す

remove

指定した要素を削除して、削除した要素の次の要素を返す
- 最も大きい要素を削除した場合、None を返す
計算量は $\mathcal{O}(\log n)$
イテレータは返した要素を指す
- None を返した場合、最大の要素の次を指す
指定した要素が入っていなければ KeyError を出す

search_higher_equal

指定した要素と同じかそれより大きい要素を返す
- そのような要素がなければ None を返す
計算量は $\mathcal{O}(\log n)$
イテレータは返した要素を指す
- None を返した場合、最大の要素の次を指す

min

最小の要素を返す
イテレータは返した要素を指す
計算量は $\mathcal{O}(1)$
要素数が 0 の場合、 IndexError を出す

max

最大の要素を返す
イテレータは返した要素を指す
計算量は $\mathcal{O}(1)$
要素数が 0 の場合、 IndexError を出す

pop_min

最小の要素を削除し、その値を返す
イテレータは削除した要素の次の要素を指す
- すなわち、削除後の最小の要素を指す
計算量は $\mathcal{O}(1)$
要素数が 0 の場合、 IndexError を出す

pop_max

最大の要素を削除し、その値を返す
イテレータは削除した要素の次の要素を指す
- すなわち、削除後の最大の要素の次を指す
計算量は $\mathcal{O}(1)$
要素数が 0 の場合、 IndexError を出す

len

要素数を返す
計算量は $\mathcal{O}(1)$

イテレータをひとつ進めた後、イテレータの指す要素を返す
イテレータが最大の要素を指していた場合、イテレータをひとつ進め、 None を返す
イテレータが最大の要素の次を指していた場合、イテレータを動かさず、 None を返す
計算量は $\mathcal{O}(1)$

イテレータをひとつ戻した後、イテレータの指す要素を返す
イテレータが最小の要素を指していた場合、イテレータを動かさず、 None を返す
計算量は $\mathcal{O}(1)$

to_list

要素をリストにして返す
計算量は $\mathcal{O}(n)$

get

イテレータの指す要素を返す
イテレータが最大の要素の次を指していた場合、 None を返す
計算量は $\mathcal{O}(1)$

erase

イテレータの指す要素を削除し、その次の要素を返す
- そのような要素がなければ None を返す
イテレータは返した要素を指す
- None を返した場合、最大の要素の次を指す
計算量は $\mathcal{O}(1)$
イテレータが最大の要素の次を指していた場合、 KeyError を出す

getitem

k 番目の要素を返す
- 負の値もいける
計算量は $\mathcal{O}(\log n)$
イテレータは返した要素を指す
- g++ 環境でない場合、計算量は $\mathcal{O}(n)$
k 番目の要素が存在しない場合、 IndexError を出す

pop

k 番目の要素を削除し、その値を返す
- 負の値もいける
計算量は $\mathcal{O}(\log n)$
イテレータは返した要素の次の要素を指す
- g++ 環境でない場合、計算量は $\mathcal{O}(n)$
k 番目の要素が存在しない場合、 IndexError を出す

index

要は bisect_left
計算量は
- g++ 環境でない場合、計算量は $\mathcal{O}(n)$
イテレータは変化しない

copy

自身のコピーを返す
計算量は $\mathcal{O}(n)$
新しいオブジェクトのイテレータは最初の要素を指す

割と真面目な使用例

AtCoder Regular Contest 033 C - データ構造

k 番目の要素

atcoder.jp

圧縮版

atcoder.jp

CPSCO2019 Session1 E - Exclusive OR Queries

イテレータ操作で高速化、g++ 拡張を使わず定数倍高速化

atcoder.jp

割と真面目な注意点

実行する .py があるのと同じ階層に C++ のファイルと setup.py を作るので、同じ名前のファイルを置かないように気をつける

set は C++ だけど乗せてるものとか比較関数とかは Python のものなので速さに限度がある

PyPy では使えない

バグの検証がしきれないのでみんな使って教えてくれるとうれしい

(20/9/23追記) AtCoder 以外のオンラインジャッジで使えるか？

Codeforces

ルールで禁止されているので使ってはいけない

AOJ

利用規約で禁止されているので使ってはいけない

yukicoder

使えるっぽい

ただし、setup部分は↓のように書き換えないといけない

それと、どこかのテストケースにはコンパイル時間が乗るはず

import os
import sys
os.chdir("__pycache__")
with open("set_wrapper.cpp", "w") as f:
    f.write(code_cppset)
with open("setup.py", "w") as f:
    f.write(code_setup)
os.system(f"CC=g++7 {sys.executable} setup.py build_ext --inplace > /dev/null")
os.chdir("../")

from __pycache__.cppset import CppSet

使用例

yukicoder.me

（↑の使用例は pb_ds の tree の比較関数をいじって multiset として使うテクを使っている（具体的には 13 行目の最後を Py_LT から Py_LE に変えている）ので注意（実際のところ完全に multiset にはならなくて、lower_bound とかの以上・超過があべこべになったりする））

まとめ

C++ は Python なので当然 Python 何もわからない

菜

[競プロ] 割と真面目に Python から C++ の set を使えるようにしたのでみんな使ってみてほしい

この記事は何

真面目ではない使い方説明