CODEWITHSUNDEEP
c++visual-c++bufferbuffer-overrun
GeoCap
GeoCap

Reputation: 515

VS2019: [C6386] Buffer Overrun while to

void Counting_Sort(vector<int>& A)
{
const int size = A.size();

int max = A[0];
for (int i = 1; i < size; i++)
    if (max > A[i])
        max = A[i];

int* C = new int[max + 1]{ 0 };
for (int i = 0; i < max + 1; i++)
    C[A[i]] = C[A[i]] + 1;

for (int i = 1; i < max + 1; i++)
    C[i] = C[i] + C[i - 1];

int* B = new int[size];
for (int i = size-1; i >= 0; i--)
    B[C[A[i]] - 1] = A[i];   // <-- Warning here

}

I'm not really sure why I get the warning or what exactly it means. Setting size-1 in for loop to size-2 removes the warning, but I don't uderstand why.

Upvotes: 0

Views: 247

Answers (2)

Cow Corporation
Cow Corporation

Reputation: 409

I notice four separate issues with your sample code:

  1. The computation of maximum is incorrect. Your condition should be testing if (A[i] > max)
  2. The Counting Sort algorithm's "accumulation step" should be iterating over the input data. That is, the loop should be the following (up to size, not up to max + 1):
for (int i = 0; i < size; i++)
    C[A[i]] = C[A[i]] + 1;
  1. The algorithm's final loop forgot to update the destination of each "Counting Sort bin". That is, the final loop should be the following:
for (int i = size - 1; i >= 0; i--) {
    B[C[A[i]] - 1] = A[i];
    C[A[i]] = C[A[i]] - 1;
}
  1. Don't forget to use delete[] on B and C when you are done with them.

Here is the fully edited result:

#include <iostream>
#include <vector>

void Counting_Sort(std::vector<int>& A) {
    const int size = A.size();

    int max = A[0];
    for (int i = 1; i < size; i++)
        if (A[i] > max)
            max = A[i];

    int* C = new int[max + 1]{ 0 };
    for (int i = 0; i < size; i++)
        C[A[i]] = C[A[i]] + 1;

    for (int i = 1; i < max + 1; i++)
        C[i] = C[i] + C[i - 1];

    int* B = new int[size];
    for (int i = size-1; i >= 0; i--) {
        B[C[A[i]] - 1] = A[i];
        C[A[i]] = C[A[i]] - 1;
    }

    for (int i = 0; i < size; i++)
        std::cout << "B[" << i << "] is " << B[i] << "\n";

    delete[] B;
    delete[] C;
}

int main() {
    std::vector<int> A = {6, 1, 3, 3, 6, 9};
    Counting_Sort(A);
    return 0;
}

Upvotes: 1

Heyji
Heyji

Reputation: 1211

The compliler says that the size of B is 4xsize bytes long but in some cases, 8 bytes might be written, which might overpass the 4xsize bytes length.

Take the example of A = {10} for instance.

Upvotes: 0

Related Questions