É boa forma para comparar com a alteração de valores em um loop em C ++?

Question

Sem dúvida, alguns de vocês já viram a minha postagem recente, todos sobre o mesmo programa. Eu continuo correndo em problemas com ele. Para reiterar: ainda está aprendendo, não muito avançada, não entendo ponteiros muito bem, não tomar uma classe, não entendo conceitos OOP em tudo, etc. Este código apenas Mescla as duas classificadas vetores, Farray e sarray, em uma única classificada vetor. Pelo menos, eu espero que isso é o que ele faz. Diga-me:

    //int num is to find the size of the original vector and
    //build up farray and sarray; not used in the merge process
    int num = original.size() 
    std::vector<int> final;

    std::vector<int>::iterator it = farray.begin();
    std::vector<int>::iterator iter = sarray.begin();

    //farray.size() == (0 thru (num / 2))
    //sarray.size() == ((num / 2) thru num)
    for (;it != farray.end() && iter != sarray.end();) {
        if (*it > *iter) {
            final.push_back(*it);
            it++;
        }    
        else
        {
            final.push_back(*iter);
            iter++;
        }

            if (it == farray.end()) {
                for (int i = 0; iter < sarray.end(); i++) {
                    final.push_back(*iter);
                }
            }

            if (iter == sarray.end()) {
                for (int i = 0; it < farray.end(); i++) {
                    final.push_back(*iter);
                }
            }
        }

Eu reescrevi a parte merge da minha função merge sort, de modo a ... bem, fazer o trabalho. Na verdade, tenho várias perguntas sobre este código:

