Iteradores em C++ (stl) vs Java, existe uma diferença conceitual?

StackOverflow https://stackoverflow.com/questions/56347

  •  09-06-2019
  •  | 
  •  

Pergunta

Estou voltando para c++ depois de ficar um pouco ausente e tentar tirar a poeira do velho melão.

Em Java Iterator é uma interface para um contêiner que possui métodos:hasNext(), next() e remove().A presença de hasNext() significa que tem o conceito de limite para o contêiner que está sendo atravessado.

//with an Iterator
Iterator<String> iter = trees.iterator();
while (iter.hasNext()) 
{
    System.out.println(iter.next());
}

Na biblioteca de modelos padrão C++, os iteradores parecem representar um tipo de dados ou classe que suporta o operador++ e o operador== mas tem nenhum conceito de limite incorporado para que a comparação seja necessária antes de avançar para o próximo item.O limite deve ser verificado pelo usuário comparando dois iteradores. No caso normal, o segundo iterador é o final do contêiner.

vector<int> vec;
vector<int>::iterator iter;

// Add some elements to vector
v.push_back(1);
v.push_back(4);
v.push_back(8);

for(iter= v.begin(); iter != v.end(); iter++)
{
    cout << *i << " "; //Should output 1 4 8
}

A parte interessante aqui é que em C++ um ponteiro é um iterador para um array.O STL pegou o que existia e construiu uma convenção em torno disso.

Há alguma sutileza adicional nisso que estou perdendo?

Foi útil?

Solução

Sim, há uma grande diferença conceitual.C++ utiliza diferentes "classes" de iteradores.Alguns são usados ​​para acesso aleatório (ao contrário de Java), alguns são usados ​​para acesso direto (como java).Embora outros sejam usados ​​para gravar dados (para usar, digamos, transform).

Veja o conceito de iteradores no Documentação C++:

  • Iterador de entrada
  • Iterador de saída
  • Iterador direto
  • Iterador Bidirecional
  • Iterador de acesso aleatório

Eles são muito mais interessantes e poderosos em comparação com os iteradores insignificantes do Java/C#.Esperamos que essas convenções sejam codificadas usando C++ 0x Conceitos.

Outras dicas

Talvez um pouco mais teórico.Matematicamente, as coleções em C++ podem ser descritas como um intervalo semiaberto de iteradores, ou seja, um iterador apontando para o início da coleção e um iterador apontando apenas atrás o último elemento.

Esta convenção abre uma série de possibilidades.Da forma como os algoritmos funcionam em C++, todos eles podem ser aplicados a subsequências de uma coleção maior.Para fazer isso funcionar em Java, você precisa criar um wrapper em torno de uma coleção existente que retorne um iterador diferente.

Outro aspecto importante dos iteradores já foi mencionado por Frank.Existem diferentes conceitos de iteradores.Os iteradores Java correspondem aos iteradores de entrada do C++, ou seja,eles são iteradores somente leitura que só podem ser incrementados uma etapa de cada vez e não podem retroceder.

No outro extremo, você tem ponteiros C que correspondem exatamente ao conceito C++ de um iterador de acesso aleatório.

Resumindo, C++ oferece um conceito muito mais rico e puro que pode ser aplicado a uma variedade muito maior de tarefas do que ponteiros C ou iteradores Java.

Conforme mencionado, os iteradores Java e C# descrevem uma mistura de posição (estado) e intervalo (valor), enquanto os iteradores C++ separam os conceitos de posição e intervalo.Os iteradores C++ representam 'onde estou agora' separadamente de 'para onde posso ir?'.

Os iteradores Java e C# não podem ser copiados.Você não pode recuperar uma posição anterior.Os iteradores C++ comuns podem.

Considerar este exemplo:

// for each element in vec
for(iter a = vec.begin(); a != vec.end(); ++a){
  // critical step!  We will revisit 'a' later.
  iter cur = a; 
  unsigned i = 0;
  // print 3 elements
  for(; cur != vec.end() && i < 3; ++cur, ++i){
      cout << *cur << " ";
  }
  cout << "\n";
}

