Vector problems

[barnsta]

When i build this program i get no errors, however a message appears saying vector subscript out of range.

What does this mean and what can i do to mkae my program work


#include <iostream>
#include <ctime>
#include <cstdlib>
#include <iomanip>
#include <cstring>
#include <time.h>
#include <vector>

using namespace std;

int size;
int input;
int x, i, n;
int searchNumber;
vector < int > numArray;
void selectionSort(vector<int>&, int);
void binarySearch(vector<int>&, int);
//int* numArray;

void generateArray()
{
cout << "Please enter the amount of random numbers to be generated: ";
cin >> input;

srand(time(NULL));

vector< int > numArray(input);

size = input;

cout << "Unsorted" << endl;

for(x = 0; x < input; x++)
{
numArray[x] = 1+(rand()%10000);
cout << numArray[x] << " ";
}
}

void selectionSort(vector <int> &numArray, int size)
{
int small=0,pos=0,tmp=0;

for(i=0;i<=size-1;i++)
{
tmp = numArray[i];
small = tmp;
pos = i;

for(int j=i;j<=size;j++)
{
if(numArray[j]<tmp)
{
tmp=numArray[j];
pos=j;
}
}

numArray[i] = tmp;
numArray[pos] = small;
}
return;
}

int binarySearch(vector <int> numArray, int size, int searchValue)
{
int low = 0;
int high = size - 1;

int mid;

while (low <= high)
{
mid = (low + high) / 2;

if(searchValue == numArray[mid])
{
return mid;
}
else if (searchValue > numArray[mid])
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
}

int main()
{
int userValue;

generateArray();

cout << endl;

cout << "Sorted" << endl;

selectionSort(numArray, size);

for(i=0;i<size;i++)
{
cout << numArray[i] << " ";
}

cout << endl;

cout << "Please search for a value within the array: ";
cin >> userValue;

clock_t startTime = clock();

for(int i =0; i<100000;i++)
{
binarySearch(numArray, size, userValue);
}

int result = binarySearch(numArray, size, userValue);

if(userValue == numArray[result])
{
cout << "The number " << userValue << " was found in the array" << endl;
}
else
{
cout << "The number " << userValue << " was not found. " << endl;
}

clock_t endTime = clock();
cout << "Execution time: " << endTime - startTime << " ticks" << endl;

cin.ignore(2);
}

[ResidentBiscuit]

It means you're trying to access space outside of your vector.\

for(int j=i;j<=size;j++)
You have areas like this. At arr[j] when j == size, you'll be out of bounds. Indices in arrays go from 0 to size - 1

[barnsta]

So how would i reconstruct my for loops so i can access space outside my vector?

[Velcrohead]

Hey buddy, I was having the same problem a while ago. Like ResidentBiscuit said, size is always going to bigger than the vector

See if changing j<=size; to j<=size-1; makes any difference. It did for me :)

[ResidentBiscuit]

So how would i reconstruct my for loops so i can access space outside my vector

Do you know what you're asking? You're asking to enter space not owned by your program (or at least owned by the vector) which is undefined behavior. At the best you'll get told to stop by your compiler. At the worst, you'll stomp on whatever data happens to be lying there and that could break anything.

[TheIdeasMan]

Or this:

for(int j=0;j < size;j++){

}

[barnsta]

Nope, tried those changes and my program is still breaking

[ResidentBiscuit]

Post your updated code inside of code tags. They are located to the right under format:.

[barnsta]

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <iomanip>
#include <cstring>
#include <time.h>
#include <vector>

