C++ Sort a pointer array in asscending order

Question

I have this function where 2 vectors get compared with each other and the program finds the sum of squared difference from the vector.

    double Search::NNS(vector<vector<double>> bb, vector<vector<double>> aa)
    {
        int M = 768; int N = 1024;
        int R = 49; int C = 36;
        //double SSD[] = MainVectorBlock[] - WallyVector[];
        //double SSD[] = SSD[] * SSD[];
        //sum = sum + SSD[];

    vector<vector<double>> &MainIMG = bb;
    vector<vector<double>> &WallyIMG = aa;
    double *SSD = new double[R*C];
    double sum = 0;


    for (int bx = 0; bx < M; bx += R)
        for (int by = 0; by < N; by += C)
        {
            Compare = new double*[R];
            for (int x = 0; ((x < R) && ((bx + x) < M)); ++x)
            {
                Compare[x] = new double[R];
                for (int y = 0; ((y < C) && ((by + y) < N)); ++y)
                {
                    if ((bx + x) >= M)
                    {
                        cout << Compare[bx + x] << Compare[by + y] << " ";

                    }

                    //cout << MainIMG[bx + x][by + y] << " ";
                    Compare[x][y] = MainIMG[bx + x][by + y] - WallyIMG[x][y];
                    Compare[x][y] = Compare[x][y] * Compare[x][y];
                    //sum += Compare[x][y];
                    SSD[R*C] += Compare[x][y];
                    //SSD[R*C] = sum;
                    //cout << Compare[x][y] << " ";
                }

            }
            //cout << "\n\n\n" << endl;
            //cout << sum << endl;
            //cout << SSD[R*C] << "\t" << sum << endl;

            for (int i = 0; i < R*C; i++)
            {
                for (int j = 0; j < R*C; j++)
                {
                    if (SSD[i] > SSD[j])
                    {
                        int temp = SSD[i];
                        SSD[i] = SSD[j];
                        SSD[j] = temp;
                    }
                }
            }

        }
    for (int a = 0; a < R*C; a++)
    {
        cout << SSD[a] << endl;
    }

    return 0;
}

I can display all of the sum of squared difference values, however when I try to sort the values in ascending order, I keep on getting this value -6.27744e+66. I have tried to change the loop and place it throughout the main for-loop but I still keep on getting that value.

Answer 1

double *SSD = new double[R*C];

You have allocated memory but never initialized it to some value. Then you have used it directly:

SSD[R*C] += Compare[x][y];

initialize all the items of SSD to 0 before start adding values to it.

Answer 2

There are multiple issues with your code.

1. You're passing 2D vectors by value to the NNS function, when they should be passed by const reference.
2. You are creating memory leaks within the nested for loop.
3. You are writing one past the end of the array SSD in the sum calculation.
4. Your SSD array was not initialized to 0.

Here is a version of your function that does not have memory leaks, and will allow you to address item 3) above. Granted this can be improved, but it does not have the issues mentioned above.

#include <vector>
#include <iostream>
#include <algorithm>

double Search::NNS(const std::vector<std::vector<double>>& bb, 
                   const std::vector<std::vector<double>>& aa)
{
    int M = 768; int N = 1024;
    int R = 49; int C = 36;
    const std::vector<std::vector<double>> &MainIMG = bb;
    const std::vector<std::vector<double>> &WallyIMG = aa;
    std::vector<double> SSD(R * C);
    double sum = 0;

    for (int bx = 0; bx < M; bx += R)
    {
        for (int by = 0; by < N; by += C)
        {
            std::vector<std::vector<double>> Compare(R, std::vector<double>(R));
            for (int x = 0; ((x < R) && ((bx + x) < M)); ++x)
            {
                for (int y = 0; ((y < C) && ((by + y) < N)); ++y)
                {
                    Compare[x][y] = MainIMG[bx + x][by + y] - WallyIMG[x][y];
                    Compare[x][y] = Compare[x][y] * Compare[x][y];
                    SSD.at(R*C) += Compare[x][y];
                }
            }
        }
    }
    std::sort(SSD.begin(), SSD.end());
    for (int a = 0; a < R*C; a++)
        std::cout << SSD[a] << std::endl;
    return 0;
}

Issue 1) is addressed by passing the vectors by const reference. Passing the vector's by value as your original code was doing incurs an unnecessary copy.

Issue 2) is addressed by using std::vector instead of new[]. There are now no memory leaks.

Issue 3) is not addressed directly. What was done was to use std::vector::at() to demonstrate that there is an out of bounds condition occurring. A std::out_of_range exception will be thrown if you're going out of bounds when at() is used, showing there is an error in your array accesses. Your code would have stopped as soon as that line was executed. Here is where I leave it to you to solve the boundary condition.

You may also want to use at() on the Compare vector to ensure you're not going out-of-bounds there. I am lazy and didn't want to do the calculation in my head, but whenever you have for loop conditions that do not use the vector::size() as a limiting condition and instead, a calculation is used to determine how far to loop, it looks suspicious and is a candidate for an out-of-bounds situation to occur.

Also, when you used new[], there is no guarantee you will get this error, and from what you've stated, you didn't get an indication you were doing something wrong. Using std::vector gives you a chance to check boundary conditions using at().

Issue 4) is addressed by using std::vector<double>, as by default, the vector will initialize the contents to 0.

Last, note the usage of std::sort to sort the range, and not the slow bubble sort.