std::set<int> で、ある値が何番目の数なのか知る方法

std::set<int> s;
s.insert(3);
s.insert(2);
s.insert(5);
s.insert(8);
s.insert(7);
s.insert(4);

setの中では二分木でソートされつつ格納されていると思うのですが、
例えばこの中で 5 は何番目に小さい値かを知るのに良い方法はないですか？

int n = s.find(5)-s.begin();
でできるかと思ったのですが、コンパイルが通りませんでした。

No.1 ベストアンサー 回答者： sha-girl 回答日時： 2007/01/09 12:45

二分木の仕組み上、ルートから見ていかないとわかりませんよね？

int cnt;
std::set<int>::iterator it;
for( it = s.begin() , cnt = 1 ; it != s.end() ; ++it , cnt++ ){
　if ( *it == 5 ){
　　std::cout << cnt << "番目" << std::endl;
　}　
}
とする必要があります。

>s.find(5)-s.begin();
これは無理です。
findもbeginもsetのiterator
が戻り値です。
vector等ではiteratorに
マイナス演算子が定義されている為以下のような記述が可能なのです。
std::vector<int> v;
int cnt = v.end()-v.begin();
setのiteratorにマイナス演算子は定義されていません。
(インクリメント++やデクリメント--は定義されています。)

この回答へのお礼

>二分木の仕組み上、ルートから見ていかないとわかりませんよね？
やっぱそうですか....
操作を何回も繰り返して行いたいので、これ意外の方法があれば、と思った
のですが・・・
そもそも set 使うことが良くないのかとも思ってきました.

お礼日時：2007/01/09 16:33

No.3 回答者： koko_u 回答日時： 2007/01/09 14:45

std::set の実装が二分木であろうと、公開されたインターフェース以外を仮定してコードを書いてはいけません。

どうしても std::set が使いたいなら
count_if( s.begin(), s.end(), bind2nd( less_equal<int>(), 5 ) )
とかかな？

この回答へのお礼

>std::set の実装が二分木であろうと、公開されたインターフェース以外を仮定してコードを書いてはいけません。

そうかもしれないです。
この操作を何回も行いたいので、できれば O(1) で知りたかったのですが。
そうすると set を使うのはあまり良くないのかも、とも思ってきました。

ありがとうございます。

お礼日時：2007/01/09 16:47

No.2 回答者： Tacosan 回答日時： 2007/01/09 13:37

distance(s.begin(), s.find(5)) かその逆でわかるかなぁ?

この回答へのお礼

こちらが簡潔ですね。ありがとうござます。

お礼日時：2007/01/09 16:43