Как перебрать одинаковые значения со стандартной библиотекой?

Ответ 1

Это в основном Range v3 group_by: group_by(v, std::equal_to{}). Он не существует в стандартной библиотеке С++ 17, но мы можем написать собственный грубый эквивалент:

template <typename FwdIter, typename BinaryPred, typename ForEach>
void for_each_equal_range(FwdIter first, FwdIter last, BinaryPred is_equal, ForEach f) {
    while (first != last) {
        auto next_unequal = std::find_if_not(std::next(first), last,
            [&] (auto const& element) { return is_equal(*first, element); });

        f(first, next_unequal);
        first = next_unequal;
    }
}

Использование:

for_each_equal_range(v.begin(), v.end(), std::equal_to{}, [&] (auto first, auto last) {
    for (; first != last; ++first) {
        // Do something with each element.
    }
});

Ответ 2

Вы можете использовать std::upper_bound чтобы получить итератор к следующему значению. Поскольку std::upper_bound возвращает итератор для первого элемента, который больше указанного значения, если вы std::upper_bound значение текущего элемента, он даст вам итератор, который будет на один конец больше текущего значения. Это даст вам петлю, как

iterator it = v.begin();
while (it != v.end()) {
    iterator b = it;
    iterator e = std::upper_bound(it, v.end(), *it);

    for (iterator i=b; i!=e; ++i) {
        // do something with i
    }
    it = e; // need this so the loop starts on the next value
}

Ответ 3

Вы ищете std::equal_range.

Возвращает диапазон, содержащий все элементы, эквивалентные значению в диапазоне [first, last).

Что-то вроде следующего должно работать.

auto it = v.begin();
while (it != v.end())
{
    auto [b, e] = std::equal_range(it, v.end(), *it);
    for (; b != e; ++b) { /* do something in the range[b, e) */ }
    it = e;             // need for the beginning of next std::equal_range
}

^{Примечание: Несмотря на то, что это будет интуитивно понятный подход, std::equal_range получает свой первый и второй итераторы (то есть b и e) с помощью std::lower_bound и std::upper_bound, что делает этот подход немного неэффективным.Поскольку первый итератор может быть легко доступен для случая OP, вызывая std::upper_bound для второго итератора, что необходимо (как показано в ответе @NathanOliver).}

Ответ 4

Если ваши диапазоны равных значений короткие, то std::adjacent_find будет работать хорошо:

for (auto it = v.begin(); it != v.end();) {
    auto next = std::adjacent_find(it, v.end(), std::not_equal_to<Foo>());
    for(; it != next; ++it) {

    }
}

Вы также можете заменить лямбду на std::not_equal_to если хотите.

Ответ 5

Но даже если мы не используем e для чего-либо, эта формулировка удобна, ее сложнее допустить. Другой способ (для проверки изменения значений) является более утомительным (так как нам нужно обработать последний диапазон специально [...])

Зависит от того, как вы интерпретируете "обработку последнего диапазона специально":

auto begin = v.begin();
// we might need some initialization for whatever on *begin...
for(Iterator i = begin + 1; ; ++i)
{
    if(i == v.end() || *i != *begin)
    {
        // handle range single element of range [begin, ???);
        if(i == v.end())
            break;
        begin = i;
        // re-initialize next range
    }
}

Никакой специальной обработки для последнего диапазона - исключительно, возможно, нуждающийся в коде инициализации дважды...

Уплотненный-петля-подход:

auto begin = v.begin();
for(;;)
{
    // initialize first/next range using *begin
    for(Iterator i = begin + 1; ; ++i)
    {
        if(i == v.end() || *i != *begin)
        {
            // handle range single element of range [begin, ???);
            if(i == v.end())
                goto LOOP_EXIT;
            begin = i;
            break;
        }
    }
}
LOOP_EXIT:
// go on
// if nothing left to do in function, we might prefer returning over going to...

Более элегантно? Признаюсь, я сам сомневаюсь... Оба подхода избегают повторения в одном и том же диапазоне дважды (сначала для нахождения конца, затем для фактической итерации). И если мы сделаем нашу собственную библиотечную функцию из:

template <typename Iterator, typename RangeInitializer, typename ElementHandler>
void iterateOverEqualRanges
(
    Iterator begin, Iterator end,
    RangeInitializer ri, ElementHandler eh
)
{
    // the one of the two approaches you like better
    // or your own variation of...
}

мы могли бы тогда использовать это как:

std::vector<...> v;
iterateOverEqualRanges
(
    v.begin(), v.end(),
    [] (auto begin) { /* ... */ },
    [] (auto current) { /* ... */ }
);

Теперь, наконец, это похоже на std::for_each, не так ли?

Ответ 6

for(auto b=v.begin(), i=b, e=v.end(); i!=e; b=i) {
    // initialise the 'Do something' code for another range
    for(; i!=e && *i==*b; ++i) {
        // Do something with i
    }
}