Jak przeładować std :: swap ()


115

std::swap()jest używany przez wiele kontenerów standardowych (takich jak std::listi std::vector) podczas sortowania, a nawet przypisywania.

Jednak standardowa implementacja programu swap()jest bardzo uogólniona i raczej nieefektywna dla typów niestandardowych.

W ten sposób wydajność można uzyskać przez przeciążenie std::swap()implementacją specyficzną dla niestandardowego typu. Ale jak można go zaimplementować, aby był używany przez kontenery standardowe?



Odpowiedzi:


135

Właściwym sposobem na przeciążenie zamiany jest zapisanie go w tej samej przestrzeni nazw, w której się zamieniasz, tak aby można go było znaleźć za pomocą wyszukiwania zależnego od argumentów (ADL) . Szczególnie łatwą rzeczą jest:

class X
{
    // ...
    friend void swap(X& a, X& b)
    {
        using std::swap; // bring in swap for built-in types

        swap(a.base1, b.base1);
        swap(a.base2, b.base2);
        // ...
        swap(a.member1, b.member1);
        swap(a.member2, b.member2);
        // ...
    }
};

11
W C ++ 2003 jest w najlepszym przypadku niedookreślona. Większość implementacji używa ADL do znalezienia wymiany, ale nie jest to wymagane, więc nie możesz na to liczyć. Państwo może specjalizować std :: swap dla określonego rodzaju betonu, jak pokazano przez OP; po prostu nie oczekuj, że ta specjalizacja się przyzwyczai, np. do klas pochodnych tego typu.
Dave Abrahams

15
Byłbym zaskoczony, gdyby okazało się, że implementacje nadal nie używają ADL do znalezienia właściwej wymiany. To stara sprawa w komisji. Jeśli Twoja implementacja nie używa ADL do znalezienia wymiany, zgłoś błąd.
Howard Hinnant

3
@Sascha: Po pierwsze, definiuję funkcję w zakresie przestrzeni nazw, ponieważ jest to jedyny rodzaj definicji, która ma znaczenie dla kodu ogólnego. Ponieważ int et. glin. nie / nie mogą mieć funkcji składowych, std :: sort et. glin. muszą korzystać z darmowej funkcji; ustalają protokół. Po drugie, nie wiem, dlaczego sprzeciwiasz się posiadaniu dwóch implementacji, ale większość klas jest skazana na nieefektywne sortowanie, jeśli nie możesz zaakceptować zamiany nie będącej składnikiem. Reguły przeciążania zapewniają, że jeśli obie deklaracje są widoczne, to ta bardziej szczegółowa (ta) zostanie wybrana, gdy swap zostanie wywołany bez kwalifikacji.
Dave Abrahams

5
@ Mozza314: To zależy. A, std::sortktóre używa ADL do zamiany elementów, jest niezgodne z C ++ 03, ale zgodne z C ++ 11. Poza tym, dlaczego -1 jest odpowiedzią opartą na fakcie, że klienci mogą używać kodu nieidiomatycznego?
JoeG

4
@curiousguy: Gdyby przeczytanie standardu było tylko prostą kwestią czytania standardu, miałbyś rację :-). Niestety, liczy się zamiar autorów. Więc jeśli pierwotnym zamiarem było, że ADL może lub powinno być używane, jest to niedookreślone. Jeśli nie, to jest to po prostu stara, przełomowa zmiana dla C ++ 0x, dlatego napisałem „w najlepszym razie” niedookreślony.
Dave Abrahams,

70

Uwaga Mozza 314

Oto symulacja efektów std::algorithmwywołania ogólnego std::swapi sytuacji, w której użytkownik udostępnia swap w przestrzeni nazw std. Ponieważ jest to eksperyment, w tej symulacji namespace expzamiast namespace std.

// simulate <algorithm>

#include <cstdio>

namespace exp
{

    template <class T>
    void
    swap(T& x, T& y)
    {
        printf("generic exp::swap\n");
        T tmp = x;
        x = y;
        y = tmp;
    }

    template <class T>
    void algorithm(T* begin, T* end)
    {
        if (end-begin >= 2)
            exp::swap(begin[0], begin[1]);
    }

}

