Jaki jest najlepszy sposób wykonania pętli wstecznej w C / C # / C ++?

102

Muszę przejść wstecz przez tablicę, więc mam taki kod:

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

Czy jest lepszy sposób na zrobienie tego?

Aktualizacja: Miałem nadzieję, że być może C # ma wbudowany mechanizm, taki jak:

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

Aktualizacja 2: lepsze sposoby. Rune zdobywa nagrodę z:

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

który wygląda jeszcze lepiej w zwykłym C (dzięki Twotymz):

for (int i = lengthOfArray; i--; )
{    
    //do something
}
MusiGenesis
źródło
1
Nie jestem pewien, dlaczego którakolwiek z alternatyw jest lepsza, jeśli dobro obejmuje przejrzystość lub łatwość konserwacji.
dkretz
Prawdziwe. Miałem nadzieję, że znajdę bardziej rozsądny sposób, aby to zrobić, ponieważ muszę to robić dość często.
MusiGenesis
4
Większość z tych pytań to rodzaj przeglądu odpowiedzi poniżej. Zaproponuj znaczne skrócenie.
einpoklum
Usuń C i C ++ z tytułu i hashtagów.
jaskmar

Odpowiedzi:

150

Choć wprawdzie trochę niejasne, powiedziałbym, że najbardziej typograficznie przyjemnym sposobem na zrobienie tego jest

for (int i = myArray.Length; i --> 0; )
{
    //do something
}
MusiGenesis
źródło
33
Kiedy po raz pierwszy przeczytałem twoją odpowiedź, wyglądało na to, że nawet się nie skompiluje, więc założyłem, że jesteś szaloną osobą. Ale właśnie tego szukałem: lepszego sposobu na napisanie pętli wstecznej.
MusiGenesis
4
Myślę, że i -> 0; jest celowe. To właśnie ma na myśli, mówiąc „zadowalający typograficznie”
Johannes Schaub - litb
16
Sam uznałem to za "zagmatwane typograficznie". Dla mnie „-” nie wygląda dobrze, chyba że sąsiaduje ze zmienną, na którą wpływa.
MusiGenesis
26
To zbyt niejasne i zaciemnione. Nigdy nie napisałbym czegoś takiego w kodzie produkcyjnym ...
Mihai Todor
9
Ach, idzie do operatora (->) załatwia sprawę!
nawfal
118

W C ++ masz wybór między iteracją przy użyciu iteratorów lub indeksów. W zależności od tego, czy masz zwykłą tablicę, czy plikstd::vector , używasz różnych technik.

Korzystanie z std :: vector

Korzystanie z iteratorów

C ++ pozwala to zrobić za pomocą std::reverse_iterator:

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

Korzystanie z indeksów

Niepodpisany integralną typ zwracany przez std::vector<T>::sizeto nie zawsze std::size_t. Może być większy lub mniejszy. Ma to kluczowe znaczenie dla działania pętli.

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

To działa, ponieważ wartości typów całkowitych bez znaku są definiowane za pomocą modulo ich liczby bitów. Tak więc, jeśli ustawiasz-N , kończysz na(2 ^ BIT_SIZE) -N

Korzystanie z tablic

Korzystanie z iteratorów

Używamy std::reverse_iteratordo iteracji.

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

Korzystanie z indeksów

Możemy bezpiecznie użyć std::size_ttutaj, w przeciwieństwie do powyższego, ponieważ sizeofzawsze wraca std::size_tz definicji.

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

Unikanie pułapek, w których do wskaźników zastosowano sizeof

W rzeczywistości powyższy sposób określania rozmiaru tablicy jest do niczego. Jeśli a jest w rzeczywistości wskaźnikiem zamiast tablicą (co zdarza się dość często i początkujący będą go mylić), po cichu zawiedzie. Lepszym sposobem jest użycie poniższego, co zakończy się niepowodzeniem w czasie kompilacji, jeśli podany zostanie wskaźnik:

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

Działa poprzez pobranie najpierw rozmiaru przekazanej tablicy, a następnie deklarację zwrócenia odwołania do tablicy typu char o tym samym rozmiarze. charjest zdefiniowana jako posiadająca sizeof: 1. Więc zwrócona tablica będzie miała wartość sizeof: N * 1, czyli to, czego szukamy, tylko z obliczaniem czasu kompilacji i zerowym narzutem czasu wykonania.

