Одна очевидная ошибка - ваша реализация класса Node.
Если вы посмотрите на ваш Node конструктор, который занимает один int, вы не смогли инициализировать итератор below.Таким образом, любой доступ при попытке разыменования below приведет к возникновению неопределенного поведения, как вы делаете в этой строке:
cout << (*(skipList[1].front().below)).value;
Если список пропусков пуст, вы увидите, что ваш код будет производитьNode объекты, где below не инициализирован.
Вот упрощенный, упрощенный пример, более или менее использованный вами отправленный код:
#include <list>
#include <vector>
#include <iostream>
struct Node // in header file
{
int value;
std::list<Node>::iterator below;
Node(int v, std::list<Node>::iterator b) {
value = v;
below = b;
}
Node() {}
Node(int v) {
value = v;
}
};
class SkipLists
{
private:
std::vector<std::list<Node>> skipList;
public:
void insert(int num);
std::list<Node>::iterator insertPlace(int num, std::list<Node>::iterator it, int height);
void stack(int num, std::list<Node>::iterator loc);
};
using namespace std;
void SkipLists::insert(int num)
{
list<Node>::iterator loc;
if (skipList.empty())
{
list<Node> nodes;
nodes.push_back(Node(num));
skipList.push_back(nodes);
}
else
{
loc = insertPlace(num, skipList[skipList.size() - 1].begin(), skipList.size() - 1);
skipList[0].insert(loc, Node(num));
}
stack(num, loc);
//this if statement also segfaults
if (skipList.size() > 1) {
cout << (*(skipList[1].front().below)).value;
}
}
list<Node>::iterator SkipLists::insertPlace(int num, list<Node>::iterator it, int height)
{
if (height == 0) {
while (it != skipList[0].end() && skipList[0].size() > 0 && num > (*it).value)
{
it++;
}
return it;
}
while (it != skipList[height].end() && skipList[height].size() > 0 && num > (*it).value)
{
cout << "he\n";
it++;
cout << "lo\n";
}
return insertPlace(num, (*it).below, --height);
}
void SkipLists::stack(int num, list<Node>::iterator loc) {
int flip = rand() % 2;
int count = 1;
list<Node>::iterator prev = loc;
list<Node>::iterator it;
while (flip == 1) {
count++;
flip = rand() % 2;
if (skipList.size() < count) {
list<Node> nodes;
nodes.push_back(Node(num, prev));
skipList.push_back(nodes);
prev = skipList[skipList.size() - 1].begin();
}
else {
it = skipList[count - 1].begin();
while (it != skipList[count - 1].end() && num > (*it).value) {
it++;
}
prev = skipList[count - 1].insert(it, Node(num, prev));
}
}
}
// Test
int main()
{
SkipLists s;
s.insert(4);
}
Вы увидите, что below не инициализируется в строке, в которой вы говорите, что ваше приложение дает сбой при запуске этого очень маленького образца.
У вас также есть та же проблема с конструктором Node по умолчанию, где оба value и belowчлены не инициализированы.Когда вы создаете объект, все члены должны быть в каком-то действительном состоянии или в некотором смысле «нулевыми».Для итераторов это сделать труднее, поскольку не существует «нулевого» итератора, если только вы не можете установить итератор в end() итератор существующего списка.
В основном вам нужно спроектировать свой класс так, чтобыВы уверены, что итератор указывает где-то действительный или какой-либо другой способ указать, что итератор не должен быть разыменован.