compiler problem

[eduard77]

i have the next code that compiles without problems but when I run it after I put in the input data it gives me the next error:

line 128 vector iterator not decrementable
I use visual c++ 2010.

#include <iostream>
#include <iomanip>
#include <vector>
#include <iterator>
#include <algorithm>
#include <numeric>
/* Get the number of different lengths from the user */

struct Cut{
    unsigned number;
	double length;
};


int main () {
	
std::vector< Cut > allCuts;
Cut currentCut;
unsigned numberOfSizes;
std::cout << "Enter number of different sizes: ";
std::cin >> numberOfSizes;
 
/* Now get the actual numbers and lengths from the user */
for(unsigned i = 0; i < numberOfSizes; ++i){
	//currentCut = new Cut;
    std::cout << "Enter new cut: <number> <length>" << std::endl;
	std::cin >> currentCut.number >> currentCut.length;
   /* Check that the length is sensible */
    if((currentCut.length <= 0) || (currentCut.length > 12)){
        std::cerr << "Error length must be in the range (0,12]" << std::endl;
        --i;
    }
    else
        allCuts.push_back(currentCut);
}
 
/* Now put all the cuts into a single large vector */
std::vector< double > lengths;
for(unsigned i = 0; i < allCuts.size(); ++i){
    for(unsigned j = 0; j < allCuts[i].number; ++j)
        lengths.push_back(allCuts[i].length);
}
 
/* Sort the vector */
std::sort(lengths.begin(), lengths.end());
 
/* Make a place to put the lengths to cut from each bar */
const unsigned NEW_BAR_LENGTH = 12;
std::vector< std::vector< double > >bars;
std::vector< double > currentBar;
double remainingLength = NEW_BAR_LENGTH;
 
/* Now keep going through the lengths vector until all the cuts are accounted for */
while(lengths.size() > 0){
    /* start at the longest length that needs to be cut ... */
    std::vector< double >::iterator it = lengths.end() - 1;
    /* Go until the smallest length that's needed is reached */
    while(it >= lengths.begin()){
        /* Check if the current length will fit */
        if(*it < remainingLength){ /* If it will... */
            /* ... Add it to the current bar and remove it from the list to be fitted */
            currentBar.push_back(*it);
            /* Update the amount of the bar remaining */
            remainingLength -= *it;
            /* Remove the current element from the lengths vector */
           lengths.erase(it);
        }
        /* Check that we didn't just remove the last element */
        if(lengths.size() > 0){
            /* length[0] is the shortest length cut that we still need to get
               if this is more than the remaining amount of the current bar,
               then we should finish this bar and start a new one, check for
               this now */
            if(lengths[0] > remainingLength){
                /* Reset the remaining length */
                remainingLength = NEW_BAR_LENGTH;
                /* Add this completed bar to the vector of bars */
                bars.push_back(currentBar);
                /* Clear the current bar */
                currentBar.clear();
                /* Exit this loop and start on the new bar */
                break;
            }
        }
        --it;
    }
}

double totalWaste = 0.0;
for(unsigned i = 0; i < bars.size(); ++i){
    std::cout << "Bar " << std::setw(2) << i + 1 << ":\t";
    for(unsigned j = 0; j < bars[i].size(); ++j)
        std::cout << std::setprecision(3) << std::fixed << bars[i][j] << " ";
    std::cout << std::endl;
    std::partial_sum(bars[i].begin(), bars[i].end(), bars[i].begin());
    totalWaste += NEW_BAR_LENGTH - bars[i].back();
}
 
/* Print a summary */
std::cout << "===============================" << std::endl;
std::cout << "Bars used:\t" << bars.size() << std::endl;
std::cout << "Total waste:\t" << totalWaste << " m" << std::endl;
std::cout << "Waste/Bar:\t" << totalWaste/bars.size() << " m" << std::endl;
std::cout << "===============================" << std::endl;
system("pause");
return 0;
}

So, if anyone could help me I would really appreciate it.
Thank you

[Fbody]

On Line 85 of this code, what is your reason for decrementing your iterator called "it"? If I trace your program's execution, this is the line that triggers the error.

