Qual é a melhor maneira de fazer um loop reverso em C / C # / C ++?

101

Preciso retroceder em uma matriz, então tenho um código como este:

for (int i = myArray.Length - 1; i >= 0; i--)
{
    // Do something
    myArray[i] = 42;
}

Existe um jeito melhor de fazer isso?

Atualização: eu esperava que talvez C # tivesse algum mecanismo integrado para isso, como:

foreachbackwards (int i in myArray)
{
    // so easy
}

Update 2: Não são as melhores formas. Rune leva o prêmio com:

for (int i = myArray.Length; i-- > 0; )
{    
    //do something
}
//or
for (int i = myArray.Length; i --> 0; )
{
    // do something
}

que fica ainda melhor em C normal (graças a Twotymz):

for (int i = lengthOfArray; i--; )
{    
    //do something
}
MusiGenesis
fonte
Não tenho certeza se vejo por que alguma das alternativas é melhor, se a bondade inclui clareza ou facilidade de manutenção.
dkretz
Verdade. Eu esperava encontrar uma maneira mais razoável de fazer isso, já que tenho que fazer isso com bastante frequência.
MusiGenesis
3
A maior parte desta pergunta é uma espécie de revisão das respostas abaixo. Sugira que seja reduzido significativamente.
einpoklum
Remova C e C ++ do título e das hashtags.
jaskmar

Respostas:

149

Embora seja um pouco obscuro, eu diria que a maneira mais agradável tipograficamente de fazer isso é

for (int i = myArray.Length; i --> 0; )
{
    //do something
}
MusiGenesis
fonte
32
Quando li sua resposta pela primeira vez, parecia que nem mesmo compilava, então presumi que você fosse uma pessoa maluca. Mas é exatamente o que eu estava procurando: uma maneira melhor de escrever um loop for backward.
MusiGenesis
3
Eu acho que i -> 0; é de propósito. Isso é o que ele quer dizer com "tipograficamente agradável"
Johannes Schaub - litb de
16
Eu mesmo achei isso "tipograficamente confuso". Para mim, o "-" não parece certo a menos que seja adjacente à variável que está afetando.
MusiGenesis de
26
Isso é muito obscuro e ofuscado. Eu nunca escreveria algo assim em código de produção ...
Mihai Todor
9
Aah, o operador vai para (->) faz o truque!
nawfal
118

Em C ++, você basicamente tem a escolha entre iterar usando iteradores ou índices. Dependendo se você tem um array simples ou um std::vector, você usa técnicas diferentes.

Usando std :: vector

Usando iteradores

C ++ permite que você faça isso usando std::reverse_iterator:

for(std::vector<T>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it) {
    /* std::cout << *it; ... */
}

Usando índices

O tipo integral sem sinal retornado por std::vector<T>::sizeé não sempre std::size_t. Pode ser maior ou menor. Isso é crucial para o loop funcionar.

for(std::vector<int>::size_type i = someVector.size() - 1; 
    i != (std::vector<int>::size_type) -1; i--) {
    /* std::cout << someVector[i]; ... */
}

Funciona, pois os valores dos tipos inteiros sem sinal são definidos por meio do módulo de sua contagem de bits. Assim, se você está configurando -N, você acaba em(2 ^ BIT_SIZE) -N

Usando matrizes

Usando iteradores

Estamos usando std::reverse_iteratorpara fazer a iteração.

for(std::reverse_iterator<element_type*> it(a + sizeof a / sizeof *a), itb(a); 
    it != itb; 
    ++it) {
    /* std::cout << *it; .... */
}

Usando índices

Podemos usar com segurança std::size_taqui, ao contrário de acima, pois sizeofsempre retorna std::size_tpor definição.

for(std::size_t i = (sizeof a / sizeof *a) - 1; i != (std::size_t) -1; i--) {
   /* std::cout << a[i]; ... */
}

Evitando armadilhas com sizeof aplicado a ponteiros

Na verdade, a maneira acima de determinar o tamanho de uma matriz é uma droga. Se a for na verdade um ponteiro em vez de um array (o que acontece com frequência e os iniciantes vão confundi-lo), ele falhará silenciosamente. A melhor maneira é usar o seguinte, que falhará no tempo de compilação, se for fornecido um ponteiro:

