std Swap dla listy dwukierunkowej

Cześć!

Chciałabym wykorzystać algorytm swap dla mojej listy dwukierunkowej którą tworze obiektowo. Czy w ogóle to możliwe? Nie mam pojęcia jak ją zdefiniować. Byłabym wdzięczna bardzo o pomoc. Dodam na dodatek, że korzystam z szablonu. Mam klasę Kontener i muszę zamienić kolejność dwóch obiektów. Stąd pomysł na użycie funkcji swap.

void swap( T &a, T &b){
???
}

Z góry dziękuje!

https://en.cppreference.com/w/cpp/algorithm/swap

T must meet the requirements of MoveAssignable and MoveConstructible.
T2 must meet the requirements of Swappable.

to Twój trop

Mmm, nie znam się na C++ za dobrze, a widzę, że Tobie chodzi zarówno o algorytm, jak i o odwzorowanie algorytmu w zapisie C++. Myślę, że możesz spróbować zacząć od tego:

http://www.cplusplus.com/reference/algorithm/swap/

Spróbuj złapać ideę.

Odpowiedź: tak, to jest możliwe. Tylko, że z pewnością nie oczekiwałabyś takiego wyniku ;)

Załóżmy, że masz wezel1 -> wezel2 -> wezel3 -> wezel4 -> ...
tzn. wezel1 jest takiego typu, że ma w sobie pole wskaźnikowe, na wezel2 (ale chyba nie muszę aż tak prosto pisać?)

jeśli wykonasz std::swap(wezel2, wezel3), to zamienisz je miejscami ale… wezel1 wskazuje na wezel2 a dokładniej na miejsce w pamięci (adres), gdzie się ów znajdował przed zamianą. Po zamianie w tym regionie pamięci jest teraz to co się znajdowało pod wezel3, a on zaś wskazuje na wezel4. Czyli masz teraz tak:
wezel1 -> wezel3 -> wezel4 -> ...
Czyli straciłaś właśnie dostęp do wezel2.

Zastanów się do czego tego Potrzebujesz; jeśli Twój swap ma zamienić elementy miejscami, to co jak będzie więcej takich samych [elementów]? Może, trzeba zindeksować listę (niestety w tym typie będzie to złożoność O(n) ) i zamieniać swap(int i, int, j)?
Pomijając, to, żeby zrobić tą metodę, Potrzebujesz:

• usuwanie elementu o danym indeksie, lub pierwsze wystąpienie danego;
• dodawanie elementu przed danym indeksem lub danym elementem (jego pierwszym wystąpieniem w zasadzie).

Jeśli potrzebujesz zrobić swap pomiędzy dwoma listami, to po prostu musisz zamienić wskaźniki na początek (i koniec, jeśli masz takie coś) pomiędzy listami i nic więcej.
Dlatego najlepiej przeciążyć std::swap dla twojej listy (dostarczyć specjalizację szablonu).
Jeśli jest to C++11 lub wyższe dostarczenie operatora move assignment też powinno rozwiązać problem.