sort a struct based on one member's alpha?

[sjahf7]

I apologize in advance for my stupidity, but I am trying to sort a data stucture in order to form a database (similar to those in cell phones) which would display names and phone numbers. I'm having trouble sorting the data. Here's what I've got so far, could anyone help?

#include <iostream>
#include <string>

using namespace std;
int main()
{
int c=3; //c is number of entries
struct data_t {string name; string number;} data [c];



data[0].name="steve"; data [0].number="34"; data[1].name="bob"; data[1].number="16"; data[2].name="joe"; data[2].number="21";

string t;
int i;
for (i = 1; i < c; ++i)
{
t = data[i].name;
int k;
for (k = i-1; k >= 0 && data[k].name > t; k--)
{
data[k+1].name = data[k].name;
data[k+1].number=data[k].number;

//i added the above bolded line to an alphabatezing algorithm I got from some forum, thinking that assigning the data.number to the same array entry as the data.name would cause them to be associated after sorting; it does not

}

data[k+1].name = t;}
for(i=0;i<n;i++)
{cout<<endl<<data[i].name<<endl<<data[i].number<<endl; } system ("pause");
}

Thanks for any help
-steve

[webJose]

Any reason why you don't use std::sort()? You can use it by:

1. #including <algorithm>.
2. Defining operator< for your struct or providing a comparison function.

[sjahf7]

The reason is that I don't know how...like at all. I guess I would have to write a new sorting algorithm? The one I'm using I just took off of the web, I don't really know anything about them. Any recommendations on a good place to learn?

[webJose]

Well, it's been a very long time since I coded sorting algorithms. Mostly did that as exercise to learn to program over a decade ago. Truth be told, it is best to use what is available to you.

If you want to pursue the learning path (good for exercise), search for sorting algorithms in Wikipedia. If you want to get this done, use std::sort(), which AFAIK, it is the Quicksort algorithm, widely accepted as the best overall algorithm.

#include <iostream>
#include <algorithm>

class MyData
{
public:
    int A;
    int B;
    MyData() : A(0), B(0)
    { }
    MyData(int a, int b) : A(a), B(b)
    { }
    //std::sort requires operator<.
    bool operator<(const MyData &op2) const
    {
        //Default sorting by integer A.
        return A < op2.A;
    }
};

void DisplayArray(const MyData *parr, int size)
{
    std::cout << "Displaying array:" << std::endl;
    for(int i = 0; i < size; i++)
    {
        std::cout << "Item " << i << ":  A = " << parr[i].A << "; B = " << parr[i].B << std::endl;
    }
}

int main()
{
    MyData myArray[5];
    myArray[0] = MyData(1, 11);
    myArray[1] = MyData(9, 23);
    myArray[2] = MyData(7, 19);
    myArray[3] = MyData(8, 3);
    myArray[4] = MyData(5, 7);
    DisplayArray(myArray, _countof(myArray));
    //Sort using default sorting criterion (MyData::operator<()).
    std::sort(myArray, myArray + _countof(myArray));
    //Display the sorted array.
    DisplayArray(myArray, _countof(myArray));
#ifdef DEBUG
    cin.get();
#endif
    return 0;
}

It is that simple. :D

[sjahf7]

ok newbie alert. is the "std::" before certain functions equivalent to "using namespace std;"?
also, my compiler gives an error about _countof being not defined.

[webJose]

Yes, it is the namespace. If you don't using namespace std;, then you must fully qualify the function and class names with the namespace they belong to, in this case std.

About _countof(), I'm used to having it available in MS Visual Studio. It returns the number of elements in a stack array. In C it can be defined as:

#define _countof(x) (sizeof(x) / sizeof(x[0]))

But using a template is safer in C++. Don't ask me about the template definition because I don't know it. I guess I could look it up in the header files but alas, I'm kind of full with my lunch right now and that seems to be like a lot of work! :-P

Now you know what _countof() is supposed to return. Use the C #define I show or just hardcode the array size (5 in my example).

[kev82]

bool operator<(const MyData &op2) const
    {
        //Default sorting by integer A.
        return A < op2.A;
    }

That looks very bad to me. What about B? I could sort permutations of the same data and get a different answer with your comparator.

[webJose]

Not sure what you mean by bad. Works just fine ordering the array example perfectly by A. If that is not the desired sort order you simply code the sort order that you want. The example intends to merely demonstrate how to code a simple class and enable it for std::sort(). Nothing more. It doesn't intend to show all possible sorting criteria that could be programmed into operator<().

Or am I misunderstanding?

[bluecoder]

I think this will solve the problem .

// Sorting the data structure . 
#include <iostream>
#include <string>

