Bağlantılı listeler neden düğümleri düğümlerin içinde depolamak yerine işaretçiler kullanıyor?

Daha önce Java ile bağlantılı listelerle çalıştım, ancak C ++ için çok yeniyim. Bana verilen bu düğüm sınıfını iyi bir projede kullanıyordum.

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

ama çok iyi cevaplanmayan bir sorum vardı. Kullanmak neden gerekli

Node *m_next;

listedeki bir sonraki düğüme işaret etmek yerine

Node m_next;

İşaretçi sürümünü kullanmanın daha iyi olduğunu anlıyorum; Gerçekleri tartışmayacağım, ama neden daha iyi olduğunu bilmiyorum. İşaretçinin bellek ayırma için nasıl daha iyi olduğu konusunda net bir cevap alamadım ve buradaki herhangi birinin bunu daha iyi anlamama yardımcı olabileceğini merak ediyordum.

114
Çünkü bağlantılı bir liste, bir hafıza adresinin işaretçilerinin bir listesidir. Java muhtemelen gerçek bağlantılı listeler içermez.
katma yazar Ryan McCullagh, kaynak
Java'da işaretçiler yok
katma yazar Ryan McCullagh, kaynak
@mckenzm Bu tür "kovalanmış" bağlantılı liste tasarımı hala oldukça yaygındır, bir avantaj, "boşları" takip etmenin doğru CPU komutuyla çok verimli bir şekilde yapılabilmesidir (bunları bir bitmapte tutun ve ilk bit set kullanın) benzeri talimatlar)
katma yazar Thomas, kaynak
Yığın Taşması başlattıktan sonra bu 6 yıldan daha da çoğalmaz mı?
katma yazar Peter Mortensen, kaynak
Bu sadece bir yol değildir ... Önceden tahsis edilmiş bir yapı dizisini, üyelerden biri referans olmak üzere kolayca kullanabilirsiniz. Dizi boyutu <= 256 ise, başvuru "düğüm" sayısının belirli bir eşiğin altında olduğu biliniyorsa yararlı olabilecek bir uint8_t (uint {16,32} _t için benzer) olabilir. 64 bit üzerindeki alan tasarrufu 256 * 7 (karakter), 65536 * 6 (kısa) vb ... çünkü bir işaretçi 8 bayt alır. Bunu yapmak mantıklı geldiğinde her programcıya bir egzersiz olarak bırakılmıştır.
katma yazar technosaurus, kaynak
@jamesqf - Hayır, sadece indekslenmiş bir dizi kullanır (temel olarak önceden tahsis edilmiş bir hafıza havuzu olarak), hala bir bellek adresi yerine dizi göstergesini kullanarak (işaretçi matematiği sayesinde 64 bitlik bir adres için 8 bayttan ziyade büyük yapılar için bile 1 bayt kadar az gösterilebilir) Ayrıca diski okumayı ve diske yazmayı kolaylaştırır ve mmap bile kullanabilir. Dezavantajı, "kaldırılmış" düğümleri yeniden kullanmak için ekstra kod gerekmesidir (malloc gerekli olmasa da, genel kazanç)
katma yazar technosaurus, kaynak
@self Java, açıkça kullanmayacağınız işaretçilere sahiptir.
katma yazar m0meni, kaynak
Lütfen Java hakkında bildiğiniz her şeyi unutmayın. C ++ ve Java, belleği temelde farklı şekillerde işler. Git, kitap önerileri için bu soruyu inceleyin; ve oku. Hepimize büyük bir iyilik yapacaksın.
katma yazar Rob K, kaynak
İpucu: Düğüm 'in boyutu ne olur?
katma yazar Angew, kaynak
Afedersiniz beni? Neden her şeyin bir işaretçi olduğu bir dilin bağlantılı listeleri yoktur?
katma yazar Angew, kaynak
@self: Java, C ve C ++ 'daki işaretçilerle aynı semantikliğe sahip olan nesne referanslarına sahiptir.
katma yazar Mike Seymour, kaynak
@Davor: Düzeltme için teşekkürler, onları her zaman "referans" olarak adlandırıldığını gördüm ve resmi terminolojiyi öğrenmek için hiç sıkıntı yaşamadım.
katma yazar Mike Seymour, kaynak
katma yazar Cole Johnson, kaynak
Baştan aşağı kapar bir seçenek değildir . Çılgınlık bir yerde sona ermeli.
katma yazar WhozCraig, kaynak
C ve C ++ 'nın Java'dan nesne işaretçisi ve referanslar açısından ne kadar farklı olduğunu not etmek önemlidir. Düğüm m_next bir düğüme başvuru değil, Düğüm öğesinin tamamı için depolandı.
katma yazar Brian Cain, kaynak
@dwcanillas: boost::optional ve std::optional nesnede her ikisi de en azından sizeof değerine eşit miktarda bir alan ayırır ( T) . Zenith'in cevabında açıklanan nedenlerden dolayı, struct node {std :: isteğe bağlı n; }; çalışmıyor.
katma yazar Bill Lynch, kaynak
@Davor Bağlantılı liste veri yapısının türüdür, java.util.LinkedList , java.util.List 'in özel bir uygulamasıdır. Muhtemelen eski anlamını (boşlukla) kullanmıyordu. [Eğer sıkı takma ve sanal hafıza gibi süslü kavramları görmezden gelirsek, o zaman tüm fiziksel hafıza sadece bir dizidir ve işaretçiler bu dizi içinde indekslenir, böylece herhangi bir bağlantılı liste bu şekilde uygulanır].
katma yazar Maciej Piechotka, kaynak
Hafızanın pahalı olduğu ve tahsis edilmesinin pahalı olduğu eski zamanlarda, bir zamanlar 100 düğüm için hafızayı önceden tahsis edeceğimizi söyler ve “boşları” takip etmek zorunda kalırız, bu nedenle “dizi” ish'in dayanaktan kalan anestezi olabilir. bağlantılı listeler (C cinsinden). Onlar hala bağlantılı listelerdi çünkü bitişik değillerdi.
katma yazar mckenzm, kaynak
@technosaurus - hayır, bu bir dizi listesi, bağlantılı liste değil. Bağlantılı liste, liste arabiriminin belirli bir uygulamasıdır ve açıkladığınız dizi listesidir. İkisi de aynı uygulamaları farklı uygulamalarla yapıyorlar.
katma yazar Davor, kaynak
@MikeSeymour - Java özelliğinde, kelimenin tam anlamıyla işaretçiler olarak adlandırılır. Bu yüzden NullReferenceException değil, Java’dan NullPointerException aldığınızda.
katma yazar Davor, kaynak
@ BillLynch kuyu TIL. Sanırım bu mantıklı
katma yazar dwcanillas, kaynak
@zenith'i teknik olarak boost :: isteğe bağlı olarak kullanabilirsiniz, ancak aslında temelde aynı şey - bir nesnenin boşuna sahip olmasının ve aynı tipteki başka bir nesneye referans içermesinin bir yolu.
katma yazar dwcanillas, kaynak
@technosaurus: Ama sonra sahip olduğunuz bağlantılı bir liste değil, dizine alınmış bir dizi.
katma yazar jamesqf, kaynak