Clique no link acima para ver a saída do programa.

Esse loop bastante bobo passa por uma sequência (usando apenas a semântica do iterador direto), imprimindo cada subsequência contígua de 3 elementos exatamente uma vez (e algumas subsequências mais curtas no final).Mas supondo N elementos e M elementos por linha em vez de 3, esse algoritmo ainda seria O(N*M) incrementos de iterador e O(1) espaço.

Os iteradores de estilo Java não têm a capacidade de armazenar posições de forma independente.Você também vai

  • perder espaço O(1), usando (por exemplo) uma matriz de tamanho M para armazenar o histórico conforme você itera
  • precisará percorrer a lista N vezes, perfazendo O(N^2+N*M) tempo
  • ou use um tipo Array concreto com função de membro GetAt, perdendo o genericismo e a capacidade de usar tipos de contêiner de lista vinculada.

Como apenas a mecânica de iteração direta foi usada neste exemplo, consegui trocar uma lista com sem problemas.Isso é fundamental para a criação de algoritmos genéricos, como pesquisa, inicialização e avaliação atrasadas, classificação, etc.

A incapacidade de reter o estado corresponde mais de perto ao iterador de entrada STL C++, no qual poucos algoritmos são construídos.

Um ponteiro para um elemento do array é de fato um iterador no array.

Como você disse, em Java, um iterador tem mais conhecimento do contêiner subjacente do que em C++.Iteradores C++ são gerais e um par de iteradores pode denotar qualquer intervalo:isso pode ser um subintervalo de um contêiner, um intervalo de vários contêineres (consulte http://www.justsoftwaresolutions.co.uk/articles/pair_iterators.pdf ou http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/zip_iterator.html) ou mesmo um intervalo de números (veja http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/counting_iterator.html)

As categorias do iterador identificam o que você pode ou não fazer com um determinado iterador.

Para mim, a diferença fundamental é que os iteradores Java apontam entre itens, enquanto os iteradores C++ STL apontam para itens.

Os iteradores C++ são uma generalização do conceito de ponteiro;eles o tornam aplicável a uma gama mais ampla de situações.Isso significa que eles podem ser usados ​​para fazer coisas como definir intervalos arbitrários.

Os iteradores Java são enumeradores relativamente burros (embora não tão ruins quanto os do C#;pelo menos Java possui ListIterator e pode ser usado para alterar a coleção).

Iteradores são equivalentes apenas a ponteiros no caso trivial de iterar o conteúdo de um array em sequência.Um iterador poderia fornecer objetos de inúmeras outras fontes:de um banco de dados, de um arquivo, da rede, de algum outro cálculo, etc.

Os iteradores da biblioteca C++ (a parte anteriormente conhecida como STL) são projetados para serem compatíveis com ponteiros.Java, sem aritmética de ponteiros, teve a liberdade de ser mais amigável ao programador.

Em C++ você acaba tendo que usar um par de iteradores.Em Java você usa um iterador ou uma coleção.Supõe-se que os iteradores sejam a cola entre o algoritmo e a estrutura de dados.O código escrito para 1.5+ raramente precisa mencionar iteradores, a menos que esteja implementando um algoritmo ou estrutura de dados específica (o que a maioria dos programadores não precisa fazer).Como o Java utiliza subconjuntos de polimorfismo dinâmico e similares, são muito mais fáceis de manusear.

Há muitas respostas boas sobre as diferenças, mas senti que o que mais me incomoda nos iteradores Java não foi enfatizado: você não pode ler o valor atual várias vezes.Isso é realmente útil em muitos cenários, especialmente quando você está mesclando iteradores.

Em c++, você tem um método para avançar o iterador e ler o valor atual.Ler seu valor não avança a iteração;para que você possa lê-lo várias vezes.Isso não é possível com iteradores Java e acabo criando wrappers que fazem isso.

Uma nota lateral:uma maneira fácil de criar um wrapper é usar um já existente -PeekingIterator da goiaba.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top