C++, count_if, and equals

Question

I have a struct with a name and number:

struct S {
  string name;
  int number;
};

Objects of S are stored in a vector. The vector is sorted based on name. There may be more than 1 item with the same name.

When iterating over the items in the vector, I'm trying to use count_if to detect duplicates:

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
}

In the above, I can't figure out what XXX should be. I tried to create a predicate, but its pretty useless since there's nothing to compare:

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

The documentation I'm finding leaves a lot to be desired.

I feel like I am missing something very obvious, but I don't see what it is. Could anyone point out my mistake?

Jeff

Answer 1

Since your items are sorted, you can do better than find_if. In this case, std::upper_bound should work nicely.

Since you're basing the order of your S on name it's probably easiest to start by overloading operator< to do that:

struct S { 
    string name;
    int number;

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

[By the way, you can use that when sorting, as in sort(v.begin(), v.end()); ]

To find how many times each item occurs, start from v.begin(), and use std::upper_bound to find the upper bound of items equal to the first, then update the beginning of the range you're looking at to the iterator upper_bound just returned, and repeat until you reach the end of the collection:

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);
}

This has at least the potential to be somewhat faster if you have quite a few duplicates -- or a lot faster if you really have a lot of duplicates (upper_bound is logarithmic, where find_if is linear).

Answer 2

Could write a functor to achieve this:

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"));

Or use lambda if you are with C++11:

int count = count_if(v.begin(), v.end(), 
                     [](const S& s){ return s.name == "noloader"; });