Por que todas as funções do algoritmo levam apenas intervalos, não contêineres?

46

Existem muitas funções úteis em <algorithm> , mas todas elas operam em "seqüências" - pares de iteradores. Por exemplo, se eu tiver um contêiner e quiser executar std::accumulate , preciso escrever:

std::vector<int> myContainer = ...;
int sum = std::accumulate(myContainer.begin(), myContainer.end(), 0);

Quando tudo que pretendo fazer é:

int sum = std::accumulate(myContainer, 0);

O que é um pouco mais legível e claro, aos meus olhos.

Agora, vejo que pode haver casos em que você deseja operar apenas partes de um contêiner, por isso é útil ter a opção de passar intervalos. Mas pelo menos na minha experiência, esse é um caso especial raro. Eu geralmente quero operar em contêineres inteiros.

É fácil escrever uma função de invólucro que usa um contêiner e chama begin() e end() , mas essas funções de conveniência não são incluídas na biblioteca padrão.

Gostaria de saber o raciocínio por trás dessa escolha de design de STL.

    
por lethal-guitar 05.03.2014 / 14:14
fonte

5 respostas

37

... it's definitely useful to have the option of passing ranges. But at least in my experience, that's a rare special case. I'll usually want to operate on whole containers

Pode ser um caso especial raro em sua experiência , mas na realidade o recipiente inteiro é o caso especial, e o intervalo arbitrário é o caso geral.

Você já percebeu que é possível implementar o caso recipiente inteiro usando a interface atual, mas não pode fazer o inverso.

Assim, o criador de bibliotecas tinha a opção de implementar duas interfaces iniciais ou apenas implementar uma que ainda abrangesse todos os casos.

It's easy to write a wrapper function which takes a container and calls begin() and end() on it, but such convenience functions are not included in the standard library

Verdade, especialmente porque as funções gratuitas std::begin e std::end estão agora incluídas.

Então, digamos que a biblioteca forneça a sobrecarga de conveniência:

template <typename Container>
void sort(Container &c) {
  sort(begin(c), end(c));
}

agora ele também precisa fornecer a sobrecarga equivalente usando um functor de comparação, e precisamos fornecer os equivalentes para todos os outros algoritmos.

Mas, pelo menos, cobrimos todos os casos em que queremos operar em um contêiner cheio, certo? Bem, não é bem assim. Considere

std::for_each(c.rbegin(), c.rend(), foo);

Se quisermos operar para trás em containers, precisamos de outro método (ou par de métodos) por algoritmo existente.

Assim, a abordagem baseada em intervalos é mais geral no sentido simples de que:

  • pode fazer tudo o que a versão de contêiner inteiro pode
  • a abordagem de todo o contêiner duplica ou triplica o número de sobrecargas necessárias, embora ainda seja menos eficiente
  • os algoritmos baseados em intervalo também são compostos (você pode empilhar ou encadear adaptadores de iteradores, embora isso seja mais comumente feito em linguagens funcionais e Python)

Existe outro motivo válido, é claro, que já era muito trabalho para obter o STL padronizado, e inflá-lo com invólucros de conveniência antes de ter sido amplamente usado não seria um grande uso do tempo limitado da comissão. Se você estiver interessado, você pode encontrar Stepanov & O relatório técnico de Lee aqui

Como mencionado nos comentários, o Boost.Range fornece uma abordagem mais recente sem exigir mudanças no padrão.

    
por 05.03.2014 / 15:44
fonte
18

Acontece que há um artigo de Herb Sutter sobre esse mesmo assunto . Basicamente, o problema é a ambigüidade da sobrecarga. Dado o seguinte:

template<typename Iter>
void sort( Iter, Iter ); // 1

template<typename Iter, typename Pred>
void sort( Iter, Iter, Pred ); // 2

E adicionando o seguinte:

template<typename Container>
void sort( Container& ); // 3

template<typename Container, typename Pred>
void sort( Container&, Pred ); // 4

Tornará difícil distinguir 4 e 1 corretamente.

Conceitos, como proposto, mas em última análise, não incluídos no C ++ 0x, teriam resolvido isso, e também é possível contorná-lo usando enable_if . Para alguns dos algoritmos, não há problema algum. Mas eles decidiram contra isso.

Agora, depois de ler todos os comentários e respostas aqui, acho que range objetos seria a melhor solução. Acho que vou dar uma olhada em Boost.Range .

    
por 06.03.2014 / 14:54
fonte
10

Basicamente, uma decisão legada. O conceito do iterador é modelado em ponteiros, mas os contêineres não são modelados em matrizes. Além disso, como os arrays são difíceis de passar (em geral, é necessário um parâmetro de modelo sem tipo para comprimento), muitas vezes uma função só tem ponteiros disponíveis.

Mas sim, em retrospectiva, a decisão está errada. Estaríamos melhor com um objeto de intervalo construtável a partir de begin/end ou begin/length ; agora temos vários algoritmos com _n com sufixo.

    
por 05.03.2014 / 16:26
fonte
4

Adicioná-los não lhe traria nenhum poder (você já pode fazer o container inteiro chamando .begin() e .end() você mesmo), e adicionaria mais uma coisa à biblioteca que precisa ser especificada corretamente, adicionada à bibliotecas pelos fornecedores, testadas, mantidas, etc, etc.

Em suma, provavelmente não está lá porque não vale a pena manter um conjunto de modelos extras apenas para salvar usuários de contêiner inteiro de digitar um parâmetro de chamada de função extra.

    
por 05.03.2014 / 14:51
fonte
-1

Até agora, o link é uma boa alternativa para std::for_each . Observe, não há iteradores explícitos:

int a[5] = {1, 2, 3, 4, 5};
for (auto &i: a) { i *= 2; }

(Inspirado pelo link .)

    
por 22.05.2015 / 21:54
fonte