Zadanie

Dana jest kolekcja liczb całkowitych Zaimplementuj rozwiązanie polegające na umieszczeniu wszystkich wartości równych ”0” na początku kontenera.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
   std::vector<int> coll{ 0, 3, 0, 1, 0, 0, 2, 5, 0, 4 };

   // Implement your solution here
    
   std::copy(std::begin(coll), std::end(coll), std::ostream_iterator<int>(std::cout, " "));
}

Uruchom w edytorze

0 3 0 1 0 0 2 5 0 4

Rozwiązanie

Algorytm std::sort

Zacznijmy od rozwiązania opartego na sortowaniu. W tym celu użyjemy standardowego algorytmu std::sort lub std::stable_sort (plik nagłówkowy algorithm). Algorytm ten domyślnie sortuje dane rosnąco, co w naszym przypadku pozwala na umieszczenie wartości równych ”0” na początku kontenera. Implementacja tego rozwiązania jest bardzo prosta bowiem sprowadza się wyłącznie do jednolinijkowego wywołania funkcji std::sort na naszej kolekcji liczb:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
   std::vector<int> coll{ 0, 3, 0, 1, 0, 0, 2, 5, 0, 4 };

   // Implement your solution here
   std::sort(std::begin(coll), std::end(coll));
    
   std::copy(std::begin(coll), std::end(coll), std::ostream_iterator<int>(std::cout, " "));
}

Uruchom w edytorze

0 0 0 0 0 1 2 3 4 5

Jak widać otrzymany rezultat jest prawidłowy. Nie polecam jednak takiego rozwiązania z dwóch powodów. Po pierwsze nie jest ono generyczne. Wystarczy bowiem wystarczy zmienić typ naszej kolekcjistd::vector (plik nagłówkowy vector) na std::list (plik nagłówkowy list) aby otrzymać całkiem długi output z błędu kompilacji:

In file included from /usr/include/c++/6/algorithm:62:0,
                 from main.cpp:3:
