Implementing treesort

[redf150flames]

Trying to get my treesort function to execute but I'm getting a segmentation fault. Any help would be appreciated.

Assignment
Implement the TREESORT function after the following algorithm:

Given: * a vector filled with N values of some type T; not in order;
* and empty set<T>

Step1: Iterate over the vector and insert each vector element into
the Set;

Step2: Iterate over the set, and copy the first set element into
[0] of vector, the second set element into [1] of vector,
etc.

#include <vector>
#include <iostream>
#include <set>
using namespace std;

template <class T>
void treesort(vector<T> & data)
{
	// declare a search tree of the correct type
	multiset<T> sorter;
	typename vector<T>::iterator itr, stop;
	stop=data.end();

	// copy the entire vector into the tree
	for (itr=data.begin(); itr != stop; ++itr)
		sorter.insert(*itr);

	// now copy the values back into the array
	typename multiset<T>::iterator tree;
	for (itr = data.begin(); itr != stop; ++itr)
		*itr = *tree++;
}

int main() {
	// Get size of vector
	int N; 
	cout << "Enter size for the vector: ";
	cin >> N;
	// Create vector of size N
	vector<int> v(N);
	// Fill vector with user input for elements
	cout << "Fill vector with the following elements: ";
	for (int i=0;i<N;i++)
		cin >> v[i];
	// Print out vector
	for (int i=0;i<N;i++)
		cout << v[i] << " ";	

	treesort(v);

	for (int i=0;i<N;i++)
		cout << v[i] << " ";

	return 0;
}

I used gdb to get more info on the seg fault and got this:

Program received signal SIGSEGV, segmentation fault.
0x00007ffff7b4acf0 in std::_Rb_tree_increment(std::_Rb_tree_node_base const*)
() from /usr/lib.../libstdc++.so.6

[long double main]

// now copy the values back into the array
typename multiset<T>::iterator tree;
for (itr = data.begin(); itr != stop; ++itr)
    *itr = *tree++; // Umm...where is 'tree' pointing to? 

[redf150flames]

To be honest I have no idea. I just copied the template from our book which is not a good book. It doesn't explain anything.

[Duthomhas]

LDM's response is a hint to help you.

A multiset is a set that may have more than one copy of a value. Hence, given a list (std::vector) of unordered values, like:

    1 7 9 3 7 1 9 7 4

You can then insert each of those into the multiset. The multiset orders the values:

    { 1 1 3 4 7 7 7 9 9 }

All you have to do is copy the values back from the set into the original vector. Try to figure out what to set "tree" to reference when you first create it. If you can't get past that before your homework is due, just use a standard int i just like when you print the vector.

Hope this helps.

[redf150flames]

Would "tree" have to be set to reference the 0 position in the multiset?

This might be a dumb question, but is "tree" first created at typename multiset<T>::iterator tree;? If so, how would I set the value?

Also, where would I put the int i if I did it that way?

[redf150flames]

I'm not sure but I may have made some progress.

I changed

typename multiset<T>::iterator tree;
for (itr = data.begin(); itr != stop; ++itr)
    *itr = *tree++;

to

typename multiset<T>::iterator tree;
for (int i=0; i < data.size(); i++)
data[i] = *itr;

and the program runs but after sorting, it returns a vector zeros the size of the vector.

[Duthomhas]

The sorted stuff is in sorter. The place you want to put it is data, right?

So data[i] has to be on the left side of the assignment, and the iterator into sorter on the right.