Using Multiset

The way to swing the list follows the algorithm below :

1Pick the smallest integer from s and append it to the result.
2Pick the smallest integer from which is greater than the last appended integer to the result and append it.
3Repeat step 2 until you cannot pick more integers.
4Pick the largest integer from s and append it to the result.
5Pick the largest integer from s which is smaller than the last appended integer to the result and append it.
6Repeat step 5 until you cannot pick more integer.
7Repeat the steps from 1 to 6 until you pick all integers from s .


Input Format

The first line has a integer meaning there are n lists.

The next n line, each line has a list. The first integer l of a line is the length of the list. And followed integers are the elements of the list.

The code below shows segmentation fault, and I'm thinking the way I use the multiset iterator isn't applicable.
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
#include <cmath>
#include <cstdio>
#include <vector>
#include <queue>
#include <list>
#include <iostream>
#include <algorithm>
#include <set>
#include <iterator>
using namespace std;


int main() {
   int n;
    cin>>n;
    while(n--)
    {
       int L,val;
        cin>>L;  
        multiset<int> A;
        A.clear();
        for(int i=0;i<L;i++)
        { int x; cin>>x;  A.insert(x);}
        
        list<int> myList = list<int>();
        while(!A.empty())
        {
            val=*(A.begin());
            myList.push_back(val);
            A.erase(A.begin());
        
            while(*(A.begin())>val)
            {
             val=*(A.begin());
             myList.push_back(val);
             A.erase(A.begin());
            }

            val=*(A.end());
            myList.push_back(val);
            A.erase(A.end());
            
             while(*(A.end())<val)
            {
             val=*(A.end());
             myList.push_back(val);
             A.erase(A.end());
            }
            
        }

        for(auto v: myList)
        cout<<v<<" ";
        cout<<"\n";
        
    }
    return 0;
}

Last edited on
and it faults at which line? Where does tracing through the code using the debugger cause an issue?

For run-time issues, use the debugger to find where is the problem.
L35. After the .erase() at L39, the iterator it is invalid as the entry has been removed. Trying to de-reference an invalid iterator is a no-no .erase() returns a valid iterator so don't you mean something like:

1
2
3
4
5
while((*it)>val) {
    val=*it;
    myList.push_back(val);
    it = A.erase(it);
}


and similarly for elsewhere in the code. When using iterators, you always need to make sure they are valid.

Last edited on
Topic archived. No new replies allowed.