Adding struct in container in sorted way

[bunnyboy]

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.

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

[Clinton Portis]

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

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

#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.

[Clinton Portis]

Error - Line #6, Should be:

bool deq_test(Str& deq1, Str& deq2){Return (deq1.a < deq2.a);}

[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

[JasonHippy]

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?

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]

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:

#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.

[bunnyboy]

Yes it does work! :) I'm very grateful to you ... TNX!

[Clinton Portis]

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