алгоритм — C ++, count_if и равно

Question

алгоритм — C ++, count_if и равно

у меня есть 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 == ???;
}

Документация, которую я нахожу оставляет желать лучшего.

Я чувствую, что упускаю что-то очень очевидное, но я не понимаю, что это такое. Кто-нибудь может указать на мою ошибку?

Джефф

0

algorithm c++class countif

Решение

Другие решения

Могли бы написать функтор для достижения этого:

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

5

Источник

Accepted Answer

Так как ваши предметы отсортированы, вы можете сделать лучше, чем 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 является линейным).

1