CODEWITHSUNDEEP
c++iteratorcontainerssequential
JWD
JWD

Reputation: 13

Sequential Containers || C++ Primer Fifth Edition Exercise 9.22

I am baffled by this exercise.

Exercise 9.22: Assuming iv is a vector of ints, what is wrong with the following program? How might you correct the problem(s)?

vector<int>::iterator iter = iv.begin(),
                      mid  = iv.begin() + iv.size()/2;

while(iter != mid)     
    if(*iter == some_val)
        iv.insert(iter, 2 * some_val)

The first thing I would do is go and ask what the intent of this program was. Since I am not sure who wrote this section of the book and don't want to bother the authors for something probably trivial I started guessing.

I assume they want to insert the double of the first value in the vector until the value is in the middle. (since they point iter to the beginning and never move through the vector to look for an actual value (then again they named it some_val, to look for a value not at the beginning is a trivial fix, but then one would have to validate that the value actually is in the first half of the container))

so a) vector would grow like this?

{1,2,3,4,5}
{(2),1,2,3,4,5}
{2,(2),1,2,3,4,5}
{2,2,(2),1,2,3,4,5}

The first problem in that case, inserting in a vector most likely instantly invalidates the iterators. We could use a list instead, but then we can't use iterator arithmetic to calculate the mid. Calculating the mid only once like in the example is not enough, since in a list like a.) it would point to the 3 and keep pointing to the 3, just because we called the iterator mid and initialized him with the element in the mid doesn't mean it still points to the mid after all those inserts.

So here is what I did:

vector<int>::iterator iter=iv.begin();

while(iter!=iv.begin()+iv.size()/2){    //calculating mid each time
    if(*iter==some_val)
        iv.insert(iter,2*some_val);

    iter=iv.begin();                        //revalidate iter
    while(*iter!=some_val)                  //find the original first element
        ++iter;
}

I see how the exercise forces you to think about which sequential container to use and how iterators behave in a growing container, but the way the exercise is presented, still baffles me. Did I miss some obvious point?

PS: Since the whole chapter deals with sequential containers I did not focus on the problems that arise with the condition in the while loop (it is like they forgot everything they taught just a few chapters ago).

Upvotes: 1

Views: 260

Answers (2)

Surt
Surt

Reputation: 16109

The original code doesn't advance and invalidates all used iterators.

 vector<int>::iterator iter = iv.begin(),
                          mid  = iv.begin() + iv.size()/2;

 while(iter != mid)
         if(*iter == some_val)
                  iv.instert(iter, 2 * some_val);

There are more problems

vector<int>::iterator iter = iv.begin(),
                      mid  = iv.begin() + iv.size()/2;
int s = iv.size()/2; // assuming we should stop at the original position

while(iter != iv.begin() + s) { // update end condition if that is the intended function
     if(*iter == some_val) {
              iter = iv.instert(iter, 2 * some_val); // gets new valid iter
              ++s; // update position of mid 
              ++iter; // skips the inserted
     }
     ++iter; // advance in vector.
}

Upvotes: 0

rubenvb
rubenvb

Reputation: 76720

Let's go through the program step by step, and update the code style to modern C++:

auto iter = iv.begin(); // type will be std::vector<int>::iterator
const auto mid  = iv.begin() + iv.size()/2; // type will be std::vector<int>::iterator

while(iter != mid)
{
  if(*iter == some_val)
    iv.insert(iter, 2 * some_val);
}

The first two lines create your iterator pair. The loop iterates until you reach the middle of your vector. The condition inside the loop checks that the value at the position iter is pointing to is equal to some predefined value someval. The next line of code inserts a new item into the vector, equal to double the value of some_val.

Now to answer your questions: the insert line does indeed invalidate all iterators, and that is indeed the problem in the program. Additionally, the iterator doesn't iterate, as it is never incremented. One invalidation can be solved by using the return value of the insert call to make iter valid and usable again:

iter = iv.insert(iter, 2*some_val);

But this still leaves us with mid. There is not enough info in your question to fix this bit, but possible options are:

while(std::distance(iter, iv.end()) > iv.size()) // shift the middle when the vector grows

const auto half = iv.size()/2;
while(std::distance(iter, iv.begin()) < half) // only iterate until iter is halfway the original length by insertion

So an example solution might look like this:

auto iter = iv.begin();

while(std::distance(iter, iv.begin()) < iv.size()/2) // iterate until halfway the current vector
{
  if(*iter == some_val)
    iter = iv.insert(iter, 2 * some_val);
  else
    ++iter;
}

But this might of course not be the intended solution.

Upvotes: 1

Related Questions