Por que todas as funções <algorithm> usam apenas intervalos, não contêineres?

49

Existem muitas funções úteis <algorithm>, mas todas elas operam em "sequências" - pares de iteradores. Por exemplo, se eu tenho um container e gostaria de rodar std::accumulatenele, 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 mais claro aos meus olhos.

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

É fácil escrever uma função wrapper que leva um recipiente e chamadas begin()e end()sobre ele, mas tais funções de conveniência não estão incluídos na biblioteca padrão.

Gostaria de saber o raciocínio por trás dessa opção de design da STL.

guitarra letal
fonte
7
A STL normalmente fornece wrappers de conveniência ou segue a política mais antiga de C ++, aqui é as ferramentas, agora você vai atirar em si mesmo no pé?
precisa
2
Para o registro: em vez de escrever seu próprio wrapper, você deve usar os wrappers de algoritmo no Boost.Range; neste caso,boost::accumulate
ecatmur 5/03/2014

Respostas:

40

... é definitivamente útil ter a opção de passar intervalos. Mas pelo menos na minha experiência, esse é um caso especial raro. Normalmente, eu quero operar em contêineres inteiros

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

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

Portanto, o escritor da biblioteca teve a opção de implementar duas interfaces antecipadamente ou apenas uma que ainda abrange todos os casos.


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

Verdade, especialmente desde as funções gratuitas std::begine std::endagora estão incluídas.

Então, digamos que a biblioteca ofereç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 exatamente. Considerar

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

Se queremos lidar com a operação reversa em contêineres, precisamos de outro método (ou par de métodos) por algoritmo existente.


Portanto, a abordagem baseada em faixa é mais geral no sentido simples de que:

  • ele pode fazer tudo o que a versão do contêiner inteiro pode
  • a abordagem de todo o contêiner duplica ou triplica o número de sobrecargas necessárias, enquanto ainda é menos poderosa
  • 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)

Há outro motivo válido, é claro, que era muito trabalhoso padronizar o STL e inflá-lo com invólucros de conveniência antes que ele fosse amplamente utilizado não seria um ótimo uso do tempo limitado do comitê. Se você estiver interessado, pode encontrar o relatório técnico de Stepanov & Lee aqui

Conforme mencionado nos comentários, o Boost.Range fornece uma abordagem mais nova sem exigir alterações no padrão.

Sem utilidade
fonte
9
Eu não acho que alguém, OP incluído, esteja sugerindo adicionar sobrecargas para cada caso especial. Mesmo que "contêiner inteiro" seja menos comum que "um intervalo arbitrário", é definitivamente muito mais comum que "contêiner inteiro, invertido". Restrinja-o a f(c.begin(), c.end(), ...), e talvez apenas a sobrecarga mais comumente usada (como você determinar) para evitar duplicar o número de sobrecargas. Além disso, os adaptadores do iterador são completamente ortogonais (como você observa, eles funcionam bem no Python, cujos iteradores funcionam de maneira muito diferente e não têm a maior parte do poder sobre o qual você fala).
3
Concordo que todo o contêiner, caso avançado é muito comum, mas queria ressaltar que é um subconjunto de usos possíveis muito menor do que a pergunta sugerida. Especificamente porque a escolha não é entre contêiner inteiro e parcial, mas entre contêiner inteiro e parcial, possivelmente revertida ou adaptada. E acho justo sugerir que a complexidade percebida do uso de adaptadores é maior, se você também precisar alterar a sobrecarga do algoritmo.
inútil
23
Observe a versão do contentor iria cobrir todos os casos, se o STL oferecido um objeto de intervalo; por exemplo std::sort(std::range(start, stop)).
3
Pelo contrário: os algoritmos funcionais composíveis (como mapa e filtro) pegam um único objeto que representa uma coleção e retornam um único objeto, eles certamente não usam nada parecido com um par de iteradores.
svick
3
uma macro poderia fazer isso: #define MAKE_RANGE(container) (container).begin(), (container).end()</jk>
catraca aberração
21

Acontece que há um artigo de Herb Sutter sobre esse assunto. Basicamente, o problema é a ambiguidade 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 4e 1adequadamente.

Os conceitos, conforme propostos, mas 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.

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

guitarra letal
fonte
11
Bem, usar apenas a typename Iterparece ser muito tipificado para uma linguagem estrita. Eu preferiria, por exemplo template<typename Container> void sort(typename Container::iterator, typename Container::iterator); // 1e template<template<class> Container, typename T> void sort( Container<T>&, std::function<bool(const T&)> ); // 4etc. (o que talvez resolver o problema da ambiguidade)
Vlad
@ Vlad: Infelizmente, isso não funcionará para matrizes antigas simples, pois não há T[]::iteratordisponível. Além disso, o iterador adequado não é obrigado a ser um tipo aninhado de qualquer coleção, basta definir std::iterator_traits.
Firegurafiku
@firegurafiku: Bem, matrizes são fáceis de serem aplicadas em casos especiais com alguns truques básicos de TMP.
Vlad
11

Basicamente, uma decisão herdada. O conceito de iterador é modelado em ponteiros, mas os contêineres não são modelados em matrizes. Além disso, como as matrizes são difíceis de passar (precisam de um parâmetro de modelo não-tipo para comprimento, em geral), muitas vezes uma função tem apenas ponteiros disponíveis.

Mas sim, em retrospectiva, a decisão está errada. Teríamos ficado melhor com um objeto de intervalo construtível a partir de begin/endou begin/length; agora temos vários _nalgoritmos com sufixo.

MSalters
fonte
5

Adicionando-se você ganhar nenhum poder (você já pode fazer todo o recipiente chamando .begin()e .end()você mesmo), e gostaria de acrescentar mais uma coisa para a biblioteca que tem de ser devidamente especificado, adicionadas às bibliotecas pelos vendedores, testado, mantido, etc etc.

Em suma, provavelmente não está lá porque não vale a pena manter um conjunto de modelos extras apenas para evitar que usuários de contêineres inteiros digitem um parâmetro de chamada de função extra.

Michael Kohne
fonte
9
Isso não me conquistaria poder, isso é verdade - mas no final, também não std::getline, e ainda está na biblioteca. Pode-se chegar ao ponto de dizer que estruturas de controle estendidas não me ganham poder, pois eu poderia fazer tudo usando apenas ife goto. Sim, comparação injusta, eu sei;) Eu acho que posso entender a carga de especificação / implementação / manutenção de alguma forma, mas é apenas um pequeno invólucro de que estamos falando aqui, então ..
lethal-guitar
Um invólucro minúsculo não custa nada para codificar e talvez não faça sentido estar na biblioteca.
ebasconp
-1

Até agora, http://en.wikipedia.org/wiki/C++11#Range-based_for_loop é uma boa alternativa para std::for_each. Observe, nenhum iterador explícito:

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

(Inspirado em https://stackoverflow.com/a/694534/2097284 .)

Camille Goudeseune
fonte
11
Ele resolve apenas essa parte <algorithm>, não todos os algos reais que precisam begine enditeradores - mas o benefício não pode ser exagerado! Quando experimentei o C ++ 03 pela primeira vez em 2009, evitei os iteradores devido ao clichê de loop e, felizmente ou não, meus projetos na época permitiam isso. Reiniciando em C ++ 11 em 2014, foi um upgrade incrível, a linguagem C ++ sempre deveria ter sido, e agora eu não posso viver sem auto &it: them:)
underscore_d