using namespace std; 
int main()
{
	int c=3; //c is number of entries
	struct data_t 
	{
		string name; 
		string number;
	} data [c];



	data[0].name="steve";
	data [0].number="34";
	data[1].name="bob";
	data[1].number="16";
	data[2].name="joe";
	data[2].number="21"; 

	struct data_t t , s , temp ; 
	int i;
	string str1  ,str2 ; 
	for (i = 0; i <= (c-1); ++i)
	{
		str1 = data[i].name;
		str2 = data[i + 1].name;
		t = data[i];
		s = data[i+1];
		if( str1[0] > str2[0] )
		{
			temp = t;
			t = s ; 
			s = temp;
		}

	} 
	for(i=0;i<ca;i++)
	{
		cout<<endl<<data[i].name<<endl<<data[i].number<<endl; 
	} 
	system ("pause"); 
}

but i have not thought about the performance issue over here .

[kev82]

Not sure what you mean by bad. Works just fine ordering the array example perfectly by A.

I already explained why I thought it was bad

I could sort permutations of the same data and get a different answer with your comparator.

This code demonstrates.

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

class MyData
{
public:
	int A;
	int B;
	MyData() : A(0), B(0) { }
	MyData(int a, int b) : A(a), B(b) { }

	//std::sort requires operator<.
	bool operator<(const MyData &op2) const
	{
		//Default sorting by integer A.
		return A < op2.A;
	}

	void display(std::ostream &os) const {
		os << "(" << A << "," << B << ")";
	} 
};

std::ostream &operator<<(std::ostream &os, const MyData &d) {
	d.display(os);
}

int main()
{
	std::vector<MyData> v;
	v.push_back(MyData(3,8));
	v.push_back(MyData(2,9));
	v.push_back(MyData(7,4));
	v.push_back(MyData(3,6));

	std::vector<MyData> u = v;
	std::swap(u.front(), u.back());

	std::sort(v.begin(), v.end());
	std::sort(u.begin(), u.end());

	std::copy(v.begin(), v.end(),
	 std::ostream_iterator<MyData>(std::cout, ""));
	std::cout << std::endl;
	std::copy(u.begin(), u.end(),
	 std::ostream_iterator<MyData>(std::cout, ""));
	std::cout << std::endl;

	return 0;
}

(2,9)(3,8)(3,6)(7,4)
(2,9)(3,6)(3,8)(7,4)

There is no denying that it works, it clearly does sort by A. If you notice though, I didn't mention whether it works or not. I suggested that it was bad.

When I see an operator< I make certain assumptions about it. I believe that other people do the same. I assume things like:

1) If !(a<b) and !(b<a) then a==b
2) The ordering over distinct objects is unique

Now it may be wrong to make these assumptions, but nobody has the time to go and read the innards of every piece of code they use. There may be cases where these assumptions don't hold. However, I think those circumstances are rare, and should be pointed out to the programmer with gigantic flashing neon pink signs.

In my opinion defining an operator< like you did, when it is completely unnecessary, is nothing but bone idle laziness. If you want to do that in your own code then that's fine, but this is a forum where people learn, and this thread was pretty much about learning how to define an operator<. In a environment where people are learning, I believe you should do things like that properly.

[webJose]

I see. You are "complaining" about my operator<() because it doesn't take into account that std::sort() is non-deterministic. I have never used it, but I hear std::stable_sort() takes care of that without complaining so much about the particular implementation of operator<(). You are making a huge deal out of a perfect simple example that intends to show something else. You are picking up what you think is a bug and making it look so big for some reason. Want an operator<() that resolves ties? Here:

bool operator<(const MyData &op2) const
{
    if (A == op2.A) return b < op2.B;
    return A < op2.A;
}

Also note that for MANY implementations, people don't really care about the sorting being non-deterministic. Of course many do, but also many don't. Let the OP find out for him/herself if a deterministic sort is required or not, but to me that's a whole new different story that has to do with std::stable_sort().

So there. Two more lines of code (or one, whatever) and the sort order is fixed. The above resolves the tie on A by relying on B to settle it. On more time: My example was NOT about how to implement the absolute perfect logic on how to compare a class/struct. It was made to show the OP how simple this can be and show the minimum requirements for the use of std::sort(). DON'T blow this out of proportion.

kev82 wrote:

In my opinion defining an operator< like you did, when it is completely unnecessary, is nothing but bone idle laziness.

You clearly have issues with me. Spill them out. Send me a PM with your grievances.

[kev82]

I'm unsure as to what you mean by deterministic, but stable_sort doesn't solve the problem. In fact, I think you will find that using stable_sort guarantees the problem, and will force the sorting of u and v to be different.

Thankyou for posting a much better operator<.

Perhaps I am being too pernickety about this, it's a sin I am guilty of more often than I like. However, I do think on a forum, a place where people learn, a place where lots more people read stuff and take it away than we realise, it is much better to do things properly - especially when teaching a new concept. People may not realise the issue with your operator< unless they are prompted to think about it in some way.

