Kurde balans. Nie wiem, czy to ja mam schrzanione myślenie, ale ciągle łapię się na tym, że chcę używać STL-owych kontenerów z incomplete types.

Przykład. Banalnie proste zadanie algorytmiczne. Otóż są karty ustawione w gromadki, a gromadki kart są ustawione w rzędzie. (std::list<gromadka> rząd;)

Można wykonywać ruchy w ten sposób, że się przekłada kartę z góry jednej gromadki na górę innej gromadki, według jakichś tam reguł. W każdym razie wykonanie jednego ruchu może umożliwić wykonanie innych ruchów, które przedtem były niemożliwe, ale także uniemożliwić wykonanie jakichś ruchów, które przedtem były możliwe do wykonania.

Decyzja, który ruch należy w danym momencie wykonać jest algorytmicznie bardzo prosta. Jeśli natomiast chodzi o kwestie "machania łopatą": no to mam sobie kolejkę priorytetową, std::set<ruch> możliwości, i który ruch jest na wierzchu kolejki ten jest wykonywany.

To teraz problemy. W strukturze gromadka wstawiłem std::list<std::set<ruch>::iterator> powiązanie_ruchy;. Chodzi o to, że jak pisałem, wykonanie jednego ruchu może unieważnić inne, wcześniej wykonywalne ruchy, więc po zasymulowaniu jakiegoś ruchu muszę przejrzeć powiązane z tą gromadką możliwe ruchy, by móc powywalać z kolejki priorytetowej nieaktualne możliwości. Muszę mieć iterator, bo w przeciwnym wypadku erase na tym setcie nie będzie miało stałej złożoności.

Ale analogiczny cyrk jest i w drugim kierunku: wykonanie jakiegoś ruchu może opróżnić którąś gromadkę, a wtedy trzeba taką gromadkę wyrzucić z listy. A więc muszę albo: (a) w strukturze ruch trzymać iteratory, a nie wskaźniki na gromadki, kórych ruch dotyczy albo (b) w strukturze gromadka trzymać iterator na siebie. Jeśli wybiorę możliwość (a), no to mamy wzajemną rekurencję i gdzieś muszę odwołać się do iteratora kontenera z niekompletnym typem. A jeśli wybiorę możliwość (b), to dzieje się to natychmiast w strukturze gromadka.

Nawet jeśli w myśl tego dokumentu http://open-std.org/JTC1/SC22/WG21/docs/papers/2015/n4510.html uznamy, że wolno stworzyć instancję listy z niekompletnym typem, to i tak nie wolno odwołać się do jej iteratora.

Co powieniem zrobić w takiej sytuacji? Jak przestawić myślenie?

Mam ochotę po prostu połączyć te gromadki w ten sposób:

struct gromadka
{
  gromadka *poprzednia, *następna;
  // ...
};

I wtedy będę mógł usuwać gromadki mając tylko do nich wskaźnik bez użycia żadnego STLa.

Jest to oczywiście proste i łatwe. Ale i tak pytam tutaj, bo jak pisałem, tego rodzaju problemy się u mnie powtarzają, przypuszczam że gdzieś powinienem sobie myślenie przestawić, a chociaż akurat zastąpienie std::list jest proste, tak wynajdywanie koła na nowo w przypadku std::set czy innych podobnych to już często overkill a skoro te problemy się u mnie powtarzają to teraz muszę pisać własną std::list ale za chwilę okaże się że ten sam cyrk się pojawił z std::set i zaraz zacznę pisać własne AVL.

Dlatego chciałbym wiedzieć jak najlepiej taki problem rozwiązać wykorzystując jednak STLowe kontenery?