/usr/include/c++/6/bits/stl_algo.h: In instantiation of ‘void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_List_iterator<int>; _Compare = __gnu_cxx::__ops::_Iter_less_iter]’:
/usr/include/c++/6/bits/stl_algo.h:4707:18:   required from ‘void std::sort(_RAIter, _RAIter) [with _RAIter = std::_List_iterator<int>]’
main.cpp:11:46</span>:   required from here
/usr/include/c++/6/bits/stl_algo.h:1966:22: error: no match for ‘operator-’ (operand types are ‘std::_List_iterator’ and ‘std::_List_iterator’)
     std::__lg(__last - __first) * 2,
               ~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/bits/char_traits.h:39,
                 from /usr/include/c++/6/ios:40,
                 from /usr/include/c++/6/ostream:38,
                 from /usr/include/c++/6/iostream:39,
                 from main.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:336:5: note: candidate: template decltype ((__x.base() - __y.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
     operator-(const reverse_iterator<_Iterator>& __x,
     ^~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:336:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/6/algorithm:62:0,
                 from main.cpp:3:
/usr/include/c++/6/bits/stl_algo.h:1966:22: note:   ‘std::_List_iterator’ is not derived from ‘const std::reverse_iterator<_Iterator>’
     std::__lg(__last - __first) * 2,
               ~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/bits/char_traits.h:39,
                 from /usr/include/c++/6/ios:40,
                 from /usr/include/c++/6/ostream:38,
                 from /usr/include/c++/6/iostream:39,
                 from main.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:390:5: note: candidate: template decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)
     operator-(const reverse_iterator<_IteratorL>& __x,
     ^~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:390:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/6/algorithm:62:0,
                 from main.cpp:3:
/usr/include/c++/6/bits/stl_algo.h:1966:22: note:   ‘std::_List_iterator’ is not derived from ‘const std::reverse_iterator<_Iterator>’
     std::__lg(__last - __first) * 2,
               ~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/bits/char_traits.h:39,
                 from /usr/include/c++/6/ios:40,
                 from /usr/include/c++/6/ostream:38,
                 from /usr/include/c++/6/iostream:39,
                 from main.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:1189:5: note: candidate: template decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)
     operator-(const move_iterator<_IteratorL>& __x,
     ^~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:1189:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/6/algorithm:62:0,
                 from main.cpp:3:
/usr/include/c++/6/bits/stl_algo.h:1966:22: note:   ‘std::_List_iterator’ is not derived from ‘const std::move_iterator<_IteratorL>’
     std::__lg(__last - __first) * 2,
               ~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/bits/char_traits.h:39,
                 from /usr/include/c++/6/ios:40,
                 from /usr/include/c++/6/ostream:38,
                 from /usr/include/c++/6/iostream:39,
                 from main.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:1196:5: note: candidate: template decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)
     operator-(const move_iterator<_Iterator>& __x,
     ^~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:1196:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/6/algorithm:62:0,
                 from main.cpp:3:
/usr/include/c++/6/bits/stl_algo.h:1966:22: note:   ‘std::_List_iterator’ is not derived from ‘const std::move_iterator<_IteratorL>’
     std::__lg(__last - __first) * 2,
               ~~~~~~~^~~~~~~~~

Przyczyna tego błędu leży w typie iteratrów jakie przyjmuje algorytm std::sort. Otóż wymaga on iteratora o dostępie swobodnym (ang. random access iterator), służącego do obsługi m.in. kontenera std::vector czy ”gołej” tablicy. W ich przypadku jako iterator może posłużyć zwykły, czyli ”surowy” wskaźnik, ze względu na ciągłość obszaru pamięci w tych kolekcjach danych. Sytuacja wygląda zupełnie inaczej w przypadku listy dwukierunkowej reprezentowanej przez kontener std::list. Iteratorem nie może być tutaj zwykły wskaźnik, bowiem dane na takiej liście nie znajdują się w ciągłym obszarze pamięci, ale w powiązanych ze sobą węzłach (ang. nodes), położonych w różnych obszarach pamięci. W efekcie do obsługi kontenera std::list używamy nieco ”uboższego” iteratora dwukierunkowego (ang. bidirectional iterator). Aby pozbyć się przedstawionego wcześniej błędu kompilacji, należy zastąpić funkcję  std::sort metodą kontenera std::list o tej samej nazwie (podobnie jak w przypadku std::stable_sort algorytm zaimplementowanymetodzie std::list::sort  ma charakter stabilny, chociaż jej nazwana to nie wskazuje):

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

int main()
{
   std::list<int> coll{ 0, 3, 0, 1, 0, 0, 2, 5, 0, 4 };

   // Implement your solution here
   coll.sort();
    
   std::copy(std::begin(coll), std::end(coll), std::ostream_iterator<int>(std::cout, " "));
}

Uruchom w edytorze

0 0 0 0 0 1 2 3 4 5

Brak generyczności to jednak nie największy problem tego rozwiązania. Główny problem polega bowiem na tym, że rozwiązanie to nie będzie prawidłowe w przypadku pojawienia się liczb ujemnych:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
   std::vector<int> coll{ 0, 3, 0, -1, 0, 0, 2, 5, 0, 4 };

   // Implement your solution here
   std::sort(std::begin(coll), std::end(coll));
    
   std::copy(std::begin(coll), std::end(coll), std::ostream_iterator<int>(std::cout, " "));
}

Uruchom w edytorze

-1 0 0 0 0 0 2 3 4 5

Takie rozwiązanie z pewnością nie przeszłoby testów jednostkowych (ang. unit tests). Rozwiązanie oparte na sortowaniu sprawdzi się jedynie dla liczb całkowitych bez znaku. Oznacza to, że nasz kontener zmiast przechowywać dane typu int, powininien przechowywać dane takiego typu jak unisgned int, dla których wartość równa ”0” jest najmniejsza:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
   std::vector<unsigned int> coll{ 0, 3, 0, 1, 0, 0, 2, 5, 0, 4 };

   // Implement your solution here
   std::sort(std::begin(coll), std::end(coll));
    
   std::copy(std::begin(coll), std::end(coll), std::ostream_iterator<int>(std::cout, " "));
}

Uruchom w edytorze

0 0 0 0 0 1 2 3 4 5

Pętla for

Kolejne rozwiązanie oparte zostało na ”ręcznie” napisanej pętli for. Takie podejście wymaga od nas samodzielnej implementacji algorytmu. Oto przykładowe rozwiązanie:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
   std::vector<int> coll{ 0, 3, 0, 1, 0, 0, 2, 5, 0, 4 };

   // Implement your solution here
   auto condition = [](auto v){ return (v == 0); };
   
   auto first = std::distance(std::begin(coll), 
                              std::find_if_not(std::begin(coll), std::end(coll),
                              condition));
    
   for (auto i = first + 1; i < coll.size(); ++i)
   {
      if (condition(coll[i]))
      {
         std::swap(coll[i], coll[first]);
         ++first;
      }
    }
    
    std::copy(std::begin(coll), std::end(coll), std::ostream_iterator<int>(std::cout, " "));
}