EDIT:
nvm.... looked at something wrong... have to look again...
<section erased>

EDIT 2:
Due to how the scope of "it" is defined, I think I would just get rid of that decrement statement altogether, it really doesn't serve any purpose. Your iterator "it" is declared and initialized within the scope of the outer while loop. This causes the scope of "it" to be limited to only the statement block that executes as part of that loop and any sub-blocks. This causes "it" to go out of scope and be destroyed at the end of each iteration of the loop with a new iterator being constructed at the beginning of each iteration. If I've read your code correctly the construction of the new iterator at the beginning of the iteration accomplishes what you are hoping this decrement will.

[djarn]

Line 57 is probably causing some issues for you here. The end() method returns an iterator that points 1 position past the end of the vector. 1 position isn't the same as the integer 1.

There is some danger in doing this, so I would probably look at how to implement using a reverse iterator, but if you split that line up into the components and use the decrementor, you'll probably be able to continue...

std::vector< double >::iterator it = lengths.end();
it--;

[Fbody]

>>The end() method returns an iterator that points 1 position past the end of the vector. 1 position isn't the same as the integer 1.
Actually, there really isn't anything wrong with that.

An iterator is essentially just a templatized wrapper for a pointer. If you take the std::vector::end() iterator and subtract 1, it should perform the appropriate pointer arithmetic on it changing the address in the pointer by (-1 * sizeof(double)) causing it to point at the actual last element instead of the phantom "one-past" element.

[ravenous]

If I've read your code correctly the construction of the new iterator at the beginning of the iteration accomplishes what you are hoping this decrement will.

No, you do need to decrement the iterator here. There are two while loops and the decrement is inside the inner one, like this:

while(lengths.size() > 0){
    std::vector< double >::iterator it = lengths.end() - 1;
    while(it >= lengths.begin()){
        /* Do things here ... */
        
        /* Now decrement the iterator */
        --it;
    }
}

Without it, the inner loop could run indefinitely.

Also, this code compiles and runs and does what it's supposed to on my computer (Ubuntu 10.10, gcc 4.4.5). Could it be a Visual Studio/Windows problem?

[Fbody]

>>No, you do need to decrement the iterator here. There are two while loops and the decrement is inside the inner one, like this:
Oops, you're right. I matched up the braces wrong...

>>Could it be a Visual Studio/Windows problem?
Possibly. But I did it on Win7 using VS 2008 (OP has VS 2010), so it's a different version of the compiler. I wonder if it's a problem with the prefix version of the operator. Maybe changing to the postfix version of the operator will help?

[mike_2000_17]

Three points to make here:
1) The error is caused by the fact that you are changing the size of the vector at line 67 by calling erase() on it. Once you change the size, the iterator is invalid. You could refrain from modifying the length of the vector in the loop or you could use the fact that the erase function returns an iterator to the element that is now at the place where the element that you erased used to be before it was removed. In other words, do this at line 67:

it = lengths.erase(it); //notice the "it = "

2) Definitely, you should use a reverse iterator for this, if you want your code to be robust. So, make the follow changes:

//at line 57:
std::vector< double >::reverse_iterator it = lengths.rbegin();
//at line 59:
while(it != lengths.rend()){
//at line 86:
++it;

3) If what you really need is the vector to be sorted from biggest to lowest numbers (and not the default from lowest to biggest), I would suggest you do so with the sorting algorithm, at line 46 (and you would need to #include <functional>):

std::sort(lengths.begin(), lengths.end(), std::greater<double>());

@Fbody>>An iterator is essentially just a templatized wrapper for a pointer.
You think too much. An iterator is an iterator and that's all you need to know. The fact that it most probably is just a (wrapped) pointer is a piece of information that is more harmful than anything else. You are inferring on the behaviour of decrementing the end() iterator based on the assumption that it's a wrapped pointer. The specifications say that the end() iterator is an invalid one and that operating on it is undefined behaviour, you shouldn't try to infer anything passed that. And robust code shouldn't include undefined behaviour, even if there is 99.9% chance that the behaviour you infer is correct.

[eduard77]

I also tried with dev-cpp and it works perfectly.
So I think it's a visual studio problem.

[ravenous]

2) Definitely, you should use a reverse iterator for this, if you want your code to be robust. So, make the follow changes:

