I ran into the fact that my program works incorrectly if I "just" launch it for execution. But if you put breakpoints in IDE, it works fine. I implement the list with gaps and for the test I just fill it with numbers from 1 to 10. If I run "just", it turns out that

lvl 0 :1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 lvl 1 :1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 lvl 2 :1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 lvl 3 :1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

Or that:

 lvl 0 :1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 lvl 1 :1 lvl 2 :1 lvl 3 :1

If with breakpoints, then about this:

 lvl 0 :1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 lvl 1 :1 -> 2 -> 4 -> 6 -> 9 lvl 2 :1 -> 6 -> 9 lvl 3 :1

I use CLion.

Code:

main:

 #include <iostream> #include "SkipList.h" int main() { SkipList list{4, 1/4.0}; for (int i = 0; i < 10; i++) { list.push(i + 1); list.out(); } //list.out(); }

SkipList.h:

 // // Created by nail1 on 09.08.2018. // #ifndef INC_18_11_SKIPLIST_H #define INC_18_11_SKIPLIST_H struct intList { int value; intList* next {nullptr}; }; class SkipList { intList** lvls; int numb_lvls; double p; void pushInLvl(int numb, int val); void findPlace(intList **prev, intList **next, int numb, int val); public: SkipList(int numb, double pp) : numb_lvls{numb}, p{pp} {lvls = new intList*[numb]{nullptr};} void push(int val); void out(); }; #endif //INC_18_11_SKIPLIST_H

SkipList.cpp:

 // // Created by nail1 on 09.08.2018. // #include "SkipList.h" #include <cstdlib> #include <ctime> #include <iostream> void SkipList::push(int val) { for (int i = 0; i < numb_lvls; i++) { srand(time(NULL)); double rand_numb = ( rand() % 101 ) / 100.0; if (i == 0 || !lvls[i] || rand_numb < p) pushInLvl(i, val); else return; } } void SkipList::pushInLvl(int numb, int val) { intList* prev{nullptr}; intList* next{nullptr}; findPlace(&prev, &next, numb, val); intList* newMemb = new intList{val, nullptr}; if (!prev && !next) { lvls[numb] = newMemb; return; } else if (!prev) { newMemb->next = next; lvls[numb] = newMemb; return; } else if (!next) { prev->next = newMemb; return; } else if (prev && next) { newMemb->next = next; prev->next = newMemb; return; } } void SkipList::findPlace(intList **prev, intList **next, int numb, int val) { *prev = nullptr; *next = nullptr; intList* curLvl{lvls[numb]}; if (!curLvl) return; else if(val < curLvl->value) { *next = curLvl; return; } else { *prev = curLvl; *next = curLvl->next; while (*next && (*next)->value < val) { *prev = *next; *next = (*next)->next; } } } void SkipList::out() { for (int i = 0; i < numb_lvls; i++) { std::cout << "lvl " << i << " :"; intList* curLvl = lvls[i]; while(curLvl) { std::cout << curLvl->value; if (curLvl->next) std::cout << " -> "; curLvl = curLvl->next; } std::cout << std::endl; } }
  • If you set a breakpoint and then remove and continue the program in "normal" mode, it also does not work correctly. - Cheshire Cat
  • That is, the program works correctly if you step by step “monitor it”. - Cheshire Cat

2 answers 2

You have srand(time(NULL)); it is called for each push , respectively, with a high probability of launching the same sequence of random numbers as in the previous step. And breakpoint breaks these consecutive calls.

srand makes sense to call once per stream. Well, or use more advanced random number generators.

    In the SkipList.h constructor, call

     lvls = new intList*[numb]{nullptr};

    This is not what you think. This record cannot be made at all. (Not in the standard.) Only lvls[0] := nullptr; initialized lvls[0] := nullptr; All other default values ​​are clogged with zero. Remove {nullptr} . Just do an empty initialization.

     lvls = new intList*[numb]{};
    • It is not clear what exactly you want to say. Yes, nullptr initializes only the zero element of the array, and all others are initialized by default, which for pointers means initialization to a null pointer. That is, as a result, the effect is exactly the same for all elements of the array. And it exactly matches your version with {} . That is, your option is shorter, but the effect is the same in all cases. What makes you think that “this record cannot be made at all” is not clear. - AnT
    • @AnT This is a warning to the following attempts to initialize the array. Any attempts to initialize so with non-zero values ​​will fail. Tipo I warned you. - AlexGlebe