Uruchom w edytorze

0 0 0 0 0 1 2 5 3 4

Oczywiście tym razem nasz algorytm nie ma nic wspólnego z sortowaniem, a więc rozwiązanie to pozostanie prawidłowe także dla liczb ujemnych (wynikowa kolekcja liczb nie jest posortowana).

Nasz algorytm wymaga zdefiniowania odpowiedniego warunku. Jest on bardzo prosty, bowiem polega na sprawdzeniu czy podana liczba jest równa ”0”. Ponieważ warunek ten będziemy potrzebować w więcej niż jednym miejscu, do jego sformułowania poslużymy się obiektem (nazwanym condition) reprezentującym wyrażenie lambda (ang. lambda expression). Wykorzystamy tutaj generyczną wersję wyrażenia lambda dostępną od standardu C++14 (zauważ że zamiast konkretnego typu dla przyjmowanego parametru mamy tutaj słowo kluczowe auto). Ponieważ spodziewany typ (czyli int) jest nieduży, parametr przekazujemy przez wartość (zamiast przez referencję do stałej):

auto condition = [](auto v){ return (v == 0); };

Zanim zaczniemy wykonywać naszą pętlę, najpierw pominiemy ewentualne piersze wartości równe ”0”, które mogę pojawić się w naszej kolekcji (w naszym przypadku pierwszy element jest równy ”0”, a więc znajduje się już na prawidłowym miejscu). Inaczej mówiąc potrzebujemy znaleźć indeks, pod którym znajduje się pierwszy element różny od ”0”. W tym celu skorzystamy z funkcji std::distance (plik nagłówkowy iterator), która wyznaczy odległość między pierwszym elementem kolekcji  (reprezentowanym przez iterator std::begin(coll)”) oraz pierwszym niezerowym elementem kolekcji. Aby otrzymać położenie pierwszego elementu różnego od ”0” w naszej kolekcji posłużymy się algorytmem std::find_if_not (plik nagłówkowy algorithm), który po zanegowaniu naszego warunku (tutaj po raz pierszy potrzebujemy naszego obiektu condition) zwróci odpowiedni iterator:

auto first = std::distance(std::begin(coll), 
                           std::find_if_not(std::begin(coll), std::end(coll),
                           condition));

