Por que usar iteradores em vez de índices de matriz?
https://stackoverflow.com/questions/131241
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Tome as seguintes duas linhas de código:
for (int i = 0; i < some_vector.size(); i++)
{
//do stuff
}
E esta:
for (some_iterator = some_vector.begin(); some_iterator != some_vector.end();
some_iterator++)
{
//do stuff
}
Me disseram que é preferível o segundo caminho. Por que exatamente é isso?
Solução
A primeira forma é eficiente somente se vector.size () é uma operação rápida. Isto é verdade para vetores, mas não para as listas, por exemplo. Além disso, o que você está planejando fazer dentro do corpo do loop? Se você planeja acessar os elementos como em
T elem = some_vector[i];
então você está fazendo a suposição de que o recipiente tem operator[](std::size_t) definido. Novamente, isso é verdade para o vetor mas não para outros recipientes.
O uso de iteradores aproximá-lo de independência recipiente. Você não está fazendo suposições sobre a capacidade de acesso aleatório ou operação size() rápido, apenas que o recipiente tem iteradoras capacidades.
Você poderia aumentar o seu código ainda mais usando algoritmos padrão. Dependendo do que é que você está tentando alcançar, você pode optar por usar std::for_each(), std::transform() e assim por diante. Usando um algoritmo padrão em vez de um loop explícita você está evitando re-inventar a roda. Seu código é provável que seja mais eficiente (dado o algoritmo certo é escolhido), correta e reutilizável.
Outras dicas
porque você não está amarrando seu código para a implementação específica da lista some_vector. se você usa índices de array, tem que haver alguma forma de matriz; se você usar iteradores você pode usar esse código em qualquer implementação da lista.
É parte do processo de doutrinação moderno C ++. Iterators são a única forma de interagir maioria dos recipientes, para que você usá-lo mesmo com vetores apenas para obter-se na mentalidade adequada. Sério, essa é a única razão pela qual eu faço isso - Eu não acho que eu já substituiu um vector com um tipo diferente de recipiente.
Uau, isso ainda está sendo downvoted depois de três semanas. Eu acho que não vale a pena ser um pouco tongue-in-cheek.
Eu acho que o índice de matriz é mais legível. Ele corresponde a sintaxe utilizada em outros idiomas, e a sintaxe utilizada para arrays antiquados C. Também é menos detalhado. Eficiência deve ser uma lavagem se o seu compilador é bom, e quase não há casos em que é importante de qualquer maneira.
Mesmo assim, eu ainda me encontrar com iterators frequentemente com vetores. Eu acredito que o iterador é um conceito importante, então eu promovê-lo sempre que posso.
Imagine que some_vector é implementada com uma lista ligada. Em seguida, solicitar um item no i-th lugar requer operações de I a ser feito para percorrer a lista de nós. Agora, se você usar iterator, em geral, ele vai fazer o seu melhor esforço para ser o mais eficiente possível (no caso de uma lista ligada, ele vai manter um ponteiro para o nó atual e avançar-lo em cada iteração, exigindo apenas um única operação).
Por isso, fornece duas coisas:
- Abstraction de uso: você só quer iterate alguns elementos, você não se importa sobre como fazê-lo
- Desempenho
Eu vou ser os demônios defender aqui, e não recomendo iteradores. A principal razão pela qual, é todo o código fonte que eu tenha trabalhado a partir de desenvolvimento de aplicações Desktop para desenvolvimento de jogos tem i nem que eu precisava usar iteradores. Todo o tempo que eles não tenham sido exigidos e em segundo lugar os pressupostos ocultos e confusão código e pesadelos de depuração que você começa com iterators torná-los um excelente exemplo para não usá-lo em todas as aplicações que exigem velocidade.
Mesmo de um ponto de maintence eles são uma bagunça. A sua não é por causa deles, mas por causa de todo o aliasing que acontecem por trás da cena. Como eu sei que você não tenha implementado o seu próprio vetor virtual ou lista de matriz que faz algo completamente diferente para os padrões. Eu sei que tipo é atualmente agora durante a execução? Será que você sobrecarregar um operador não tive tempo para verificar todo o código fonte. Diabos eu mesmo sei qual a versão do STL seu uso?
O próximo problema que você tem com iteradores é abstração de fuga, embora existam inúmeros sites que discutem isso em detalhes com eles.
Desculpe, eu não tenho e ainda não vi qualquer ponto iteradores. Se eles abstrato da lista ou vetor de distância de você, quando na verdade você já deve saber o vector ou lista de seu lidar com se não o fizer, então o seu só vai estar se preparando para algumas grandes sessões de depuração no futuro.
Você pode querer usar um iterador se você estiver indo para adicionar / itens Remover para o vetor enquanto estiver a iteração sobre ele.
some_iterator = some_vector.begin();
while (some_iterator != some_vector.end())
{
if (/* some condition */)
{
some_iterator = some_vector.erase(some_iterator);
// some_iterator now positioned at the element after the deleted element
}
else
{
if (/* some other condition */)
{
some_iterator = some_vector.insert(some_iterator, some_new_value);
// some_iterator now positioned at new element
}
++some_iterator;
}
}
Se você estava usando índices que você teria que embaralhar itens para cima / baixo na matriz para lidar com as inserções e deleções.
separação de interesses
É muito bom para separar o código de iteração da preocupação 'core' do loop. É quase uma decisão de projeto.
Na verdade, interagindo por índice laços-lo para a implementação do recipiente. Pedindo o recipiente para um começar e terminar iterador, permite que o código de loop para uso com outros tipos de contêineres.
Além disso, no caminho std::for_each, você dizer a coleção o que fazer, em vez de pedindo que algo sobre seus internos
O padrão 0x vai introduzir fechamentos, o que tornará esta abordagem muito mais fácil de usar - ter um olhar para o poder expressivo de exemplo [1..6].each { |i| print i; } de Ruby ...
Desempenho
Mas talvez uma questão muito supervisionado é que, usando a abordagem for_each produz uma oportunidade de ter a iteração parallelized - o intel enfiando blocos pode distribuir o bloco de código sobre o número de processadores no sistema!
Nota: depois de descobrir a biblioteca algorithms e, especialmente, foreach, passei por dois ou três meses de escrever estruturas ridiculamente pequenos 'ajudante' do operador que irá conduzir o seu desenvolvedores companheiros louco. Após este tempo, eu voltei para uma abordagem pragmática - corpos de loop pequenas não merecem foreach não mais:)
A deve ler referência sobre iteradores é o livro "STL estendida" .
O GoF tem um pequeno parágrafo no final do padrão Iterator, que fala sobre esta marca de iteração; ele é chamado de 'iterador interno'. Dê uma olhada aqui também.
Porque é mais orientada a objetos. se você está interagindo com um índice que você está assumindo:
a) que os objetos são ordenados
b) de que esses objectos podem ser obtidos por um índice
c) que o incremento do índice vai bater cada item
d) que esse índice começa em zero
Com um iterador, você está dizendo "me dá tudo que eu possa trabalhar com ele" sem saber o que a implementação subjacente é. (Em Java, há coleções que não podem ser acessados ??por meio de um índice)
Além disso, com um iterador, não há necessidade de se preocupar em ir para fora dos limites da matriz.
Outra coisa legal sobre iteradores é que eles melhor que lhe permitem expressar (e aplicar) a sua const-preferência. Este exemplo garante que você não vai estar alterando o vetor no meio de seu loop:
for(std::vector<Foo>::const_iterator pos=foos.begin(); pos != foos.end(); ++pos)
{
// Foo & foo = *pos; // this won't compile
const Foo & foo = *pos; // this will compile
}
Além de todas as outras respostas excelentes ... int pode não ser grande o suficiente para o seu vetor. Em vez disso, se você quiser usar a indexação, use o size_type para o seu recipiente:
for (std::vector<Foo>::size_type i = 0; i < myvector.size(); ++i)
{
Foo& this_foo = myvector[i];
// Do stuff with this_foo
}
Eu provavelmente deveria apontar você também pode ligar
std::for_each(some_vector.begin(), some_vector.end(), &do_stuff);
iteradores STL são principalmente lá para que os algoritmos STL como espécie pode ser recipiente independente.
Se você quiser apenas fazer um loop sobre todas as entradas em um vetor é só usar o estilo de índice de loop.
É menos digitação e mais fácil de analisar para a maioria dos seres humanos. Seria bom se C ++ tinha um loop foreach simples sem ir ao mar com a magia modelo.
for( size_t i = 0; i < some_vector.size(); ++i )
{
T& rT = some_vector[i];
// now do something with rT
}
'
Eu não acho que isso faz muita diferença para um vetor. Eu prefiro usar um índice mim como eu considerá-lo a ser mais legível e você pode fazer de acesso aleatório como saltar para a frente 6 itens ou para trás salto, se for preciso.
Eu também gosto de fazer uma referência ao item dentro do loop como este por isso não há um monte de colchetes em torno do lugar:
for(size_t i = 0; i < myvector.size(); i++)
{
MyClass &item = myvector[i];
// Do stuff to "item".
}
Usando um iterador pode ser bom se você acha que pode precisar de substituir o vector com uma lista em algum momento no futuro e também parece mais elegante para os freaks STL, mas eu não consigo pensar em qualquer outra razão.
A segunda forma representa o que você está fazendo com mais precisão. No seu exemplo, você não se preocupam com o valor de i, na verdade - tudo que você quer é o próximo elemento no iterador
.Depois de ter aprendido um pouco mais sobre o assunto de esta resposta, eu percebo que foi um pouco de uma simplificação exagerada. A diferença entre este loop:
for (some_iterator = some_vector.begin(); some_iterator != some_vector.end();
some_iterator++)
{
//do stuff
}
E este loop:
for (int i = 0; i < some_vector.size(); i++)
{
//do stuff
}
É bastante mínimo. Na verdade, a sintaxe de fazer laços desta forma parece estar crescendo em mim:
while (it != end){
//do stuff
++it;
}
Iterators fazer desbloqueio alguns bastante poderosos recursos declarativas, e quando combinado com a biblioteca de algoritmos STL você pode fazer algumas coisas legais bonitas que estão fora do alcance do índice da matriz administrivia.
A indexação requer uma operação mul extra. Por exemplo, para vector<int> v, os convertidos compilador v[i] em &v + sizeof(int) * i.
Durante a iteração você não precisa saber o número do item a ser processado. Você só precisa do item e iterators fazer essas coisas muito bom.
Ninguém ainda mencionou que uma das vantagens de índices é que eles não estão se tornar inválido quando você anexar a um recipiente contíguo como std::vector, assim você pode adicionar itens para o recipiente durante a iteração.
Isto também é possível com iteradores, mas você deve chamar reserve(), e, portanto, precisa saber quantos itens você vai anexar.
Vários pontos positivos já.Tenho alguns comentários adicionais:
Supondo que estamos falando da biblioteca padrão C++, "vetor" implica um contêiner de acesso aleatório que possui as garantias do array C (acesso aleatório, layout de memória contíguo, etc.).Se você tivesse dito 'some_container', muitas das respostas acima teriam sido mais precisas (independência de contêiner, etc.).
Para eliminar quaisquer dependências na otimização do compilador, você pode mover some_vector.size() para fora do loop no código indexado, assim:
const size_t numElems = some_vector.size(); for (size_t i = 0; i
Sempre pré-incremente os iteradores e trate os pós-incrementos como casos excepcionais.
Então, assumindo e indexável std::vector<> como o contêiner, não há boas razões para preferir um ao outro, passando sequencialmente pelo contêiner.Se você precisar consultar índices de elementos mais antigos ou mais recentes com frequência, a versão indexada será mais apropriada.
Em geral, é preferível usar os iteradores porque os algoritmos fazem uso deles e o comportamento pode ser controlado (e documentado implicitamente) alterando o tipo do iterador.Locais de array podem ser usados no lugar de iteradores, mas a diferença sintática será destacada.
Não uso iteradores pelo mesmo motivo que não gosto de instruções foreach.Ao ter vários loops internos, é difícil o suficiente controlar as variáveis globais/membro sem ter que lembrar todos os valores locais e nomes de iteradores também.O que considero útil é usar dois conjuntos de índices para ocasiões diferentes:
for(int i=0;i<anims.size();i++)
for(int j=0;j<bones.size();j++)
{
int animIndex = i;
int boneIndex = j;
// in relatively short code I use indices i and j
... animation_matrices[i][j] ...
// in long and complicated code I use indices animIndex and boneIndex
... animation_matrices[animIndex][boneIndex] ...
}
Eu nem quero abreviar coisas como "animation_matrices [i]" para algum iterador aleatório chamado "anim_matrix", por exemplo, porque então você não pode ver claramente de qual array esse valor é originado.
- Se você gosta de estar próximo do metal/não confia nos detalhes de implementação, não use iteradores.
- Se você trocar regularmente um tipo de coleção por outro durante o desenvolvimento, usar iteradores.
- Se você achar difícil lembrar como iterar diferentes tipos de coleções (talvez você tenha vários tipos de diversas fontes externas em uso), usar iteradores para unificar os meios pelos quais você percorre os elementos.Isso se aplica, por exemplo, à troca de uma lista vinculada por uma lista de array.
Realmente, isso é tudo.Não é como se você fosse ganhar mais brevidade de qualquer maneira, em média, e se a brevidade realmente for seu objetivo, você sempre poderá recorrer às macros.
Ainda melhor do que "dizer à CPU o que fazer" (imperativo) é "dizer às bibliotecas o que você deseja" (funcional).
Então, em vez de usar loops, você deve aprender os algoritmos presentes em stl.
Para independência de contêiner
Eu sempre uso o índice de array porque muitos aplicativos meus exigem algo como "exibir imagem em miniatura".Então escrevi algo assim:
some_vector[0].left=0;
some_vector[0].top =0;<br>
for (int i = 1; i < some_vector.size(); i++)
{
some_vector[i].left = some_vector[i-1].width + some_vector[i-1].left;
if(i % 6 ==0)
{
some_vector[i].top = some_vector[i].top.height + some_vector[i].top;
some_vector[i].left = 0;
}
}
Ambas as implementações estão corretas, mas eu preferiria o loop 'for'.Como decidimos usar um Vector e não qualquer outro container, usar índices seria a melhor opção.Usar iteradores com Vetores perderia o benefício de ter os objetos em blocos de memória contínuos que facilitam seu acesso.