// simulate user code which includes <algorithm>

struct A
{
};

namespace exp
{
    void swap(A&, A&)
    {
        printf("exp::swap(A, A)\n");
    }

}

// exercise simulation

int main()
{
    A a[2];
    exp::algorithm(a, a+2);
}

Dla mnie to drukuje:

generic exp::swap

Jeśli Twój kompilator drukuje coś innego, oznacza to, że nie implementuje poprawnie „wyszukiwania dwufazowego” dla szablonów.

Jeśli twój kompilator jest zgodny (z którymkolwiek z C ++ 98/03/11), to da to samo wyjście, które pokazuję. I w takim przypadku wydarzy się dokładnie to, czego się obawiasz. Umieszczenie twojego swapw przestrzeni nazw std( exp) nie powstrzymało tego.

Dave i ja jesteśmy członkami komitetu i zajmujemy się tym obszarem normy od dziesięciu lat (i nie zawsze w porozumieniu). Ale ta kwestia została rozstrzygnięta od dawna i oboje zgadzamy się, jak została rozwiązana. Zignoruj ​​opinię / odpowiedź Dave'a w tej dziedzinie na własne ryzyko.

Ten problem wyszedł na jaw po opublikowaniu C ++ 98. Od około 2001 roku Dave i ja zaczęliśmy pracować w tej dziedzinie . A to jest nowoczesne rozwiązanie:

// simulate <algorithm>

#include <cstdio>

namespace exp
{

    template <class T>
    void
    swap(T& x, T& y)
    {
        printf("generic exp::swap\n");
        T tmp = x;
        x = y;
        y = tmp;
    }

    template <class T>
    void algorithm(T* begin, T* end)
    {
        if (end-begin >= 2)
            swap(begin[0], begin[1]);
    }

}

// simulate user code which includes <algorithm>

struct A
{
};

void swap(A&, A&)
{
    printf("swap(A, A)\n");
}

// exercise simulation

int main()
{
    A a[2];
    exp::algorithm(a, a+2);
}

Wynik to:

swap(A, A)

Aktualizacja

Stwierdzono, że:

namespace exp
{    
    template <>
    void swap(A&, A&)
    {
        printf("exp::swap(A, A)\n");
    }

}

Pracuje! Dlaczego więc tego nie użyć?

Rozważ przypadek, że Twój Ajest szablonem klasy:

// simulate user code which includes <algorithm>

template <class T>
struct A
{
};

namespace exp
{

    template <class T>
    void swap(A<T>&, A<T>&)
    {
        printf("exp::swap(A, A)\n");
    }

}

// exercise simulation

int main()
{
    A<int> a[2];
    exp::algorithm(a, a+2);
}

