Program crashed after end of scope

Question

I was confused from this following codes, it's creating crash that I fully don't understand.

#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

struct Store
{
    int pos;
    char character;
};

vector<struct Store> v_store;

void swap_inside_vector(vector<struct Store> &v_store, int a, int b)
{
    struct Store tmp = v_store[b];
    v_store[b] = v_store[a];
    v_store[a] = tmp;
}

int find_inside_vector(vector<struct Store> &v_store, int pos)
{
    for(int i = 0; i < v_store.size(); i++)
    {
        if(v_store[i].pos == pos)
            return i;
    }

    return -1;
}

void swap_most_right_to_most_left(vector<struct Store> &v_store)
{
    struct Store tmp = v_store[v_store.size() - 1];

    for(int i = v_store.size(); i > 0; i--)
    {
        v_store[i] = v_store[i-1];
    }

    v_store[0] = tmp;
}

void print_char_inside_vector(vector<struct Store> &v) // used for debugging
{
    for(int i = 0; i < v.size(); i++)
    {
        printf("%C", v[i].character);
    }
}

int check_vector_original_state(vector<struct Store> &v_store)
{
    for(int i = 1; i <= v_store.size(); i++)
    {
        if(v_store[i-1].pos != i)
            return 0;
    }

    return 1;
}

int main()
{
    int n;
    char input_str[100];

    for(int q = 1; scanf("\n%d", &n), n; q++)
    {
        scanf("%s", input_str); 

        vector<struct Store> original_store, tmp_origin_store, v_store;
        vector<vector<struct Store> > store_vector;

        original_store.clear();
        tmp_origin_store.clear();
        v_store.clear();
        store_vector.clear();

        for(int i = 1; i <= strlen(input_str); i++)
        {
            struct Store s = {.pos = i, .character = input_str[i-1]};
            original_store.push_back(s);
        }

        tmp_origin_store = original_store;
        v_store = tmp_origin_store;

        for(int i = 1, current_pos = 0; i <= n; i++, current_pos++)
        {
            int vector_index = find_inside_vector(v_store, tmp_origin_store[current_pos].pos);

            //printf("Processing -> [%d], Current Pos -> [%d]\n", i, current_pos);

            for(int z = 0; z < (current_pos + 1); z++)
            {
                if(vector_index == (v_store.size() - 1))
                {
                    swap_most_right_to_most_left(v_store);
                    vector_index = 0;
                }
                else
                {
                    swap_inside_vector(v_store, vector_index, vector_index + 1);
                    vector_index++;
                }

                //print_char_inside_vector(v_store);
                //puts("");
            }

            //puts("");

            store_vector.push_back(v_store);

            if(check_vector_original_state(v_store))
            {
                store_vector.push_back(v_store);
                break;
            }

            if(current_pos == (v_store.size() - 1))
            {
                tmp_origin_store = v_store;
                current_pos = -1;
            }
        }

        // debugging
        /*for(int x = 0; x < store_vector.size(); x++)
        {
            printf("[%d] -> ", x + 1);
            print_char_inside_vector(store_vector[x]);
            puts("");
        }*/

        int target_pos;

        if(store_vector.size() < n)
        {
            target_pos = n % store_vector.size();
        }
        else
        {
            target_pos = store_vector.size();
        }

        if(target_pos == 0)
        {
            printf("%d. ", q);
            print_char_inside_vector(store_vector[0]);
            puts("");
        }
        else
        {
            printf("%d. ", q);
            print_char_inside_vector(store_vector[target_pos - 1]);
            puts("");
        }
    }
}

What this program does is accepting input from STDIN, process it, and output it on STDOUT.

My expecting input is

3 ABCD
13 ACM
3 DAEQD
4 FAEQS

Expected output is

1. CABD
2. CAM
3. DAQDE
4. FQASE

My problem is, after inputing fourth input into STDIN, and after output is being shown, crash occured.

C:\Study>h.exe
3 ABCD
1. CABD
13 ACM
2. CAM
3 DAEQD
3. DAQDE
4 FAEQS
4. FQASE
      0 [main] h 9092 cygwin_exception::open_stackdumpfile: Dumping stack trace to h.exe.stackdump

From my observation, I think the problem is at the vector, but it's just a guess.

In C++ you don't need `struct Store` everywhere you use it. You should use a debugger to see where the crash is and what causes it. — Retired Ninja, Oct 24 '14 at 19:00
[disadvantages of scanf](http://stackoverflow.com/questions/2430303/disadvantages-of-scanf) — qwr, Oct 24 '14 at 19:12
This loop`for(int i = v_store.size(); i > 0; i--) { v_store[i] = v_store[i-1]; }` has definitely problems. It starts at size() whereas the largest index of vector is size()-1 — Oncaphillis, Oct 24 '14 at 19:14
Also, this code would be greatly reduced in size if you just used the algorithm functions instead of these full-blown functions you've coded. For example `std::swap(v_store[vector_index], v_store[vector_index + 1]);` is all you need to swap two `Stores`. — PaulMcKenzie, Oct 24 '14 at 19:34
As the comment previous to mine stated, you should get out of the habit of starting your loops at 1 or at `size`. In C++, array and vector indices start at 0, not 1. If you kept that in mind when writing your code, you would reduce the chance of going out of bounds. — PaulMcKenzie, Oct 24 '14 at 19:47

score 2 · Accepted Answer · answered Oct 24 '14 at 20:50

Your code didn't compile :

//struct Store s = { .pos = i, .character = input_str[i - 1] }; // syntax not recongnized 
Store s = { i, input_str[i - 1] };   // replaced with this.

After fixing this, the debugging immediatly identified an out of bound problem on a vector, which could lead to memory corruption issue. It's in swap_most_right_to_most_left():

for (int i = v_store.size(); i > 0; i--)  {  // you start with i=v_store.size() 
    v_store[i] = v_store[i - 1];             // and you immediately get out of bounds !  
}

If you correct this instruction to :

for (int i = v_store.size()-1; i > 0; i--) {
    v_store[i] = v_store[i - 1];
}

you'll get the expected output for the given input.

Thank you very much for the correction, what debugger are you currently use now? :-) — Mohd Shahril, Oct 25 '14 at 13:11
MSVC 2013 - when you choose "debuging build", the code gets compiled with some nice tricks to detect runtime problems like memory corruption, and a lot of extra asserts in the libraries. — Christophe, Oct 25 '14 at 13:17

Program crashed after end of scope

1 Answers1