C++ - Alt/üst sınırlarla dairesel dizi?

Question

Alt/üst sınırlarla çalışan çift bağlantılı bir listeye benzer (ancak diziler içeren) bir şey oluşturmak istiyorum.

Tipik dairesel dizi muhtemelen şöyle olacaktır:

next = (current + 1) % count; 
previous = (current - 1) % count; 

Ama düzgün bu işe alt/üst sınırları dahil etmek matematiksel aritmetik nedir?

• 0 (alt sınır madde 1)
• 2 (üst sınır madde 1)
• 3 (alt sınır madde 2)
• 4 (üst sınır madde 2)

Böylece:

- öğenin endeksi 2> sonraki 1 döner 0

- öğenin indeksi 4> önümüzdeki 2 döner 3

- - 1 döndürür 2

öğe için endeks 0 ile> Önceki öğe için endeks 3> Önceki 2 döner

4 teşekkür ederiz !

NOT: Harici kitaplıkları kullanamazsınız.

Answer 1

:

next === current + 1 (mod count) 
prev === current - 1 (mod count) 

Yani maksimum 3 olduğunu söylemek:

Ama yine de, kolayca bir modüle kullanarak bunun matematik bölümünü başarabileceğimizi Burada === 'uyumlu' operatördür. modül operatöre bu dönüştürme, öyle olurdu:

count = upper - lower 
next = ((current + 1 - (lower%count) + count) % count) + lower 
prev = ((current - 1 - (lower%count) + count) % count) + lower 

Her öğe için üst & alt sınır öğrenmek için size kalmış olurdu. Hızlı geri alma için bunu bir ikili ağaçta saklayabilirsiniz. Belki sorunuzu anlamıyorum.

(bu alt varsayar unutmayın < üst ve> 0 düşük) Yani, 3 üye listesi için bkz

Answer 2

Yükseltme, sınırlar da ayarlayabileceğine inandığım bir Circular container içeriyor.

Aslında bu sayfadaki Örnek, burada söylediklerinize çok benziyor. Genel matematiksel anlamda

int MAX = 3; 
someArray[ 0 % MAX ]; // This would return element 0 
someArray[ 1 % MAX ]; // This would return element 1 
someArray[ 3 % MAX ]; // This would return element 0 
someArray[ 4 % MAX ]; // This would return element 1 

Answer 3

  +=======+  +=======+  +=======+ 
      | Obj | ---> | Obj | ---> | Obj | 
buffer | 1 | <--- | 2 | <--- | 3 | 
      +=======+  +=======+  +=======+ 

index  0     1    2  /* our first run */ 

index  3     4    5  /* second run */ 

and so on ... 

, 1 kalem vb 0, 3, 6, tarafından dizineBenzer şekilde, ikinci öğe 1, 4 (1 + 3), 7 (4 + 3), ...

genel kural tarafından dizine olmasıdır:

curr |  next 
-------+----------------- 
    0 | (0 + 1) % 3 = 1 
-------+----------------- 
    1 | (1 + 1) % 3 = 2 
-------+----------------- 
    2 | (2 + 1) % 3 = 0 
-------+----------------- 

Umut Bu makaleyi yazmadan

Answer 4

yardımcı olur: aldığımız Bu formülün kullanılması next <- (next + 1) % size, size = upper - lower + 1

dairesel bir STL yineleyici hakkında birkaç yıl önce.

http://noveltheory.com/Iterators/Iterator_N0.htm

Herhangi STL koleksiyonu üzerinde çalışacak (vektörler & boost: dizi, vs)