Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
1

Ошибка "Segmentation fault" при вызове метода erase() контейнера vector

05.02.2019, 16:28. Просмотров 1278. Ответов 34

Хочу убрать изолированные вершины в графе. На строке 75 выдает "Segmentation fault".

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <vector>
#include <forward_list>
 
using namespace std;
 
struct Node
{
    int weight;
    int vertex;
};
 
int main()
{
    vector<forward_list<Node> > g;
    int nvertex, nedges;
    cin >> nvertex >> nedges;
    g.reserve(nvertex);
    int nv1, nv2, edgeWeight;
    Node *inode = new Node;
    // ввожу граф
    for(int i = 0; i < nedges; ++i)
    {
        cin >> nv1 >> nv2 >> edgeWeight;
        // пусть вершины с 0 нумеруются
        --nv1;
        --nv2;
        bool isEdgeUnique = true;
        // проверка ребра на уникальность
        // (если ребро (nv1, nv2) или (nv2, nv1) уже есть в графе g и его вес больше, чем edgeWeight, то меняем его вес на edgeWeight 
        for(forward_list<Node>::iterator itv1 = g[nv1].begin(); itv1 != g[nv1].end(); ++itv1)
        {
            if(itv1->vertex == nv2)
            {
                isEdgeUnique = false;
                if(edgeWeight < itv1->weight)
                {
                    itv1->weight = edgeWeight;
                    for(forward_list<Node>::iterator itv2 = g[nv2].begin(); itv2 != g[nv2].end(); ++itv2)
                        if(itv2->vertex == nv1)
                            itv2->weight = edgeWeight;
                }
            }
        }
        if(isEdgeUnique) // если ребро уникально
        {
            inode->vertex = nv2;
            inode->weight = edgeWeight;
            g[nv1].push_front(*inode);
            inode->vertex = nv1;
            if(nv1 != nv2)
                g[nv2].push_front(*inode);
        }
    }
    delete inode;
    inode = 0;
    
    // вывожу граф
    cout << endl;
    for(int j = 0; j < nvertex; ++j)
    {
        cout << j << ":";
        for(forward_list<Node>::iterator it = g[j].begin(); it != g[j].end(); ++it)
            cout << " " << it->vertex;
        cout << endl;
    }
    
    // пытаюсь коряво убрать изолированные вершины
    vector<forward_list<Node> >::iterator bi = g.begin();
    for(int i = 0; i < nvertex; ++i)
    {
        if(g[i].empty())
        {
            advance(bi, i);
            g.erase(bi);
           --nvertex;
        }
    }
    
    // вывожу граф
    cout << endl;
    for(int j = 0; j < nvertex; ++j)
    {
        cout << j << ":";
        for(forward_list<Node>::iterator it = g[j].begin(); it != g[j].end(); ++it)
            cout << " " << it->vertex;
        cout << endl;
    }
    return 0;
}
Например, ввожу такой граф:

5 4
1 2 5
1 2 3
2 3 4
1 4 10

Выводит:

0: 3 1
1: 2 0
2: 1
3: 0
4:
Segmentation fault

Метод empty() нормально определяет, что вершина с номером 4 изолирована, но удалить её не получается.
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.02.2019, 16:28
Ответы с готовыми решениями:

