数组(向量)中大于值的元素的起始索引和结束索引

Question

给定这样的数组：

{1, 3, 11, 2, 24, 13, 5....}

数组长度可能大于1,000。

如果元素的值不适当，如大于10，则应以适当的值代替。在这种情况下，适当的值是通过线性插值计算的。

例如：

Arr = {1，3，11，2，24，13，5}；

新的阵列应为：

NewArr = {1，3，3+(2-3)/2，2，2+(5-2)/3，2+2*(5-2)/3，5，.}

为了做到这一点，我必须知道的开始和结束索引的不适当的元素。

起止指数应为(2,2)表示"11“，(4,5)表示"24，13”。

我试过了for loop。但这是没有效率的。然后我搜索了IPP API，没有得到任何结果。:(

有更好的主意吗？

谢谢你的帮助:)。

BTW：IPP API将是一个更好的选择。

更新：

样本代码：

int arr[] = {1, 3, 11, 2, 24, 13, 5....};

/// find the starting index and ending index of inappropriate values
/// (2,2) (4,5).
int i = 0; 
std::map<int,int> Segments;
if(arr[i] > Threshold)
{
    int b = i;
    while(arr[i] > Threshold )
        i ++;
    int e = i;
    Segments.insert(std::map<int,int>::value_type(b,e));
}

/// linear interpolation
for(std::map<int,int>::iterator i = 0; i != Segments.end(); i ++) /// len means the number of inappropriate segments  
{
    //// linear interpolation of each segments
    int b = i->first;
    int e = i->second;
    int num = e - b + 1;
    float step = (arr[e+1]-arr[b-1]) / num; // For short. The case that b=0 or e=len-1 is not considered. 
    for(int j = b; j <= e; j ++)
        arr[j] = arr[j-1] + step;
}

Update2：谢谢你的帮助。但是基于这些问题的答案：使用迭代器访问std：：向量的速度是通过operator[]/index？和为什么使用迭代器而不是数组索引？，两种形式(对于vs迭代器)的效率几乎是相同的。所以iterator可能还不够好。

我通常使用SIMD (如IPP API )作为优化选项。但是我没有搞清楚，因为所有的find API都只得到了--指定元素的第一次出现。

如果有天我会更新解决方案的。:)

Answer 1

如果您想要搜索一个特定的值，并替换与特定条件匹配的向量中的项，则可以使用transform()在一行中完成这一操作。

也可以使用replace_if()，但是考虑到对问题的模糊描述，我不知道替换值是否需要根据原始值的不同而变化(replace_if需要一个常数的替换值)。现在让我们来看一下std::transform()。

#include <algorithm>
#include <vector>

struct Transformer 
{
   bool ThisNumberNeedsTransformation(int num) { 
     // you fill this in.  Return true if number needs to be changed, false otherwise
   }

   int TransformNumber(int num) {
      // you fill this in.  Return the changed number, given the original number.
   }

   int operator()(int num)
   {
      if ( ThisNumberNeedsTransformation(num) )
          return TransformNumber(num);
      return num;
   }
};

int main()
{
     std::vector<int> intVector;
     //...
     std::transform(intVector.begin(), intVector.end(), intVector.begin(), Transformer());
}

基本上，该结构充当一个函数对象。对于intVector中的每个项，函数对象将对该数字进行操作。如果该数字与条件匹配，则转换并返回该数字，否则将返回原始数字。

由于您没有真正阐明更改数字的标准，因此这种方法为您的问题提供了更大的灵活性。您所需要做的就是填写我在Transformer结构中打开的两个函数，然后一切都应该正常工作。

如果您的需求更复杂，可以对函数对象转换器进行扩展以包含成员变量，或者简单地说，它可以像您想要的那样复杂。

还请记住，如果你在计时这些事情，时间发布，优化的构建。不要浪费时间“调试”或未优化的构建。

Answer 2

我不太清楚您所说的“不适当元素的开始和结束索引”是什么意思，所以我假设您只是指索引。

在这里使用向量是一种很好的方法：

std::vector<int> the_stuff {1, 3, 11, 2, 24, 13, 5, ... };
std::vector<int>::iterator it = the_stuff.begin();

while (it != the_stuff.end()
{
   if (*it > 10) { // do stuff };
   etc.
}

你明白了吧。使用向量，它会使事情变得更容易。在空闲时间搜索/插入/获取索引/删除/等等。

Answer 3

如果将数字存储在std::vector中，则可以通过迭代器对数组进行迭代。一旦找到符合条件并需要删除的元素，就可以删除它，同时将迭代器分配给下一个元素。这将是最有效的方式：

下面是您的代码的样子：

std::vector<int> intVector;
for(auto it = intVector.begin(); it != intVector.end(); ++it)
{
    if (*it > 10)
    {
        it = intVector.erase(it);
    }
}