template<typename T, std::size_t N> char (& array_size(T(&)[N]) )[N];

Ele funciona obtendo o tamanho do array passado primeiro e, em seguida, declarando retornar uma referência a um array do tipo char do mesmo tamanho. charé definido para ter sizeofde: 1. Portanto, o array retornado terá um sizeofde: N * 1, que é o que estamos procurando, com apenas avaliação de tempo de compilação e zero overhead de tempo de execução.

Em vez de fazer

(sizeof a / sizeof *a)

Mude seu código para que agora

(sizeof array_size(a))
Johannes Schaub - litb
fonte
Além disso, se seu contêiner não tiver um iterador reverso, você pode usar a implementação de reverse_iterator do boost: boost.org/doc/libs/1_36_0/libs/iterator/doc/…
MP24
seu array_size parece funcionar para arrays alocados estaticamente, mas falhou para mim quando um era 'new int [7]', por exemplo.
Nate Parsons
2
sim, essa é a intenção :) new int [7] retorna um ponteiro. então sizeof (new int [7]) não retorna 7 * sizeof (int), mas retornaria sizeof (int *). array_size causa um erro de compilação para esse caso em vez de funcionar silenciosamente.
Johannes Schaub - litb
também tente array_size (+ statically_allocated_array), que também falha, porque o operador + transforma a matriz em um ponteiro para seu primeiro elemento. usar o tamanho simples daria o tamanho de um ponteiro novamente
Johannes Schaub - litb
Para começar, por que não usar ende beginna ordem inversa?
Tomáš Zato - Reintegração de Monica
54

Em C # , usando o Visual Studio 2005 ou posterior, digite 'forr' e pressione [TAB] [TAB] . Isso se expandirá para um forloop que vai para trás em uma coleção.

É tão fácil errar (pelo menos para mim), que pensei que seria uma boa ideia inserir este trecho.

Dito isso, eu gosto de Array.Reverse()/ Enumerable.Reverse()e itero melhor para frente - eles declaram a intenção com mais clareza.

Jay Bazuzi
fonte
41

Eu sempre preferiria código claro em vez de código ' tipograficamente agradável '. Portanto, eu sempre usaria:

for (int i = myArray.Length - 1; i >= 0; i--)  
{  
    // Do something ...  
}    

Você pode considerá-lo a maneira padrão de fazer um loop para trás.
Apenas meus dois centavos...

Jack Griffin
fonte
Trabalhou. Ainda não fiz isso em C #, mas obrigado.
PCPGMR de
Então, como se a matriz for realmente grande (então o índice tem que ser do tipo sem sinal)? size_t não tem sinal, não é?
lalala
Você pode declarar i como uint. Consulte a postagem de Marc Gravell.
Jack Griffin
Não funcionará para um tipo não assinado devido ao envoltório, ao contrário do tipograficamente agradável. Não é bom.
Ocelot
17

Em C # usando Linq :

foreach(var item in myArray.Reverse())
{
    // do something
}
Keltex
fonte
Isso é com certeza o mais simples, mas observe que na versão atual do CLR, reverter uma lista é sempre uma operação O (n) ao invés da operação O (1) que poderia ser se fosse um IList <T>; consulte connect.microsoft.com/VisualStudio/feedback/…
Greg Beech de
1
Parece que .Reverse () faz uma cópia local do array e, em seguida, itera de trás para frente. Parece meio ineficiente copiar um array apenas para que você possa iterar por ele. Eu acho que qualquer post com "Linq" é digno de votos positivos. :)
MusiGenesis
Há uma possível compensação, mas então você se depara com o problema de que a "resposta votada" (i -> 0) pode resultar em um código mais lento porque (i) deve ser verificado em relação ao tamanho da matriz cada vez que for usado como no índice.
Keltex de
1
Embora eu concorde que o Linq seja ótimo, o problema com essa abordagem é que um iterador não permite que você selecione itens seletivamente do array - considere a situação em que você queria navegar por uma parte de um Array, mas não por todo coisa ...
jesses.co.tt
11

