2009-11-09 11 views
5

STL :: multimapを持っており、equal_rangeで上下限を返します。この範囲内の要素の数をすべて調べ、1つずつ数えることなく見つけることはできますか?C++ STL :: multimapから範囲内の要素の数を調べる

#include <iostream> 
#include <map> 

using namespace std; 

int main() { 
    multimap<int,int> mm; 
    pair<multimap<int, int>::iterator,multimap<int, int>::iterator> ret; 
    multimap<int,int>::iterator retit; 

    for (int n=0; n<100; n++) { 
     mm.insert (make_pair(rand()%10,rand()%1000)); 
    } 

    ret = mm.equal_range(5); 

    int ct = 0; 
    for (retit=ret.first; retit!=ret.second; ++retit) { 
     cout << retit->second << endl; 
      ct++; 
    } 
    cout << ct << endl; 

    return 0; 
} 

答えて

18

イテレータ間の距離を見つけるには、std::distanceアルゴリズムを使用してください。

int ct1 = std::distance(ret.first, ret.second); 
+0

感謝を!これは私にどんなスピードも救いますか?これは私が上に示しているのと同じですか?私はこのページの一番下に表示しています:http://www.cplusplus.com/reference/std/iterator/distance/それは速いかもしれませんO(1)が、これが 'ランダムであるかどうかわかりませんアクセス反復子 'かどうか。 – Travis

+1

いいえ、時間を節約できません。ランダムアクセスイテレータ(ベクトルイテレータなど)では一定時間です。しかし、マップには双方向イテレータがあるため、線形時間の複雑さがあります。 – Naveen

+0

ここにお越しいただきありがとうございます。 – Travis

1

あなただけcountを使用し、与えられたキーを持つ要素の数をカウントしたい場合::のような迅速な応答を

int ct = mm.count(5); 
+1

確かに私もこれを使うことができましたが、それは自分自身を繰り返すのと同じスピードであるようです(このページの一番下を見てください):http://www.cplusplus.com/reference/stl/multimap/count/私は、これには無料のランチがあると思う。 – Travis

+2

これは、コードの書き方が少なく、繰り返しよりも読みやすくなっています。 さらに高速かもしれません。マルチマップはベクトルのマップのようなものとして実装できるので、count()は開始点を見つけ、その範囲を反復することなくカウントを調べます。もちろん、これは実装者の責任であり、まったく信頼できません。 –

関連する問題