10 cevap

Sadece daha iyi değil, mümkün olan tek yol.

Kendi içinde bir Düğüm nesnesi sakladıysanız, sizeof (Node) ne olurdu? sizeof (int) + sizeof (Node) olacaktır, bu sizeof (int) + (sizeof (int) + sizeof (Node)) 'a eşit olacaktır. sizeof (int) + (sizeof (int) + (sizeof (int) + sizeof (Düğüm))) 'a eşit olacaktır, vb.

Böyle bir nesne var olamaz. İmkansız .

216
katma
@Voo, Haskell'in topak kullanmasına gerek yok; Bu sadece GHC'nin uyguladığı yöntem.
katma yazar PyRulez, kaynak
@Voo Bir düğüm, bir değer ve null veya bir değer ve bir düğüm içeren bir demetdir. İşte durdurma koşulu olan ve bir sorun olan özyinelemeli bir tanım. Bu gibi nesneleri tanımlamak mümkün değildir - aynı zamanda son derece yaygındır, işte Haskell'de çalışan gerçek (kötü) kod - veri Listesi a = Düğüm a ( Liste a) | Nil .
katma yazar Benjamin Gruenbaum, kaynak
İpucu (işe yarıyor, çünkü yapmamanız için alan ayırıyor, daha ziyade tembel, çünkü Haskell, sadece gerektiğinde değerlendirme yapan katı olmayan bir dil.
katma yazar Benjamin Gruenbaum, kaynak
@Voo: Bu bağlamda sabit boyutta neyi kastettiğinizi veya son unsurun neden farklı olması gerektiğinden emin değilim. Bağlantılı bir listenin, verilerin sonunun nerede olduğunu belirtmek için ayrı bir mekanizmaya ihtiyaç duymak yerine, boş bir işaretçi ile sonlandırılabileceği doğrudur, ancak bildiriminiz bağlantı kullanmıyorsa, bu itirazda bulunuyorum. o zaman tanımı gereği, “bildiriminizin uygulanması doğal olarak mümkün değildir” değil, “bağlantılı bir liste değildir”.
katma yazar Harry Johnston, kaynak
@Voo: Verilen örnekte, Düğüm matematiksel olarak sonsuz bir int dizisine eşdeğerdir. Sınırsız bir diziyi, uygun bir şekilde büyük bir adres alanı bölümü ayırarak (yani, gerçekten işleyebildiğiniz bellek miktarından daha büyük) ve işletim sisteminin gerektiğinde belleği işlemesini sağlayarak gerçekleştirebilirsiniz. Diziyi bu şekilde uygulamak için yerleştirmeniz gereken tek kısıtlama, n + 1 elemanını referans almanın tek yolu n elemanı olduğu için bu bağlamda iyi olan seyrek olamayacağında ısrar etmektir. Adres alanı tükenmeden önce kaynak tükeniyor.
katma yazar Harry Johnston, kaynak
Alternatif olarak, hem çoklu adres alanlarına (bu gerçek bir şey ama artık modası geçmiş) hem de isteğe bağlı adres uzunluklarına (bildiğim kadarıyla hiç var olmadı) izin veren bir işlemci mimarisi olduğunu varsayabilirsiniz. :-)
katma yazar Harry Johnston, kaynak
@ Carcigenicate, Node nesnesindeki bazı işlevleri değerlendirmek/yürütmekle ilgili değildir - bu, herhangi bir değerlendirme yapılmadan önce derleme zamanında belirlenmesi gereken her bir Düğüm örneği bellek düzeniyle ilgilidir.
katma yazar Peteris, kaynak
@svick Aslında düşündüğüm Haskell. Dil izin verdiğinde sonsuz listeler eğlencelidir. Java'da asla böyle bir şey denemedim, bu yüzden onunla konuşamam.
katma yazar Carcigenicate, kaynak
* Lazly değerlendirilmediği sürece. Sınırsız listeler, kesin bir değerlendirme ile mümkün değildir.
katma yazar Carcigenicate, kaynak
@David aklım karıştı. Öncelikle bunun mantıksal olarak imkansız olduğuna katılıyorsunuz, fakat sonra bunu düşünmek mi istiyorsunuz? C veya C ++ herhangi bir şeyi kaldırın - görebildiğim kadarıyla hayal edebileceğiniz herhangi bir dilde imkansız. Bu yapı, tanım gereği sonsuz bir özyinelemede ve bir dereceye kadar dolaysızlık olmadan bunu kıramazız.
katma yazar Voo, kaynak
@DavidK Bunu yapmak mantıklı değil. Burada bir işaretleyiciye (gerçekten bir dolaylı) ihtiyacınız var - dilin onu sizden gizleyebildiğinden emin olun, ama sonuçta bu şekilde olmaz.
katma yazar Voo, kaynak
@HarryJohnston Ancak her bağlantılı listenin büyüklüğü sabittir ve son elemanın farklı olması gerektiğinden, artık artık sonsuz özyinelemeli bir tanım değildir. İşaretçi davasında, işaretçilerin bunu aşması için kodlamanın keyfi bir uzunluğuna ihtiyacımız olacaktı, ancak mümkün olacaktı.
katma yazar Voo, kaynak
@DavidK Bana yapının matematiksel tanımını yap, o zaman içinde sonsuz bir özyineleme yok. Bunu yapabiliyorsanız, bunu yapmanın en azından teorik olarak mümkün olduğunu gösterdiniz (bu gece çok fazla boş vaktim varsa, bunun imkansız olduğunu kanıtlayabilirim ..). Tembel değerlendirmenin bununla hiçbir ilgisi yok (geçmişte Haskell'de programladım, konsept bana yabancı değil gibi) - hala yaratılışta thunk için yer ayırıyorsunuz (ve dolaylı olarak söz konusu olan yere giriyor) tekrar yerleştirin).
katma yazar Voo, kaynak
@ benjamin Aslında şunu söyledim (çünkü aksi halde birisinin bunu ortaya koyacağını biliyordum - pek yardımcı olmadı) Haskell'in thunks'ı yaratılış sırasında tahsis ettiğini ve bu nedenle çalıştığını çünkü bu thunklar bize ihtiyaç duyduğumuz yönlendirmeyi verdi. Bu, kılık değiştirmiş fazladan veri içeren bir göstergeden başka bir şey değil
katma yazar Voo, kaynak
@BenjaminGruenbaum İşaretçileri içeren bir yapı tanımlıyorsunuz. Sadece Haskell'in açıkça onu işaretçi olarak çağırmasını gerektirmediği için, bunun böyle bir şekilde uygulanmadığı anlamına gelmez.
katma yazar Aaron Dufour, kaynak
@Voo Sorunun konusu C ++ ve bu bağlamda bu veri yapısı mümkün değil. Fakat C ++ 'da mantıklı bir zorunluluktan ziyade diğer dillere alışkanlık dışı teslim etme eğiliminde olduğumuza dair birçok varsayım var. Yukarıdaki ilk yoruma bakınız: "Lazly değerlendirilmediği sürece." Bu, C dilinin bize veri yapıları hakkında düşünmeyi öğrettiğine tamamen yabancı bir kavram; ancak bu, düşünülebilecek her dilde mantıklı olarak imkansız olduğu anlamına gelmez.
katma yazar David K, kaynak
Matematiksel olarak, veri yapısı , bir Turing makinesinin kasetlerinden biri gibi (ki bu işlemin klasik matematiksel modellerden biri olduğu gibi), sonsuz özyinelemeye sahip olacaktır. Uygulamada böyle bir yapıyı gerçekten uygulamak faydalı olabilir mi? Şüpheliyim. İşaretçileri bir düğümden diğerine perde arkasını kullanmayacak şekilde yapmak mümkün mü? Evet, ancak sonuçta ortaya çıkan performansı beğenmeyebilirsiniz.
katma yazar David K, kaynak
@Peteris Düğüm tahsisinin sanal bellekte nerede biteceğini bilmek konusunda ısrar edememiş olsaydık, C ve C ++ 'ın yaptığı gibi, belki de en az bir tane bir liste içinde bir düğümü diğerine depolayabilirdik. Bununla birlikte, daha yüksek bir adrese başka bir şey tahsis etmek sorunlu olabilir. :-) Ama bu şekilde çalışan hiçbir dil bilmiyorum.
katma yazar David K, kaynak
@Voo Evet, mantıksal olarak imkansızdır, ancak daha önce ifade edilen nokta (yorum yapmadan önce bile), bunun en azından kısmen C ve C ++ dillerinin tasarımından kaynaklanıyor olmasıdır. Veri yapısının mümkün olduğu alternatif bir dili düşünmeyi eğlenceli buluyorum. Ancak daha önce söylediklerimi tekrarlamak için, gerçekte, Bu şekilde çalışan herhangi bir dili bilmiyorum.
katma yazar David K, kaynak

Java’da

Node m_node

işaretçiyi başka bir düğüme depolar. Bu konuda başka seçeneğin yok. C ++ dilinde

Node *m_node

aynı şeyi ifade eder. Aradaki fark, C ++ 'da nesneyi aslında bir göstericinin aksine saklayabilmenizdir. Bu yüzden bir işaretçi istediğini söylemek zorundasın. C ++ dilinde:

Node m_node

düğümü tam burada depolamak anlamına gelir (ve bir liste için açık bir şekilde çalışamaz - özyinelemeli bir yapıya sahip olursunuz).

175
katma
Bu kabul edilen cevap olmalı.
katma yazar Salman A, kaynak
boyut veya hız sorunu değil - imkansızlık sorunu. İçerilen Node nesnesi, Node nesnesi içerecek bir Node nesnesi içerecektir ... Aslında onu derlemek imkansız
katma yazar pm100, kaynak
@ pm100 Demek istediğim bu. C ++ belirtiminin bunu engelleyip engellemeyeceğinden emin değilim, ancak bir dil derlenmişse derlenmiş kod tekrar derlenmiş kurucunun başlangıcına atlamaya devam edecek şekilde derlenmişse derlemek mümkün olacaktır; ancak programcı bunu yapıcıda doğru şekilde kullanmazsa, sonsuz bir döngü olacaktır.
katma yazar Panzercrisis, kaynak
Ancak gerçekte tek istediğiniz şey listedeki hangisinin hangisi olduğunu göstermenin bir yolu, aslında ilk Düğüm içinde olan bir Düğüm değil. Yani, temelde Java'nın ilkellerin aksine nesneleri nasıl işlediğini gösteren bir işaretçi yaratırsınız. Bir yöntemi çağırdığınızda veya bir değişken yaptığınızda, Java nesnenin bir kopyasını, hatta nesnenin kendisini saklamaz; bir nesneye yapılan atıfta bulunur, bu temelde etrafına sarılmış bir küçük çocuk eldiveni olan bir işaretçidir. Her iki cevabın temelde söylediği de budur.
katma yazar Panzercrisis, kaynak
@ AR7 Her ikisi de aynı açıklamaları yapıyorlar, iki farklı yaklaşımla. Bunu "normal" bir değişken olarak ilan ettiyseniz, o zaman bir yapıcı ilk kez arandığında, bunu yeni bir örneğe yerleştirirdi. Fakat bunu başlatmayı bitirmeden önce - birincinin kurucusu bitmeden önce - üye Düğüm 'in kendi kurucusu çağrılacak ve başka bir yeni örneği başlatacaktı ... ve sonsuz sözde özyineleme. Gerçekten bir performans sorunu olduğu için tamamen katı ve gerçek anlamda çok büyük bir konu değil.
katma yazar Panzercrisis, kaynak
OP'nin ana diliyle karşılaştırılması için 1+.
katma yazar Paul Draper, kaynak
@ abligh Neden öyleyse? Java Node boş olabilir, oysa C ++ Node & olamaz. Öte yandan, Düğüm * boş olabilir, bu da Java'yı Düğüm ile aynı yapar.
katma yazar emlai, kaynak
@ abligh Aslında, işaretçinin değeri (bellek adresi) her iki durumda da kopyalanır.
katma yazar emlai, kaynak
@Panzercrisis İkisinin de aynı açıklaması yaptığının farkındayım. Bununla birlikte, bu yaklaşım benim için yararlı değildi çünkü zaten anladığım şeye odaklanmıştı: işaretçilerin C ++ 'da nasıl çalıştığı ve işaretçilerin Java'da nasıl kullanıldığı. Kabul edilen cevap, özellikle olarak işaretlenmiş, neden bir imleç kullanmamasının imkansız olacağı, çünkü boyut hesaplanamamaktadır. Öte yandan, bu bir daha belirsiz bir şekilde “özyinelemeli bir yapı” olarak bıraktı. P. Az önce yazdığın açıklama, her ikisinden de daha iyi açıklıyor: D.
katma yazar m0meni, kaynak
@SalmanA Bunu zaten biliyordum. Sadece neden bir cevaplayıcı olmadan işe yaramayacağını bilmek istedim.
katma yazar m0meni, kaynak
@zenith - mükemmel bir eşleşme değil, örneğin; node1 = m_node``. Java'da, m_node` başvuru olarak tanımlanmışsa, kod C ++ 'ya benzer şekilde çalışır, yani hiçbir şey kopyalanmaz.
katma yazar abligh, kaynak
IMHO Java'nın Düğümü m_node , C ++ 'nın Düğümü ve m_node ' sine, yani bir işaretçi yerine bir referansa çok benzer.
katma yazar abligh, kaynak

C ++, Java değil. Yazarken

Node m_next;

Java’da bu yazıyla aynı

Node* m_next;

C ++ 'da. Java'da, işaretçi örtük, C ++ ise açıktır. Eğer yazarsan

Node m_next;

C ++ 'da, tanımladığınız nesnenin içine bir Node örneği koyarsınız. Her zaman oradadır ve ihmal edilemez, new ile ayrılamaz ve kaldırılamaz. Bu etkinin Java'da elde edilmesi imkansızdır ve Java'nın aynı sözdizimi ile yaptıklarından tamamen farklıdır.

38
katma
@Falco Gerçek, miras, temel sınıfların yerinde yer almasının bir şeklidir. Ancak, Java çoklu kalıtıma izin vermediğinden (C ++ 'ın aksine), kalıtım yoluyla yalnızca önceden var olan başka bir sınıfın örneğini alabilirsiniz. Bu nedenle mirastan, yerinde üye olmanın yerine geçecek bir yedek olarak düşünmezdim.
katma yazar cmaster, kaynak
SuperNode, Düğümü uzatırsa, Java'da benzer bir şey elde etmek için muhtemelen "genişletme" olur, SuperNodes, Düğümün tüm Niteliklerini içerir ve tüm ek alanı ayırmak zorunda kalır. Yani Java’da “Düğüm Düğümü Uzatıyor” i yapamazsınız.
katma yazar Falco, kaynak

Bir işaretçi kullanıyorsunuz, aksi halde kodunuz:

class Node
{
   //etc
   Node m_next; //non-pointer
};

…would not compile, as the compiler cannot compute the size of Node. This is because it depends on itself — which means the compiler cannot decide how much memory it would consume.

27
katma
@ Tommalar: Biri Doğal Sayıların bile gittiğine işaret edebilir. (-Perdantik üst geçiyor: p)
katma yazar bitmask, kaynak
Daha kötüsü, geçerli bir boyut yok: k == sizeof (Düğüm) tutarsa ​​ve türünüzde veri varsa, bu sizeof (Düğüm) = k + sizeof (Veri) değerini de tutması gerekir. = sizeof (Node) + sizeof (Data) ve sonra sizeof (Node)> sizeof (Node) .
katma yazar bitmask, kaynak
@k_g Peki, C/C ++ standardı, sizeof 'ın dönüş değerinin imzasız bir integral tip olması şartı ile zorunludur, bu nedenle transfinit ve hatta gerçek boyutlar umudunu giderir. (daha da bilgisel olmak!: p)
katma yazar Thomas, kaynak
Aslında, Düğüm bile bu snippet'in sonundan önce tanımlanmadı, bu yüzden içinde gerçekten kullanamazsınız. İşaretçilerin henüz ilan edilmemiş bir sınıfa işaretçi olarak açıkça bildirilmesine izin vermek, bu tür yapıları mümkün kılmak için her zaman açıkça işaretçilere gerek kalmadan dilin izin verdiği küçük bir hiledir.
katma yazar osa, kaynak
@ bitmask, gerçek sayılarda geçerli bir boyut yok. Transinfinitlere izin verirseniz, aleph_0 çalışır. (Sadece aşırı bilgiçlik :-))
katma yazar k_g, kaynak

İkincisi ( Düğüm m_next ) düğümü içermelidir . Bunu göstermezdi. Ve o zaman hiçbir element bağlantısı olmazdı.

13
katma
Teknik olarak hala bağlantı kurmayacak mıydı, çünkü düğüm içeren bir düğüm içeren bir düğüm olacaktı ve böyle devam eder mi?
katma yazar m0meni, kaynak
@ AR7: Hayır, çevreleme kelimenin tam anlamıyla nesnenin içinde ona bağlı değil demektir.
katma yazar Mike Seymour, kaynak
Daha da kötüsü, bir nesnenin aynı türde bir şey içermesi mantıklı olarak imkansız olurdu.
katma yazar Mike Seymour, kaynak

Tanımladığınız yaklaşım yalnızca C ++ ile değil, aynı zamanda (çoğunlukla) alt küme dili C ile de uyumludur. C tarzı bir bağlantılı liste geliştirmeyi öğrenmek, düşük seviyeli programlama tekniklerini (manuel bellek yönetimi gibi) tanıtmak için iyi bir yoldur, ancak genellikle modern C ++ için en iyi uygulama değil 'dir. gelişme.

Aşağıda, C ++ 'da bir öğe listesinin nasıl yönetileceği konusunda dört varyasyon uyguladım.

  1. raw_pointer_demo uses the same approach as yours -- manual memory management required with the use of raw pointers. The use of C++ here is only for syntactic-sugar, and the approach used is otherwise compatible with the C language.
  2. In shared_pointer_demo the list management is still done manually, but the memory management is automatic (doesn't use raw pointers). This is very similar to what you have probably experienced with Java.
  3. std_list_demo uses the standard-library list container. This shows how much easier things get if you rely on existing libraries rather than rolling your own.
  4. std_vector_demo uses the standard-library vector container. This manages the list storage in a single contiguous memory allocation. In other words, there aren't pointers to individual elements. For certain rather extreme cases, this may become significantly inefficient. For typical cases, however, this is the recommended best practice for list management in C++.

Bunların arasında: Bunlardan yalnızca raw_pointer_demo aslında hafızanın “sızmasını” önlemek için listenin açıkça yok edilmesini gerektirir. Diğer üç yöntem, konteyner kapsam dışı kaldığında (işlevin sonunda) listeyi ve içeriğini otomatik olarak yok eder. Var olan nokta: C ++ bu konuda çok "Java benzeri" olma yeteneğine sahiptir - ancak yalnızca programınız hizmetinizde olan üst düzey araçları kullanarak geliştirmeyi seçerseniz.


/*BINFMTCXX: -Wall -Werror -std=c++11
*/

#include 
#include 
#include 
#include 
#include 
#include 
using std::cerr;

/** Brief   Create a list, show it, then destroy it */
void raw_pointer_demo()
{
    cerr << "\n" << "raw_pointer_demo()..." << "\n";

    struct Node
    {
        Node(int data, Node *next) : data(data), next(next) {}
        int data;
        Node *next;
    };

    Node * items = 0;
    items = new Node(1,items);
    items = new Node(7,items);
    items = new Node(3,items);
    items = new Node(9,items);

    for (Node *i = items; i != 0; i = i->next)
        cerr << (i==items?"":", ") << i->data;
    cerr << "\n";

   //Erase the entire list
    while (items) {
        Node *temp = items;
        items = items->next;
        delete temp;
    }
}

raw_pointer_demo()...
9, 3, 7, 1

/** Brief   Create a list, show it, then destroy it */
void shared_pointer_demo()
{
    cerr << "\n" << "shared_pointer_demo()..." << "\n";

    struct Node;//Forward declaration of 'Node' required for typedef
    typedef std::shared_ptr Node_reference;

    struct Node
    {
        Node(int data, std::shared_ptr next ) : data(data), next(next) {}
        int data;
        Node_reference next;
    };

    Node_reference items = 0;
    items.reset( new Node(1,items) );
    items.reset( new Node(7,items) );
    items.reset( new Node(3,items) );
    items.reset( new Node(9,items) );

    for (Node_reference i = items; i != 0; i = i->next)
        cerr << (i==items?"":", ") << i->data;
    cerr<<"\n";

   //Erase the entire list
    while (items)
        items = items->next;
}

shared_pointer_demo()...
9, 3, 7, 1

/** Brief   Show the contents of a standard container */
template< typename C >
void show(std::string const & msg, C const & container)
{
    cerr << msg;
    bool first = true;
    for ( int i : container )
        cerr << (first?" ":", ") << i, first = false;
    cerr<<"\n";
}

/** Brief  Create a list, manipulate it, then destroy it */
void std_list_demo()
{
    cerr << "\n" << "std_list_demo()..." << "\n";

   //Initial list of integers
    std::list items = { 9, 3, 7, 1 };
    show( "A: ", items );

   //Insert '8' before '3'
    items.insert(std::find( items.begin(), items.end(), 3), 8);
    show("B: ", items);

   //Sort the list
    items.sort();
    show( "C: ", items);

   //Erase '7'
    items.erase(std::find(items.begin(), items.end(), 7));
    show("D: ", items);

   //Erase the entire list
    items.clear();
    show("E: ", items);
}

std_list_demo()...
A:  9, 3, 7, 1
B:  9, 8, 3, 7, 1
C:  1, 3, 7, 8, 9
D:  1, 3, 8, 9
E:

/** brief  Create a list, manipulate it, then destroy it */
void std_vector_demo()
{
    cerr << "\n" << "std_vector_demo()..." << "\n";

   //Initial list of integers
    std::vector items = { 9, 3, 7, 1 };
    show( "A: ", items );

   //Insert '8' before '3'
    items.insert(std::find(items.begin(), items.end(), 3), 8);
    show( "B: ", items );

   //Sort the list
    sort(items.begin(), items.end());
    show("C: ", items);

   //Erase '7'
    items.erase( std::find( items.begin(), items.end(), 7 ) );
    show("D: ", items);

   //Erase the entire list
    items.clear();
    show("E: ", items);
}

std_vector_demo()...
A:  9, 3, 7, 1
B:  9, 8, 3, 7, 1
C:  1, 3, 7, 8, 9
D:  1, 3, 8, 9
E:

int main()
{
    raw_pointer_demo();
    shared_pointer_demo();
    std_list_demo();
    std_vector_demo();
}
9
katma
Yukarıdaki Node_reference bildirimi, Java ve C ++ arasındaki en ilginç dil düzeyindeki farklılıklardan birine yöneliktir. Java'da, Node tipinde bir nesne bildirmek, ayrı olarak tahsis edilen bir nesneye bir referans kullanır. C ++ 'da, başvuru (işaretçi) ve doğrudan (yığın) ayırma seçeneğine sahipsiniz - bu nedenle ayrımın açıkça ele alınması gerekir. Çoğu durumda, liste öğeleri için olmasa da, doğrudan tahsisat kullanırsınız.
katma yazar nobar, kaynak

Genel Bakış

C ++ 'da nesnelere başvuru yapmanın ve ayırmanın 2 yolu vardır, Java'da ise sadece bir yol vardır.

Bunu açıklamak için, aşağıdaki şemalar, nesnelerin bellekte nasıl depolandıklarını göstermektedir.

1.1 C ++ İşaretçisiz öğeler

class AddressClass
{
  public:
    int      Code;
    char[50] Street;
    char[10] Number;
    char[50] POBox;
    char[50] City;
    char[50] State;
    char[50] Country;
};

class CustomerClass
{
  public:
    int          Code;
    char[50]     FirstName;
    char[50]     LastName;
   //"Address" IS NOT A pointer !!!
    AddressClass Address;
};

int main(...)
{
   CustomerClass MyCustomer();
     MyCustomer.Code = 1;
     strcpy(MyCustomer.FirstName, "John");
     strcpy(MyCustomer.LastName, "Doe");
     MyCustomer.Address.Code = 2;
     strcpy(MyCustomer.Address.Street, "Blue River");
     strcpy(MyCustomer.Address.Number, "2231 A");

   return 0;
}//int main (...)

.......................................
..+---------------------------------+..
..|          AddressClass           |..
..+---------------------------------+..
..| [+] int:      Code              |..
..| [+] char[50]: Street            |..
..| [+] char[10]: Number            |..
..| [+] char[50]: POBox             |..
..| [+] char[50]: City              |..
..| [+] char[50]: State             |..
..| [+] char[50]: Country           |..
..+---------------------------------+..
.......................................
..+---------------------------------+..
..|          CustomerClass          |..
..+---------------------------------+..
..| [+] int:      Code              |..
..| [+] char[50]: FirstName         |..
..| [+] char[50]: LastName          |..
..+---------------------------------+..
..| [+] AddressClass: Address       |..
..| +-----------------------------+ |..
..| | [+] int:      Code          | |..
..| | [+] char[50]: Street        | |..
..| | [+] char[10]: Number        | |..
..| | [+] char[50]: POBox         | |..
..| | [+] char[50]: City          | |..
..| | [+] char[50]: State         | |..
..| | [+] char[50]: Country       | |..
..| +-----------------------------+ |..
..+---------------------------------+..
.......................................

Warning: The C++ syntax used in this example, is similar to the syntax in Java. But, the memory allocation is different.

1.2 C ++ İşaretçileri kullanan öğeler

class AddressClass
{
  public:
    int      Code;
    char[50] Street;
    char[10] Number;
    char[50] POBox;
    char[50] City;
    char[50] State;
    char[50] Country;
};

class CustomerClass
{
  public:
    int           Code;
    char[50]      FirstName;
    char[50]      LastName;
   //"Address" IS A pointer !!!
    AddressClass* Address;
};

.......................................
..+-----------------------------+......
..|        AddressClass         +<--+..
..+-----------------------------+...|..
..| [+] int:      Code          |...|..
..| [+] char[50]: Street        |...|..
..| [+] char[10]: Number        |...|..
..| [+] char[50]: POBox         |...|..
..| [+] char[50]: City          |...|..
..| [+] char[50]: State         |...|..
..| [+] char[50]: Country       |...|..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|         CustomerClass       |...|..
..+-----------------------------+...|..
..| [+] int:      Code          |...|..
..| [+] char[50]: FirstName     |...|..
..| [+] char[50]: LastName      |...|..
..| [+] AddressClass*: Address  +---+..
..+-----------------------------+......
.......................................

int main(...)
{
   CustomerClass* MyCustomer = new CustomerClass();
     MyCustomer->Code = 1;
     strcpy(MyCustomer->FirstName, "John");
     strcpy(MyCustomer->LastName, "Doe");

     AddressClass* MyCustomer->Address = new AddressClass();
     MyCustomer->Address->Code = 2;
     strcpy(MyCustomer->Address->Street, "Blue River");
     strcpy(MyCustomer->Address->Number, "2231 A");

     free MyCustomer->Address();
     free MyCustomer();

   return 0;
}//int main (...)

Her iki yol arasındaki farkı kontrol ederseniz, ilk teknikte, adres öğesinin müşteriye tahsis edildiğini, ikincisinde ise her adresi açıkça oluşturmalısınız.

Warning: Java allocates objects in memory like this second technique, but, the syntax is like the first way, which may be confusing to newcomers to "C++".

Uygulama

Yani liste örneğiniz, aşağıdaki örneğe benzer bir şey olabilir.

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

.......................................
..+-----------------------------+......
..|            Node             |......
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|            Node             +<--+..
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|            Node             +<--+..
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................v..
...................................[X].
.......................................

Özet

Bağlantılı Listede değişken miktarda öğe bulunduğundan, bellek gerektiğinde ve mümkün olduğu şekilde tahsis edilir.

GÜNCELLEŞTİRME:

Ayrıca, @haccks adlı kişinin yayınına yorum yaptığı için bahsetmeye değer.

Bu bazen referanslar veya nesne işaretçileri iç içe geçmiş öğeleri gösterir (a.k.a. "U.M.L. Kompozisyon").

Ve bazen, referanslar veya nesne işaretçileri dış maddeleri belirtir (a.k.a. "U.M.L. Agregation").

Ancak, aynı sınıfın iç içe geçmiş öğeleri "işaretçi olmayan" teknikle uygulanamaz.

8
katma

Bir yan notta, bir sınıfın veya yapının ilk üyesi bir sonraki işaretçi ise (bu nedenle sanal işlevler veya bir sınıfın diğer hiçbir özelliği, bir sınıfın veya yapının ilk üyesi değil), o zaman Sadece bir sonraki göstericiyle "base" sınıfını veya yapısını kullanabilir ve ekleme, önce ekleme, önden alma, ... gibi temel bağlantılı liste işlemleri için ortak kod kullanabilirsiniz. Bunun nedeni, C/C ++, bir sınıf veya yapının ilk üyesinin adresinin, sınıf veya yapının adresiyle aynı olduğunu garanti etmesidir. Temel düğüm sınıfı veya yapı yalnızca temel bağlı liste işlevleri tarafından kullanılacak bir sonraki göstericiye sahip olacak, daha sonra temel düğüm tipi ile "türetilmiş" düğüm tipleri arasında dönüşüm yapmak için gerektiği gibi tip tahmini kullanılacaktır. Yan not - C ++ 'da, temel düğüm sınıfının sadece bir sonraki işaretçisine sahip olması durumunda, türetilmiş sınıfların sanal fonksiyonlara sahip olamayacağını varsayıyorum.

7
katma

İşaretçileri bağlantılı bir listede kullanmak neden daha iyidir?

Bunun nedeni, bir Düğüm nesnesi oluşturduğunuzda, derleyicinin o nesneye bellek ayırması ve bunun için nesne boyutunun hesaplanmasıdır.
İşaretçinin herhangi bir türe göre boyutu derleyici olarak bilinir ve bu nedenle nesnenin kendine ait işaretçi işaretçi boyutu ile hesaplanabilir.

Bunun yerine Düğüm m_node kullanılırsa, derleyicinin Düğüm boyutu hakkında hiçbir fikri yoktur ve hesaplamasının sonsuz özyinelemesine sıkışır. sizeof (Düğüm) . Her zaman hatırlayın: bir sınıf kendi türünde bir üye içeremez .

6
katma

Because this in C++

int main (..)
{
    MyClass myObject;

   //or

    MyClass * myObjectPointer = new MyClass();

    ..
}

is equivalent to this in Java

public static void main (..)
{
    MyClass myObjectReference = new MyClass();
}

her ikisi de varsayılan yapıcıyı kullanarak Sınıfım adlı yeni bir nesne oluşturur.

5
katma