Teraz to już nie działa. :-(

Więc możesz wstawić swapstd przestrzeni nazw i sprawić, by działało. Ale trzeba pamiętać, aby umieścić swapw A„s nazw dla przypadku, gdy masz szablon: A<T>. A ponieważ w obu przypadkach będzie działać, jeśli umieścić swapw A„s nazw, to jest po prostu łatwiejsze do zapamiętania (a uczyć innych) po prostu zrób to, że jeden sposób.


4
Bardzo dziękuję za szczegółową odpowiedź. Mam wyraźnie mniejszą wiedzę na ten temat i zastanawiałem się, w jaki sposób przeciążenie i specjalizacja mogą powodować różne zachowania. Nie proponuję jednak przeciążenia, ale specjalizację. Kiedy umieszczam template <>twój pierwszy przykład, otrzymuję dane wyjściowe exp::swap(A, A)z gcc. Dlaczego więc nie preferować specjalizacji?
voltrevo,

1
Łał! To jest naprawdę pouczające. Zdecydowanie mnie przekonałeś. Myślę, że nieznacznie zmodyfikuję twoją sugestię i użyję składni przyjaciela w klasie Dave'a Abrahamsa (hej, mogę tego użyć także dla operatora << też! :-)), chyba że masz powód, aby tego również uniknąć (poza kompilacją osobno). Ponadto, czy uważasz, że using std::swapjest to wyjątek od reguły „nigdy nie używaj instrukcji w plikach nagłówkowych”? W rzeczywistości, dlaczego nie włożyć do using std::swapśrodka <algorithm>? Przypuszczam, że mogłoby to złamać kod małej mniejszości. Może zrezygnować z obsługi i ostatecznie ją włączyć?
voltrevo,

3
składnia znajomego w klasie powinna wystarczyć. Spróbuję ograniczyć using std::swapzakres funkcji w twoich nagłówkach. Tak, swapto prawie słowo kluczowe. Ale nie, to nie jest słowo kluczowe. Dlatego najlepiej nie eksportować go do wszystkich przestrzeni nazw, dopóki naprawdę nie będzie to konieczne. swapjest bardzo podobny operator==. Największą różnicą jest to, że nikt nawet nie myśli o wywołaniu operator==z kwalifikowaną składnią przestrzeni nazw (byłoby to po prostu zbyt brzydkie).
Howard Hinnant,

15
@NielKirk: To, co postrzegasz jako komplikację, to po prostu zbyt wiele błędnych odpowiedzi. Nie ma nic skomplikowanego w poprawnej odpowiedzi Dave'a Abrahamsa: „Właściwym sposobem na przeciążenie zamiany jest zapisanie go w tej samej przestrzeni nazw, co zamieniasz, aby można go było znaleźć za pomocą wyszukiwania zależnego od argumentów (ADL)”.
Howard Hinnant

2
@codeshot: Przepraszamy. Herb stara się przekazać tę wiadomość od 1998 roku: gotw.ca/publications/mill02.htm W tym artykule nie wspomina o wymianie. Ale to tylko kolejne zastosowanie zasady interfejsu Herba.
Howard Hinnant

53

Nie możesz (zgodnie ze standardem C ++) przeciążać std :: swap, jednak możesz w szczególności dodawać specjalizacje szablonów dla własnych typów do przestrzeni nazw std. Na przykład

namespace std
{
    template<>
    void swap(my_type& lhs, my_type& rhs)
    {
       // ... blah
    }
}

wtedy zastosowania w kontenerach std (i gdziekolwiek indziej) wybiorą twoją specjalizację zamiast ogólnej.

Należy również pamiętać, że zapewnienie implementacji klasy bazowej wymiany nie jest wystarczające dla typów pochodnych. Np. Jeśli masz

class Base
{
    // ... stuff ...
}
class Derived : public Base
{
    // ... stuff ...
}

namespace std
{
    template<>
    void swap(Base& lha, Base& rhs)
    {
       // ...
    }
}

to zadziała dla klas bazowych, ale jeśli spróbujesz zamienić dwa obiekty pochodne, użyje wersji ogólnej ze standardowego, ponieważ zamiana szablonowa jest dokładnym dopasowaniem (i pozwala uniknąć problemu zamiany tylko części "bazowych" twoich obiektów pochodnych ).

UWAGA: zaktualizowałem to, aby usunąć niewłaściwe bity z mojej ostatniej odpowiedzi. D'oh! (dzięki puetzk i j_random_hacker za wskazanie tego)


1
W większości dobra rada, ale muszę -1 ze względu na subtelne rozróżnienie zauważone przez puetzka między specjalizacją szablonu w przestrzeni nazw std (na co pozwala standard C ++) a przeciążeniem (co nie jest).
j_random_hacker

11
Ocena negatywna, ponieważ poprawnym sposobem dostosowania zamiany jest zrobienie tego we własnej przestrzeni nazw (jak wskazuje Dave Abrahams w innej odpowiedzi).
Howard Hinnant

2
Moje powody do odrzucenia głosu są takie same jak Howarda
Dave Abrahams,

13
@HowardHinnant, Dave Abrahams: Nie zgadzam się. Na jakiej podstawie twierdzisz, że Twoja alternatywa jest „właściwą” drogą? Jak cytuje puetzk ze standardu, jest to wyraźnie dozwolone. Chociaż jestem nowy w tym problemie, naprawdę nie podoba mi się metoda, którą popierasz, ponieważ jeśli zdefiniuję Foo i zamienię w ten sposób, ktoś inny, kto używa mojego kodu, prawdopodobnie użyje std :: swap (a, b) zamiast swap ( a, b) na Foo, który dyskretnie używa nieefektywnej wersji domyślnej.
voltrevo

5
@ Mozza314: Przestrzeń i ograniczenia formatowania obszaru komentarza nie pozwoliły mi w pełni odpowiedzieć. Zobacz odpowiedź, którą dodałem, zatytułowaną „Attention Mozza314”.
Howard Hinnant

29

Chociaż prawdą jest, że generalnie nie należy dodawać rzeczy do przestrzeni nazw std ::, dodawanie specjalizacji szablonów dla typów zdefiniowanych przez użytkownika jest szczególnie dozwolone. Przeciążanie funkcji nie jest. To subtelna różnica :-)