Zamiast robić

(sizeof a / sizeof *a)

Zmień swój kod tak, aby działał teraz

(sizeof array_size(a))
Johannes Schaub - litb
źródło
Dodatkowo, jeśli twój kontener nie ma odwrotnego iteratora, możesz użyć implementacji reverse_iterator boost
MP24
twój rozmiar_tablicy wydaje się działać dla tablic przydzielonych statycznie, ale zawiódł, gdy na przykład a było 'new int [7]'.
Nate Parsons
2
tak, taki jest tego cel :) new int [7] zwraca wskaźnik. więc sizeof (new int [7]) zwraca nie 7 * sizeof (int), ale zwróci sizeof (int *). array_size powoduje błąd kompilacji dla tego przypadku zamiast cichej pracy.
Johannes Schaub - litb
spróbuj także array_size (+ statically_allocated_array), co również się nie powiedzie, ponieważ operator + zamienia tablicę we wskaźnik do jej pierwszego elementu. użycie zwykłego sizeof dałoby ponownie rozmiar wskaźnika
Johannes Schaub - litb
Po pierwsze - dlaczego po prostu nie użyć endi beginw odwrotnej kolejności?
Tomáš Zato - Przywróć Monikę
54

W C # , używając Visual Studio 2005 lub nowszego, wpisz „forr” i naciśnij [TAB] [TAB] . To rozwinie się do forpętli, która przechodzi wstecz przez kolekcję.

Tak łatwo się pomylić (przynajmniej dla mnie), że pomyślałem, że umieszczenie tego fragmentu będzie dobrym pomysłem.

To powiedziawszy, podoba mi się Array.Reverse()/ Enumerable.Reverse()a następnie lepiej iteruję do przodu - wyraźniej określają zamiar.

Jay Bazuzi
źródło
41

Zawsze wolałbym czysty kod zamiastprzyjemnego typograficznie ” kodu. Dlatego zawsze używałbym:

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

Można to uznać za standardowy sposób wykonywania pętli wstecz.
Tylko moje dwa centy...

Jack Griffin
źródło
Pracował. Nie zrobiłem tego jeszcze w C #, ale dziękuję.
PCPGMR
Więc jak, jeśli tablica jest naprawdę duża (więc indeks musi być typu bez znaku)? size_t faktycznie jest bez znaku, prawda?
lalala
Możesz zadeklarować i jako uint. Zobacz post Marca Gravella.
Jack Griffin
Nie będzie działać dla typu bez znaku ze względu na zawijanie, w przeciwieństwie do typograficznie przyjemnego. Niedobrze.
Ocelot
17

W C # przy użyciu Linq :

foreach(var item in myArray.Reverse())
{
    // do something
}
Keltex
źródło
Jest to z pewnością najprostsze, ale należy zauważyć, że w bieżącej wersji CLR odwrócenie listy jest zawsze operacją O (n), a nie operacją O (1), którą mogłoby to być, gdyby była to operacja IList <T>; zobacz connect.microsoft.com/VisualStudio/feedback/…
Greg Beech
1
Wygląda na to, że .Reverse () tworzy lokalną kopię tablicy, a następnie wykonuje iterację wstecz przez nią. Kopiowanie tablicy tylko po to, aby można było ją iterować, wydaje się nieefektywne. Wydaje mi się, że każdy post zawierający „Linq” zasługuje na pochwałę. :)
MusiGenesis
Jest możliwy kompromis, ale wtedy natrafisz na problem polegający na tym, że "głosowanie na odpowiedź" (i -> 0) może skutkować wolniejszym kodem, ponieważ (i) musi być sprawdzane z rozmiarem tablicy za każdym razem, gdy jest używany jak w indeksie.
Keltex
1
Chociaż zgadzam się, że Linq jest świetny, problem z tym podejściem polega na tym, że iterator nie pozwala na selektywne wybieranie elementów tablicy - rozważ sytuację, w której chciałeś nawigować po części tablicy, ale nie po całej rzecz ...
jesses.co.tt
11

To zdecydowanie najlepszy sposób dla każdej tablicy, której długość jest typem całkowitym ze znakiem. W przypadku tablic, których długości są typami całkowitymi bez znaku (np. std::vectorW C ++), należy nieco zmodyfikować warunek końcowy:

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

