使用取模运算符来保持在容器索引范围内

Question

假设我有一个包含 m 个元素的向量 v，以及一个名为 i 的随机访问索引。

当我递增索引时，如果超出范围，我想要索引第一个（零）元素。同样地，当我递减索引时，如果索引小于 0，则我想要索引最后一个元素。目前，我只能一次移动一个元素来遍历容器，因此提出了这个函数：

unsigned int GetIndexModM(int index,unsigned int m) {return (index + m) % m;}

调用位置可能如下所示：

std::vector<Whatever> v = ... // initialise with 5 elements
unsigned int i = 0;
unsigned int j = GetIndexModM(static_cast<int>(i) - 1,v.size()); // get preceeding index

如果从索引中减去一个大于m的值，那么此函数将失败：

unsigned int j = GetIndexModM(static_cast<int>(i) - 17,v.size()); // oops: returns -2

我的问题是：如何最优雅地实现一个函数，该函数接受任何整数并返回它作为索引的位置？

- PeteUK

Answer 1

处理MOD的技巧是这样的，它适用于正数和负数：

  val = ((val % mod_val) + mod_val) % mod_val; 

例如，假设我们想要保持值在0和359之间（包括0和359）。我们可以使用以下代码：

  val = ((val % 360) + 360) % 360; 

这是一个简单的C++示例。

int getmod(int val, int mod) {
  return ((val % mod) + mod) % mod; 
}

int main() {
  printf("%d\n", getmod(50,360));   // prints 50
  printf("%d\n", getmod(-400,360)); // prints 320
  printf("%d\n", getmod(350,360));  // prints 350
  printf("%d\n", getmod(375,360));  // prints 15
  printf("%d\n", getmod(-725,360));  // prints 355


  return 0;
}

- dcp

---

在某些平台上，避免第二个模运算可能会更快，但代价是需要进行比较：val = val％mod; return val <0？val + mod：val; - Mike Seymour

这个程序在 val < -mod_val 的情况下是否有效，还是只处理 -mod_val < val < 0 的负整数？模数在正数方面正确处理。 - André Caron

@Andre Caron - 在那种情况下它是有效的，我添加了另一个示例（请参见最后一个printf）。 - dcp

@dcp：啊，我明白了！你在第一个模数之后添加*。很好。 - André Caron

我以前只是添加了一个足够大的'mod_val'倍数，以确保模运算在正空间中执行，例如(val+3600)%360适用于val < -3600。如果modval是固定的或可移位到所需大小，则这可能比进行2个模运算更快。 - strainer

Answer 2

不幸的是，C++没有实现一个适用于负整数的正确模数。

我认为最干净的解决方案确实是使用if来正确处理所有情况。这至少使代码明显（因为每种情况都是明确的），并且更容易找到错误：

unsigned GetIndexModM(int index, unsigned m) {
    if (index < 0)
        return GetIndexModM(index + m, m);
    if (index >= m)
        return index % m;
    return index;
}

- Konrad Rudolph

---

如果 index 很大且为负数，那么效率非常低。 - Mike Seymour

我使用参数-400, 360尝试了您的函数，返回值为216，但正确答案应该是320。 - dcp

@Mike 没错 - 如果这是一个常见的用例，那么函数需要被重写。另一方面，对于接近零的负数，这种方法实际上可能比取模方法更快。 - Konrad Rudolph

Answer 3

以下代码可以确保index在[0,n)范围内，但只需一次模运算且无需使用跳转语句：

index = index % n + (index < 0)*n

第一个项（包含模运算符）将值放入（-n，n），而第二个项确保该值在[0，n)之间。

请注意，在n为无符号类型和旧版（11年前）的C ++中，当%运算符对负参数实现依赖时，此方法不可靠。

- Thomas Hardin