compare関数は2つのキー値を比較する関数で、コレクションから繰り返し呼び出されます。この関数はキー値が等しいときは0、最初のキー引数が2つめより小さいときは-1、1つめが2つめより大きいときは+1を返します。キーとされたコレクションがソートされていないと、等しくないキーには、どちらが大きいかに関わらず-1と+1のいずれかが返されます。
あるキー値と他のキー値の比較が必要になるつど、関数は呼び出されることになります。典型的には、コレクションにメンバを追加、削除するたびに複数呼び出しが発生し、それは挿入や削除する正しいメンバが決まるまで続きます。