Vector Going Out of Bounds Without Giving Error

Vector going out of bounds without giving error

STL vectors perform bounds checking when the .at() member function is called, but do not perform any checks on the [] operator.

When out of bounds, the [] operator produces undefined results.

Aren't vectors protected from going out of bounds?

No, they're not that protected. C++ makes it easy to be correct:

std::vector<int> v;
for (int i : v) // cannot go out of bounds

but in general it cannot always prove up front that you're correct:

std::vector<int> v = something();
int i = v[v[0]]; // How would the compiler know if it's legal?

To make this safe regardsless of the contents of v, you can write

int i = v.at(v.at(0)); // might throw at runtime

but this is slower because of the additional runtime check.

vector going out of bounds depending on a swap statement

In the first loop iteration:

• i is 0
• A.at(i) is 417
• A.at(A.at(i)-1) is A.at(416) which is 589
• Then you swap A.at(0) with A.at(416), so now A.at(0) is 589 and A.at(416) is 417.
• Then you execute if(A.at(i)!=A.at(A.at(i)-1)). But since A.at(i)-1 is 588, so this does if(589 != A.at(588)) which accesses out of bounds.

Perhaps you meant to do the if test first, i.e.:

if(A.at(i)<=n && A.at(i)>0){
   if(A.at(i)!=A.at(A.at(i)-1)){
        swap(A.at(A.at(i)-1),A.at(i));
        i--;
    }
}

IMO it would be easier to read to use some aliases, e.g.:

auto& current = A.at(i);

if ( current > 0 && current <= n )
{
    auto& other = A.at(current - 1);
    if ( current != other )
    {
        swap(current, other);
        --i;
    }
}

Vector going out of bounds

I have a very strong feeling that this line of code:

i++;

is your culprit which is missing either a needed break condition or another conditional check that is missing from your loops. As it pertains to your nested while loops' conditions since they are based on the current size of your vector and are not being updated accordingly.

while (pieces.size() > 1) {
    // ...
    while (i < pieces.size()) {
        // ...
        while (j < pieces.size()) {
              // ...
        }
    }
} 

This is due to the fact that you are calling this within the inner most nested loop:

 pieces.erase(pieces.begin() + j);

---

You are inside of a nested while loop and if a certain condition is met you are then erasing the object at this index location within your vector while you are still inside of the inner while loop that you never break from or check to see if the index is still valid.

Initially you are entering this while loop with a vector that has 6 entries, and you call erase on it within the nested loop and now your vector has 5 entries.

This can reek havoc on your loops because your index counters i & j were set according to the original length of your vector with a size of 6, but now the vector has been reduced to a size of 5 while you are still within the inner most nested loop that you never break from nor check to see if the indices are valid. On the next iteration these values are now invalidated as you never break out of the loops to reset the indices according to the new size of your vector, nor check to see if they are valid.

---

Try running this simple program that will demonstrate what I mean by the indices being invalidated within your nested loops.

int main() {
    std::vector<std::string> words{ "please", "erase", "me" };

    std::cout << "Original Size: " << words.size() << '\n';
    for (auto& s : words)
        std::cout << s << " ";
    std::cout << '\n';

    words.erase(words.begin() + 2);

    std::cout << "New Size: " << words.size() << '\n';
    for (auto& s : words)
        std::cout << s << " ";
    std::cout << '\n';

    return 0;
}

-Output-

Original Size: 3
please erase me
New Size: 2
please erase

Accessing an array out of bounds gives no error, why?

Welcome to every C/C++ programmer's bestest friend: Undefined Behavior.

There is a lot that is not specified by the language standard, for a variety of reasons. This is one of them.

In general, whenever you encounter undefined behavior, anything might happen. The application may crash, it may freeze, it may eject your CD-ROM drive or make demons come out of your nose. It may format your harddrive or email all your porn to your grandmother.

It may even, if you are really unlucky, appear to work correctly.

The language simply says what should happen if you access the elements within the bounds of an array. It is left undefined what happens if you go out of bounds. It might seem to work today, on your compiler, but it is not legal C or C++, and there is no guarantee that it'll still work the next time you run the program. Or that it hasn't overwritten essential data even now, and you just haven't encountered the problems, that it is going to cause — yet.

As for why there is no bounds checking, there are a couple aspects to the answer:

• An array is a leftover from C. C arrays are about as primitive as you can get. Just a sequence of elements with contiguous addresses. There is no bounds checking because it is simply exposing raw memory. Implementing a robust bounds-checking mechanism would have been almost impossible in C.
• In C++, bounds-checking is possible on class types. But an array is still the plain old C-compatible one. It is not a class. Further, C++ is also built on another rule which makes bounds-checking non-ideal. The C++ guiding principle is "you don't pay for what you don't use". If your code is correct, you don't need bounds-checking, and you shouldn't be forced to pay for the overhead of runtime bounds-checking.
• So C++ offers the std::vector class template, which allows both. operator[] is designed to be efficient. The language standard does not require that it performs bounds checking (although it does not forbid it either). A vector also has the at() member function which is guaranteed to perform bounds-checking. So in C++, you get the best of both worlds if you use a vector. You get array-like performance without bounds-checking, and you get the ability to use bounds-checked access when you want it.

Getting out of bounds error at the runtime without any output

Output is buffered. You can use std::endl or std::cout.flush() to force a flush of the stream:

for (size_t i = 0; i < s; i++)
{
    cout << v.at(i) << " ";
    cout.flush();
    v.pop_back();
}

PS: As mentioned in comments this code is bound to fail. You iterate till i < s but remove an element in each iteration. I suppose the code is merely to demonstrate the issue of missing output.

Can a char vector go out of bounds?

Yes there ary many places in your code that can cause a seg fault (or other undefined behaviour):

if(pay[1]=='0') // UB if pay.size() < 2
{
    pay.erase(pay.begin());
    while(pay[0]=='0') // UB if pay.size() < 1, e.g. if pay is originally "00000" this loop has UB
        pay.erase(pay.begin()); // UB if pay.size() < 1
}
else
{
    maxdigit=*max_element(pay.begin(),pay.end()); // UB if pay is empty, max_element will return pay.end(), dereferencing this iterator is UB
    p = find(pay.begin(),pay.end(),maxdigit);
    pay.erase(p);   
}

Safer code would be:

if(!pay.empty() && pay.front()=='0') // I'm assuming pay[1]=='0' was meant to be pay[0]=='0'
{
    pay.erase(pay.begin());
    while(!pay.empty() && pay.front()=='0')
        pay.erase(pay.begin());
}
else
{
    p = max_element(pay.begin(),pay.end());
    if (p != pay.end())
    {
        maxdigit = *p;
        pay.erase(p);
    } 
}

Can I access a location in vector which I haven't declared?

The answer can be read in the C++ reference.

Here you can read that no boundary check will be done and no new element will be inserted. You simply have undefined behaviour.

So, in moredetail:

• using an index operator with an index bigger than the size of the vector, will not increase the size of the vector and add new elements.
• Using an out of bound index that is bigger than the vectors size, will simply access a memory location, which does not belong to the vector.
• Reading such a position will mostly give a random value or better set, an undefined value. This will usually not harm your program, except that you get undefined values back.
• Writing to an out of bounds value usually is a very severe problem, because you are overwriting memory, which you do not won. Very dangerous.

If you want to have boundary checking, then use vectors at-function.

---

Related Topics