Ad:

C++ Discussion Thread
Marked Solved
Views: 516

Oct 28th, 2009

Adding struct in container in sorted way

Expand Post »

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.

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;
}

Similar Threads

adding a JFrame component to JTabbedPane in Java
Alphabetically sort lines in text file in C++
Orderby equivalent in VB Scripting in Visual Basic 4 / 5 / 6
Using UserControls in ASP.NET in ASP.NET
How to position buttons/boxes in a JTabbed Pane? in Java

bunnyboy

Reputation Points: 10

Solved Threads: 1

Junior Poster in Training

Offline

55 posts
since Apr 2009

Permalink

Oct 28th, 2009

Re: Adding struct in container in sorted way

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():

(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).

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.

Clinton Portis

Reputation Points: 237

Solved Threads: 117

Practically a Posting Shark

Offline

822 posts
since Oct 2005

Permalink

Oct 28th, 2009

Re: Adding struct in container in sorted way

Error - Line #6, Should be:

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);}

Clinton Portis

Reputation Points: 237

Solved Threads: 117

Practically a Posting Shark

Offline

822 posts
since Oct 2005

Permalink

Oct 29th, 2009

Re: Adding struct in container in sorted way

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

bunnyboy

Reputation Points: 10

Solved Threads: 1

Junior Poster in Training

Offline

55 posts
since Apr 2009

Permalink

Oct 29th, 2009

Re: Adding struct in container in sorted way

Click to Expand / Collapse Quote 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?

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.

JasonHippy

Reputation Points: 590

Solved Threads: 123

Practically a Master Poster

Offline

672 posts
since Jan 2009

Permalink

Oct 29th, 2009

Re: Adding struct in container in sorted way

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:

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

Click image for larger version

Name: SortedDeque.png
Views: 19
Size: 9.1 KB
ID: 12365

JasonHippy

Reputation Points: 590

Solved Threads: 123

Practically a Master Poster

Offline

672 posts
since Jan 2009

Permalink

Oct 29th, 2009

Re: Adding struct in container in sorted way

Yes it does work!

I'm very grateful to you ... TNX!

bunnyboy

Reputation Points: 10

Solved Threads: 1

Junior Poster in Training

Offline

55 posts
since Apr 2009

Permalink

Oct 29th, 2009

Re: Adding struct in container in sorted way

I just want to say that the deque class reminds me of Dairy Queen teehee.

Clinton Portis

Reputation Points: 237

Solved Threads: 117

Practically a Posting Shark

Offline

822 posts
since Oct 2005

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: help with binary search trees and saving them

Next Thread in C++ Forum Timeline: Urgent help neede! Need to extract speech transcript from video

DaniWeb Message

Cancel Changes

User Name
Password