Sorted Set / Map

SortedSet、SortedMultiSet、SortedMap、SortedMultiMapは、 比較関数が定める順序を保つ連想コンテナです。

import atcoder/extra/structure/sorted_set_map

初期化

var sortedSet = initSortedSet[int]()
var sortedMultiSet = initSortedMultiSet[int]()

var sortedMap = initSortedMap[int, string]()
var sortedMultiMap = initSortedMultiMap[int, string]()

すべてのコンテナは常に部分木サイズを保持します。 追加のmode指定なしで、比較順による順位アクセス、iteratorのindex、 iterator間のdistanceを利用できます。

過去のコードとのソース互換性のためcountable引数も受理されますが、 公開仕様上はその値によらず順序統計が常に利用できます。 新しいコードでは指定しません。

基本操作

var s = initSortedSet[int]()

s.insert(30)
s.insert(10)
s.insert(20)

doAssert 20 in s
doAssert s.len == 3

s.erase(20)
doAssert 20 notin s

Mapでは[]がkeyによるvalueアクセスです。

var m = initSortedMap[int, string]()

m[20] = "twenty"
m[10] = "ten"

doAssert m[10] == "ten"

比較順による順位アクセス

順位は0-basedです。container{index}は、比較順でindex番目を指す iteratorを返します。

var s = initSortedSet[int]()

s.insert(30)
s.insert(10)
s.insert(20)

let first = s{0}
let second = s{1}
let third = s{2}

doAssert *first == 10
doAssert *second == 20
doAssert *third == 30

明示的な既存APIとしてkth_element(index)も利用できます。

doAssert s.kth_element(1) == s{1}

前提条件は次です。

0 <= index < container.len

Mapでは[]と{}の意味が異なります。

var m = initSortedMap[int, string]()

m[30] = "thirty"
m[10] = "ten"
m[20] = "twenty"

doAssert m[20] == "twenty"  # key 20のvalue

let it = m{1}               # 比較順で1番目のpair
doAssert *it == (20, "twenty")

MultiSetとMultiMapでは、重複する要素もそれぞれ1個として順位を持ちます。

forによる反復

Set系は比較順に要素を返します。

var s = initSortedSet[int]()

s.insert(3)
s.insert(1)
s.insert(2)

for value in s:
  echo value

itemsを明示しても同じです。

for value in s.items:
  echo value

Map系はkeyとvalueを比較順に返します。

var m = initSortedMap[int, string]()

m[2] = "two"
m[1] = "one"

for key, value in m:
  echo key, ": ", value

for key, value in m.pairs:
  echo key, ": ", value

iteratorの直接操作

beginとend

var it = s.begin()

while it != s.end():
  echo *it
  it.inc

end()は終端iteratorです。end()をdereferenceしてはいけません。

find

let it = s.find(2)

if it != s.end():
  doAssert *it == 2

lower_boundとupper_bound

let first = s.lower_bound(2)
let last = s.upper_bound(2)

• lower_bound(value)は、value以上となる最初の位置を返します。
• upper_bound(value)は、valueより大きくなる最初の位置を返します。

比較の意味はコンテナの比較関数に従います。

incとdec

var it = s.begin()
it.inc

var last = s.end()
last.dec

• it.incは次の要素へ進みます。
• it.decは前の要素へ戻ります。

index

let it = s.find(2)

doAssert it.index == 1
doAssert s{it.index} == it

indexは比較順における0-based順位です。

distance

let first = s.lower_bound(1)
let last = s.upper_bound(2)

doAssert s.distance(first, last) == 2
doAssert distance(first, last) == 2

distance(first, last)は、iteratorの順位の差を返します。

計算量

互換性

countableを指定する古いconstructor呼び出しは引き続き受理されます。

この指定でも順序統計は利用できます。ただし新しいコードでは、 引数を省略した通常のconstructorを使用してください。

kth_elementと{index}は現在の公開APIです。 []／{}の割り当てや明示的な順位アクセス名については、 この文書更新では変更していません。