utilizadas - transform std c++




Como faço para iterar valores iguais com a biblioteca padrão? (4)

Mas mesmo que não usemos e para nada, essa formulação é conveniente, é mais difícil cometer um erro. A outra maneira (para verificar a mudança de valores) é mais entediante (como precisamos lidar com o último intervalo especialmente [...])

Depende de como você interpreta "lidar com o último intervalo especialmente" :

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...

Nenhum tratamento especial para o último intervalo - somente, possivelmente precisando do código de inicialização duas vezes ...

Abordagem de loop aninhado:

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

Mais elegante? Admitido, estou em dúvida ... Ambas as abordagens evitam repetir o mesmo intervalo duas vezes (primeiro para encontrar o fim, depois a iteração atual). E se fizermos a nossa própria biblioteca a partir de:

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

poderíamos então usá-lo como:

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) {

    }
}

Agora, finalmente, parece semelhante a, por exemplo, std::for_each , não é?

Suponha que eu tenha um vetor de alguma coisa:

std::vector<Foo> v;

Esse vetor é classificado, então os elementos iguais estão próximos uns dos outros.

Qual é a melhor maneira de obter todos os pares de iteradores representando intervalos com elementos iguais (usando a biblioteca padrão)?

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

Eu gostaria de saber como obter valores de b e e no código acima.

Então, por exemplo, se v contiver esses números:

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

Então eu gostaria de ter b e aponte para elementos no loop:

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

Existe uma maneira elegante de resolver isso com a biblioteca padrão?


Este é basicamente o group_by do group_by v3: group_by(v, std::equal_to{}) . Não existe na biblioteca padrão do C ++ 17, mas podemos escrever nosso próprio equivalente em bruto:

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

Uso:

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

Você está procurando por std::equal_range .

Retorna um intervalo contendo todos os elementos equivalentes ao valor no intervalo [first, last] .

Algo como o seguinte deve funcionar.

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

Observação : Mesmo que essa seja uma abordagem intuitiva, o std::equal_range obtém seus primeiro e segundo iteradores (ie b e e ) com a ajuda de std::lower_bound e std::upper_bound , o que torna essa relação um pouco ineficiente . Desde então, o primeiro iterador poderia ser facilmente acessível para o caso do OP, chamando std::upper_bound para o segundo iterador apenas neccesarry (como mostrado pela resposta de @NathanOliver ).


Você pode usar std::upper_bound para obter o iterador para o valor "next". Como std::upper_bound retorna um iterador para o primeiro elemento maior que o valor fornecido, se você fornecer o valor do elemento atual, ele fornecerá um iterador que será passado após o final do valor atual. Isso daria um loop como

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
}




iterator-range