CODEWITHSUNDEEP
c++
Shal
Shal

Reputation: 57

Why does my iterator point to null, but only sometimes?

I need to write some classes to implement Context Free Grammars in my code. CFGs have production rules of the format "lefthand side -> righthand side". They are implemented as follows:

class GrammarProduction{

  public:

  Nonterminal mLhs;
  std::vector<GrammarSymbol*> mRhs;

I want to store my production rules in a std::set to make sure no one can add duplicate rules. To make duplicate detection work, I implemented the operator< for GrammarProductions as shown below.

bool GrammarProduction::operator<(const GrammarProduction& other) const{
  if (mLhs < other.Lhs()) return true;
  if (mRhs.size() < other.Rhs().size()) return true;
  std::vector<GrammarSymbol*>::const_iterator it1, it2;
  it2 = other.Rhs().begin();
  for(it1 = mRhs.begin(); it1 != mRhs.end(); it1++){
    std::cout << (*it1) << std::endl;
    std::cout << (*it2) << std::endl;
    if(**it1 < **it2) return true;
    it2++;
  }
  return false;    
}

Running this code gets me a segmentation fault at line 

    if(**it1 < **it2) return true;

because the pointer *it2 is null. However, if I change the line which prints *it2 to

    std::cout << (*it2) << other.Str() << std::endl;

it works just fine and *it2 is not null. I have no idea why that is and any advice would be greatly appreciated. If it is necessary to post the functions which are called, I will do so. I haven't because I hope it's not important to the question and it will be a rather large amount (for a post, at least).

Edit: I've narrowed down the problem and it boils down to this

bool GrammarProduction::operator<(const GrammarProduction& other) const{
  std::vector<GrammarSymbol*>::const_iterator it1, it2;

  it1 = mRhs.begin();
  std::cout << "it1:" << std::endl;
  std::cout << (*(mRhs.begin()))->Str() << std::endl; //output (1,2,2)
  std::cout << (*it1)->Str() << std::endl; //output (1,2,2)

  it2 = other.Rhs().begin();
  std::cout << "it2:" << std::endl;
  std::cout << (*(other.Rhs().begin()))->Str() << std::endl; //output (1,2,2)
  std::cout << (*it2)->Str() << std::endl; //Segmentation Fault

  //do whatever
  return false;
}

Upvotes: 2

Views: 345

Answers (3)

Xeo
Xeo

Reputation: 131789

You're invoking undefined behaviour. Since your Rhs() function returns the vector by value, it's destroyed at the end of the full expression:

//          vvvvv -- created here
it2 = other.Rhs().begin();
//          gone here -- ^

This makes it2 a dangling iterator, which is basically the same as a dangling pointer. Dereferencing this iterator will cause UB. To fix, make the return type a reference:

std::vector<GrammarSymbol*>& Rhs(){ return mRhs; } // depending on your needs
std::vector<GrammarSymbol*> const& Rhs() const{ return mRhs; }

Upvotes: 2

Dirk Holsopple
Dirk Holsopple

Reputation: 8831

You should check for it2 == other.Rhs().end() in the loop. If you increment the iterator past the last element, dereferencing it is invalid and will likely cause a segmentation fault.

Upvotes: 2

Adrian Herea
Adrian Herea

Reputation: 658

if(**it1 < **it2) return true;
it2++;

is not very good because in your for loop you don't check if it2 reach the end of list.

a version that should work will be :

bool GrammarProduction::operator<(const GrammarProduction& other) const{
  if (mLhs < other.Lhs()) return true;
  if (mRhs.size() < other.Rhs().size()) return true;
  std::vector<GrammarSymbol*>::const_iterator it1, it2;
  it2 = other.Rhs().begin();
  it2End = other.Rhs().end();
  for(it1 = mRhs.begin(); it1 != mRhs.end(); it1++){
    std::cout << (*it1) << std::endl;
    if (it2 == it2End ) return true;
    std::cout << (*it2) << std::endl;
    if(**it1 < **it2) return true;
    it2++;
  }
  return false;

}

Upvotes: 1

Related Questions