Jeśli właśnie powiedziałeś i >= 0, jest to zawsze prawdziwe dla liczby całkowitej bez znaku, więc pętla będzie nieskończoną pętlą.

Adam Rosenfield
źródło
W C ++ "i--" byłoby automatycznie zawijane do najwyższej wartości, gdybym był 0? Przepraszam, mam problemy z C ++.
MusiGenesis
Niesamowity. Właśnie pomogliście mi zrozumieć przyczynę błędu zapełniania dysku twardego w czymś, co napisałem 12 lat temu. Dobrze, że nie pracuję w C ++.
MusiGenesis
Warunkiem zakończenia powinno być: i <myArray.size (). Zależy tylko od właściwości przepełnienia unsigned int; nie szczegóły implementacji liczb całkowitych i rzutów. Dzięki temu jest łatwiejszy do czytania i działa w językach z alternatywnymi reprezentacjami liczb całkowitych.
ejgottl
Myślę, że lepszym rozwiązaniem dla mnie jest pozostanie w świecie C #, w którym nie mogę nikogo skrzywdzić.
MusiGenesis
4

Dla mnie wygląda dobrze. Jeśli indeksator był bez znaku (uint itp.), Być może będziesz musiał wziąć to pod uwagę. Nazwij mnie leniwym, ale w tym (bez znaku) przypadku mogę po prostu użyć zmiennej przeciwnej:

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

(właściwie nawet tutaj trzeba uważać na przypadki takie jak arr.Length = uint.MaxValue ... może a! = gdzieś ... oczywiście, to jest bardzo mało prawdopodobny przypadek!)

Marc Gravell
źródło
Jednak kwestia „--pos” jest trudna. W przeszłości miałem współpracowników, którzy lubili losowo „poprawiać” rzeczy w kodzie, które nie wyglądały całkiem dobrze.
MusiGenesis
1
Następnie użyj .arr.Length-1 i pos
Marc Gravell
4

W CI lubię to robić:


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

Przykład C # dodany przez MusiGenesis:

{int i = myArray.Length; while (i-- > 0)
{
    myArray[i] = 42;
}}
Twotymz
źródło
Lubię to. Zajęło mi sekundę lub dwie, zanim zdałem sobie sprawę, że twoja metoda działa. Mam nadzieję, że nie masz nic przeciwko dodanej wersji C # (dodatkowe nawiasy klamrowe są tak, że zakres indeksu jest taki sam jak w pętli for).
MusiGenesis
Nie jestem pewien, czy użyłbym tego w kodzie produkcyjnym, ponieważ wywołałoby to uniwersalne "WTF to jest?" reakcja każdego, kto musiał ją obsługiwać, ale w rzeczywistości łatwiej jest wpisać niż normalna pętla for i nie ma znaków minus ani symboli> =.
MusiGenesis
1
Szkoda, że ​​wersja C # wymaga dodatkowego „> 0”.
MusiGenesis
Nie jestem pewien, jaki to język. ale twój pierwszy fragment kodu z pewnością NIE jest C :) tylko po to, by powiedzieć ci oczywiste. może chciałeś napisać C # i html nie udało się go przeanalizować czy coś?
Johannes Schaub - litb
@litb: Wydaje mi się, że „myArray.Length” nie jest poprawnym C (?), ale część pętli while działa i wygląda świetnie.
MusiGenesis
3

Najlepszym sposobem na zrobienie tego w C ++ jest prawdopodobnie użycie iteratorów (lub lepiej zakresów), które będą leniwie przekształcać sekwencję podczas przechodzenia.

Gruntownie,

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

Wyświetla zakres „zakres” (tutaj jest pusty, ale jestem prawie pewien, że możesz samodzielnie dodawać elementy) w odwrotnej kolejności. Oczywiście zwykłe iterowanie zakresu nie jest zbyt przydatne, ale przekazanie tego nowego zakresu algorytmom i tak dalej jest całkiem fajne.

Ten mechanizm można również wykorzystać do znacznie potężniejszych zastosowań:

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

Leniwie obliczy zakres "zakres", gdzie funkcja "f" jest zastosowana do wszystkich elementów, elementy, dla których "p" nie jest prawdziwe, są usuwane, a na koniec wynikowy zakres jest odwracany.

