O padrão C ++ 20 aparecerá em breve, no qual, provavelmente, o conceito de
intervalos será adicionado, mas poucas pessoas sabem o que são e com o que comem. Não consegui encontrar fontes de língua russa acessíveis sobre esta fera, e é por isso que neste artigo gostaria de lhe contar mais sobre ela, com base em uma palestra de Arno Schödl
"De Iteradores a Intervalos: A Próxima Evolução do STL" da Conference Meeting C ++ 2015- do ano. Tentarei deixar este artigo o mais claro possível para aqueles que encontrarem esse conceito pela primeira vez e, ao mesmo tempo, falarei sobre todos os tipos de chips, como adaptadores de intervalo, para aqueles que já estão familiarizados com esse conceito e desejam saber mais.
Bibliotecas com intervalos
No momento da redação deste artigo, existem três bibliotecas principais que implementam intervalos:
A primeira biblioteca, de fato, é a progenitora desse conceito (o que não é surpreendente, porque não há nada na coleção de bibliotecas
Boost :)). A segunda é a biblioteca de Eric Niebler, que será descrita mais adiante. E, finalmente, a última biblioteca, como você pode imaginar, foi escrita pelo think-cell, que, podemos dizer, desenvolveu e melhorou o Boost.Range.
Por que intervalos é o nosso futuro?
Para aqueles que não estão familiarizados com o conceito de intervalo, definimos esse conceito não trivial como aquele que tem um começo e um fim (um
par de iteradores ).
Vamos agora considerar a seguinte tarefa: existe um vetor, é necessário remover todos os elementos repetidos dele. Sob o padrão atual, resolveríamos assim:
std::vector<T> vec=...; std::sort( vec.begin(), vec.end() ); vec.erase( std::unique( vec.begin(), vec.end() ), vec.end() );
Nesse caso, indicamos o nome do vetor em até
6 vezes! No entanto, usando o conceito de intervalos (combinando iteradores no início e no final do vetor em um objeto), podemos escrever muitas vezes mais facilmente especificando o vetor desejado apenas
uma vez :
tc::unique_inplace( tc::sort(vec) );
Quais dos intervalos estão atualmente dentro do padrão atual?
No padrão C ++ 11, um loop baseado em intervalo e acesso universal ao início / fim de contêineres foram adicionados e, no último padrão C ++ 17, nada de novo relacionado a intervalos foi adicionado.
for ( int& i : <range_expression> ) { ... }
std::begin/end(<range_expression>)
Intervalos futuros
Vamos agora nos debruçar sobre a biblioteca Range V3 mencionada anteriormente. Eric Nibler, seu criador, como seu projeto em casa, criou a
Especificação técnica da gama , modificando a biblioteca de
algoritmos para suportar intervalos. Parece algo como isto:
namespace ranges { template< typename Rng, typename What > decltype(auto) find( Rng && rng, What const& what ) { return std::find( ranges::begin(rng), ranges::end(rng), what ); } }
Em seu site, há uma prévia do que ele deseja padronizar, esse é o
Range V3 .
O que pode ser considerado?
Primeiro de tudo,
contêineres (vetor, string, lista etc.), porque eles têm um começo e um fim. É claro que os contêineres têm seus próprios elementos, ou seja, quando nos referimos a contêineres, então nos referimos a todos os seus elementos. Da mesma forma, ao copiar e declarar uma constante (cópia profunda e consistência). Em segundo lugar, as
visualizações também podem ser consideradas intervalos. As visualizações são apenas um par de iteradores apontando para o início e o fim, respectivamente. Aqui está a implementação mais simples:
template<typename It> struct iterator_range { It m_itBegin; It m_itEnd; It begin() const { return m_itBegin; } It end() const { return m_itEnd; } };
As visualizações, por sua vez, referem-se apenas aos elementos, portanto, a cópia e a consistência são preguiçosas (isso não afeta os elementos).
Adaptadores de intervalo
Os inventores de intervalos não pararam nisso, porque, caso contrário, esse conceito seria bastante inútil. Portanto, eles introduziram um conceito como adaptadores de alcance.
Transformar adaptador
Considere a seguinte tarefa: seja dado um vetor
int , no qual precisamos encontrar o primeiro elemento igual a 4:
std::vector<int> v; auto it = ranges::find(v, 4);
Agora vamos imaginar que o tipo do vetor não seja int, mas algum tipo de estrutura auto-escrita complexa, mas na qual existe um int e a tarefa ainda é a mesma:
struct A { int id; double data; }; std::vector<A> v={...}; auto it = ranges::find_if( v, [](A const& a) { return a.id == 4; } );
É claro que esses dois códigos são semelhantes na semântica, no entanto, diferem significativamente na sintaxe, porque no último caso, tivemos que escrever manualmente uma função que é executada no campo
int . Mas se você usar um adaptador de transformação (
adaptador de transformação ), tudo parecerá muito mais sucinto:
struct A { int id; double data; }; std::vector<A> v={...}; auto it = ranges::find( tc::transform(v, std::mem_fn(&A::id)), 4);
De fato, o adaptador de transformação "transforma" nossa estrutura criando uma classe de wrapper em torno do campo int. É claro que o ponteiro aponta para o campo
id , mas se queremos que ele aponte para toda a estrutura, precisamos adicionar no final de
.base () . Este comando encapsula o campo, pelo qual o ponteiro pode percorrer toda a estrutura:
auto it = ranges::find( tc::transform(v, std::mem_fn(&A::id)), 4).base();
Aqui está um exemplo de implementação de um adaptador de transformação (consiste em iteradores, cada um dos quais com seu próprio functor):
template<typename Base, typename Func> struct transform_range { struct iterator { private: Func m_func;
Adaptador de filtro
E se na última tarefa precisamos encontrar não o primeiro elemento desse tipo, mas "filtrar"
todo o campo de
ints pela presença de tais elementos? Nesse caso, usaríamos um adaptador de filtro:
tc::filter( v, [](A const& a) { return 4 == a.id; } );
Observe que o filtro é executado lentamente durante as iterações.
E aqui está sua implementação ingênua (algo como isso é implementado no Boost.Range):
template<typename Base, typename Func> struct filter_range { struct iterator { private: Func m_func;
Como podemos ver, dois iteradores são necessários aqui em vez de um, como no adaptador de transformação. O segundo iterador é necessário para não ir além dos limites do contêiner acidentalmente durante as iterações.
Algumas otimizações
Ok, mas como é o iterador de
tc :: filter (tc :: filter (tc :: filter (...))) ?
Boost.range
Como parte da implementação acima, é assim:
Os fracos de coração não assistem!m_func3
m_it3
m_func2
m_it2
m_func1
m_it1;
m_itEnd1;
m_itEnd2
m_func1
m_it1;
m_itEnd1;
m_itEnd3
m_func2
m_it2
m_func1
m_it1;
m_itEnd1;
m_itEnd2
m_func1
m_it1;
m_itEnd1;
Obviamente, isso é
terrivelmente ineficiente.
Range v3
Vamos pensar em como otimizar esse adaptador. A ideia de Eric Nibler era colocar informações gerais (um functor e um ponteiro para o final) no objeto adaptador, e então podemos armazenar um link para esse objeto adaptador e o iterador desejado
*m_rng
m_it
Então, sob essa implementação, um filtro triplo será algo como isto:
Tykm_rng3
m_it3
m_rng2
m_it2
m_rng1
m_it1
Isso ainda não é perfeito, embora às vezes seja mais rápido que a implementação anterior.
think-cell, conceito de índice
Agora considere a solução think-cell. Eles introduziram o chamado
conceito de índice para resolver esse problema. Um índice é um iterador que executa as mesmas operações que um iterador regular, mas faz isso consultando intervalos.
template<typename Base, typename Func> struct index_range { ... using Index = ...; Index begin_index() const; Index end_index() const; void increment_index( Index& idx ) const; void decrement_index( Index& idx ) const; reference dereference( Index& idx ) const; ... };
Mostramos como combinar um índice com um iterador regular.
É claro que um iterador regular também pode ser considerado um índice. Na direção oposta, a compatibilidade pode ser implementada, por exemplo, da seguinte maneira:
template<typename IndexRng> struct iterator_for_index { IndexRng* m_rng; typename IndexRng::Index m_idx; iterator& operator++() { m_rng.increment_index(m_idx); return *this; } ... };
Em seguida, o filtro triplo será implementado de maneira super eficiente:
template<typename Base, typename Func> struct filter_range { Func m_func; Base& m_base; using Index = typename Base::Index; void increment_index( Index& idx ) const { do { m_base.increment_index(idx); } while ( idx != m_base.end_index() && !m_func(m_base.dereference_index(idx)) ); } };
template<typename IndexRng> struct iterator_for_index { IndexRng* m_rng; typename IndexRng::Index m_idx; ... };
Na estrutura dessa implementação, o algoritmo funcionará rapidamente, independentemente da profundidade do filtro.
Intervalos com contêineres lvalue e rvalue
Agora vamos ver como os intervalos funcionam com os contêineres lvalue e rvalue:
lvalue
O intervalo V3 e o think-cell se comportam da mesma forma com lvalue. Suponha que tenhamos código como este:
auto rng = view::filter(vec, pred1); bool b = ranges::any_of(rng, pred2);
Aqui temos um vetor declarado anteriormente que está na memória (lvalue) e precisamos criar um intervalo e, de alguma forma, trabalhar com ele. Criamos uma view usando
view :: filter ou
tc :: filter e ficamos felizes, não há erros, e podemos usar essa view, por exemplo, em any_of.
Faixa V3 e rvalue
No entanto, se nosso vetor ainda não estivesse na memória (por exemplo, se apenas o criassemos) e teríamos enfrentado a mesma tarefa, tentaríamos escrever e encontramos um erro:
auto rng = view::filter(create_vector(), pred1);
Por que surgiu? O View será um link dangling para o rvalue devido ao fato de criarmos um vetor e o colocarmos diretamente em um filtro, ou seja, haverá um link de rvalue no filtro, que apontará para algo desconhecido quando o compilador for para a próxima linha e ocorrer um erro. Para resolver esse problema, o Range V3 apresentou a seguinte
ação :
auto rng = action::filter(create_vector(), pred1);
A ação faz tudo de uma vez, ou seja, simplesmente pega um vetor, filtra por predicado e o coloca em um intervalo. No entanto, o ponto negativo é que ele não é mais preguiçoso, e o think-cell tentou corrigir esse ponto negativo.
think-cell e rvalue
O Think-cell fez com que, em vez de visualizar, um contêiner fosse criado:
auto rng = tc::filter(creates_vector(), pred1); bool b = ranges::any_of(rng, pred2);
Como resultado, não encontramos um erro semelhante, porque, na implementação deles, o filtro coleta o contêiner rvalue em vez do link, o que ocorre preguiçosamente. O intervalo V3 não queria fazer isso porque temiam que houvesse erros devido ao filtro se comportar como uma exibição ou como um contêiner, no entanto, a think-cell está convencida de que os programadores entendem como o filtro se comporta e a maioria dos erros surge justamente por causa dessa "preguiça".
Intervalos do gerador
Generalizamos o conceito de intervalos. De fato, existem intervalos sem iteradores. Eles são chamados de
faixas de gerador . Suponha que tenhamos um widget da GUI (um elemento da interface) e chamamos um widget de movimentação. Temos uma janela que pede para mover seu widget, também temos um botão na
caixa de listagem e outra janela também deve rolar por seus widgets, ou seja, chamamos
traverse_widgets , que conecta os elementos a um functor (
você pode dizer que há uma função de enumeração em que você conecte o functor, e a função lista todos os elementos que ele possui neste functor ).
template<typename Func> void traverse_widgets( Func func ) { if (window1) { window1->traverse_widgets(std::ref(func)); } func(button1); func(listbox1); if (window2) { window2->traverse_widgets(std::ref(func)); } }
Isso lembra o espaçamento entre widgets, mas não há iteradores aqui. Escrever diretamente seria ineficiente e, acima de tudo, muito difícil. Nesse caso, podemos dizer que essas estruturas também são consideradas intervalos. Então, nesses casos, há um uso de métodos de intervalo úteis, como
any_of :
mouse_hit_any_widget=tc::any_of( [] (auto func) { traverse_widgets(func); }, [] (auto const& widget) { return widget.mouse_hit(); } );
O think-cell tenta implementar métodos para que eles tenham a mesma interface para todos os tipos de intervalos:
namespace tc { template< typename Rng > bool any_of( Rng const& rng ) { bool bResult = false; tc::enumerate( rng, [&](bool_context b) { bResult = bResult || b; } ); return bResult; } }
Usando
tc :: enumerate , a diferença entre os intervalos fica oculta, pois essa implementação adere ao conceito de
iteração interna (que os conceitos de
iteração externa e
interna são descritos com mais detalhes na palestra); no entanto, essa implementação tem suas desvantagens, a saber:
std :: any_of pára assim que
true for encontrado. Eles tentam resolver esse problema, por exemplo, adicionando exceções (os chamados
intervalos de gerador interrompidos ).
Conclusão
Eu odeio o loop for baseado em intervalo, porque motiva as pessoas a escrevê-lo sempre que necessário e onde não é necessário, por causa de que a concisão do código geralmente piora, por exemplo, as pessoas escrevem isso:
bool b = false; for (int n : rng) { if ( is_prime(n) ) { b = true; break; } }
em vez disso:
bool b = tc::any_of( rng, is_prime );