1. É boa forma para comparar com std :: vector :: iterators que && iter para o meu último dois se declarações se o laço for pode alterá-las em sua próxima passagem?
2. Será que os valores do ITER e se alterar em último passe deste loop e estragar o meu código? Vai colocar o meu último se as declarações antes do *-lo e * iter comparação?
3. A) função end (membro referem-se ao último valor de tudo o que é chamá-lo? Parece que ele pode se estender além de alguma forma.

EDIT: Eu vou responder a todas as respostas amanhã, por isso volte em seguida, se você quiser ouvir mais. É meia-noite. Boa noite.

Answer 1

1. É bom para comparar iteradores que são do mesmo recipiente como para a condição de loop, mas isso só faz sentido se você estiver movendo um ou outros iteradores em qualquer parte incremento se o loop for declaração ou no corpo do por si mesmo loop. Neste loop você comparar iter contra sarray.end() mas o loop nunca muda iter. Isto significa que ou não haverá iterações ou o loop nunca terminará. Além disso, você provavelmente vai querer usar != e não < para a comparação. == e != trabalho para todos os iteradores, < não.

            for (int i = 0; iter != sarray.end(); i++) {
                final.push_back(*iter);
            }

Como iter começa onde você deseja que o loop para começar, você pode querer algo parecido com isto:

            for (; iter != sarray.end(); ++iter) {
                final.push_back(*iter);
            }

Como você ainda está aprendendo (embora não são todos nós!), É provavelmente instrutivo trabalho através de um algoritmo como este, mas você deve estar ciente de std::merge que provavelmente faz o que quiser.

std::merge( farray.begin(), farray.end(), sarray.begin(), sarray.end(), std::back_inserter( final ) );

(Você precisa #include <iterator> e <algorithm>.)

2. Não vejo incrementando iter ou no exterior loop invalidar a lógica no mais tarde para loops, o ponto em 1. de lado.

3. end() aponta para um após o final de um recipiente, de modo que você pode usá-lo para verificações de terminação loop, mas você não deve tentar cancelar a referência de um iterador que é "==" para ".end()".

Answer 2

Eu não verificar a implementação do algoritmo, vou apenas referir-se a seus três perguntas:

1. Iterators são muito parecidos com os ponteiros para valores de um recipiente. É exatamente como usar size_t i e depois ++ i no loop for. se você sente que é problemático para comparar farray [i] com sarray [i]? Provavelmente não, portanto, é OK.
2. O que eu vejo que você está fazendo em seu código aqui, é que você acabou de ler os valores de *-lo e * iter, você não realmente alterá-los, pois eles não vão mudar.
3. O fim () aponta para um local inválido. Ele não aponta para o último valor, mas "depois". É como "NULL" se você vai, portanto, se (iter == sarray.end ()) é verdadeiro, você irá falhar se você vai escrever * iter, porque você não pode excluir a referência um iterador que é igual a end ().

Answer 3

Alguns conselhos gerais: Você precisa pensar sobre nomes de variáveis. Chamando seus iterators 'ele' e 'iter' vai confundi-lo em algum ponto. Na verdade, se você olhar de perto, ele já tem. Se 'farray' e 'sarray' são nomes significativos, como sobre 'fiter' e 'siter'.

Além disso, pensar com o que o merge sort está fazendo. Esses dois últimos blocos estão lá apenas para "fuga" qualquer iterador tem algumas coisas para a esquerda. Assim, eles não precisam estar no primeiro loop.

Eu provavelmente escrevê-lo como (pseudocódigo):

while not (list1.empty and list2.empty):
    if list1.empty:
        result.push(list2.pop)
    else if list2.empty:
        result.push(list1.pop)
    else if list1.top > list2.top:
        result.push(list2.pop)
    else:
        result.push(list1.pop)

Ou em um pouco enferrujado C culted-cargo ++:

std::vector<int>::iterator fiter = farray.begin();
std::vector<int>::iterator siter = sarray.begin();

while (fiter != farray.end() || siter != sarray.end()) {
    if (fiter == farray.end())      final.push_back(*siter++);
    else if (siter == sarray.end()) final.push_back(*fiter++);
    else if (*fiter > *siter)       final.push_back(*siter++);
    else                            final.push_back(*siter++);
}

Answer 4

Você tem algumas coisas para pensar aqui.

Em primeiro lugar, se você estiver mesclando duas faixas que você seria muito melhor fora de usar o std :: função de mesclagem vez que rolar seus próprios.

Seu código é um pouco difícil de ler porque você usa diferentes estilos para recuo e onde as suas chaves. Escolha um estilo e cumpri-lo.

A primeira parte do seu loop parece ser uma correcta aplicação de um merge:

for (;it != farray.end() && iter != sarray.end();) {
    if (*it > *iter) {
        final.push_back(*it);
        it++;
    }    
    else
    {
        final.push_back(*iter);
        iter++;
    }

... e isso deve ser tudo que você precisa para começar o trabalho feito.

A segunda parte do seu ciclo tem um dos problemas dos pares:

   for (;it != farray.end() && iter != sarray.end();) {
         :   :
            if (it == farray.end()) {
                for (int i = 0; iter < sarray.end(); i++) {
                    final.push_back(*iter);
                }
            }

            if (iter == sarray.end()) {
                for (int i = 0; it < farray.end(); i++) {
                    final.push_back(*iter);
                }
            }
        }

Por um lado, os condicionais para () são escritos de modo que ambos it e iter não deve ponto ao end() da respectiva recolha, ou então as extremidades do laço. Então it nunca pode apontar para sarray.end(), iter não pode apontar para farray.end(), e nem declaração if pode jamais fogo. Eles são ambos código morto (inacessível).

Mas, mesmo se eles não estavam código morto, eles têm bugs. O condicional nos intervalos for(...) o loop quando o iterador aponta para o final da coleção, mas este iterador nunca é movido, então você tem um loop infinito.

Novamente ambos os for(...)s são código morto uneeded porque os iteradores nunca pode apontar para o final do vetor.

Answer 5

Um comentário simples:. Por que não usar while (condition) vez de for(; !condition; )

A última construção é fora do padrão e difícil de entender!