C++

Forum

 
Python Exception <class 'ValueError'>

vaderboi (140)
When I run my program, I get a segmentation fault. When I run the gdb debugger, it gives me this error:
Program received signal SIGSEGV, Segmentation Fault; 0x00000000004015cd in std::__cx11::list<int, std::allocator<int> >::erase (Python Exception <class 'ValueError'> Cannot find type std::__cx11::list<int, std::allocator$ int> >::const_iterator::_Node: this=0x7fffffffe460, __position=) at usr/include/c++/5/bits/list.tcc::155 iterator __ret = iterator(__position._M_node->_M_next);


When I establish breakpoints, I get the segmentation fault at line 82. I also know, by placing print statements throughout, that the program enters the for loop within hotPotatoLoop() twice and then enters the if-condition before the program crashes.

Can anyone tell me what is happening here? I am really confused what is happening. Is the iterator trying to access invalid memory?

(Also, I know that the program is probably pretty inefficient right now since its worst case runtime is O(n^2). That is something I am definitely going to work on)

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
 
#include <list>
#include <iostream>
#include <iterator>
#include <vector>

void hotPotatoGame( int N, int M );
std::list<int>* hotPotatoLoop( std::list<int> *myList, int M, int currentCount );
std::vector<int>* placeElementsInVector( int num, std::vector<int> *V );

int main()
{
	//"amountOfItegers" represents initial number of integers to loop through
	int amountOfIntegers = 10;
	//"amountOfPasses" represents how many elements to pass before one is deleted
	int amountOfPasses = 0;

	hotPotatoGame( amountOfIntegers, amountOfPasses );
	
	return 0;
}



void hotPotatoGame( int N, int M )
{
	std::cout << "Hot potato game function invoked " << std::endl;

	//list of integers to loop through in the hot potato game
	std::list<int> *L;
	
	std::vector<int> initialVector;

	std::vector<int> *myVector = &initialVector;

	//place integers from 1 to N in vector
	std::vector<int> *newVector = placeElementsInVector( N, myVector );

	//initialize list full of values from myVector
	std::list<int> copy( newVector->begin(), newVector->end() );

	L = &copy;
	
	//while list isn't empty continue the hot potato game
   	//for( std::list<int>::iterator itL = L->begin(); itL != L->end();  )
	
	std::list<int> *finalList;

	/*the result of the hot potato game elimination is assigned to "finalList"
	 * which essentially means it should be assigned an empty list*/
	finalList = hotPotatoLoop( L, M, 0 );

}

std::list<int>* hotPotatoLoop( std::list<int> *myList, int M, int currentCount )
{
	std::cout << "Hot potato loop function invoked" << std::endl;

	if( myList->empty() )
	{
		return myList;
	}
	else
	{
		/*keeps track of how many passes have occurred. One for-loop ends, the 
		 * current value of count is passed so that the next function call will
		 * know how many passes have already occurred*/

		std:: cout << "else condition entered " << std::endl;
		int count = currentCount;

		for( std::list<int>::iterator itL = myList->begin(); itL != myList->end(); ++itL )
		{
			std::cout << "for loop entered " << std::endl;
			/*if M passes have occurred, then delete the current element from the list.
			 * Otherwise, iterate count*/
			if( count == M )
			{
				std::cout << "if condition met" << std::endl;
				myList->erase( itL );
				count = 0;
			}
			else
			{
				std::cout << "else condition met" << std::endl;
				std::cout << *itL << " ";
				++count;
			}
		}

		std::cout << '\n';

		return hotPotatoLoop( myList, M, count );
	}	
}


std::vector<int>* placeElementsInVector( int num, std::vector<int> *V )
{
	std::cout << "placeElementsInVector function invoked" << std::endl;
	int currentValue = 1;

	for( int i = 0; i < num; i++ )
	{
		V->push_back( currentValue );
		std::cout<< (*V)[i] << std::endl;
		currentValue++;
	}
	
	return V;

}


Last edited on
JLBorges (13770)
Brute force:

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
 
#include <iostream>
#include <vector>
#include <numeric>

// return the position of the next player
std::size_t next_pos( const std::vector<int>& players, std::size_t curr_pos )
{
    #ifndef NDEBUG
        const int from = players[curr_pos] ;
    #endif // NDEBUG

    ++curr_pos ;
    if( curr_pos == players.size() ) curr_pos = 0 ; // reached end, go to the front

    #ifndef NDEBUG
        const int to = players[curr_pos] ;
        std::cout << "  " << from << " => " << to << "  | " ;
    #endif // NDEBUG

    return curr_pos ;
}