Składnia potoku jest najbardziej czytelną wersją IMO, biorąc pod uwagę jej wrostek. Aktualizacja biblioteki Boost.Range oczekująca na recenzję implementuje to, ale jest to całkiem proste, aby zrobić to również samodzielnie. Jeszcze fajniej jest generować wbudowaną funkcję f i predykat p z lambda DSEL.


źródło
czy możesz nam powiedzieć, skąd masz „foreach”? Czy jest to #define do BOOST_FOREACH? Wygląda uroczo przez cały czas.
Johannes Schaub - litb
1
// this is how I always do it
for (i = n; --i >= 0;){
   ...
}
Mike Dunlavey
źródło
1

Wolę pętlę while. Jest to dla mnie bardziej jasne niż dekrementacja iw stanie pętli for

int i = arrayLength;
while(i)
{
    i--;
    //do something with array[i]
}
Petko Petkov
źródło
0

Użyłbym kodu w oryginalnym pytaniu, ale jeśli naprawdę chciałbyś użyć foreach i mieć indeks całkowity w C #:

foreach (int i in Enumerable.Range(0, myArray.Length).Reverse())
{
    myArray[i] = 42; 
}
xyz
źródło
-1

Spróbuję tutaj odpowiedzieć na własne pytanie, ale to też mi się nie podoba:

for (int i = 0; i < myArray.Length; i++)
{
    int iBackwards = myArray.Length - 1 - i; // ugh
    myArray[iBackwards] = 666;
}
MusiGenesis
źródło
Zamiast robić .Length - 1 - i za każdym razem, może rozważ drugą zmienną? Zobacz mój [zaktualizowany] post.
Marc Gravell
Głosowałem w dół na moje własne pytanie. Szorstki. Nie jest bardziej grzeczny niż oryginał.
MusiGenesis
-4

UWAGA: Ten post okazał się znacznie bardziej szczegółowy i dlatego nie na temat, przepraszam.

Mając to na uwadze, moi rówieśnicy czytają go i uważają, że „gdzieś” jest wartościowy. Ten wątek nie jest odpowiednim miejscem. Byłbym wdzięczny za twoją opinię na temat tego, gdzie to powinno iść (jestem nowy w tej witrynie).


W każdym razie jest to wersja C # w .NET 3.5, która jest niesamowita, ponieważ działa na każdym typie kolekcji przy użyciu zdefiniowanej semantyki. Jest to domyślna miara (ponowne użycie!), A nie wydajność lub minimalizacja cyklu procesora w większości typowych scenariuszy deweloperskich, chociaż wydaje się, że nigdy tak nie dzieje się w świecie rzeczywistym (przedwczesna optymalizacja).

*** Metoda rozszerzenia działająca na dowolnym typie kolekcji i przyjmująca delegata akcji oczekująca pojedynczej wartości typu, wszystkie wykonywane na każdym elemencie w odwrotnej kolejności **

Wymagania 3.5:

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

Starsze wersje .NET, czy chcesz lepiej poznać wewnętrzne funkcje Linq? Czytaj dalej… Albo nie…

ZAŁOŻENIE: W systemie typów .NET typ Array dziedziczy po interfejsie IEnumerable (nie z ogólnego IEnumerable tylko IEnumerable).

To wszystko, czego potrzebujesz, aby iterować od początku do końca, jednak chcesz przejść w przeciwnym kierunku. Ponieważ IEnumerable działa na tablicy typu „object”, każdy typ jest prawidłowy,

ŚRODEK KRYTYCZNY: Zakładamy, że jeśli można przetworzyć dowolną sekwencję w odwrotnej kolejności, która jest „lepsza”, to można to zrobić tylko na liczbach całkowitych.

Rozwiązanie a dla .NET CLR 2.0-3.0:

Opis: zaakceptujemy każde wystąpienie implementujące IEnumerable z wymaganiem, że każde zawarte w nim wystąpienie jest tego samego typu. Więc jeśli otrzymamy tablicę, cała tablica zawiera instancje typu X. Jeśli jakiekolwiek inne instancje są typu! = X, wyrzucany jest wyjątek:

Usługa 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;
    }
}
zespół domain.dot.net
źródło
2
Koleś lub Dudette: po prostu szukałem mniej niezgrabnego sposobu pisania „for (int i = myArray.Length - 1; i> = 0; i--)”.
MusiGenesis
1
nie ma żadnej wartości w tej odpowiedzi
Matt Melton