Essa é definitivamente a melhor maneira para qualquer array cujo comprimento seja um tipo integral assinado. Para matrizes cujos comprimentos são de um tipo integral sem sinal (por exemplo, std::vectorem C ++), você precisa modificar ligeiramente a condição final:

for(size_t i = myArray.size() - 1; i != (size_t)-1; i--)
    // blah

Se você acabou de dizer i >= 0, isso sempre é verdade para um inteiro sem sinal, então o loop será um loop infinito.

Adam Rosenfield
fonte
Em C ++, o "i--" seria automaticamente alterado para o valor mais alto se i fosse 0? Desculpe, sou deficiente em C ++.
MusiGenesis
Surpreendente. Vocês acabaram de me ajudar a entender a causa de um bug de enchimento do disco rígido em algo que escrevi 12 anos atrás. Ainda bem que não trabalho em C ++.
MusiGenesis
a condição de terminação deve ser: i <myArray.size (). Depende apenas das propriedades de estouro de unsigned int; não detalhes de implementação de inteiros e casts. Conseqüentemente, mais fácil de ler e funciona em idiomas com representações inteiras alternativas.
ejgottl
Acho que a melhor solução para mim é permanecer no mundo C #, onde não posso machucar ninguém.
MusiGenesis
4

Parece bom para mim. Se o indexador não tiver assinatura (uint etc), talvez seja necessário levar isso em consideração. Chame-me de preguiçoso, mas nesse caso (sem sinal), posso apenas usar uma contra-variável:

uint pos = arr.Length;
for(uint i = 0; i < arr.Length ; i++)
{
    arr[--pos] = 42;
}

(na verdade, mesmo aqui, você precisa ter cuidado com casos como arr.Length = uint.MaxValue ... talvez a! = em algum lugar ... claro, esse é um caso muito improvável!)

Marc Gravell
fonte
A coisa "--pos" é complicada, no entanto. Eu tive colegas de trabalho no passado que gostavam de "corrigir" aleatoriamente coisas no código que não pareciam muito certas para eles.
MusiGenesis
1
Em seguida, use .arr.Length-1 e pos--
Marc Gravell
4

Em CI gosto de fazer isso:


int i = myArray.Length;
while (i--) {
  myArray[i] = 42;
}

Exemplo C # adicionado por MusiGenesis:

{int i = myArray.Length; while (i-- > 0)
{
    myArray[i] = 42;
}}
Twotymz
fonte
Eu gosto disso. Levei um ou dois segundos para perceber que seu método funciona. Espero que você não se importe com a versão C # adicionada (as chaves extras são para que o índice tenha o mesmo escopo de um loop for).
MusiGenesis
Não tenho certeza se usaria isso no código de produção, porque provocaria um "WTF é este?" Universal. reação de quem teve que mantê-lo, mas na verdade é mais fácil digitar do que um loop for normal e sem sinais de menos ou> = símbolos.
MusiGenesis
1
Pena que a versão C # precisa do extra "> 0".
MusiGenesis
Não tenho certeza de que idioma é. mas seu primeiro trecho de código certamente NÃO é C :) apenas para lhe dizer o óbvio. talvez você quisesse escrever C # e html não conseguiu analisá-lo ou algo assim?
Johannes Schaub - litb
@litb: Eu acho que "myArray.Length" não é C válido (?), mas a parte do loop while funciona e parece ótimo.
MusiGenesis de
3

A melhor maneira de fazer isso em C ++ é provavelmente usar adaptadores iteradores (ou melhor, de faixa), que transformarão preguiçosamente a sequência à medida que ela é percorrida.

Basicamente,

vector<value_type> range;
foreach(value_type v, range | reversed)
    cout << v;

Exibe o intervalo "intervalo" (aqui, está vazio, mas tenho quase certeza de que você mesmo pode adicionar elementos) na ordem inversa. É claro que simplesmente iterar o intervalo não é muito útil, mas passar esse novo intervalo para algoritmos e outras coisas é muito legal.

