3

是否有 STL 算法或快速技术来测试数组的所有成员是否都设置为相同的值？

例如，我有一个具有默认值的数组：

bool *finishFlags  =new (std::nothrow) bool[numOfBools];

    //Init all to false:

for(int i = 0 ; i < numOfBools; ++i){
   *finishFlags++ = false;
}

现在，在运行时，一些数组成员设置为 true，我想测试它们是否都设置为相同的值（在这种情况下为 true）。是否有一种快速的方法可以在没有典型数组迭代的情况下做到这一点？

4

6 回答 6

7

保留一个计数器并在标志翻转为真或假时加/减。那么if ctr == numOfBools或者ctr == 0它们都是一样的。

编辑：应该添加您需要检查，因此如果 bool 已经关闭，则不要减去，或者如果它已经打开，则不要添加。

于 2013-08-25T14:15:32.173 回答
3

除非您在构建集合时存储和更新了元数据，否则这将需要迭代数组，因此所有解决方案都是 O(N)。

但是，可以使用单指令多数据架构（例如 Intel 上的 SSE、ARM 上的 Neon）进行矢量化，从而显着减少循环迭代的次数。如果您的数据是对齐的并且是 SIMD 步幅的倍数，这将最有效，否则您将需要处理最终效果。一些编译器甚至可以自动执行此操作。

要考虑的另一件事是提前退出。例如，count_of另一个答案中提到的函数将始终迭代整个数组，即使前两个元素不同。因此，与具有显式迭代的天真方法相比，这是一种去优化。

于 2013-08-25T14:14:58.343 回答
2

您可以all_of在适当的条件下使用。

或者，count, count_if, find_if, any_of,none_of也可以用于此目的。count变体不会提前退出，因此总是会遍历整个数组。

如果您不想使用基于迭代的方法，我可以想到两种相当老套的方法。

  1. 跟踪插入 -num_true每次插入或一组时都会修改的计数。稍后这可用于验证您的状况。
  2. 如果它是一个纯数组，您可以做一些memcmp事情来与一个全真数组进行比较，看看它是否相同。这可能会稍微快一些。
于 2013-08-25T14:09:52.507 回答
1

也许有一个功能可以自动完成。

但无论如何你必须测试数组的每个成员，所以它不能比迭代解决方案更快

于 2013-08-25T14:09:35.333 回答
1

您必须使用循环来遍历所有对象并检查它们。

您也许可以通过循环优化来提高性能。

除此之外，如果数据存在于容器内（无指针），并且架构允许，您可以使用SSE矢量化来提高整体性能

于 2013-08-25T14:14:38.187 回答
0

您可以通过封装对数组的访问来缓存数组状态，并记录有多少条目设置为 true。

在数组初始化为 false 时，将计数器设置为 0。每次条目从 false 变为 true 时，递增计数器，当条目从 true 变为 false 时，将其递减。

现在，您可以通过一次测试检查数组是全为真、全为假还是混合。

于 2013-08-25T14:18:38.477 回答