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集合工作（矢量&升压：阵列等）