C++ - 具有下限/上限的循環數組？

Question

我想創建一個類似於雙鏈表（但與數組）的東西，可與下限/上限一起工作。

一個典型的圓陣很可能是這樣的：

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

但是，什麼是數學算法納入低/上限正常到這一點？

• 0（下界項目1）
• 2（上限項目1）
• 3（下界項目2）
• 4（上限項目2）

因此：

- >下一個項目1的索引2返回0

- >先前關於索引0爲項1返回2

- >下一個上索引4項2返回3

- >先前關於索引3項2個返回4

謝謝！

注意：不能使用外部庫。

Answer 1

在一般數學方面：

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

===是'一致'運算符。這個轉換成模運算，這將是：

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

這將是由你來找出每個項目上&下限。您可以將其存儲在二叉樹中以便快速檢索。也許我不理解你的問題。

（注意，這個假設下<和上下> 0）

Answer 2

Boost有一個Circular container，我相信你也可以設置邊界。

事實上，該頁面上的示例與您在此說的內容非常相似。

但無論如何，你可以完成它的數學部分容易使用模量：

所以說你最大爲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 ... 

所以，你看到一個3成員列表中，第一個項目是由0, 3, 6,等索引同樣，第二項是由1, 4 (1 + 3), 7 (4 + 3), ...

的一般規則索引是：next <- (next + 1) % size，其中size = upper - lower + 1

使用這個公式，我們得到：

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

希望幫助

Answer 4

我寫這篇文章幾年前關於一個循環STL迭代器。

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

它可以在任何STL集合工作（矢量&升壓：陣列等）