C++ - 最快的检查数组边界方法

Question

我需要一种非常快速的方式来检查数组的边界。 我当前的边界检查如下：

template<typename T>
class SmartArray {
    //...
    int size;
    T* array;
    T &operator[](int index) {
        if (index/size!=0)
            throw OUT_OF_RANGE; //#define OUT_OF_RANGE 0x0A
        return array[index];
    }
}

有更快的方法来检查索引是否超出数组范围吗？

编辑：

我的解决方案在处理负索引时出现问题。有没有办法解决这个问题？

- DividedByZero

---

std::vector 有什么问题？ - Sergey Kalinichenko

@dasblinkenlight 我正在创建解释器，我不能使用任何内部的东西。 - DividedByZero

大小和索引应该使用size_t，而不是int。这通常是一个坏主意。提供像std::vector::at()这样的方法来进行边界检查，并明确指出它会带来一些代价。尽可能让operator[]快速运行。 - Ed S.

有了现代的CPU和编译器，使用array[index]会比对size进行多次检查更为低效。原因是，在第一次检查结束后，size将被保存在CPU寄存器中，而array[index]可能还没有被加载到缓存中。 - MSalters

Answer 1

一般来说，除法是一种比较慢的操作，所以我会避免使用它。

我认为一个简单的比较将更加高效：

index >= size

然而，这种方法会忽略索引小于0的情况。但是，如果您在`size`和`index`变量上使用`unsigned`或`size_t`类型，则不会出现问题。

因此，代码如下：

T &operator[](size_t index) {
    if (index >= size)
        throw OUT_OF_RANGE; //#define OUT_OF_RANGE 0x0A
    return array[index];
}

- Lyubomir Vasilev

Answer 2

你的检查漏掉了负值：如果大小为5，索引为-1，整数除法的结果为零，但显然索引超出范围。

您可以通过使index参数无符号来解决此问题。 size的类型也应该是size_t。

- Sergey Kalinichenko

---

是的，我在问题中已经说过了。我需要一个解决方案。 - DividedByZero

@DividedByZero 我想在编辑之前回答了。现在我编辑了答案以解决问题中的编辑 :) - Sergey Kalinichenko

谢谢！等等，我是初学者，需要等待接受一个答案。 - DividedByZero

Answer 3

是的，不要使用除法，因为除法很慢（而且如果size == 0则会失败）。一个简单的

if(index >= size || index < 0)

会做得很好。

- nneonneo

---

如果大小为0，则会抛出DivideByZeroException，就像我的用户名一样 :D。 - DividedByZero

@nneonnneo 不是很确定XD。在回答这个问题之前，我有一些问题。顺便说一下，抱歉这个检查很慢。（我的项目中有很多“边界对象”使用它，所以有点慢。） - DividedByZero

最快的检查方法是将所有内容都设置为无符号，这样您只需要一个检查 index >= size。 - nneonneo

但是如果我想做这样的事情：class A {int Value;}; 然后 A *a=new A();... SmartArray[a->Value] 这会变慢，因为它会将无符号转换为有符号。 - DividedByZero

如果它们是相同大小的类型，则没有转换，只有溢出。 - nneonneo

Answer 4

如果你将数组的大小限制为2的幂次方，你就可以使用掩码。也就是说，存储额外的值size_t mask;，它等于size-1（== 2^n-1）。然后可以进行检查：

T &operator[](size_t index) {
    return array[index & mask];
}

- Michal Butterweck

Answer 5

检查数组边界最快的方法是不进行检查。调用 operator[] 的调用方应该负责确保他们知道自己在做什么，并且不会使用错误的索引调用它。

- Pete Becker