I didn't blow anything out of proportion, I simply said your comparator was bad, and briefly explained why. I did that not for you, but so that it would make anyone else who read the thread think about it.

In reply to you not understanding my post, I then went into detail, provided example code that triggers the issues, and gave my opinion on what I considered to be a lazy answer. I don't believe I have violated the TOS, however, if I have, it was unintentional and I apologise.

I have no issues with you, I don't know anything about you.

[webJose]

I understand what you say, but you have to realize here a couple of things:

1. The OP is not a C++ expert. One cannot flood his mind with advanced code that he/she may not understand. Keep it simple and to the point.
2. There are NO guidelines for writing comparators. You write the comparator that you NEED. If I need the array ordered by A only, then I make a comparator like the one in my first sample. There is NOTHING that prevents me from doing that if that is what I want and need.

Therefore, you cannot say my operator<() is BAD just because it doesn't follow YOUR concept of what I need. You don't really know what I need because it is my sample, not yours (in general, it is my project and you don't know my project requirements). So I conclude that it is far less instructive for the purposes of teaching the basics of sorting with the STL to throw out there a complex comparator when the whole objective of the code sample is something else.

I hope that your explanation and this explanation have now made things more clear.

[sjahf7]

I assume here that the OP is meant to refer to me? (This is my first forum post, yes I know I'm a loser.) Anyways, thanks for the insight, the bits I could understand were most enlightening. What is deterministic?

Also, webJose, your code did in fact work, and also kev82's version of it, but when I tried to change the variable declarations from int to string, problems arose...
before:

class MyData
{
public:
	int A;
	int B;
	MyData() : A(0), B(0) { }
	MyData(int a, int b) : A(a), B(b) { }

	//std::sort requires operator<.
	bool operator<(const MyData &op2) const
	{
		//Default sorting by integer A.
		return A < op2.A;
	}

	void display(std::ostream &os) const {
		os << "(" << A << "," << B << ")";
	} 
};

after:

class MyData
{
public:
	int A;
	int B;
	MyData() : A(0), B(0) { }
	MyData(int a, int b) : A(a), B(b) { }

	//std::sort requires operator<.
	bool operator<(const MyData &op2) const
	{
		//Default sorting by integer A.
		return A < op2.A;
	}

	void display(std::ostream &os) const {
		os << "(" << A << "," << B << ")";
	} 
};

and the error message was on the first declaration of type MyData, it said "invalid conversion from 'char' to 'const char'. To my eye, neither version of the code requires a change in any spot except the variable declaration (and the header #include). help please?

lastly, bluecoder, I was overjoyed to see that your code so nearly matched mine and was therefore so much easier to read. However, upon attempting to run, it failed. My computer crashed shortly thereafter... does that happen on your machine?
Thanks,
Steve

[sjahf7]

Also, line 41 of the blue code should, I believe,read as follows:

for(i=0;i<c;i++)

[webJose]

Yes, OP = Original Poster or Original Post.

How to use tags: http://cplusplus.com/articles/z13hAqkS/

The "after" version of MyData looks exactly the same to me as the "before" one. I guess it is a copy/paste mishap?

[sjahf7]

Yes I am dumb. After should read:

class MyData
{
public:
// changing declarations to string type
	string A;
	string B; 
	MyData() : A(0), B(0) { }
//changing parameters to string, since that is what is now being passed, correct?
	MyData(string a, string b) : A(a), B(b) { }

	//std::sort requires operator<.
	bool operator<(const MyData &op2) const
	{
		//Default sorting by integer (now string) A
		return A < op2.A;
	}

	void display(std::ostream &os) const {
		os << "(" << A << "," << B << ")";
	} 
};

[webJose]

That is basically right, but you are creating copies of the string objects for no good reason. Remember that you must always default to passing objects by reference instead of by value.

Also the default constructor's initialization list is for items A and B being of integer type. You need to change those.

class MyData
{
public:
    //Change to Strings.
    std::string A;
    std::string B;

    //Default constructor with initialization list removed.
    //No need to initialize a std::string object.  It defaults to an empty string.
    MyData()
    { }
    //Constructor receving string objects by reference, not by value.
    MyData(const std::string &a, const std::string &b) : A(a), B(b)
    { }
    //std::sort requires operator<.
    bool operator<(const MyData &op2) const
    {
        //Default sorting by integer A.
        return A < op2.A;
    }
};

That should work OK. Just add the display() method to this.

[sjahf7]

Thanks for the help and your patience. I don't know about that reference business it seems fishy to me...just kidding I've just never heard of it. First programming class this afternoon whoo! Hopefully they'll cover that bit...thanks again!

[bluecoder]

hi sjahf ..just remove the equal sign from the for loop
for (i = 0; i < (c-1); ++i)


Thanks @WebJose , @kev82