Segmentation fault при вызове метода
Собственно такое дело, имеется следующий код: Item* m_items; Player::Player() { ... ...

Ошибка "Segmentation fault" при организации дерева
Есть следующие функции Three сreateThree(Node **q) { if((*q)-&gt;p) { Three...

[C/C++] "Segmentation fault" при попытке передачи параметра командной строки.
Прога вылетает при попытке передачи параметра через командную строку.Такой код: #include...

Найти причины возникновения ошибки "Segmentation fault" в шаблонном лямбда-выражении (C++11)
Добрый день. Есть такой код:template&lt;typename ChipSelect, typename T = uint8_t&gt; static T...

Найти причины и способы исправления ошибки "Segmentation fault" в заданном коде
Здравствуйте. С языком c++ и программировании в целом только знакомлюсь. Получил задание написать...

34
LegionK
Че,пацаны,аниме?
218 / 162 / 146
Регистрация: 02.05.2017
Сообщений: 657
Завершенные тесты: 2
05.02.2019, 16:43 2
А само задание какое? Что в коде происходит?
0
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
05.02.2019, 17:16  [ТС] 3
Задание вот https://codeforces.com/problemset/problem/707/B?locale=ru
Пробовал решить представляя граф матрицей смежности, но граф занимал лимит памяти на большом числе вершин.
Теперь вот решил использовать список смежности, чтобы память сэкономить

Из решения задачки я вытащил кусок кода
Сначала в строках 15-56 я считываю граф и заношу его в вектор однонаправленных списков, эта часть кода правильна (но возможно не эффективна)
В строках 58-66 в первый раз вывожу граф на экран
В строках 68-78 избавляюсь от изолированных вершин (если в векторе есть пустой список, то этот элемент вектора следует удалить)
В строках 80-88 второй раз вывожу граф на экран

Меня интересует вот этот кусочек кода, строки 68-78
C++
1
2
3
4
5
6
7
8
9
10
11
// пытаюсь коряво убрать изолированные вершины
    vector<forward_list<Node> >::iterator bi = g.begin();
    for(int i = 0; i < nvertex; ++i)
    {
        if(g[i].empty())
        {
            advance(bi, i);
            g.erase(bi);
           --nvertex;
        }
    }
Я что-то делаю не так, ибо опыта с STL у меня мало

Добавлено через 3 минуты
Хочу задачку с использованием STL решить, нужно же все таки начинать пользоваться благами, которые C++ предоставляет

Добавлено через 44 секунды
Думаю, что итератор неправильно сдвигаю

Добавлено через 1 минуту
Саму задачку решаю алгоритмом Дейкстры
0
LegionK
Че,пацаны,аниме?
218 / 162 / 146
Регистрация: 02.05.2017
Сообщений: 657
Завершенные тесты: 2
05.02.2019, 17:29 4
peoplep8, интересная задача, а как именно вы Дейкстрой решаете? Он вроде находит кратчайшее расстояние между двумя вершинами? И если для каждого города в котором нету склада вызывать алгоритм и конечной вершиной выбирать все города в которых склад есть - я думаю оно по времени не пройдет

Добавлено через 16 секунд
peoplep8, или вы как-то по другому делаете?
0
05.02.2019, 17:29
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
05.02.2019, 17:29  [ТС] 5
Пробовал вот так, но даже в цикл не заходит
C++
1
2
3
4
5
6
for(auto i = g.begin(); i != g.end(); ++i)
{
    if(g[j].empty())
        g.erase(i);
    ++j;
}
0
Azazel-San
Mental handicap
1076 / 535 / 153
Регистрация: 24.11.2015
Сообщений: 2,186
Завершенные тесты: 1
05.02.2019, 17:29 6
Цитата Сообщение от peoplep8 Посмотреть сообщение
пытаюсь коряво убрать изолированные вершины
Вершина хранится в forward_list. Вы проверяете пустой ли ваш список, если это так, вы пытаетесь удалить весь ваш список из вектора, не похоже на удаление вершины.
Цитата Сообщение от peoplep8 Посмотреть сообщение
C++
1
vector<forward_list<Node> >::iterator
Всегда auto в приоритете.
Цитата Сообщение от peoplep8 Посмотреть сообщение
C++
1
g[i]
Нету проверки за выход массива, если nvertex != vector.size имеем выход за границы.
1
LegionK
Че,пацаны,аниме?
218 / 162 / 146
Регистрация: 02.05.2017
Сообщений: 657
Завершенные тесты: 2
05.02.2019, 17:32 7
peoplep8, Хотя вообще, я думаю это задание именно на алгоритм Флойда-Уоршелла
Хотя я могу и ошибаться, пройдет ли n^3 для 10^5?
1
Azazel-San
Mental handicap
1076 / 535 / 153
Регистрация: 24.11.2015
Сообщений: 2,186
Завершенные тесты: 1
05.02.2019, 17:32 8
Цитата Сообщение от peoplep8 Посмотреть сообщение
На строке 75 выдает "Segmentation fault"
Цитата Сообщение от peoplep8 Посмотреть сообщение
g.erase(bi);
Ну офк.. Вы все время пытаетесь удалить первый список из вашего вектора, nvertex-1 раз.
1
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
05.02.2019, 17:43  [ТС] 9
Дейкстра находит кратчайшие расстояния от одной начальной вершины до всех остальных.
Я делаю так:
для каждого склада с мукой нахожу путь до всех остальных вершин
потом в массиве weights (он содержит пути до всех остальных вершин) исключаю расстояния до складов с мукой (мне не нужно знать расстояние от одного склада с мукой для другого)
нахожу минимальный элемен min в weights
заношу min в массив минимальных расстояний mins для каждого склада
выбираю минимальный элемент из mins - это и будет минимальная сумма которую должна Маша заплатить

Добавлено через 7 минут
Azazel-San, если i-й список в векторе g пуст, то я сдвигаю итератор на i и удаляю этот список. Функция advance же сдвигает итератор...
0
LegionK
Че,пацаны,аниме?
218 / 162 / 146
Регистрация: 02.05.2017
Сообщений: 657
Завершенные тесты: 2
05.02.2019, 17:48 10
peoplep8, Можно вопрос пожалуйста?
Допустим вы посчитали расстояния для всех складов с мукой ( k* асимптотику Дейкстры(n^2 + m, m можно опустить) т.е у вас n^3 в худшем случае) ,потом вам необходимо я полагаю n^2 * k операций для того,чтобы исключить все склады с мукой из ответов. Зачем же вам удалять изолированные вершины в конце? Если можно на этапе исключения складов с мукой выбрать минимальное растояние?
Ну и n^3 вы уверены что будет работать для 2 сек и n = 10^5 ?
0
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
05.02.2019, 17:49  [ТС] 11
LegionK, возможно, что Флойдом — Уоршеллом проще решить, но Дейкстрой у меня работал для n = 450; m = 20; k = 163; но на n= 10000; m = 5054; k = 3791 получалось MEMORY_LIMIT_EXCEEDED. Я все таки хочу попробовать отослать решение с Дейкстрой. но представляя граф списком смежности, а потом уже разберусь Флойдом — Уоршеллом
0
Azazel-San
Mental handicap
1076 / 535 / 153
Регистрация: 24.11.2015
Сообщений: 2,186
Завершенные тесты: 1
05.02.2019, 17:50 12
Цитата Сообщение от peoplep8 Посмотреть сообщение
Функция advance же сдвигает итератор...
Та вы шо, жаль в коде который вы нам скинули ее там не существует..
0
LegionK
Че,пацаны,аниме?
218 / 162 / 146
Регистрация: 02.05.2017
Сообщений: 657
Завершенные тесты: 2
05.02.2019, 17:50 13
peoplep8, нет,нет, вы неправильно меня поняли, Флойд_Уоршелл имеет такую же асимптотику, т.е n^3
Я намекнул,что возможно там немного другое решение?
Но главная мысль была о том,зачем же вам в конце удалять изолированные вершины?
0
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
05.02.2019, 17:57  [ТС] 14
Azazel-San, я до этого скидывал этот код
C++
1
2
3
4
5
6
7
8
9
10
11
// пытаюсь коряво убрать изолированные вершины
    vector<forward_list<Node> >::iterator bi = g.begin();
    for(int i = 0; i < nvertex; ++i)
    {
        if(g[i].empty())
        {
            advance(bi, i);
            g.erase(bi);
           --nvertex;
        }
    }
Но он тоже не верен

Добавлено через 58 секунд
LegionK, я их удаляю не в конце, а в начале, перед работой Дейкстры

Добавлено через 1 минуту
LegionK, Потому что с изолированными вершинами алгоритм Дейкстры путается (вроде входит в бесконечный цикл)

Добавлено через 2 минуты
Вот код полностью, если интересно
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <iostream>
#include <vector>
#include <algorithm>
#include <forward_list>
#include <limits>
 
using namespace std;
 
struct Node
{
    int weight;
    int vertex;
};
 
int main()
{
    vector<forward_list<Node> > g;
    int nvertex, nedges, nFlourWarehouse;
    cin >> nvertex >> nedges >> nFlourWarehouse;
    vector<int> flourWarehouse(nFlourWarehouse);
    g.reserve(nvertex);
    int nv1, nv2, edgeWeight;
    Node *inode = new Node;
    for(int i = 0; i < nedges; i++)
    {
        cin >> nv1 >> nv2 >> edgeWeight;
        --nv1;
        --nv2;
        bool isVertexUnique = true;
        for(forward_list<Node>::iterator itv1 = g[nv1].begin(); itv1 != g[nv1].end(); ++itv1)
        {
            if(itv1->vertex == nv2)
            {
                isVertexUnique = false;
                if(edgeWeight < itv1->weight)
                {
                    itv1->weight = edgeWeight;
                    for(forward_list<Node>::iterator itv2 = g[nv2].begin(); itv2 != g[nv2].end(); ++itv2)
                        if(itv2->vertex == nv1)
                            itv2->weight = edgeWeight;
                }
            }
        }
        if(isVertexUnique)
        {
            inode->vertex = nv2;
            inode->weight = edgeWeight;
            g[nv1].push_front(*inode);
            inode->vertex = nv1;
            if(nv1 != nv2)
                g[nv2].push_front(*inode);
        }
    }
    delete inode;
    inode = 0;
    
    // уберем изолированные вершины
    vector<forward_list<Node> >::iterator bi = g.begin();
    for(int i = 0; i < nvertex; ++i)
    {
        if(g[i].empty())
        {
            advance(bi, i);
            g.erase(bi);
           --nvertex;
        }
    }
    
    for(int j = 0; j < nvertex; j++)
    {
        cout << j << ":";
        for(forward_list<Node>::iterator it = g[j].begin(); it != g[j].end(); ++it)
            cout << " " << it->vertex << ":" << it->weight;
        cout << endl;
    }
    
    int numHouse;
    for(int ihouse = 0; ihouse < nFlourWarehouse; ihouse++)
    {
        cin >> numHouse;
        --numHouse;
        flourWarehouse[ihouse] = numHouse;
    }
    
    vector<int> mins;
    for(int indHouse = 0; indHouse < nFlourWarehouse; indHouse++)
    {
        int dist;
        int v = flourWarehouse[indHouse];
        bool *intree = new bool [nvertex];
        for(int i = 0; i < nvertex; i++)
            intree[i] = false;
        vector<int> weights(nvertex, numeric_limits<int>::max());
        weights[v] = 0;
        vector<int> parent(nvertex, -1);
        while(intree[v] == false)
        {
            intree[v] = true;
            for(forward_list<Node>::iterator ind = g[v].begin(); ind != g[v].end(); ++ind)
            {
                if(weights[v] + ind->weight < weights[ind->vertex])
                {
                    weights[ind->vertex] = weights[v] + ind->weight;
                    parent[ind->vertex] = v;
                }
            }
            v = 1;
            dist = numeric_limits<int>::max();
            for(int j = 0; j < nvertex; j++)
            {
                if((intree[j] == false) && (weights[j] < dist))
                {
                    dist = weights[j];
                    v = j;
                }
            }
        }
        delete [] intree;
        intree = 0;
        
        for(int i = 0; i < nFlourWarehouse; ++i)
        {
            vector<int>::iterator it = weights.begin();
            it += flourWarehouse[i];
            weights.erase(it);
        }
        
        vector<int>::iterator begZero = remove(weights.begin(), weights.end(), 0);
        weights.erase(begZero, weights.end());
        
        int minElem = weights[0];
        for(int j = 1; j < nvertex; ++j)
            if(weights[j] < minElem)
                minElem = weights[j];
        
        mins.push_back(minElem);
    }
    
    vector<int>::iterator sum = min_element(mins.begin(), mins.end());
    cout << *sum;
    
    return 0;
}
0
LegionK
Че,пацаны,аниме?
218 / 162 / 146
Регистрация: 02.05.2017
Сообщений: 657
Завершенные тесты: 2
05.02.2019, 17:57 15
peoplep8, дико извиняюсь, но полагаю,что после строки 68 идет только вывод вашего графа (возможно проверка корректности удаления вершин), но ,извиняюсь за нескомный вопрос, зачем же вам удалять вершины из графа? Если вершина изолированна путь в неё так и не будет найден, а асимптотику это не улучшит и не ухудшит в среднем случае. Нет,конечно, есть случаи когда это повлияет в лучшую сторону, но может быть и наоборот.
0
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
05.02.2019, 18:01  [ТС] 16
А все-таки, как же правильно удалить вершину из списка смежности графа средствами STL?
0
LegionK
Че,пацаны,аниме?
218 / 162 / 146
Регистрация: 02.05.2017
Сообщений: 657
Завершенные тесты: 2
05.02.2019, 18:03 17
peoplep8, нет,конечно это замечательно, но,вы,наверное не прочитали разбор задания,верно? Конечно,это практика решения задач,это хорошо и замечательно, но там имеется более красивое решение, которое почти не требовательно к памяти и времени выполнения
Так что,если возможно,ваш код, как я предполагаю, не пройдет ряд тестов из-за большой временной сложности, советую посидеть за чашкой чая и подумать над парой моментов в этой задаче, а флойдов и дийкстр оставить на потом)
0
Azazel-San
Mental handicap
1076 / 535 / 153
Регистрация: 24.11.2015
Сообщений: 2,186
Завершенные тесты: 1
05.02.2019, 18:03 18
Цитата Сообщение от peoplep8 Посмотреть сообщение
Azazel-San, я до этого скидывал этот код
Не вижу в упор, потрохов или хотя б объявления вашей функции advance.
0
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
05.02.2019, 18:04  [ТС] 19
LegionK, да, возможно их и не нужно удалять
0
Azazel-San
Mental handicap
1076 / 535 / 153
Регистрация: 24.11.2015
Сообщений: 2,186
Завершенные тесты: 1
05.02.2019, 18:05 20
Цитата Сообщение от peoplep8 Посмотреть сообщение
Вот код полностью, если интересно
И здесь не вижу.. Правьте код, это невозможно читать. Процедурное программирование уже давно придумали.
0
05.02.2019, 18:05
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.02.2019, 18:05

Ошибка "*.exe вызвал срабатывание точки останова" и "HEAP CORRUPTION" при вызове деструктора программой
Здравствуйте! Сделал простенькое упражнение на указатели, но программа выдает названные ошибки. ...

"Идентификатор не найден" при вызове метода void
Здравствуйте. Следующая проблема: при вызове метода void Math(t1, t2), выдает ошибку &quot;идентификатор...

Ошибка при вызове wstring.erase
форум глючит ... Добавлено через 1 минуту Почему erase ругается ? std::wstring testString...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.