C++ - 带有下限/上限的循环数组？

Question

我希望创建一个类似于双向链表（但使用数组）的数据结构，可以使用下限/上限进行操作。

一个典型的循环数组可能如下所示：

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

但是如何将上下限正确地纳入其中的数学算术是什么？

• 0（下限第1项）
• 1
• 2（上限第1项）
• 3（下限第2项）
• 4（上限第2项）

以便：

- 索引2上的第1个项目的下一个返回0 - 索引0上的第1个项目的上一个返回2 - 索引4上的第2个项目的下一个返回3 - 索引3上的第2个项目的上一个返回4

谢谢！

注意：不能使用外部库。

- turbovince

---

你能稍微详细解释一下吗？看起来你想要一个循环队列的循环队列。在这种情况下，每个队列最好放在一个单独的数组中。 - sfossen

Answer 1

一般数学术语来说：

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

where === 是“恒等”运算符。将其转换为模数运算符，则为：

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

您需要找出每个项目的上限和下限，可以将其存储在二叉树中以便快速检索。也许我没有理解您的问题。

（请注意，这假定lower < upper，并且lower > 0）

- FryGuy

Answer 2

          +=======+        +=======+        +=======+
          |  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
-------+-----------------

希望这能帮到您。

- dirkgently

Answer 3

我几年前写了一篇关于STL循环迭代器的文章。

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

它可以适用于任何STL集合（例如向量和boost数组等）。

- James Curran

Answer 4

Boost有一个圆形容器，我相信你也可以设置其边界。

实际上，该页面上的示例看起来与您在此处所说的非常相似。

但无论如何，您可以轻松地使用模数完成其中的数学部分：

假设您的最大值为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

- Adam