c++ - ¿Cómo itero valores iguales con la biblioteca estándar?

algorithm c++17

Question

Supongamos que tengo un vector de algo:

std::vector<Foo> v;

Este vector está ordenado, por lo que los elementos iguales están uno junto al otro.

¿Cuál es la mejor manera de obtener todos los pares de iteradores que representan rangos con elementos iguales (utilizando la biblioteca estándar)?

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

Me gustaría saber cómo obtener valores de b y e en el código anterior.

Entonces, por ejemplo, si v contiene estos números:

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

Entonces me gustaría que b y e apunten a los elementos en el bucle:

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

¿Hay una manera elegante de resolver esto con la biblioteca estándar?

Answer 1

Pero incluso si no usamos e para nada, esta formulación es conveniente, es más difícil cometer un error. La otra forma (para verificar los valores cambiantes) es más tediosa (ya que necesitamos manejar el último rango especialmente [...])

Depende de cómo interpretas ''manejando el último rango 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...

No hay un manejo especial para el último rango - solo, posiblemente necesitando el código de inicialización dos veces ...

Enfoque anidado:

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

¿Mas elegante? Admitido, yo mismo tengo dudas ... Ambos enfoques evitan la iteración en el mismo rango dos veces (primero para encontrar el final, luego la iteración real), sin embargo. Y si hacemos nuestra propia función de biblioteca desde:

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

entonces podríamos usarlo 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) {

    }
}

Ahora, finalmente, parece similar a, por ejemplo, std::for_each , ¿no es así?

Answer 2

Básicamente, este es el rango de v3 group_by : group_by(v, std::equal_to{}) . No existe en la biblioteca estándar de C ++ 17, pero podemos escribir nuestro propio equivalente aproximado:

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

Answer 3

Puede usar std::upper_bound para llevar el iterador al valor "siguiente". Dado que std::upper_bound devuelve un iterador al primer elemento mayor que el valor proporcionado, si proporciona el valor del elemento actual, le dará un iterador que será uno más allá del final del valor actual. Eso te daría un bucle 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
}

Answer 4

Si sus rangos de valores iguales son cortos, entonces std::adjacent_find funcionaría bien:

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

También puede sustituir un lambda por std::not_equal_to si lo desea.

Answer 5

Usted está buscando std::equal_range .

Devuelve un rango que contiene todos los elementos equivalentes al valor en el rango [primero, último) .

Algo como lo siguiente debería 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
}

^{Observación : aunque este será un enfoque intuitivo, std::equal_range obtiene su primer y segundo iteradores (es decir, std::upper_bound ) con la ayuda de std::lower_bound y std::upper_bound , lo que hace que este approche sea un poco ineficiente . Desde entonces, el primer iterador podría ser fácilmente accesible para el caso del OP, llamando a std::upper_bound para el segundo iterador solo neccesarry (como lo muestra la respuesta de @NathanOliver ).}