Segmentation Fault ... Templates

SexyBachelor (41)
Hey there,

I'm writing code to sort two vectors simultaneously. One list is used to sort both of them.

Here is the code:

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
 
		// sorts countVect highest count first
		// dataVect gets sorted in the same arrangement as countVect
		// does nothing if countVect.size() != dataVect.size()
		template <typename T>
		void sortTogether( std::vector<int> & countVect, std::vector<T> & dataVect )
		{
			
			std::vector<int> countRet;
			std::vector<T> dataRet;

			if( countVect.size() != dataVect.size() )
				return;

			if ( countVect.size() == 0 )
				return;

			countRet.push_back(countVect[0]);
			dataRet.push_back(dataVect[0]);

			// linear sort of ""Vect int ""Ret
			for( int index = 1; index < countVect.size(); index++ )
			{	
				int count = countVect[index];
				T data = dataVect[index];

				for(int i = 0; i < countRet.size(); i++)
				{
					if(countRet[i] >= count)
					{
						// if last element, add
						if(i + 1 == countRet.size() )
						{
							countRet.push_back(count);
							dataRet.push_back(data);
							break;
						}

						// else, there's more elements... continue
						continue;
					}
					// countRet[i] < count
					else
					{
						// insert before i
						countRet.insert(countRet.begin() + i, count);
						dataRet.insert(dataRet.begin() + i, data);
					}
				}
			}
			
			countVect.swap(countRet);
			dataVect.clear();
			
			for(int i = 0; i < dataRet.size(); i++)
				dataVect.push_back(dataRet[i]);

		}


The error happens on the last line. I initially was using vector.swap(vector) for both (and I would like to) but I was just trying the clear and pushing to see if it fixed the problem.. but it didnt. at dataVect.push_back(dataRet[i]) I get a segmentation fault, and I don't know why.

The only difference between countVect and dataVect is that one is <int> and one is <template T>

I'm guessing it's because dataRet and dataVect are template types.. but vectors are template types so that doesn't make sense, vector should be able to handle a template anyways.

Anyone have any idea what may be causing the segmentation fault?
slicedpan (155)
What type are you using as the template parameter when you get the segfault?
slicedpan (155)
Actually, I thought that maybe the copy constructor for whatever T is might be the culprit, but if it doesn't segfault at line 18 then that's unlikely.
SexyBachelor (41)
In the program i use char as the parameter for dataVect.
SexyBachelor (41)
I found a problem in the code, but it didn't fix the problem I made this post about.

After line 46 there should be a break command to prevent count and data from being entered in-front of every single entry in dataRet and countRet.

However, fixing this (adding the break) did not fix the problem.
closed account (3hM2Nwbp)
Hello, I'm a bit short on time at the moment, so I haven't traced through your code, however: a possible debugging technique could be to change your std::vector::operator[] calls to std::vector::at(size_t) calls and to surround your suspect code blocks with a try block that catches std::out_of_range. That'll show you what part of your program is having a problem.

std::vector::operator[] doesn't run range-checking before accessing an address - resulting in unspecified results if the subscript is out of range

std::vector::at(size_t) however, does run range-checking and will throw std::out_of_range if the subscript is out of range.
SexyBachelor (41)
debug:

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
 
(gdb) run
Starting program: /home/josh/Desktop/test/a.out 
Enter a line to be decrypted.
lkjlkjljlkjljlkjlkjd
Sizes: 4, 4

Program received signal SIGSEGV, Segmentation fault.
0xb7d935f6 in ?? () from /lib/i386-linux-gnu/libc.so.6
(gdb) backtrace
#0  0xb7d935f6 in ?? () from /lib/i386-linux-gnu/libc.so.6
#1  0xb7f8c51f in operator delete(void*) () from /usr/lib/i386-linux-gnu/libstdc++.so.6
#2  0x0804a8a9 in __gnu_cxx::new_allocator<int>::deallocate (this=0xbffff20c, __p=0x804f008) at /usr/include/c++/4.6/ext/new_allocator.h:98
#3  0x0804a3cb in std::_Vector_base<int, std::allocator<int> >::_M_deallocate (this=0xbffff20c, __p=0x804f008, __n=4)
    at /usr/include/c++/4.6/bits/stl_vector.h:156
#4  0x080499a1 in std::_Vector_base<int, std::allocator<int> >::~_Vector_base (this=0xbffff20c, __in_chrg=<optimized out>)
    at /usr/include/c++/4.6/bits/stl_vector.h:142
#5  0x08049396 in std::vector<int, std::allocator<int> >::~vector (this=0xbffff20c, __in_chrg=<optimized out>)
    at /usr/include/c++/4.6/bits/stl_vector.h:351
#6  0x0804980d in Main::sortTogether<char> (this=0xbffff2ff, countVect=..., dataVect=...) at Main.h:85
#7  0x080490a7 in Main::findRareChars (this=0xbffff2ff, str=..., sensitivity=2) at Main.cpp:84
#8  0x08048d93 in Main::main (this=0xbffff2ff) at Main.cpp:17
#9  0x08048d39 in main () at Main.cpp:6
(gdb) quit
A debugging session is active.

	Inferior 1 [process 6029] will be killed.

Quit anyway? (y or n) y
cire (8284)
Your inner for loop logic ain't good.

Any time you get to the "insert before" portion, you increase the size of countRet and shift everything after the current element to the right. So, on the next iteration of the for loop, you compare the same 'to insert' value with the same element you just just compared it to, and again you insert it before the element, increasing the vector size and shifting everything after it to the right.. I think you can see where that's going.

cire (8284)
Perhaps something like the following could work. You might consider just returning the index vector and using it to index your vectors -- that would avoid a bit of copying.

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
 
struct cmp_by_freq
{
	std::vector<int>& frequency ;

	cmp_by_freq(std::vector<int>& f) : frequency(f) {}

	bool operator()(unsigned a, unsigned b)
	{ return frequency[a] > frequency[b] ; }
};

template <typename T>
void mySortTogether( std::vector<int> & frequency, std::vector<T>& data )
{
	if ( 0 == frequency.size()  ||  frequency.size() != data.size() )
		return ;

	std::vector<unsigned> index(frequency.size()) ;

	for ( unsigned i=0; i<index.size();  ++i )
		index[i] = i ;

	std::sort(index.begin(), index.end(), cmp_by_freq(frequency)) ;

	std::vector<int> frequency_sorted ;
	std::vector<T>   data_sorted ;

	frequency_sorted.reserve(frequency.size()) ;
	data_sorted.reserve(data.size()) ;

	for ( unsigned i=0; i<index.size();  ++i )
	{
		frequency_sorted.push_back(frequency[index[i]]) ;
		data_sorted.push_back(data[index[i]]) ;
	}

	frequency.swap(frequency_sorted) ;
	data.swap(data_sorted) ;
}
SexyBachelor (41)
Awesome! Thank-you Cire, that makes sense. Good catch. Ill try that on the code and post again if it's still not working.
Topic archived. No new replies allowed.