//at line 57:
std::vector< double >::reverse_iterator it = lengths.rbegin();
//at line 59:
while(it != lengths.rend()){
//at line 86:
++it;

I like this idea in principle, but I don't think that std::vector::erase() works with reverse_iterator . At least, my compiler doesn't like it.

Doing it = lengths.erase(it); has also got to be a good idea. For some reason I thought that erase() moved the iterator to the next element during its operation, I hadn't appreciated that this position is actually in the return value.

If the normal iterator can't be decremented for some reason, and if erase() isn't defined for reverse_iterator , then the easiest thing might be to call std::reverse() on the vector straight after std::sort() , that way a forward iterator can be used instead?

[mike_2000_17]

I like this idea in principle, but I don't think that std::vector::erase() works with reverse_iterator . At least, my compiler doesn't like it.

Yes, this is a frustrating point with reverse_iterators, I don't understand why the STL has this reverse iterator class for almost all their containers but no overloads of their functions to also deal with reverse iterators. Basically, all you can do with a reverse iterator is traverse a "static" container (static in the sense you don't modify the structure of it). I find them nice, especially with <algorithm> . With some trickery, you can actually use them with erase(), but it is kinda nasty see this, here is an example that works (use -std=gnu++0x or -std=c++0x flags because of the lambda expressions):

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <ctime>
using namespace std;

int main() {
  srand((unsigned int)time(0));
  vector<double> arr(20);
  cout << "The unsorted vector is:" << endl;
  generate(arr.begin(),arr.end(), []() -> double { double x = (rand() % 10000) * 0.001; 
                                                   cout << x << endl;
                                                   return x; } );
  
  sort(arr.begin(),arr.end());
  cout << "The sorted vector is:" << endl;
  for_each(arr.begin(),arr.end(), [](double x) { cout << x << endl; } );

  for(vector<double>::reverse_iterator rit = arr.rbegin(); rit != arr.rend(); ++rit)
    if(((*rit) < 7.0) && ((*rit) > 3.0)) //trim away numbers between 3 and 7
      rit = vector<double>::reverse_iterator(arr.erase(rit.base() - 1) + 1); //call erase with a reverse_iterator.. nasty..

  cout << "The trimmed vector is:" << endl;
  for_each(arr.begin(),arr.end(), [](double x) { cout << x << endl; } );

  return 0;
};

Doing it = lengths.erase(it); has also got to be a good idea. For some reason I thought that erase() moved the iterator to the next element during its operation, I hadn't appreciated that this position is actually in the return value.

That is one of those (hidden) subtleties. By forcing you to write it = lengths.erase(it); with the assignment, I think they wanted to promote the clear message in the code that the iterator is given a new value and thus, its end iterator would also change. Because some people have the habit of writing loops like this:

vector<double>::iterator it = array.begin(), it_end = array.end();
for(; it != it_end; ++it) { /*... do stuff ...*/ };

They think that this is more efficient because you don't call vector::end() at every loop. But end() is simple and inlined almost for sure, so this is a useless, premature optimization. But if you do write loops like that, and have some "erase" function in the loop, it must be made as clear as possible that when erase is called, the end iterator has to be updated too (and if the erase function took a non-const reference and modified it, it wouldn't be as clear as an assignment expression).

If the normal iterator can't be decremented for some reason, and if erase() isn't defined for reverse_iterator , then the easiest thing might be to call std::reverse() on the vector straight after std::sort() , that way a forward iterator can be used instead?

I think that in this case, the easiest thing is probably the last point I made about just sorting the array in decreasing order instead and traverse it in the forward direction. But, a normal iterator can be decremented, there's no problem doing that. It only needs to be a BidirectionalIterator, which is the case for all STL container iterators (including their reverse iterators). And, with containers like vector, there is no real problem with taking the end() iterator and decrementing it down to begin(). My preference for reverse_iterator is just a matter of clarity and abstraction (for example, I might not always be sure that decrementing the end() iterator is well defined, but I know the reverse_iterator way is always well defined because o how its implementation is hidden and robust).