Jak odnoszą się do cyklicznych kodowanym przez wskaźniki użyciu wektorów

Question

mam konstrukcjom, niech je nazwać sn, który wygląda tak:

struct sn { 
    string name; 
    vector<sn*> connected_to; 
}; 

Teraz załóżmy, że mam wektor connected_to już zadeklarowaną od 0 - 9; i łączę sn A, na sn B:

A.connected_to[0] = &B; 

Mam przeczucie, że podążam tą drogą w niewłaściwy sposób. Zasadniczo co próbuję zrobić, to unikać kopiowania struct kiedy łączę się konstrukcjom ... tj:

struct sn { 
    string name; 
    vector<sn> connected_to; 
}; 

// ... 

A.connected_to[0] = B; 

Czy ta kopia czegoś? Bardziej podstawowym problemem jest oczywiście to, że nie rozumiem, jak wektory, wskaźniki i odnośniki naprawdę działają głęboko.

Answer 1

Twoje drugie podejście to probably illegal. Jednak w niektórych implementacjach standardowej biblioteki może działać. W takich przypadkach dodane obiekty zostaną skopiowane (w tym wszystkie ich dzieci - podczas kopiowania standardowego kontenera wszystkie elementy, które on zawiera, również zostaną skopiowane). Tak więc taka struktura danych byłaby odpowiednia tylko do reprezentowania drzewa.

Twoje pierwsze podejście, z drugiej strony, jest w porządku, ponieważ sam wskaźnik do niekompletnego typu jest prawidłowym typem (§3.9.2/3 - [basic.compound]) ^✝. Ponieważ przechowujesz tylko wskaźnik, obiekt nie zostanie skopiowany. Musisz jednak uważać, kiedy zaczynasz kasować ten wykres. W zależności od typu wykresu jesteś modelowania, istnieją trzy scenariusze podczas ich realizacji:

^{✝_{There are some restrictions. Zauważ, że w twoim przypadku typ jest tylko niekompletny w definicji (sn) - w miejscu, w którym faktycznie go używasz, sn jest kompletny, dlatego możesz go również usunąć.}}

Trees

W przypadku drzewa, każde dziecko ma dokładnie jednego rodzica. Tak więc, podczas usuwania struktury, zacząłbyś od katalogu głównego, a każdy węzeł musiałby po prostu usunąć wszystkie swoje elementy podrzędne. To działałoby rekursywnie na liście, które nie mają dzieci.

Aby skutecznie wdrożyć tę funkcję, można przechowywać dzieci w postaci boost::ptr_vector<sn>. W związku z tym nie będziesz musiał sam pisać destruktora - ptr_vector usunie wszystkie jego elementy.

Directed Acyclic Graphs (DAG)

W DAG węzeł może mieć wielu rodziców, więc trzeba uważać, aby nie usuwać tego samego węzła dwukrotnie (byłoby to zdarzyć, jeśli każdy węzeł po prostu usuwa wszystkie swoje dzieci - do tego powodu, ptr_vector nie będzie działać tutaj). Jednym ze sposobów poradzenia sobie z tym jest użycie liczenia referencji - każdy węzeł zlicza ile innych punktów wskazuje i tylko gdy licznik odniesie się do zera, węzeł jest faktycznie usuwany. Możesz zautomatyzować to poprzez przechowywanie węzłów w std::vector<std::shared_ptr<sn> > (lub boost::shared_ptr, jeśli używasz kompilatora sprzed C++ 11). shared_ptr zarządza wewnętrznie licznikiem referencji i usunie tylko obiekt, na który wskazuje, gdy nie ma już więcej obiektów wskazujących na ten obiekt (gdy licznik odniesień jest równy zero).

Cyclic Graphs

cyklicznie wykresie, węzeł może również jego własny nadrzędny (bezpośrednio, jeśli zawiera pętle lub pośrednio przez cykl). W ten sposób, jeśli każdy węzeł usunie wszystkie swoje dzieci, to spowoduje nieskończoną pętlę wywołań destruktora. A shared_ptr również może tu zawieść, ponieważ kiedy masz cycle of shared_ptr referencing each other, ich licznik odniesień nigdy nie osiągnie zera. Teraz nadszedł czas, aby pomyśleć o różnicy między posiadania obiektu i odniesienia odniesienia. Każdy węzeł powinien mieć dokładnie jednego rodzica, który jest jego właścicielem, ale może mieć kilka odwołań do niego. Właściciel i tylko właściciel jest odpowiedzialny za usunięcie tego węzła. Jak wyjaśniono w doskonałej odpowiedzi, którą podałem powyżej, można to zrealizować przy użyciu kombinacji shared_ptr i weak_ptr.

