Не удалось найти причину неопределенного поведения

Question

В следующей программе я объявляю глобальную переменную (adj_matrix) с целью использования ее в различных функциях.Это определено в другой функции (init_matrix).

Я протестировал программу с помощью контрольного примера 3 1 2 и получил ошибку сегментации.

3 1 2
YES
Segmentation fault: 11

Удивительно, чтокогда я раскомментирую строку cout в функции construct_matrix, ошибка сегментации исчезает.

Для меня это похоже на случай неопределенного поведения, но я не могу понять, почему и где это происходит.Пожалуйста, помогите.

Ниже приводится программа:

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int> > adj_matrix;

void init_matrix(int size, int val)
{
    adj_matrix.reserve(size);
    for (int i = 0; i < size; ++i)
    {
        adj_matrix[i].reserve(size);
        for (int j = 0; j < size; ++j)
        {
            if(i == j)
                adj_matrix[i][i] = 0;
            else
                adj_matrix[i][j] = val;
        }
    }
}

void construct_matrix(int size, int k, int val)
{
    // k denotes how many components we want
    for (int i = k - 1; i < size - 1; ++i)
    {
        adj_matrix[i][i + 1] = val;
        adj_matrix[i + 1][i] = val;
        // Uncommenting the following line resolves the seg-fault error
        // cout << i << endl;
    }
}

void print_matrix(int size)
{
    for (int i = 0; i < size; ++i)
    {
        for (int j = 0; j < size; ++j)
            cout << adj_matrix[i][j];
        cout << endl;
    }
}

int main()
{
    int n, a, b;
    cin >> n >> a >> b;

    /*
    The solution uses the fact that atleast one of G or G complement is always connected.
    In cases where we have to show both are connected (not possible when n is 2 or 3), 
    we draw a simple graph connected v1 v2 v3...vn. The complement will be also connected (n != 2 and 3)
    */

    if(a == 1 && b == 1)
    {
        if(n == 2 || n == 3)
            cout << "NO" << endl;
        else
        {
            cout << "YES" << endl;
            init_matrix(n, 0);
            construct_matrix(n, 1, 1);
            print_matrix(n);
        }
    }
    else if(a == 1)
    {
        cout << "YES" << endl;
        init_matrix(n, 1);
        construct_matrix(n, b, 0);

        print_matrix(n);

    }
    else if(b == 1)
    {
        cout << "YES" << endl;
        init_matrix(n, 0);
        construct_matrix(n, a, 1);
        print_matrix(n);

    }
    else
        cout << "NO" << endl;

    return 0;
}

Для тех, кто заинтересован в проблеме, это решение, посетите здесь .

PS: Я проверил границы в цикле for в своих функциях, и они правильные.Если это не так, программа выдаст ошибку сегментации независимо от строки cout.

Answer 1

adj_matrix.reserve(size); Не создает никаких элементов, а просто резервирует размер вектора.Таким образом, adj_matrix[i].reserve(size); является неопределенным поведением, когда i больше adj_matrix.size()

Answer 2

Причиной / одной из причин неопределенного поведения в этом коде является использование operator[] для доступа к элементам вектора, которые еще не созданы.

С http://www.cplusplus.com/reference/vector/vector/operator[]/:

Аналогичная функция-член vector :: at имеет то же поведение, что и эта операторная функция, за исключением того, что vector :: at проверяется на наличие границ и сигнализирует о том, что запрошенная позиция выходит за пределы диапазона, вызывая исключение out_of_range.

Портативные программы никогда не должны вызывать эту функцию с аргументом n, выходящим за пределы диапазона, поскольку это вызывает неопределенное поведение.

reserve не создает новые элементы вектора.Это просто гарантирует, что вектор выделил им достаточно памяти.Если вы хотите создать новые элементы, к которым у вас есть доступ, используйте resize.(https://stackoverflow.com/a/7397862/3052438)

Я также рекомендую дважды проверить все ваши векторные обращения за пределами индексов после устранения первой проблемы.