Teraz możemy przejść do właściwej pętli for. Zauważmy najpierw, że gdyby nasza kolekcja liczb składała się z samych ”0”, wówczas nasza pętla for (zgodnie z oczekiwaniem) nie wykonałaby się ani razu, bowiem wartość indeksu first, zwrócona przez funkcję std::distance byłaby równa liczbie elementów w naszej kolekcji. Pierwsza iteracja pętli loop nie odywa się jednak od elementu wskazanego przez indeks first, bowiem dla niego nie zostanie wykonana żadna akcja. Pętla for obejmuje jedynie instrukcję if, dla której warunek zostanie spełniony wyłącznie dla liczb równych ”0” (jest to drugie użycie naszego obiektu condition). Warunku tego z całą pewnością nie spełnia liczba wskazywna przez indeks first. Dlatego też indeks i inicjalizujemy wartością ”first + 1” (zamiast ”first”), co oznacza, że iteraowanie pętli for zaczynamy od elementu znajdującego się po pierwszym elemencie równym ”0”. Gdy warunek dla instrukcji if jest spełniony, wówczas wykonywana jest właściwa logika, polegająca na zamianie wskazywanego elementu o wartości ”0”, z aktualnie pierwszym elementem różnym od ”0, wskazywanym przez indeks first. W tym celu skorzystamy z funkcji std::swap (plik nagłówkowy utility), która zamieni nam wskazane wartości. Dodatkowo musimy zaktualizować indeks first poprzez jego inkrementację, tak aby zawsze wskazywał na aktualnie pierwszy element różny od ”0”.

for (auto i = first + 1; i < coll.size(); ++i)
{
   if (condition(coll[i]))
   {
      std::swap(coll[i], coll[first]);
      ++first;
   }
}

Zobaczmy jak wygląda nasza kolekcja po kolejnych iteracjach powyższej pętli:

0 0 3 1 0 0 2 5 0 4                                                                                                                                                                         
0 0 3 1 0 0 2 5 0 4                                                                                                                                                                         
0 0 0 1 3 0 2 5 0 4                                                                                                                                                                         
0 0 0 0 3 1 2 5 0 4                                                                                                                                                                         
0 0 0 0 3 1 2 5 0 4                                                                                                                                                                         
0 0 0 0 3 1 2 5 0 4                                                                                                                                                                         
0 0 0 0 0 1 2 5 3 4                                                                                                                                                                         
0 0 0 0 0 1 2 5 3 4

Nasz algorytm działa prawidłowo, ale nasze rozwiązanie jest dalekie od ideału. Osobiście nie jestem zwolennikiem samodzielnego pisania pętli (zwróć uwagę, że podczas wyświetlania elementów kolekcji także pozbyłem się pętli stosując algorytm std::copy oraz iterator typu std::ostream_iterator). Po pierwsze zwiększają one złożoność naszego kodu źródłowego, przez co staje się on trudniejszy w utrzymaniu. Po drugie, tego typu pętle zwiększają prawdopodobieństwo wystąpienia trudnych w debugowaniu błędów.

W naszym algorytmie celowo posłużyłem się indeksami do odwoływania się do elementów kolekcji, tak aby pokazać jeszcze jeden problem. Otóż indeksy powodują, iż używamy operatora [], który nie jest dostępny chociażby dla kontera typu std::list. Zatem podobnie jak dla rozwiązania opartego na algorytmie std::sort, także i tutaj nie jest ono generyczne, a dla kontenera typu std::list otrzymamy następujący błąd kompilacji:

main.cpp: In function ‘int main()’:
main.cpp:18:25: error: no match for ‘operator[]’ (operand types are ‘std::list’ and ‘long int’)
       if (condition(coll[i]))
                         ^
main.cpp:20:24: error: no match for ‘operator[]’ (operand types are ‘std::list’ and ‘long int’)
          std::swap(coll[i], coll[first]);
                        ^
main.cpp:20:33: error: no match for ‘operator[]’ (operand types are ‘std::list’ and ‘long int’)
          std::swap(coll[i], coll[first]);
                                 ^

Algorytm std::partition

