Nasıl uygulanacağı hakkında düşünceler?

Question

Bazı eski c kodlarını C++ içine yüklüyorum ve bir dizide uygulanan bağlantılı bir listeyle karşılaşıyorum. Öğe, basit bir yapıdır: dizini biliyorsanız, bir dizide, veriye hızlı erişim vardır. Bağlantılı liste yönü, öğelerin etrafında hareket etmesini ve listeden "silinmesini" sağlar. Öğeler, kullanım sıklığına (MRU için ve LRU için aşağı) göre listede taşınabilir.

Bunu uygulamak için başka bir dizi kullanmanın daha iyi bir yolunu bulmak istiyorum. STL'yi kullanmak isterdim, fakat hangi konteynerin en iyi kullanılacağından emin değilim.

Herhangi birinin bir fikri var mı?

Answer 1

bu bir bağlantılı liste olduğundan, muhtemelen std::list kullanmalıdır ...

başparmak kuralı listedeki rastgele konumlara unsurları eklemek gerektiğinde Bağlantılı bir listesini kullanmak istediğiniz veya olması rastgele öğeleri listeden sil. Temel olarak listenin sonuna/sonuna öğelerin eklenmesi/silinmesi gerekiyorsa, std::vector'u kullanmalısınız. Başlangıç ​​veya listenin sonuna/öğesine öğelerin eklenmesi/silinmesi gerekiyorsa, std::deque'u kullanmalısınız.

Unutmayın, burada olasılıklardan bahsediyoruz. Mavi bir ayda bir std::vector'un ortasına bir eleman eklemeniz gerekiyorsa, bu muhtemelen tamam olacaktır. Ancak bunu her zaman yapmanız gerekiyorsa, performans üzerinde büyük bir etkisi olacaktır, çünkü vektörün elemanlarını sürekli hareket ettirmesi ve muhtemelen belleğini yeniden tahsis etmesi gerekecektir.

Diğer taraftan, bir vektörün kullanılmasının avantajı, öğelerinin bellekte bitişik olmasıdır; bu, önbelleğe alma nedeniyle sırayla bunları kolayca geçirmeniz gerektiğinde performansı büyük ölçüde artırır.

Answer 2

Buraya bakın:

http://linuxsoftware.co.nz/cppcontainers.html

altta sağ konteyner seçmenize yardımcı olacak bir akış şeması var.

Answer 3

Bu listedeki veriler işaretçiler olduğundan, neden bağlantılı bir listeyle uğraşmak istesin? Küçük POD'lar için, std::vector genellikle en iyi ilk bahistir ve verilerinin işlemci önbellekleriyle birlikte daha iyi bir şekilde oynaması nedeniyle, teoride, bağlantılı bir listenin daha iyi olması gereken yerlerde bile, genellikle bağlantılı bir liste çıkarır. Bazı profiller performans sorunu olduğunu ve std::list'un daha iyi performans göstermesini bekleyene kadar std::vector seçerim.