Este mecanismo também pode ser usado para usos muito mais poderosos:

range | transformed(f) | filtered(p) | reversed

Calculará preguiçosamente o intervalo "intervalo", onde a função "f" é aplicada a todos os elementos, os elementos para os quais "p" não é verdadeiro são removidos e, finalmente, o intervalo resultante é invertido.

A sintaxe do pipe é a IMO mais legível, devido ao seu infixo. A atualização da biblioteca Boost.Range com revisão pendente implementa isso, mas é muito simples de fazer você mesmo também. É ainda mais legal com um lambda DSEL gerar a função f e o predicado p em linha.


fonte
você pode nos dizer de onde vem "foreach"? É um #define para BOOST_FOREACH? Parece fofo de qualquer maneira.
Johannes Schaub - litb de
1
// this is how I always do it
for (i = n; --i >= 0;){
   ...
}
Mike Dunlavey
fonte
1

Eu prefiro um loop while. É mais claro para mim do que diminuir ia condição de um loop for

int i = arrayLength;
while(i)
{
    i--;
    //do something with array[i]
}
Petko Petkov
fonte
0

Eu usaria o código da pergunta original, mas se você realmente quisesse usar foreach e ter um índice inteiro em C #:

foreach (int i in Enumerable.Range(0, myArray.Length).Reverse())
{
    myArray[i] = 42; 
}
xyz
fonte
-1

Vou tentar responder minha própria pergunta aqui, mas também não gosto disso:

for (int i = 0; i < myArray.Length; i++)
{
    int iBackwards = myArray.Length - 1 - i; // ugh
    myArray[iBackwards] = 666;
}
MusiGenesis
fonte
Em vez de fazer o .Length - 1 - i cada vez, talvez considere uma segunda variável. Veja minha postagem [atualizada].
Marc Gravell
Votei negativamente em minha própria pergunta. Harsh. Não é mais pesado do que o original.
MusiGenesis
-4

NOTA: Esta postagem acabou sendo muito mais detalhada e, portanto, fora do tópico, peço desculpas.

Dito isso, meus colegas lêem e acreditam que é valioso "em algum lugar". Este tópico não é o lugar. Eu gostaria de receber seus comentários sobre onde isso deve ir (eu sou novo no site).


De qualquer forma, esta é a versão C # em .NET 3.5, o que é incrível, pois funciona em qualquer tipo de coleção usando a semântica definida. Esta é uma medida padrão (reutilizar!) E não o desempenho ou a minimização do ciclo da CPU no cenário de desenvolvimento mais comum, embora isso nunca pareça ser o que acontece no mundo real (otimização prematura).

*** Método de extensão trabalhando em qualquer tipo de coleção e realizando uma ação delegada esperando um único valor do tipo, tudo executado em cada item ao contrário **

Requer 3.5:

public static void PerformOverReversed<T>(this IEnumerable<T> sequenceToReverse, Action<T> doForEachReversed)
      {
          foreach (var contextItem in sequenceToReverse.Reverse())
              doForEachReversed(contextItem);
      }

Versões mais antigas do .NET ou você quer entender melhor a parte interna do Linq? Continue a ler .. Ou não ..

ASSUNÇÃO: No sistema de tipo .NET, o tipo Array herda da interface IEnumerable (não o IEnumerable genérico, apenas IEnumerable).

Isso é tudo que você precisa para iterar do início ao fim, no entanto, você deseja mover na direção oposta. Como IEnumerable funciona em Array do tipo 'objeto', qualquer tipo é válido,

MEDIDA CRÍTICA: Presumimos que se você pode processar qualquer sequência em ordem reversa que seja 'melhor' do que apenas ser capaz de fazê-lo em inteiros.

Solução a para .NET CLR 2.0-3.0:

Descrição: aceitaremos qualquer instância de implementação de IEnumerable com o mandato de que cada instância que ele contém seja do mesmo tipo. Portanto, se recebermos uma matriz, a matriz inteira contém instâncias do tipo X. Se qualquer outra instância for do tipo! = X, uma exceção é lançada:

Um serviço singleton:

public class ReverserService {private ReverserService () {}