Nasze poprzednie rozwiązanie mogłoby stać się generyczne, gdybyśmy indeksy wraz z użyciem operatora [] zastąpili iteratorami. Na szczęście takiego rozwiązania nie musimy implementować samodzielnie, bowiem autorzy biblioteki standardowej języka C++ zaimplementowali idealny do naszego zadania algorytm std::partition (plik nagłówkowy algorithm). Oto jego przykładowa implementacja:

template<class ForwardIt, class UnaryPredicate>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
    first = std::find_if_not(first, last, p);
    if (first == last) return first;
 
    for (ForwardIt i = std::next(first); i != last; ++i) {
        if (p(*i)) {
            std::iter_swap(i, first);
            ++first;
        }
    }
    return first;
}

Podobnie jak w rozwiązaniu opartym na pętli for musimy dostarczyć odpowiedni warunek reprezentowany tutaj przez predykat przyjmujący jeden parametr (ang. unary predicate). Jak już wiemy, w naszym przypadku musi on dostarczać informację o tym czy dana liczba jest równa ”0”. (predykat ten zaimplementujemy także jako wyrażenie lambda). Zadaniem algorytmu std::partition jest umieszczenie elementów spełniających predytkat na początku kolekcji, natomiast te które go nie spełnieją zajmują kolejne pozycje aż do końca kolekcji. Inaczej mówiąc algorytm ten dzieli kolekcję na dwie części w zależności od tego czy jej elementy spełniają podany predykat.

Algorytm std::partition jako parametry przyjmuje ponadto dwa iterotory jednokierunkowe (ang. forward iterator) co oznacza, że potrafi obsłużyć pełny zakres kontenerów obsługiwanych przez iteratory jednokierunkowe, dwukierunkowe czy też o dostępie swobodnym. Oczywiście mamy tu do czynienia z szablonem funkcji, co tylko potwierdza fakt, że jest to algorytm generyczny.

Zobaczmy jak to rozwiązanie działa w praktyce:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
    std::vector<int> coll{ 0, 3, 0, 1, 0, 0, 2, 5, 0, 4 };

    // Implement your solution here
    auto condition = [](auto v){ return (v == 0); };
    std::partition(std::begin(coll), std::end(coll), condition);
    
    std::copy(std::begin(coll), std::end(coll), std::ostream_iterator<int>(std::cout, " "));
}

Uruchom w edytorze

0 0 0 0 0 1 2 5 3 4

Ponieważ nasze rozwiązanie jest generyczne, użycie kontenera typu std::list nie stanowi już problemu:

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

int main()
{
    std::list<int> coll{ 0, 3, 0, 1, 0, 0, 2, 5, 0, 4 };

    // Implement your solution here
    auto condition = [](auto v){ return (v == 0); }
    std::partition(std::begin(coll), std::end(coll), condition);
    
    std::copy(std::begin(coll), std::end(coll), std::ostream_iterator<int>(std::cout, " "));
}

Uruchom w edytorze

0 0 0 0 0 1 2 5 3 4

Podsumowując, jest to rozwiązanie optymalne, bowiem jest jednocześnie generyczne (obsługuje różne rodzaje kontenerów) oraz bezpieczne (brak konieczności samdzielnego pisania podatnych na błędy pętli). Ponadto jest ono prawie tak samo łatwe w implementacji jak przedstawione na początku rozwiązanie oparte na algorytmie std::sort. Rozwiązanie to można bowiem sprowadzić do jednolinijkowego wywołania funkcji std::partition poprzez umieszczenie predykatu (wyrażenia lambda) bezpośrednio w tym wywołaniu:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
    std::vector<int> coll{ 0, 3, 0, 1, 0, 0, 2, 5, 0, 4 };

    // Implement your solution here
    std::partition(std::begin(coll), std::end(coll), [](auto v){ return (v == 0); });
    
    std::copy(std::begin(coll), std::end(coll), std::ostream_iterator<int>(std::cout, " "));
}

Uruchom w edytorze

0 0 0 0 0 1 2 5 3 4