SORU
9 HAZİRAN 2011, PERŞEMBE


Gerçekten STL bir deque nedir?

STL kapları ve onlar gerçekten kim olduğunu ne için (veri yapısı kullanılır Yani) çalışıyor, ve bakıyordumdequedurdu bana: ilk düşündüğüm o oldu bir çift bağlı liste, izin verirsen ekleme ve silme her iki ucu sabit bir zaman, ama ben sorunlu tarafından the promise made operator [] içinde yapılacak olan sabit zaman. Bağlantılı liste, rastgele erişim O(n) olması gerekir, değil mi?

Ve eğer dinamik bir dizi olsaydı, sürekli add elements? Tahsisat meydana gelebilecek, ve O(1) amortize edilmiş bir mal olduğu, like for a vector belirtilmelidir.

Sürekli rastgele erişim sağlayan bu yapının ne olduğunu merak ediyorum ve aynı zamanda asla daha iyi bir yere taşınması gerekir.

CEVAP
9 HAZİRAN 2011, PERŞEMBE


Deque biraz özyinelemeli olarak tanımlanmış: dahili çift uçlu bir kuyruk tutarparçalar(“blok” grafikte) sabit boyutlu. Her parça bir vektör ve sıra (“göster” aşağıdaki grafik) parçaları da bir vektör kendisidir.

schematic of the memory layout of a deque [Source]

CodeProject at üzerinde performans özellikleri ve vector nasıl karşılaştırır harika bir analiz var.

GCC standart kütüphane uygulaması DAHİLİ olarak T** bir harita göstermek için kullanır. Her veri bloğu 3 ** bazı sabit boyutlu sizeof(T) bağlı olan () ile ayrılan T*.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • merumputdotcom

    merumputdotc

    24 ŞUBAT 2012
  • NightShader1

    NightShader1

    25 Temmuz 2006
  • Video-Tutorials.Net

    Video-Tutori

    15 Mart 2011

İLGİLİ SORU / CEVAPLAR