0

I'm trying to make a very simple filter using recursion but for some reason, I keep getting these Seg Fault.

#include <iostream>
#include <vector>
#include <math.h>

class FilterGeneric {
public:
    std::vector<int> filter(std::vector<int>& v, std::vector<int>::iterator i); //set i=v.begin() in main
private:
    virtual bool g(int x) =0;
    std::vector<int> result;
};

std::vector<int> FilterGeneric::filter(std::vector<int>& v, std::vector<int>::iterator i)   {
    if (i==v.end()) {
        return result;
    }   else    {
        if (g(*i)==true)    {
            result.push_back(*i);
            i++;
            return filter(v,i);
        }   else    {
            i++;
            return filter(v,i);
        }
    }
}

class FilterOdd : public FilterGeneric  {
private:
    bool g(int x);
};

bool FilterOdd::g(int x)    {
    if ((x%2)!=0)   {
        return true;
    }   else    {
        return false;
    }
}

class FilterNonPositive : public FilterGeneric  {
private:
    bool g(int x);
};

bool FilterNonPositive::g(int x)    {
    if (x<0)   {
        return true;
    }   else    {
        return false;
    }
}

class FilterForTwoDigitPositive : public FilterGeneric  {
private:
    bool g(int x);
};

bool FilterForTwoDigitPositive::g(int x)    {
    if (x>=10)   {
        return true;
    }   else    {
        return false;
    }
}

int main()  {

    std::vector<int> v;
    std::vector<int>::iterator it=v.begin();

    for (int i=0;i<20;i++)  {
        v.push_back(pow(-1,i)*i);
    }

    std::cout<<std::endl;

    FilterNonPositive fnp;
    FilterForTwoDigitPositive ftd;

    FilterGeneric *f1=&fnp;
    FilterGeneric *f2=&ftd;

    std::vector<int> r1;
    std::vector<int> r2;

    r1=f1->filter(v,it);
    for (it=r1.begin();it!=r1.end();it++)   {
        std::cout<<*it<<" ";
    }
    r2=f2->filter(v,it);
    for (it=r2.begin();it!=r2.end();it++)   {
        std::cout<<*it<<" ";
    }

}
Improve this question
4
  • 2
    Running out of stack space? Commented Sep 10, 2017 at 11:49
  • @user0042 I'm so sorry for my lack of knowledge but is that possible to run out of stack space so easily? I mean, it's such a simple code? I mean, I played games on this computer. Commented Sep 10, 2017 at 12:01
  • 1
    Stack space is very limited and it's easy to run out of it when using recursive function calls. Rather use a std::stack and a simple loop instead. Commented Sep 10, 2017 at 12:03
  • @ViệtEnglandI see no conceivable way stack space has anything to do with your problem. The answer posted by Employed Russian, however, is definitely related, and I strongly suggest you read it and follow the links within. Commented Sep 10, 2017 at 16:46

1 Answer 1

Reset to default
1

The bug is here:

std::vector<int> v;
std::vector<int>::iterator it=v.begin();

for (int i=0;i<20;i++)  {
    v.push_back(pow(-1,i)*i);  // invalidates all iterators into "v"
}
...
r1=f1->filter(v,it);  // using invalidated "it"

The problem is that v.push_back() invalidates all iterators into the vector if the vector needs to be resized. From documentation:

If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.

After you correct above bug by moving it initialization after v has been intialized, there are additional bugs as well.

If you are building with g++, you can use -D_GLIBCXX_DEBUG to help you find such bugs.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Interesting, the pow function returns a floating point value. The example provided may have accuracy issues because of conversion to floating point (for parameters) conversion back to integer for the result.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.