C++ - Tablica okrągła z dolnymi/górnymi ograniczeniami?

Question

Chcę utworzyć coś podobnego do podwójnie połączonej listy (ale z tablicami), która działa z dolnymi/górnymi ograniczeniami.

Typowy okrągły tablica prawdopodobnie wyglądać następująco:

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

Ale co matematyczny arytmetyka włączyć dolne/górne granice odpowiednio do tego?

• 0 (dolny element związany 1)
• 2 (górna granica pozycja 1)
• 3 (dolny element związanego 2)
• 4 (górna granica pozycja 2)

więc, że:

-> obok na indeksie 2 do pozycji 1 zwraca 0

-> poprzedni na indeksie 0 na pozycję 1 powraca 2

-> obok na indeksie 4 na pozycji 2 zwraca 3

-> poprzedni na indeksie 3 dla pozycji 2 zwraca 4

Dziękuję !

UWAGA: Nie można korzystać z bibliotek zewnętrznych.

Answer 1

W ogólnych kategoriach matematycznych:

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

gdzie === jest "przystającym" operatorem. Konwersja to operatorowi modułu, byłoby:

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

Byłoby do ciebie, aby dowiedzieć się górne & dolne granice dla każdego elementu. Można go zapisać w drzewie binarnym w celu szybkiego pobrania. Może nie rozumiem twojego pytania.

(zauważ, że ten zakłada niższy < górna i dolna> 0)

Answer 2

Boost ma Circular container, który moim zdaniem można również ustalić.

W rzeczywistości przykład na tej stronie wygląda bardzo podobnie do tego, co tu mówisz.

Ale tak czy inaczej, można zrealizować część matematyki go łatwo za pomocą modułu:

Tak mówią Twój max wynosił 3:

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 ... 

Więc widać na liście 3 członkowskim, 1. pozycja jest indeksowana przez 0, 3, 6, etc.Podobnie, drugi element jest indeksowany przez 1, 4 (1 + 3), 7 (4 + 3), ...

Ogólną zasadą jest: next <- (next + 1) % size, gdzie size = upper - lower + 1

Używanie tego wzoru otrzymujemy:

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

nadzieję, że pomoże

Answer 4

Napisałem ten artykuł kilka lat temu o okrągłym iteratorze STL.

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

będzie działać na każdej kolekcji STL (wektory & doładowania: tablica, etc)