CODEWITHSUNDEEP
c++
devjoco
devjoco

Reputation: 484

Iterator for-loop won't acknowledge loop finished condition

This is a snippet of my program which takes a list of integers A, a number of queries Q (a bunch of ranges in the list to be sorted), and an index k. The list is sorted according to the queries, and afterwards the kth index is printed out.

Specifically:

Sorting A from (0,1), then (3,4), and finally (0,4) gives the final list of integers [2,3,5,8,9,4,3,1,9,7] where the kth index is 8, and this number is printed out.

After sorting a range of the integers, that range is recorded to avoid sorting the same range multiple times unnecessarily. These recorded ranges are stored in the variable sortedSegments.

Before sorting A according to a query, the for-loop will iterate through sortedSegments to see if the new range to sort A by has already been sorted. The problem is that the for-loop is not exiting when it should be after it iterates through all of sortedSegments.

The reason that it won't exit the loop I cannot figure out, and so I figured I would post it here so someone could point out my inevitably obvious mistake: 

    typedef vector<pair<int,int>>   pairVec;

    bool hasOverlappingRange(pair<int,int> r1, pair<int,int> r2) {
         return (r1.first)<=(r2.second) && (r1.second)>=(r2.first);
    }

    pairVec sortedSegments;

    pairVec::iterator sit = sortedSegments.begin();
    for(sit; sit!=sortedSegments.end(); ++it) 
    { // iterate through the known ordered segments, check if query overlaps one.
        if(hasOverlappingRange( {lowIdx,highIdx} , *sit)){
            sortPortion(a, {lowIdx, highIdx}, *sit);
            segmentSorted = true;
        }
        // This is where the program breaks
    }

    if (!segmentSorted) {
        sortPortion(a, {lowIdx,highIdx},{-1,-1});
        sortedSegments.push_back( {lowIdx,highIdx} );
    }

I've inserted print lines throughout the code to watch the execution of the program and after running this verbose version of the code, the output is:

Pre-sort  A:  8 5 3 9 2 4 3 1 9 7 Segments: [] This Q: (0,1)
done checking all sorted segments
seg not sorted yet
uP:  5 sP:  8
seg sorted
new idx pushed onto segments
Post-sort A:  5 8 3 9 2 4 3 1 9 7 Segments: [ (0, 1)]

Pre-sort  A:  5 8 3 9 2 4 3 1 9 7 Segments: [ (0, 1)] This Q: (3,4)
checking if Q(3,4) overlaps (0,1)
no overlapping region here

But the program never completes, and the program fails when it should be exiting the for-loop. I tested the exit condition by manually incrementing the iterator where it would be incremented by the loop itself, and checking to see if the iterator equals sortedSegments.end() which it does.

Upvotes: 0

Views: 100

Answers (1)

Lucas Hendren
Lucas Hendren

Reputation: 2826

    for(sit; sit!=sortedSegments.end(); ++it)

Your not actually iterating throught sit. Your iterating variable is it which I am guessing is a typo

Upvotes: 2

Related Questions