void print_players( const std::vector<int>& players )
{
    std::cout << "players left in the game: [ " ;
    for( int p : players ) std::cout << p << ' ' ;
    std::cout << "]\n\n" ;
}

// play the game, return the id of the winner
int play_game( std::vector<int> players, std::size_t passes_per_round )
{
    // position in the vector of the player currently holding the poteto
    std::size_t curr_pos = 0 ; // start with the first player

    while( players.size() > 1 ) // while there is more than one player left
    {
        #ifndef NDEBUG
            print_players(players) ;
        #endif // NDEBUG

        // make passes_per_round passes
        for( std::size_t i = 0 ; i < passes_per_round ; ++i )
            curr_pos = next_pos( players, curr_pos ) ;

        // remove the player holding hot potato
        #ifndef NDEBUG
            std::cout << " *** eliminate player " << players[curr_pos] << '\n' ;
        #endif // NDEBUG

        // https://en.cppreference.com/w/cpp/container/vector/erase
        players.erase( players.begin() + curr_pos ) ;

        // move to the first player if the last player was removed
        if( curr_pos == players.size() ) curr_pos = 0 ;
    }

    return players.front() ;
}

void hot_potato_game( std::size_t num_players, std::size_t passes_per_round )
{
    if( num_players == 0 || passes_per_round == 0 ) return ; // invalid argument

    // create a vector of size num_players
    std::vector<int> players(num_players) ;

    // place integers from 1 to num_players in vector
    // https://en.cppreference.com/w/cpp/algorithm/iota
    std::iota( players.begin(), players.end(), 1 ) ;

    // ignore the std::move if unfamiliar with move semantics
    // just write it as: const int winner = play_game( players, passes_per_round );
    const int winner = play_game( std::move(players), passes_per_round );

    std::cout << "\n*** winner *** : " << winner << '\n' ;
}

int main()
{
    hot_potato_game( 12, 7 ) ;
}

http://coliru.stacked-crooked.com/a/bb854d26c3ad7d31

To achieve verisimilitude, make the number of passes in each round a random value.
Last edited on
salem c (3685)
Line 79, check your iterator validity.
http://www.cplusplus.com/reference/list/list/erase/

 
 
itL = myList->erase( itL );

Last edited on
vaderboi (140)
My code iterates through all values without dumping memory now. Why does assigning the erased value to itL work and not myList->erase( itL ); without assignment?

Also, the list::erase constructor shows that the iterator is of type const_iterator but when I use a normal iterator my code runs without throwing an error. Why is that?
salem c (3685)
> Why does assigning the erased value to itL work and not myList->erase( itL ); without assignment?
Did you read the link?

Iterator validity
Iterators, pointers and references referring to elements removed by the function are invalidated.
All other iterators, pointers and references keep their validity.
vaderboi (140)
Yes, I did read the link. I am, however, still confused.

If I deleted the value that the iterator held, how is that different than assigning a deleted value to the iterator? Wouldn't the iterator still be referencing a non-existent value?
salem c (3685)
Have you ever tried to implement a linked list yourself, old school?

This is the naive way to delete an element
1
2
3
4
5
6
7
 
p = head;
while ( p != NULL ) {
    if ( something ) {
        delete p;
    }
    p = p -> next;
}

But doing p = p->next after delete p is wrong.

This is exactly what you're doing when you do myList->erase( itL ); and then follow up with the ++itL in the for loop.


coder777 (8439)
Note that this is wrong:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
		for( std::list<int>::iterator itL = myList->begin(); itL != myList->end(); ++itL )
		{
			std::cout << "for loop entered " << std::endl;
			/*if M passes have occurred, then delete the current element from the list.
			 * Otherwise, iterate count*/
			if( count == M )
			{
				std::cout << "if condition met" << std::endl;
				itL = myList->erase( itL ); // Wrong! ++itL above now will skip one element which might be very well the last!
				count = 0;
			}
			else
			{
				std::cout << "else condition met" << std::endl;
				std::cout << *itL << " ";
				++count;
			}
		}
You need to change the loop to:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
		std::list<int>::iterator itL = myList->begin();
		while(itL != myList->end())
		{
			std::cout << "for loop entered " << std::endl;
			/*if M passes have occurred, then delete the current element from the list.
			 * Otherwise, iterate count*/
			if( count == M )
			{
				std::cout << "if condition met" << std::endl;
				itL = myList->erase( itL ); // Note
				count = 0;
			}
			else
			{
				std::cout << "else condition met" << std::endl;
				std::cout << *itL << " ";
				++itL // Note
				++count;
			}
		}
vaderboi (140)
Thank you @coder777. One of the errors that drives me the craziest is accidentally accessing invalid memory or a for loop skipping a certain element.

Topic archived. No new replies allowed.