Thread: Array sort exception return

  1. #1
    Registered User
    Join Date
    Oct 2013
    Location
    greece
    Posts
    87

    Array sort exception return

    i am creating 5 deferent tables each one has 20000 more elements more than the previous when i try to sort them with the sort algorithm quick sort for the first table tha has 20000 elements runs grate then it throws this exception how is this fixable ? exception : terminate called after throwing an instanceof 'std::bad_alloc' this application has Requested the Runtime to terminate it in an unusual way. Please contact the applications's support team for more information. Process returned 255(0xFF) . here is the code that gives this return :
    Code:
    
    
    Code:
    #include<time.h>
    #include<stdlib.h>
    #include <string.h>
    #include <ctime>
    using namespace std;
    int * Create_Table(int table[],int N);
    void Quic_kSort(int arr[], int left, int right);
    int main()
    {
    for (int N=20000; N<=100000; N=N+20000)
    {
    //clock_t begin = clock();
    int *table = new int32_t [N];
    table=Create_Table(table,N);
    Quic_kSort(table,0,N);
    system("pause");
    cout << endl;
    clock_t end = clock();
    //double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    //cout << "The elapsed time for N : "<<N<< " elements is : "<<elapsed_secs<<endl;
    //delete table;
    }
    
    }
    int * Create_Table(int table[],int N)
    {
    srand(time(NULL));
        for (int i=0; i<N; i++)
            table[i]= rand()%150000;
    return table;
    
    }
    
     void Quic_kSort(int arr[], int left, int right)
     {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];
    
      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
        }
    }
    /* recursion */
    if (left < j)
        Quic_kSort(arr, left, j);
    if (i < right)
            Quic_kSort(arr, i, right);
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,719
    You ran out of available memory. Why are you not using std::vector? If you really want to use new[], then you should match it with a delete[] when you're done.

    That said, since you're not going to have an array of more than 100000 elements, you might as well create an array (or vector) with that number of elements, then reuse it on each iteration. After all, you do not have to use the entire array on every iteration.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Oct 2013
    Location
    greece
    Posts
    87
    i dont want to use vector i want to use pointers in this ocaision i tryied the delete too but it doesnt work it gives the same error is it possible to run out of memmory? that simple....

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,719
    Quote Originally Posted by wesdom
    i tryied the delete too but it doesnt work it gives the same error
    What exactly did you try? I note that you commented out delete table; but that is wrong to begin with as you used the array form of new, so you should use the array form of delete.

    Quote Originally Posted by wesdom
    is it possible to run out of memmory?
    That is what std::bad_alloc is hinting at. You might still have available memory, but not contiguously large enough.

    Anyway, as I noted, you do not need to keep creating and destroying dynamic arrays: you just need one (dynamic) array that you use over and over again.

    A few other things:
    • Get rid of <time.h> as you are already including <ctime>
    • <stdlib.h> should be <cstdlib>
    • You don't seem to need <string.h>, so you should get rid of it. If you do need it, #include <cstring>
    • You should only call srand once, typically near the start of the global main function.
    • You need to indent your code properly.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,267
    Code:
    while (arr[j] > pivot)
    You are reading past the end of your array. The array is of size N, but j is equal to N. Set j equal to (right - 1).
    bit∙hub [bit-huhb] n. A source and destination for information.

  6. #6
    Registered User
    Join Date
    Apr 2013
    Posts
    1,656
    Quote Originally Posted by laserlight View Post
    That is what std::bad_alloc is hinting at. You might still have available memory, but not contiguously large enough.
    Isn't this using a virtual address space? If so, then the physical pages can be scattered, only the virtual address space needs to be contiguous. In some cases, physical pages could end up being partially used due to many allocate and free operations on many different variables, but since only table is being allocated and freed, it shouldn't be an issue. It seems more likely that a mismatch in new ...[] and delete[] or not using [] on the delete could be the issue. As you mentioned, a one time allocation of table for the max size would be better.

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    You can still get fragmented virtual memory. If the operating system can't find a large enough contiguous virtual memory section, it will fail.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    Registered User
    Join Date
    Apr 2013
    Posts
    1,656
    Quote Originally Posted by Elysia View Post
    You can still get fragmented virtual memory. If the operating system can't find a large enough contiguous virtual memory section, it will fail.
    True in some cases, but if the example code is fixed, then the current array is freed before a new instance is allocated, so the virtual address space should also be freed up before it get's reallocated. As laserlight mentioned, it would be better to do a one time allocation of the max size array.

  9. #9
    Registered User
    Join Date
    Oct 2013
    Location
    greece
    Posts
    87
    so how can i add the memory dynamical ? without new and delete [] ?
    for instance : table = table + new int [20000];

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    1,656
    What laserlight suggested is that you create table just one time before the loop:

    Code:
    // ...
        int *table = new int[100000];
        for (int N=20000; N<=100000; N=N+20000)
    // ...
        delete[] table;

  11. #11
    Registered User
    Join Date
    Oct 2013
    Location
    greece
    Posts
    87
    thanks allot all of you ,you were really helpful i really improve my code with your advises ,and also made my code work property

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 10
    Last Post: 05-31-2012, 01:11 AM
  2. Replies: 1
    Last Post: 01-26-2010, 09:02 AM
  3. Exception, assertions AND return codes?
    By cboard_member in forum C++ Programming
    Replies: 11
    Last Post: 03-05-2008, 05:41 AM
  4. STL sort throw exception?
    By George2 in forum C++ Programming
    Replies: 11
    Last Post: 01-10-2008, 06:34 AM
  5. Replies: 5
    Last Post: 06-06-2007, 11:10 PM