CODEWITHSUNDEEP
c++pass-by-referencedynamic-memory-allocation
Ari Levisohn
Ari Levisohn

Reputation: 77

c++ – Disappearing Variable

I am writing a function to take the intersection of two sorted vector<size_t>s named a and b. The function iterates through both vectors removing anything from a that is not also in b so that whatever remains in a is the intersection of the two. Code here:

void intersect(vector<size_t> &a, vector<size_t> &b) {
  vector<size_t>::iterator aItr = a.begin();
  vector<size_t>::iterator bItr = b.begin();
  vector<size_t>::iterator aEnd = a.end();
  vector<size_t>::iterator bEnd = b.end();

  while(aItr != aEnd) {
    while(*bItr < *aItr) {
      bItr++;
      if(bItr == bEnd) {
        a.erase(aItr, aEnd);
        return;
      }
    }
    if (*aItr == *bItr) aItr++;
    else aItr = a.erase(aItr, aItr+1);
  }
}

I am getting a very bug. I am stepping the debugger and once it passes line 8 "while(*bItr < *aItr)" b seems to disappear. The debugger seems not to know that b even exists! When b comes back into existence after it goes back to the top of the loop it has now taken on the values of a!

This is the kind of behavior that I expect to see in dynamic memory error, but as you can see I am not managing any dynamic memory here. I am super confused and could really use some help.

Thanks in advance!

Upvotes: 1

Views: 505

Answers (2)

einpoklum
einpoklum

Reputation: 131666

Well, perhaps you should first address a major issue with your code: iterator invalidation.

See: Iterator invalidation rules here on StackOverflow.

When you erase an element in a vector, iterators into that vector at the point of deletion and further on are not guaranteed to be valid. Your code, though, assumes such validity for aEnd (thanks @SidS).

I would guess either this is the reason for what you're seeing, or maybe it's your compiler optimization flags which can change the execution flow, the lifetimes of variables which are not necessary, etc.

Plus, as @KT. notes, your erases can be really expensive, making your algorithm potentially quadratic-time in the length of a.

Upvotes: 3

Sid S
Sid S

Reputation: 6125

You are making the assumption that b contains at least one element. To address that, you can add this prior to your first loop :

if (bItr == bEnd)
{
    a.clear();
    return;
}

Also, since you're erasing elements from a, aEnd will become invalid. Replace every use of aEnd with a.end().

std::set_intersection could do all of this for you :

void intersect(vector<size_t> &a, const vector<size_t> &b)
{
    auto it = set_intersection(a.begin(), a.end(), b.begin(), b.end(), a.begin());
    a.erase(it, a.end());
}

Upvotes: 1

Related Questions