    /// <summary>
    /// Most importantly uses yield command for efficiency
    /// </summary>
    /// <param name="enumerableInstance"></param>
    /// <returns></returns>
    public static IEnumerable ToReveresed(IEnumerable enumerableInstance)
    {
        if (enumerableInstance == null)
        {
            throw new ArgumentNullException("enumerableInstance");
        }

        // First we need to move forwarad and create a temp
        // copy of a type that allows us to move backwards
        // We can use ArrayList for this as the concrete
        // type

        IList reversedEnumerable = new ArrayList();
        IEnumerator tempEnumerator = enumerableInstance.GetEnumerator();

        while (tempEnumerator.MoveNext())
        {
            reversedEnumerable.Add(tempEnumerator.Current);
        }

        // Now we do the standard reverse over this using yield to return
        // the result
        // NOTE: This is an immutable result by design. That is 
        // a design goal for this simple question as well as most other set related 
        // requirements, which is why Linq results are immutable for example
        // In fact this is foundational code to understand Linq

        for (var i = reversedEnumerable.Count - 1; i >= 0; i--)
        {
            yield return reversedEnumerable[i];
        }
    }
}



public static class ExtensionMethods
{

      public static IEnumerable ToReveresed(this IEnumerable enumerableInstance)
      {
          return ReverserService.ToReveresed(enumerableInstance);
      }
 }

[TestFixture] public class Testing123 {

    /// <summary>
    /// .NET 1.1 CLR
    /// </summary>
    [Test]
    public void Tester_fornet_1_dot_1()
    {
        const int initialSize = 1000;

        // Create the baseline data
        int[] myArray = new int[initialSize];

        for (var i = 0; i < initialSize; i++)
        {
            myArray[i] = i + 1;
        }

        IEnumerable _revered = ReverserService.ToReveresed(myArray);

        Assert.IsTrue(TestAndGetResult(_revered).Equals(1000));
    }

    [Test]
    public void tester_why_this_is_good()
    {

        ArrayList names = new ArrayList();
        names.Add("Jim");
        names.Add("Bob");
        names.Add("Eric");
        names.Add("Sam");

        IEnumerable _revered = ReverserService.ToReveresed(names);

        Assert.IsTrue(TestAndGetResult(_revered).Equals("Sam"));


    }

    [Test]
    public void tester_extension_method()
  {

        // Extension Methods No Linq (Linq does this for you as I will show)
        var enumerableOfInt = Enumerable.Range(1, 1000);

        // Use Extension Method - which simply wraps older clr code
        IEnumerable _revered = enumerableOfInt.ToReveresed();

        Assert.IsTrue(TestAndGetResult(_revered).Equals(1000));


    }


    [Test]
    public void tester_linq_3_dot_5_clr()
    {

        // Extension Methods No Linq (Linq does this for you as I will show)
        IEnumerable enumerableOfInt = Enumerable.Range(1, 1000);

        // Reverse is Linq (which is are extension methods off IEnumerable<T>
        // Note you must case IEnumerable (non generic) using OfType or Cast
        IEnumerable _revered = enumerableOfInt.Cast<int>().Reverse();

        Assert.IsTrue(TestAndGetResult(_revered).Equals(1000));


    }



    [Test]
    public void tester_final_and_recommended_colution()
    {

        var enumerableOfInt = Enumerable.Range(1, 1000);
        enumerableOfInt.PerformOverReversed(i => Debug.WriteLine(i));

    }



    private static object TestAndGetResult(IEnumerable enumerableIn)
    {
      //  IEnumerable x = ReverserService.ToReveresed(names);

        Assert.IsTrue(enumerableIn != null);
        IEnumerator _test = enumerableIn.GetEnumerator();

        // Move to first
        Assert.IsTrue(_test.MoveNext());
        return _test.Current;
    }
}
equipe domain.dot.net
fonte
2
Cara ou dudette: Eu só estava procurando uma maneira menos desajeitada de escrever "para (int i = myArray.Length - 1; i> = 0; i--)".
MusiGenesis
1
não há nenhum valor nesta resposta
Matt Melton