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

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

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

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

Следует отметить, что код в вопросе не является хорошим примером того, как это может быть полезно. С e ничего не делается, кроме ограничения внутреннего цикла, а внутренний цикл можно было бы точно так же ограничить, проверив новое значение в элементе i. Таким образом, любые усилия, затрачиваемые на поиск e, не имеют смысла (если только вычисление «значения», используемого для сортировки v, не настолько дорого, что бинарный поиск e будет дешевле, чем проверка каждого элемента по ходу дела).

Eric Postpischil 02.07.2019 23:09

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

geza 02.07.2019 23:22

@geza Для последнего диапазона не требуется специальной обработки.

Walter 10.07.2019 10:39
Стоит ли изучать PHP в 2026-2027 годах?
Стоит ли изучать PHP в 2026-2027 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
41
3
1 980
6
Перейти к ответу Данный вопрос помечен как решенный

Ответы 6

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

Единственная проблема в том, что std::upper_bound делает немного больше, потому что он должен найти элемент с помощью бинарного поиска. Но в моем случае в этом нет необходимости.

geza 02.07.2019 22:55

Это имеет смысл, если поддиапазоны одинаковых элементов велики. Если они малы, вы тратите усилия на бинарный поиск по всему диапазону, тогда как линейный поиск может найти следующий элемент быстрее (и с лучшей локальностью кеша).

Justin 02.07.2019 22:55

@geza Если вместо этого вы хотите выполнить линейный обход, вы можете заменить std::upper_bound(it, v.end(), *it); на std::find_if (it, v.end(), [=](auto e) { return *it != e; });. В зависимости от данных это определенно может быть быстрее.

NathanOliver 02.07.2019 22:59

+1, спасибо, но я принял решение Джастина, так как оно немного понятнее при использовании (я имею в виду, что у алгоритма есть имя, поэтому легче понять, что делает код - но, конечно, ваш вариант можно изменить и таким образом, ваше решение в основном такое же).

geza 03.07.2019 08:47
Ответ принят как подходящий

Это в основном group_by Range v3: 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.
    }
});

Если вы знаете, что эти поддиапазоны равных элементов велики, вы можете извлечь пользу из своего рода бинарного поиска.

Justin 02.07.2019 22:52

Мне нравится это решение больше всего, так как его использование является самым понятным.

geza 03.07.2019 08:44

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

Returns a range containing all elements equivalent to value in the 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
}

Remark: Even though this will be an intuitive approach, the std::equal_range obtains its first and second iterators(i.e b and e) with the help of std::lower_bound and std::upper_bound, which makes this approche slightly inefficient. Since, the first iterator could be easily accessible for the OP's case, calling std::upper_bound for second iterator only neccesarry(as shown by @NathanOliver 's answer).

Это требует дополнительной работы, чтобы найти нижнюю границу диапазона, когда мы знаем, что это просто it, но в этот момент мы будем такими же, как ответ Натана Оливера (std::upper_bound вместо std::equal_range).

Justin 02.07.2019 23:09

@Джастин Согласен. Возможно небольшое преимущество: меньше печатать из-за возможности структурированного связывания.

JeJo 02.07.2019 23:12

+1, но я принял решение Джастина, так как, хотя это самая короткая версия (и ее легко понять без добавления имени), есть небольшая проблема с ненужной работой, выполненной std::equal_range.

geza 03.07.2019 08:48

But even if we don't use e for anything, this formulation is convenient, it's harder to make an error. The other way (to check for changing values) is more tedious (as we need to handle the last range specially [...])

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

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) { /* ... */ }
);

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

Спасибо за решение, мне нравится, что оно не требует двойной итерации элементов. Под «специальной обработкой последнего диапазона» я имел в виду, что нам нужно как-то его проверить. Даже сделав i == v.end() дважды.

geza 03.07.2019 08:52

Если ваши диапазоны одинаковых значений короткие, то 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, если хотите.

Хороший трюк с использованием std::adjacent_find, чтобы найти границу!

geza 03.07.2019 08:49
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
    }
}

Другие вопросы по теме