DaniWeb Forum Index > Software Development > C++

Adding struct in container in sorted way

Please support our C++ advertiser: Programming Forums - DaniWeb Sister Site

Thread Solved

•

Join Date: Apr 2009

Posts: 33

Reputation: bunnyboy is an unknown quantity at this point

Solved Threads: 1

bunnyboy

Offline

Light Poster

Adding struct in container in sorted way

Oct 28th, 2009

So I would like to make a function which would add elements in container in sorted manner.

Let's say we have a struct with two integer. I randomly initialize them and the add it to deque. And now what I want is that my function would add them in a way that values would be sorted. Example:

We generate numbers for 6 struct.
1 0
3 6
2 4
0 2
2 1
0 5

What I want now is that my function would add them in that order:
0 2
0 5
1 0
2 1
2 4
3 6

I came up with that, but it does not work. I am kinda new with iterators ... any help is appreciated.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream>
#include <deque>
#include <ctime>
#include <cstdlib>
 
using namespace std;
 
struct Str 
{
	int a,b;
	Str(int aa, int bb): a(aa), b(bb){}
};
 
void m_Add(const Str& str, deque<Str>& deq)
{
	if (deq.empty()) deq.push_back(str);
	else
	{
		deque<Str>::iterator it = deq.begin();
		for (int i = 0, size = deq.size(); i < size; i++)
		{
			if (str.a != deq[i].a)
			{
				it++;
			}
			else break;
		}
 
		for (int i = 0, size = deq.size(); i < size; i++)
		{
			if (str.b > deq[i].b)
			{
				it++;
			}
			else break;
		}
 
		deq.insert(it, str);
	}
}
 
int _tmain()
{
	srand((unsigned)time(NULL));
	deque<Str> deq;
 
	for (int i(0); i < 10; i++)
	{
		for (int j = 0; j < 15; j++)
		{
			Str a(rand()%3, rand()%6);
			m_Add(a,deq);
		}
	}
 
	for (int i = 0, size = deq.size(); i < size; i++)
	{
		cout << deq[i].a << " " << deq[i].b << endl;
	}
 
	return 0;
}
#include <iostream>
#include <deque>
#include <ctime>
#include <cstdlib>

using namespace std;

struct Str 
{
	int a,b;
	Str(int aa, int bb): a(aa), b(bb){}
};

void m_Add(const Str& str, deque<Str>& deq)
{
	if (deq.empty()) deq.push_back(str);
	else
	{
		deque<Str>::iterator it = deq.begin();
		for (int i = 0, size = deq.size(); i < size; i++)
		{
			if (str.a != deq[i].a)
			{
				it++;
			}
			else break;
		}

		for (int i = 0, size = deq.size(); i < size; i++)
		{
			if (str.b > deq[i].b)
			{
				it++;
			}
			else break;
		}

		deq.insert(it, str);
	}
}

int _tmain()
{
	srand((unsigned)time(NULL));
	deque<Str> deq;

	for (int i(0); i < 10; i++)
	{
		for (int j = 0; j < 15; j++)
		{
			Str a(rand()%3, rand()%6);
			m_Add(a,deq);
		}
	}
	
	for (int i = 0, size = deq.size(); i < size; i++)
	{
		cout << deq[i].a << " " << deq[i].b << endl;
	}
	
	return 0;
}

•

Join Date: Oct 2005

Posts: 481

Reputation: Clinton Portis is on a distinguished road

Solved Threads: 58

Clinton Portis Clinton Portis is offline

Offline

Posting Pro in Training

Oct 28th, 2009

Let me offer this suggestion:

Using the sort() function from <algorithm> we find that there is an overloaded version of sort() that will allow us to supply our own custom-made 'test' function. Let's use this in order to specifically perform a test between two 'deques of structs'. We'll base our test on the 'int a' attribute of the struct:

Here are the two versions of sort():

Help with Code Tags

(Toggle Plain Text)

template <class RandomAccessIterator>
  void sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
  void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp };

The version we will be using is in green (above).

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include<algorithm>
#include<deque>
#include<ctime>
...
...
bool deq_test(Str& deq1, Str& deq2){Return (deq1.a < deq2.b);}
...
Str MyStr;
...
srand(time(NULL));
...
//Randomly populate ye' deque
for(int i=0; i<6; i++)
{
     MyStr.a = rand()%10;
     MyStr.b = rand()%10;
 
     deq.push_back(MyStr);
}
...
//Deque sorting goodness
sort(deq.begin(), deq.end(), deq_test);
 
//Now your deque is sorted according to the 'int a' Str struct attribute in ascending order.
#include<algorithm>
#include<deque>
#include<ctime>
...
...
bool deq_test(Str& deq1, Str& deq2){Return (deq1.a < deq2.b);}
...
Str MyStr;
...
srand(time(NULL));
...
//Randomly populate ye' deque
for(int i=0; i<6; i++)
{
     MyStr.a = rand()%10;
     MyStr.b = rand()%10;

     deq.push_back(MyStr);
}
...
//Deque sorting goodness
sort(deq.begin(), deq.end(), deq_test);

//Now your deque is sorted according to the 'int a' Str struct attribute in ascending order.

The above code is untested and also I have never done this before but according to the instructions all this should work bueno.