Answer 2

A.connected_to[0] = &B;

Czy skopiować coś: tymczasową wartość wskaźnika wyrażenia &B.

Klasy szablonów wektorowych zawsze zajmują się automatyczną budową i zniszczeniem kopii, ale kopiowanie konstrukcji typu pierwotnego jest równoznaczne z przypisaniem i zniszczeniem typu pierwotnego, w tym wskaźników, nie jest opcją.

Wskaźnik jest bardzo podstawowym typem - prawie nic nie jest automatycznie wykonywane przy użyciu wskaźników. Pod maską to tylko integralna wartość odpowiadająca adresowi w pamięci. Kiedy usuniesz wskaźnik, kompilator po prostu ufa ci, że wskaźnik przytrzymuje adres (lub "wskazuje na") obiekt odpowiedniego typu.

Na przykład, biorąc pod uwagę klasy Foo i bar, które nie są związane przez dziedziczenie:

Foo *ptr1, *ptr2; 
Bar *ptr3; 
    // All pointers are uninitialized. 
    // Dereferencing them is undefined behavior. Most likely a crash. 
    // The compiler will almost certainly issue a warning. 
ptr1= new Foo(); // ptr1 now points to a valid Foo. 
ptr2 = ptr1; // ptr2 points to the same Foo. 
ptr3=(Bar*)ptr1; // This is an obvious programmer error which I am making here for demonstration. 
// ptr3 points to the same block of memory as ptr1 & 2. 
// Dereferencing it is likely to do strange things. 
delete ptr1; // The compiler is allowed to set ptr1 to 0, but you can't rely on it. 
    // In either case dereferencing ptr1 is once again undefined behavior 
    // and the value of ptr2 is unchanged. 

Kompilator jest znacznie mniej prawdopodobne, aby wydać ostrzeżenie, jeśli uzna to za ptr1 dereferencjonowane po usunięciu niż przed inicjalizacji. Praktycznie nigdy nie wyda ostrzeżenia, jeśli usuniesz obiekt ptr2 po usunięciu obiektu przez ptr1. Jeśli nie jesteś ostrożny, tak jak ostrzegali cię inni, twój wektor wskaźników może spowodować nieumyślne wywołanie nieokreślonego zachowania w ten sposób.

I wprowadził bardzo źle odlew Foo* do Bar* zilustrować absolutną ufność kompilator w ciebie. Kompilator pozwala to zrobić i szczęśliwie potraktuje bity tak, jakby były pasku, gdy wyłączysz ptr3.

Biblioteka standardowa C++ udostępnia kilka klas szablonów, które oferują zachowanie podobne do wskaźnika z dużo bardziej automatycznym bezpieczeństwem. Na przykład, std::shared_pointer:

std::shared_ptr jest inteligentny wskaźnik, który zarządza żywotność obiektu, zazwyczaj przydzielane z new. Kilka obiektów shared_ptr może zarządzać tym samym obiektem; obiekt zostanie zniszczony, gdy ostatni pozostały do ​​niego wskaźnik zostanie zniszczony lub zresetowany. Obiekt jest zniszczony przy użyciu polecenia delete-expression lub niestandardowego deletera, który jest dostarczany do shared_ptr podczas budowy.

Jeśli w twoim środowisku nie ma jeszcze biblioteki standardowej C++ 11, może ona dostarczyć bibliotekę boost lub przestrzeń nazw std::tr1::. Oba zapewniają bardzo podobne shared_ptr. std::auto_ptr, które na pewno masz, jest podobne, ale pozwala tylko jednemu obiektowi auto_ptr odwoływać się do obiektu w określonym czasie. _{(C++ 11 wprowadza std::unique_ptr jako zamierzonego zamiennik auto_ptr. Na auto_ptr jest zgodne z większością std pojemników szablonu. unique_ptr może być umieszczony w pojemniku szablonu std::move).}

Możliwe jest wkręcona z tych klasy przez utrzymywanie lub uzyskiwanie wskaźnika i małpowanie z nim, np

Foo *basic_ptr=new Foo(); 
std::auto_ptr<Foo> fancy_ptr(basic_ptr); 
delete basic_ptr; // Oops! This statement broke our auto_ptr. 

Będziesz także je łamać, jeśli przechodzą w adresie zmiennej w automatycznym przechowywania:

Foo aFoo; 
std::auto_ptr<Foo> fancy_ptr(&aFoo); // automatic storage automatically breaks auto_ptr 

Jeśli po prostu zrobić std::shared_ptr<sn> fresh_sn(new sn()) a następnie użyć std::vector< std::shared_ptr<sn> > Będzie dobrze.