using namespace std;

	int size = 0;
	int input;
	int x, i, n;
	int searchNumber;
	vector < int > numArray;
	void selectionSort(vector<int>&, int);
	void binarySearch(vector<int>&, int);
	//int* numArray;

	void generateArray()
	{
		cout << "Please enter the amount of random numbers to be generated: ";
		cin >> input;
	
		srand(time(NULL));

		vector< int > numArray(input);

		size = input;
	
		cout << "Unsorted" << endl;
	
		for(x = 0; x < input; x++)
		{
			numArray[x] = 1+(rand()%10000);
			cout << numArray[x] << " ";
		}
	}

	void selectionSort(vector <int> &numArray)
	{
		int small=0,pos=0,tmp=0;

		 for(i=0;i<size-1;i++)
		 {
 			tmp = numArray[i];
			small = tmp;
			pos = i;

 			for(int j=i;j<size-1;j++)
 			{
 				if(numArray[j]<tmp)
 				{
 					tmp=numArray[j];
 					pos=j;
				}
 			}

			numArray[i] = tmp;
			numArray[pos] = small;
		 }
		 return;
	}

	int binarySearch(vector <int> numArray, int size, int searchValue)
	{
		int low = 0;
		int high = size - 1;

		int mid;

		while (low <= high)
		{
			mid = (low + high) / 2;

			if(searchValue == numArray[mid])
			{
				return mid;
			}
			else if (searchValue > numArray[mid])
			{
				low = mid + 1;
			}
			else
			{
				high = mid - 1;
			}
		}
	}

	int main()
	{
		int userValue;

		generateArray();

		cout << endl;

		cout << "Sorted" << endl;
		
		selectionSort(numArray);

		for(i=0;i<size;i++)
		{
 			cout << numArray[i] << " ";
		}
	
		cout << endl;

		cout << "Please search for a value within the array: ";
		cin >> userValue;
		
		clock_t startTime = clock();

		for(int i =0; i<100000;i++)
		{
			binarySearch(numArray, size, userValue);
		}		
	
		int result = binarySearch(numArray, size, userValue);
		
		if(userValue == numArray[result])
		{
			cout << "The number " << userValue << " was found in the array" << endl;
		}
		else 
		{
			cout << "The number " << userValue << " was not found. " << endl;
		}

		clock_t endTime = clock();
		cout << "Execution time: " << endTime - startTime << " ticks" << endl;

		cin.ignore(2);
	}

[ResidentBiscuit]

Are you still getting the same error message? I don't see anything obvious that would lead to you being out of bounds.

[barnsta]

No errors, just a program break. I went through debugging and my program crashes when it gets to the selection sort function

[ResidentBiscuit]

Where exactly does it crash there? Have you stepped through it?

[barnsta]

Yes i have stepped through, it crashes on the first for loop of the selection sort function

[ResidentBiscuit]

Does it crash right when I gets to the for loop? Or does it crash after some number of iterations?

Is there is a reason you have literally everything in global namespace?

[barnsta]

No, just after the first for loop when it hits:
tmp = numArray[i];

[ResidentBiscuit]

numArray isn't initialized at that point. Putting everything in global space is killing you here. You have a numArray declared globally, then in generateArray() you declare another and initialize. I don't even think this should compile, but whatever. After generateArray() exits, you lose that variable. Selection sort only knows the one globally declared, it knows nothing about the one that existed in generateArray(). So when you try to access it numArray[i], it breaks because it's not even initialized.

[TheIdeasMan]

As an aside, I got this warning when compiling under g++, with the flags - Wall - Wextra -pedantic

main.cpp: In function ‘int binarySearch(std::vector<int>, int, int)’:
main.cpp:89:1: warning: control reaches end of non-void function [-Wreturn-type]

This isn't related to your current problem, but there you go.

With debugging, the big thing is the values of the variables. For example can you see the values in the vector, and are the other values valid? One or more must be wrong for it to crash.

ResidentBiscuit is right, global variables are bad news, and could yet be causing your problem. I notice you don't use references consistently.

Any way that is my 2 cents worth.

Edit: My slow typing again .....

[barnsta]

So what would i do to the code to fix this?

[ResidentBiscuit]

Get rid of all the global crap. Create the vector in main(), pass it to the functions by reference.

As a rule of thumb, don't declare a variable until you need it.

[Darkmaster]

@ResidentBiscuit: sometimes declaring a bunch of variables at a certain place isn't a bad idea ;)



just use vector.size()-1 in your loops, gets hard to use a wrong index that way