0

我有struct一个名字和号码：

struct S {
  string name;
  int number;
};

的对象S存储在向量中。向量基于 排序name。可能有超过 1 个项目具有相同的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，请使用 lambda：

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 回答