beginner_intermediate

Iterator com predicado, o que é isso?

O iterator é um objeto que aponta ou indica um elemento em uma extensão de elementos, tais como containers da STL (por exemplo: std::vector) ou um array.

A Standard Template Library (STL) possui uma boa variedade de containers ou coleções que podem armazenar elementos, onde uma das operações naturais sobre estes containers são as iterações – assim é possível percorrer ou visitar cada elemento presente. Certa vez, li uma definição do relacionamento entre os principais recursos da STL (iterators, algorithms e containers) que era algo do tipo: algorithms atuam em containers através de iterators. Esta é uma definição simplificada e válida do que chamamos de “STL-way”. Se tentar copiar elementos de um std::vector para outro std::vector, provavelmente utilizará um std::copy e passará um par de iterators (begin e end) para indicar a extensão a ser copiada, além de utilizar um outro iterator para indicar o destino:

A idéia básica do iterator vêm dos ponteiros, afinal um ponteiro é um tipo de iterator rústico, onde as operações triviais são incremento (ir para o próximo elemento quando o incremento positivo, operator++), dereferencia (operator*) e outras operações aritméticas. O iterator no C++ amplia a capacidade dos ponteiros de memória introduzindo certas categorias que determinam o que é permitido, em termos de operações, se fazer com aquele iterator – neste post iremos apresentar um iterator do tipo Forward, em futuros posts apresentaremos cada uma das categorias existentes, ok?

Quando utilizamos um par de iterators de um container qualquer (normalmente begin e end, mas também pode ser algo parcial: begin() e begin() + 4 dependendo do tipo), isto significa que a intenção é de iterar os elementos deste container um a um, até chegarmos ao final. Isto é feito declarativamente da seguinte forma, utilizando o algoritmo std::replace como exemplo:

Ou em sua forma imperativa:

No entanto, mesmo visitando cada elemento do intervalo aberto (note que usando uma notação matemática, o intervalo indicado pelo par é [begin, end) é fechado no inicio e aberto no final – por isso também que o end é conhecido como past-end, ou seja, o próximo elemento do último elemento desejado), não queremos visitar ou alterar todos eles, simplesmente desejamos descartar ou filtrar alguns deles. Para isto, existem algoritmos, normalmente sufixados com _if que possuem um predicado para filtragem, por exemplo, std::copy_if para copiar apenas elementos com uma certa caracteristica:

Um predicado, nada mais é que uma função (functor, lambda, …) que tem como retorno um valor booleano (true ou false, tipo bool no C++). Se estivermos atento, notaremos que para cada algoritmo que desejamos filtrar alguma coisa, deveremos ter uma versão com predicado, correto? Logo duplicamos um algoritmo que atua sobre este par de iterators para introduzirmos uma versão com predicado. Correto, C++ optou por isto por questões de eficiência, mas e se tivéssemos iterators com predicado? Ou seja, já que iterator é um tipo de abstração de ponteiros, porque não introduzirmos uma certa funcionalidade no iterator permitindo que ele “ignore” ou “aceite” certos elementos, tudo isso de uma maneira opaca para o algoritmo? Introduzimos aqui o iterator_with_predicate ou o “iterador com predicado”, cujo o beneficio é utilizar algoritmos que suportem iterator e não possuem uma versão com predicado:

Por exemplo, na STL não existe um std::transform_if, mas é possível adaptar este comportamento com iterator_with_predicate:

A idéia principal do iterator_with_predicate é oferecer uma visão do container que ele atua, uma visão limitada apenas a filtragem de dados, pois a idéia de view pode ser mais ampla do que a apresentada aqui.

Em termos de eficiência, conforme no assembly x64 gerado a partir do Visual C++ 14.0 (2015) em Release, a introdução desta abstração (iterator_with_predicate) não parece causar grande degradação de desempenho se comparada com uma versão _if de um algoritmo da STL (46 instruções geradas inline contra 30 necessárias para o std::copy_if), portanto pode ser uma conveniência interessante para algoritmos que possuem iterators e não possuem predicados.

Gerados a partir deste exemplo:

Abaixo, a implementanção em C++ moderno do iterator_with_predicate em termos de um ForwardIterator:

Fontes:
https://github.com/SimplyCpp/examples/blob/master/forward_iterator_with_predicate_program.cpp
https://github.com/SimplyCpp/examples/blob/master/forward_iterator_with_predicate.hpp

4 Comments

  1. Me pareceu um pouco estranha essa parte:
    “ys.resize(xs.size() / 2);”

    E se os elementos ímpares não fossem exatamente metade dos elementos contidos no vector?
    Há alguma forma de fazê-lo sem especificar o tamanho do vetor de saída?

  2. Olá Kauê,

    Fora de contexto parece ser estranho mesmo. Mas, veja que ys é usado para armazenar metade dos valores contidos no outro vector (xs) que possui tamanho par – coisa que já sabemos de antemão. Como o propósito do exemplo não é a melhor prática do resize, o foco não é dado a ele – quem sabe num outro post podemos falar disto – afinal seria necessário falar também do reserve e sobre amortização.

    Sabemos que o vector é uma estrutura dinâmica, ao aplicarmos o algoritmo copy, se quisermos evitar problemas ao indicar um container com menor número de elementos pré-alocados, podemos usá-lo juntamente com o back_inserter. Assim, teríamos algo do tipo ‘std::copy(xs.begin(), xs.end(), std::back_inserter(ys))’. Neste caso não usaríamos o resize (como no exemplo), mas o reserve como “hint” para reajustar a capacidade de realocação automática do container.

Leave a Reply

Your email address will not be published. Required fields are marked *