Szybkie przetwarzanie danych w wektorze

0
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

0

opisz co chcesz osiganac a nie jak to rozwiazac.

Bo moze vector nie jest struktura danych ktora potrzebujesz

wiec co chcesz osiagnac?

0

Mam dane wejściowe w postaci dwóch stringów z danymi określającymi położenie. np.:
string_1: "2 1 4 3 5 6 7",
string_2: "7 5 1 4 6 3 2"
Kazdy z tych numerów określa jakiś obiekt. I tak. Obiekt pierwszy jest na pozycji początkowej 2, a musi się znaleźć na pozycji końcowej 7, obiekt drugi jest na pozycji początkowej 1, a musi znaleźć się na pozycji końcowej 5 itd. Każdy z obiektów ma jeszcze wagę, która jest mi potrzebna aby obliczyć wysiłek związany z przemieszczeniem tych obiektów.
Mam algorytmy, które muszę wykorzystać przy obliczeniu tego wysiłku. Oba wymagają tego aby rozdzielić zbiór na cykle i wykonywać operacje w ramach tych cykli tj.
cykl_1: 2->7->2 (obiekt na pozycji 2 musi być na pozycji 7, a obiekt na pozycji 7 musi byc na pozycji 2)
cykl_2: 1->5->6->3->4->1 (obiekt na pozycji 1 musi być na pozycji 5 ............., a obiekt na pozycji 4 musi być na pozycji 1)
I stąd moje pytanie jak wyznaczyć cykle, aby była jak najlepsza złożoność obliczeniowa :).

0

To wygląda na zadanie SPOJ lub coś pokrewnego.
Nie widzę powodu, by używać shared_ptr, wystarczy ci struktura opisująca obiekt: ile wymaga wysiłku i gdzie powinien się znaleźć.
Bieżące położenie obiektu powinno być równocześnie jego pozycją w wektorze.

Jako, że nie przepisałeś zadania, to trzeba się domyślać o co chodzi (może lepiej podaj do niego linka). Prawdopodobnie:

  • szukasz takiej sekwencji ruchów, która minimalizuje wysiłek potrzeby do uzyskania pożądanego porządku
  • nie opisałeś na czym polega ruch i jak jest związany z wysiłkiem? Przesuwasz obiekty parami, czy może większymi grupami? jak to się ma do potrzebnego wysiłku?
  • nie rozumiem, czemu zakładasz, że potrzebne ci są jakieś cykle?
  • to raczej nie wygląda na problem, który można rozwiązać w czasie liniowym

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0