0

私はstruct名前と番号を持つ を持っています:

struct S {
  string name;
  int number;
};

のオブジェクトはSベクトルに格納されます。ベクトルは に基づいてソートされnameます。同じ のアイテムが複数ある場合がありますname。

count_ifベクター内のアイテムを反復処理するとき、重複を検出するために使用しようとしています:

for(size_t i = 0; i < v.size(); ++i)
{
  const S& s = v[i];
  int count = count_if(v.begin(), v.end(), XXX);
  // do something with count
}

上記では、XXX がどうあるべきかわかりません。述語を作成しようとしましたが、比較するものがないため、かなり役に立ちません。

bool IsEqualName(const S& s) {
  return s.name == ???;
}

私が見つけたドキュメンテーションには、多くの要望が残されています。

非常に明白な何かが欠けているように感じますが、それが何であるかわかりません。誰かが私の間違いを指摘できますか？

ジェフ

4

2 に答える 2

5

これを達成するためにファンクターを書くことができます：

struct FindName
{
  FindName(const std::string& name) : name_(name) {}
  bool operator()(const S& s) { return s.name == name_; }

private:
  std::string name_;
};


int count = count_if(v.begin(), v.end(), FindName("noloader"));

または、C++11 を使用している場合はラムダを使用します。

int count = count_if(v.begin(), v.end(), 
                     [](const S& s){ return s.name == "noloader"; });
于 2013-03-14T03:02:12.757 に答える
1

アイテムはソートされているため、find_if よりも優れた結果が得られます。この場合、std::upper_boundうまく機能するはずです。

の順序に基づいているので、Sそれを行うためnameにオーバーロードすることから始めるのがおそらく最も簡単operator<です:

struct S { 
    string name;
    int number;

    bool operator<(S const &other) { return name < other.name; }
};

[ちなみに、のようにソートするときにそれを使用できますsort(v.begin(), v.end());]

各アイテムが何回発生するかを調べるには、v.begin() から開始しstd::upper_bound、最初のアイテムと等しいアイテムの上限を見つけるために使用し、次に、見ている範囲の開始を、upper_bound返された反復子に更新します。コレクションの最後に到達するまで繰り返します。

std::vector<size_t> counts;

auto pos = v.begin();

for (auto prev=v.begin(); prev != v.end(); prev = pos) {
    pos = std::upper_bound(prev, v.end(), *prev);
    counts.push_back(pos - prev);
}

これは、かなりの数の重複がある場合、少なくともいくらか高速になる可能性があります-または、実際に多くの重複がある場合は、はるかに高速になります(upper_boundは対数、find_ifは線形です)。

于 2013-03-14T05:06:20.273 に答える