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

Question

Предположим, что у меня есть вектор чего-то:

std::vector<Foo> v;

Этот вектор отсортирован, поэтому равные элементы расположены рядом друг с другом.

Каков наилучший способ получить все пары итераторов, представляющие диапазоны с равными элементами (с использованием стандартной библиотеки)?

while (v-is-not-processed) {
    iterator b = <begin-of-next-range-of-equal-elements>;
    iterator e = <end-of-next-range-of-equal-elements>;

    for (iterator i=b; i!=e; ++i) {
        // Do something with i
    }
}

Я хотел бы знать, как получить значения b и e в коде выше.

Так, например, если v содержит эти числа:

 index 0 1 2 3 4 5 6 7 8 9
 value 2 2 2 4 6 6 7 7 7 8

Тогда я бы хотел, чтобы b и e указывали на элементы в цикле:

 iteration  b  e
 1st        0  3
 2nd        3  4
 3rd        4  6
 4th        6  9
 5th        9 10

Есть ли элегантный способ решить эту проблему с помощью стандартной библиотеки?

Answer 1

Это в основном диапазон v3 group_by: group_by(v, std::equal_to{}).Его нет в стандартной библиотеке C ++ 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.
    }
});

Answer 2

Вы можете использовать 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
}

Answer 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 получает first и вторых итераторов (то есть b и e) с помощью std::lower_bound и std::upper_bound, что делает этот подход немного неэффективно .Поскольку итератор first может быть легко доступен для случая OP, вызывая std::upper_bound для second только для итератора (как показано в ответе @ NathanOliver ).}

Answer 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, если хотите.

Answer 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, неэто?

Answer 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
    }
}