Перебор уникальных элементов `std :: multiset`

Question

Перебор уникальных элементов `std :: multiset`

Все, что мне нужно, это знать, существует ли что-то и сколько раз оно существует. Я буду перебирать существующие вещи и спрашивать, сколько из этого существует.

Моя реализация пока использует multisetДелаю как следует:

std::multiset<thing> a;
auto previous = a.end();
for( auto each = a.begin(); each != a.end(); ++each ) {
if( previous == a.end() || *previous != *each ) {
a.count(*each);
}
previous = each;
}

У меня есть вектор things. Но они иногда повторяют значение, я хочу перебрать уникальный thingы и для каждого уникального сделать что-то. Это «что-то» должно знать, сколько времени это thing появляется на векторе.

Код, который я разместил выше, — это то, как я решаю свою проблему прямо сейчас, это не самый элегантный способ сделать то, что я хочу.

Я просто следую рекомендациям Stackoverflow: я сообщаю, в чем заключается моя проблема, и говорю свое (опробованное) решение.

Если предложение с вопросительным знаком действительно необходимо, то вы идете: есть ли способ перебрать уникальные элементы над multiset?

7

c++c++11 multiset

Решение

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

Других решений пока нет …

Источник

Accepted Answer

Три возможных подхода:

использование std::unique создать временную коллекцию уникальных значений. Это может сделать код немного более читабельным, но менее эффективным.
Продвиньте свой итератор, используя std::multiset::upper_bound а не приращения: for( auto each = a.begin(); each != a.end(); each=a.upper_bound(*each)) — таким образом, вам не нужно if проверьте инсайдерскую петлю, плюс она гарантированно будет логарифмический по размеру. Довольно круто (не знал, что до того, как я его посмотрел). Для следующего предложения, весь кредит идет в @MarkRansom: С помощью std::upper_bound от <algorithm>Вы можете указать диапазон, в котором искать верхнюю границу. В вашем случае у вас уже есть хороший кандидат на начало этого диапазона, поэтому этот метод, вероятно, будет более эффективным, в зависимости от реализации в вашей стандартной библиотеке.
Если для вас это реальная проблема с производительностью, а предыдущее решение все еще недостаточно, рассмотрите возможность перехода к map<thing, unsingned> или даже unordered_map<thing,unsigned> где unsigned просто отслеживает количество эквивалентных thingу вас есть. Это подразумевает переписывание кода вставки / удаления.

12