struct MyStruct {
unsigned int value;
std::shared_ptr<MyStruct> pointer;
};
std::vector<std::shared_ptr<MyStruct>> container_raw;
std::vector < std::vector<std::shared_ptr<MyStruct>>> container_proccessed;
Załóżmy, że w container_raw
mam elementy 1,2,3,4,5,6,7, gdzie
1->3->5->1,
2->2,
4->6->7->4,
strzałka oznacza na który element wskazuje dany element wektora. Potrzebuję napisać funkcję, która rozdzieli mi poszczególne cykle do oddzielnych wektorów, które z kolei będą w wektorze container_proccessed
. Zależy mi na tym aby złożoność obliczeniowa była max O(n).
Generalnie mój pomysł jest taki aby szukanie elementów w cyklu zaczynać od pierwszego elementu wektora container_raw
i do tymczasowego wektora władać elementy do momentu aż element_x.pointer == container_raw[0]
, jednocześnie z container_raw
usuwając już elementy które znalazły się w wektorze tymczasowym. Następnie wektor ten dodać do wektora container_proccessed
i powtarzać całą procedurę do momentu aż container_raw
będzie pusty.
Mam tylko problem z zaimplementowaniem tego rozwiązania. Największym chyba jest to w jaki sposób szybko wyszukiwać element_x.pointer
i usuwać go z wektora container_raw