Let me know how this works for ye' if you decide to use this.

Last edited by Clinton Portis; Oct 28th, 2009 at 11:08 pm. Reason: your mom.

•

Join Date: Oct 2005

Posts: 481

Reputation: Clinton Portis is on a distinguished road

Solved Threads: 58

Clinton Portis Clinton Portis is offline

Offline

Posting Pro in Training

Oct 28th, 2009

Error - Line #6, Should be:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
bool deq_test(Str& deq1, Str& deq2){Return (deq1.a < deq2.a);}
bool deq_test(Str& deq1, Str& deq2){Return (deq1.a < deq2.a);}

•

Join Date: Apr 2009

Posts: 33

Reputation: bunnyboy is an unknown quantity at this point

Solved Threads: 1

bunnyboy

Offline

Light Poster

Oct 29th, 2009

I have already try this ... and i have not been able to successfully write the comparison function which would sort deque by both values.

With your code deque is sorted only by a value, so youl'll get
let's say:
02
01
05
13
11
15
21
20

instead of :
01
02
05
11
13
15
20
21

•

Join Date: Jan 2009

Posts: 343

Reputation: JasonHippy is just really nice

Solved Threads: 63

JasonHippy JasonHippy is offline

Offline

Posting Whiz

Oct 29th, 2009

•

Originally Posted by bunnyboy

I have already try this ... and i have not been able to successfully write the comparison function which would sort deque by both values.

With your code deque is sorted only by a value, so youl'll get
let's say:
02
01
05
13
11
15
21
20

instead of :
01
02
05
11
13
15
20
21

I've not actually tried this, but would something like this work for the deq_test function?

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
bool deq_test(Str& deq1, Str& deq2)
{
 
	if(deq1.a==deq2.a)
	{
		return(deq1.b<deq2.b);
	}
	else
		return(deq1.a<deq2.a);
}
bool deq_test(Str& deq1, Str& deq2)
{

	if(deq1.a==deq2.a)
	{
		return(deq1.b<deq2.b);
	}
	else
		return(deq1.a<deq2.a);
}

In other words, if the values of deq1.a and deq2.a are the same, you sort them by their b values. Otherwise you sort them by their a values.

As mentioned, I've not tested this but I think it should work!
Cheers for now,
Jas.

If you're into metal, check out my new band at:
http://www.myspace.com/kinasis
Now booking gigs for 2010....

•

Join Date: Jan 2009

Posts: 343

Reputation: JasonHippy is just really nice

Solved Threads: 63

JasonHippy JasonHippy is offline

Offline

Posting Whiz

Oct 29th, 2009

Aha, I've just quickly tested it and it seems to work!
Here's a little program I knocked up, loosely based around previously posted code in this thread:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream>
#include <algorithm>
#include <deque>
#include <ctime>
#include <iterator>
 
using namespace std;
 
struct Str
{
	int a,b;
};
 
bool deq_test(Str& deq1, Str& deq2)
{
	if(deq1.a==deq2.a)
	{
		return(deq1.b<deq2.b);
	}
	else
		return(deq1.a<deq2.a);
}
 
int main()
{
	deque<Str> deq;
	srand(time(NULL));
	Str MyStr;
 
	cout << "Generating values and populating deque:" << endl;
	for(int i=0; i<6; ++i)
	{
		MyStr.a = rand()%10;
		MyStr.b = rand()%10;
		cout << "a = " << MyStr.a << ", b = " << MyStr.b << endl;
		deq.push_back(MyStr);	
	}
 
	cout << endl << "Sorting Deque..." << endl << endl;
	sort(deq.begin(), deq.end(), deq_test);
 
	cout << "Sorted values are: " << endl;
	for(deque<Str>::iterator iter = deq.begin(); iter!=deq.end(); iter++)
	{
		cout << "a = " << (*iter).a << ", b = " << (*iter).b << endl; 
	}
}
#include <iostream>
#include <algorithm>
#include <deque>
#include <ctime>
#include <iterator>

using namespace std;

struct Str
{
	int a,b;
};

bool deq_test(Str& deq1, Str& deq2)
{
	if(deq1.a==deq2.a)
	{
		return(deq1.b<deq2.b);
	}
	else
		return(deq1.a<deq2.a);
}

int main()
{
	deque<Str> deq;
	srand(time(NULL));
	Str MyStr;

	cout << "Generating values and populating deque:" << endl;
	for(int i=0; i<6; ++i)
	{
		MyStr.a = rand()%10;
		MyStr.b = rand()%10;
		cout << "a = " << MyStr.a << ", b = " << MyStr.b << endl;
		deq.push_back(MyStr);	
	}

	cout << endl << "Sorting Deque..." << endl << endl;
	sort(deq.begin(), deq.end(), deq_test);
	
	cout << "Sorted values are: " << endl;
	for(deque<Str>::iterator iter = deq.begin(); iter!=deq.end(); iter++)
	{
		cout << "a = " << (*iter).a << ", b = " << (*iter).b << endl; 
	}
}

And some sample output is shown in the attached .png.
Looking at the png, you can see that there are several values which have an 'a' value of 2. These have successfully been sorted by their 'b' values.

Problem solved??

Cheers for now,
Jas.

Attached Thumbnails