C++检查数组是否包含特定范围的值？

Question

我想检查一个数组是否包含一定范围内的特定数值。 例如，值的范围是0 -> 9，而实际数组有50个元素。

我还想跟踪每个值有多少个。 例如，如果有3个零，8个一和5个二，则我的最终向量应该是3 8 5.

我已经用下面的代码解决了这个问题。但是，我发现我的范围值需要等于我的数组大小，否则它不会检查所有元素。

有没有更好的方法来解决这个问题？

int main() {

int intensityRange = 10;
int cloudSize = 10;

int cloud [] = {0, 3, 3, 2, 1, 5, 2, 3, 5, 2};
vector <int> totalGreyValues;
int k = 0;

for (int i = 0; i < intensityRange; i++) {
   for (int j = 0; j < cloudSize; j++) {
      if (cloud[j] == i) {
         k = k + 1;
         cout << "   " << k;
      }
      else
        cout << "  no match  ";
   }
   totalGreyValues.push_back (k);
   k = 0;
}

cout << endl << endl << totalGreyValues.size();

for (int h = 0; h < totalGreyValues.size(); h ++)
   cout << "   " << totalGreyValues[h];

// values --> 0 1 2 3 4 5 6 7 8 9
// answer --> 1 1 3 3 0 2 0 0 0 0 

return 0;
}

- bob blob

Answer 1

使用 std::map 要容易得多：

int size = 50;
int data[size] = { 1, 2, 3, 4, 5, ... };

std::map<int, int> mymap;

for(int i = 0; i < size; i++)
{
   if(data[i] >= min && data[i] <= max)
      mymap[data[i]] = mymap[data[i]] + 1;
}

这样做可以节省空间，因为您不保存未使用的值，并且循环计数也更小，因为您每个值仅处理一次。

- Pillum

---

该死！我差点就写出同样的代码来解决这个问题了！给你点赞，先生。 - Not_a_Golfer

:D 我有种感觉，好像还有别人在回答这个问题，所以我加快了一点速度。 - Pillum

谢谢！作为一个新手，我不太理解if语句。我猜min和max是我的代码中的intensityRange，但它如何检查每个值之间的差异呢？看起来它只是检查最小值和最大值，而不是每个值之间的差异……还是说？ - bob blob

你是对的，min和max是范围，但它不会检查每个值，因为由于std::map的存在，它不需要这样做。例如，使用此方法，您可以编写mymap[8] = 1;，它会自动创建一个int，您可以将其用作值（此处为8）的计数器，并在每次进一步检查时递增。稍后，您只需遍历所有保存的计数器和值即可。 - Pillum

只有在直方图稀疏的情况下使用映射才有用。如果范围内的大多数元素可能被填充，则使用初始化为范围长度的向量。映射是相对昂贵的数据结构。 - Tom Whittock

最好使用multiset，它内置支持您手动执行的操作，并且不需要额外的空间开销。另一个建议是：您正在两次索引到映射中；您可以只进行一次查找就能完成。 - Sebastian Mach

Answer 2

如果您的范围是连续的，我建议使用boost::vector_property_map。

#include <boost/property_map/vector_property_map.hpp>
#include <iostream>

int main()
{
  boost::vector_property_map<unsigned int> m(10); // size of expected range

  std::vector<int> cloud = {0, 3, 3, 2, 1, 5, 2, 3, 5, 2};
  for(auto x : cloud) { m[x]++; }
  for(auto it = m.storage_begin(); it != m.storage_end(); ++it) { 
    std::cout << *it << " ";
  }
  std::cout << std::endl;

  return 0;
}

如果您的范围不是从0开始，您可以使用IndexMap模板参数来重新映射索引。如果您要将非连续的值映射到连续的范围中进行计数，这也适用。如果您只想计算特定值，则可能需要执行检查，但考虑到计数操作的昂贵性，我宁愿计算所有值而不是检查要计算什么。

- pmr

Answer 3

使用 std::map 和 std::accumulate 函数：

#include <map>
#include <algorithm>

typedef std::map<int, int> Histogram;

Histogram& addIfInRange(Histogram& histogram, const int value)
{
    if(inRange(value))
    {
        ++histogram[value];
    }
    // else don't add it

    return histogram;
}

Histogram histogram =
    std::accumulate(data, data + size, Histogram(), addIfInRange);

- Peter Wood

Answer 4

如果您有足够大的空白区域，可以尝试使用 multiset 以及 C++ 的一些新功能：

#include <set>
#include <iostream>

int main () {
    int vals[] = { 0, 1, 2, 3, 4, 5, 5, 5, 6 };

    std::multiset <int> hist;
    for (auto const &v : vals)
        if (v >= 3 && v <= 5) hist.insert (v);

    for (auto const &v : hist)
        std::cout << v << " -> " << hist.count (v) << '\n';
}

如果你的数据密集分布，使用std::vector可能会得到更好的结果：

#include <algorithm>
#include <iostream>

int main () {
    using std::begin; using std::end;

    int vals[] = { 1, 2, 4, 5, 5, 5, 6 };

    const auto val_mm  = std::minmax_element (begin(vals), end(vals));
    const int  val_min = *val_mm.first,
               val_max = *val_mm.second + 1;

    std::vector<int> hist (val_max - val_min);

    for (auto v : vals)
        ++hist [v - val_min];

    for (auto v : vals)
        std::cout << v << " -> " << hist[v-val_min] << '\n';
}

- Sebastian Mach