starting index and ending index of elements in a array(vector) that are greater than a value

Question

Given a array like this:

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

The array length might be larger than 1,000.

If the value of the element is inappropriate, such as larger than 10, it shall be replaced by appropriate value. In this case, the appropriate value is calculated by linear interpolation.

For example:

Arr = {1, 3, 11, 2, 24, 13, 5....};

The new array shall be:

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

In order to do this, I have to know the starting and ending index of the inappropriate elements.

The starting and ending index shall be (2,2) indicating the "11" and (4,5) indicating the "24, 13"

I have tried the for loop. But it is not efficient. Then I searched IPP API and did not get an result. :(

Is there a better idea?

Thanks for your help, :).

BTW: IPP API will be a better choice.

Update:

Sample Codes:

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: Thanks for all your help. But based of the answers of these questions:Speed accessing a std::vector by iterator vs by operator[]/index? and Why use iterators instead of array indices?, the efficients of two forms( for vs iterator) are almost the same. So iterator might not be good enough.

I usually used the SIMD such as IPP API as the optimize option. But I did not figure it out since all the find API only get the first occurrence of the specified element.

I will update the solution if I figure out some day. :)

Answer 1

If you want to search for a particular value, and replace the items from a vector that match a certain criteria, then that can be done in one line using transform().

The replace_if() can also be used, but given the vague description of your issue, I don't know if the replacement value needs to vary depending on the original value (replace_if needs a constant replacement value). So let's go with std::transform() for now.

#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());
}

Basically, the struct serves as a function object. For each of the items in the intVector, the function object will operate on that number. If the number matches the criteria, then the number is transformed and returned, else the original number is returned.

Since you didn't really clarify what your criteria is to change numbers, this approach gives the solution to your issue more flexibility. All you need to do is fill in the two functions that I left open in the Transformer struct, then things should work correctly.

If your needs are more complex, the function object Transformer can be expanded upon to include member variables, or just simply put, can be as complex as you want to make it.

Also remember, if you're timing these things, time a release, optimized build. Don't time "debug" or unoptimized builds.

Answer 2

I'm not exactly sure what you mean by the "starting and ending index of the inappropriate elements", so I'm going to assume you just mean the index.

Using a vector here would be a good approach:

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.
}

You get the idea. Use a vector, and it should make things a lot easier for you. search / insert / get indexes / remove / etc. at your leisure.

Answer 3

If you store your number in an std::vector, you can iterate over the array through an iterator. As soon as you find an element that meets your condition and needs to be removed, you can remove it and at the same time assign your iterator to the next element. This will be the most efficient way:

Here is what your code will look like:

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