17.4.3.1/1 Jest niezdefiniowane dla programu C ++, aby dodawać deklaracje lub definicje do przestrzeni nazw lub przestrzeni nazw z przestrzenią nazw, chyba że określono inaczej. Program może dodać specjalizacje szablonów dla dowolnego standardowego szablonu biblioteki do standardowej przestrzeni nazw. Taka specjalizacja (pełna lub częściowa) biblioteki standardowej skutkuje niezdefiniowanym zachowaniem, chyba że deklaracja zależy od zdefiniowanej przez użytkownika nazwy powiązania zewnętrznego i chyba, że ​​specjalizacja szablonu spełnia wymagania biblioteki standardowej dla oryginalnego szablonu.

Specjalizacja std :: swap wyglądałaby następująco:

namespace std
{
    template<>
    void swap(myspace::mytype& a, myspace::mytype& b) { ... }
}

Bez bitu template <> byłoby to przeciążenie, które jest nieokreślone, a nie specjalizacja, która jest dozwolona. @ Wilka sugerowane podejście do zmiany domyślnej przestrzeni nazw może działać z kodem użytkownika (z powodu wyszukiwania Koeniga preferującego wersję bez przestrzeni nazw), ale nie jest to gwarantowane, a tak naprawdę nie powinno (implementacja STL powinna używać w pełni -qualified std :: swap).

Istnieje wątek na comp.lang.c ++. Moderowany z długą dyskusją na ten temat. Większość z nich dotyczy jednak częściowej specjalizacji (na którą obecnie nie ma dobrego sposobu).


7
Jednym z powodów, dla których używanie specjalizacji szablonów funkcji do tego (lub czegokolwiek) jest niewłaściwe: źle współdziała z przeciążeniami, których jest wiele do zamiany. Na przykład, jeśli specjalizujesz się w zwykłym std :: swap dla std :: vector <mytype> &, twoja specjalizacja nie zostanie wybrana zamiast wymiany specyficznej dla wektora standardu, ponieważ specjalizacje nie są uwzględniane podczas rozwiązywania przeciążenia.
Dave Abrahams

4
To jest również to, co Meyers zaleca w Effective C ++ 3ed (pozycja 25, str. 106-112).
jww

2
@DaveAbrahams: Jeśli Specjalizujemy (bez wyraźnych argumentów szablonu), częściowe uporządkowanie powoduje, że jest to specjalizacja z tej vectorwersji i będą wykorzystywane .
Davis Herring

1
@DavisHerring właściwie, nie, kiedy robisz to częściowe zamówienie, nie odgrywa żadnej roli. Problem nie polega na tym, że w ogóle nie możesz tego nazwać; tak się dzieje w przypadku pozornie mniej specyficznych przeciążeń wymiany: wandbox.org/permlink/nck8BkG0WPlRtavV
Dave Abrahams

2
@DaveAbrahams: Porządkowanie częściowe polega na wybraniu szablonu funkcji do specjalizacji, gdy jawna specjalizacja pasuje do więcej niż jednej. ::swapPrzeciążenie została dodana jest bardziej wyspecjalizowane niż std::swapprzeciążeniem vector, zapisuje więc połączenie i bez specjalizacji to ostatnie jest istotne. Nie jestem pewien, jak to jest praktyczny problem (ale nie twierdzę też, że to dobry pomysł!).
Davis Herring,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.