473,698 Members | 2,005 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Even-Odd sorting

Hello.

It seems a year is all it takes for one's proficiency in C++ to become
too rusty. Professionally, I've been away from the language (and from
programming in general), but I still preserve an appreciation for it.

So I decided to toy with some idea, just for fun and for evaluating how
rusty I'd become. "Let me write a simple functor for sorting the
elements of a collection! I will start with a simple collection of
integers.", I thought. I then chose an unusual criterion for the
sorting: "I'd like the elements to be ordered so that the even members
should appear before the odd ones." The following is what I came up
with. The program is not producing the expected behavior and I suspect
it has to do with my predicate. It is probably not fully complying to
the requirements for such a function.

#include <iostream>
#include <set>
#include <functional>
#include <algorithm>
#include <iterator>

class EvenOddSorting {
public:
bool operator()(cons t int i, const int j) const {
return i % 2 == 0 && j % 2 != 0;
}
};

int main() {
std::set<int, EvenOddSortingi ntSet;
intSet.insert(1 0);
intSet.insert(7 );
intSet.insert(5 );
intSet.insert(1 8);
intSet.insert(3 );
std::cout << "Even-Odd ordered set: ";
std::copy(intSe t.begin(),
intSet.end(),
std::ostream_it erator<int>(std ::cout, " "));
std::cout << "\n";
}

Given the above program, the expected output should read:

Even-Odd ordered set: 10 18 3 5 7

Notice how my proposed output implies a hidden requirement of ordering
among even and odd numbers. That would be ideal, but I'd be satisfied
(at first) with an output like '18 10 5 7 3'. Would anybody care to give
me a hand?

Thank you!

--
Ney André de Mello Zunino
Jun 27 '08 #1
18 4904
Ney André de Mello Zunino wrote:
[..]
So I decided [..] "Let me write a simple functor for sorting the
elements of a collection! I will start with a simple collection of
integers.", I thought. I then chose an unusual criterion for the
sorting: "I'd like the elements to be ordered so that the even members
should appear before the odd ones." The following is what I came up
with. The program is not producing the expected behavior and I suspect
it has to do with my predicate. It is probably not fully complying to
the requirements for such a function.

#include <iostream>
#include <set>
#include <functional>
#include <algorithm>
#include <iterator>

class EvenOddSorting {
public:
bool operator()(cons t int i, const int j) const {
return i % 2 == 0 && j % 2 != 0;
What if they are both odd? What if they are both even? Does the
predicate satisfy the requirement of strict weak ordering?

The predicate returns 'true' if the first is even and the second is odd.
For the rest it would return 'false', right? That means that when
comparing 5 and 7 it would determine that 5 is not less than 7. And
when comparing 7 and 5 it would determine that 7 is not less than 5.
That seems to me that 5 is the same as 7. That is, 5 and 7 cannot
coexist in the set that has your 'EvenOddSorting ' as the predicate.

Do the same with two evens.
}
};

int main() {
std::set<int, EvenOddSortingi ntSet;
intSet.insert(1 0);
intSet.insert(7 );
After this the collection should be {10, 7}. Is it?
intSet.insert(5 );
After this the collection _could_ be 10, 5, 7, or it could be 10, 7, 5,
if the predicate allowed placing both 5 and 7 next to each other. It
does not, AFAICT. So, here the collection will be {10, 7}, still.

And so on.
intSet.insert(1 8);
intSet.insert(3 );
std::cout << "Even-Odd ordered set: ";
std::copy(intSe t.begin(),
intSet.end(),
std::ostream_it erator<int>(std ::cout, " "));
std::cout << "\n";
}

Given the above program, the expected output should read:

Even-Odd ordered set: 10 18 3 5 7
OK, that's what it *should* read (you believe). What *does* it read?
>
Notice how my proposed output implies a hidden requirement of ordering
among even and odd numbers. That would be ideal, but I'd be satisfied
(at first) with an output like '18 10 5 7 3'. Would anybody care to give
me a hand?
Not sure what kind of help you are seeking. You've not specified all
the requirements for your predicate to implement it correctly. Have I
given you enough hints to go on?

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Jun 27 '08 #2

On May 23, 3:41 pm, Ney André de Mello Zunino <zun...@inf.ufs c.br>
wrote:
[snip]
I then chose an unusual criterion for the
sorting: "I'd like the elements to be ordered so that the even members
should appear before the odd ones."
[snip]
The program is not producing the expected behavior and I suspect
it has to do with my predicate.
[snip]
class EvenOddSorting {
public:
bool operator()(cons t int i, const int j) const {
return i % 2 == 0 && j % 2 != 0;
}

};
[snip]
std::set<int, EvenOddSortingi ntSet;
[snip]
Your main problem is your predicate along with your use of an
std::set. Note that a set can only hold unique items. That is, no two
elements a and b exist in a set such that a == b.

Your predicate tests if a < b. If a < b OR b < a then a != b. If (NOT
a < b) AND NOT (b < a) then a == b. The set uses your predicate to
determine uniqueness. Because your predicate only compares based on
parity and not values, in effect you have defined all even numbers to
be equivalent, and all odd numbers to be equivalent. Therefore your
set, which must only contain unique values, will contain one even
number, and one odd number.

If you want the value of the integers to be a criteria for uniqueness
your predicate must take that into account. You can also, then, have
sorting "within" the even and odd numbers, if you do something like
this instead:

class EvenOddValueSor ting {
public:
bool operator()(cons t int i, const int j) const {
bool i_is_even = !(i % 2);
bool j_is_even = !(j % 2);
if (i_is_even == j_is_even) // if parity is same...
return i < j; // ... compare by value only
else
return i_is_even; // ... otherwise even always < odd.
}
};

Alternatively, you can use the predicate you have now for sorting, but
do not use a container that requires value uniqueness. For example,
use a vector with your current predicate:

std::vector<int v;
v.push_back(10) ;
v.push_back(7);
v.push_back(5);
v.push_back(18) ;
v.push_back(3);
std::sort(v.beg in(), v.end(), EvenOddSorting( ));

Doing that with EvenOddSorting will place all the even numbers before
all the odd ones. Doing it with EvenOddValueSor ting will sort by
numeric value also. Note that std::sort is not stable; but you can use
std::stable_sor t if that is a requirement. See:

http://www.sgi.com/tech/stl/table_of_contents.html

Jason
Jun 27 '08 #3
Victor Bazarov wrote:
What if they are both odd? What if they are both even? Does the
predicate satisfy the requirement of strict weak ordering?

The predicate returns 'true' if the first is even and the second is odd.
For the rest it would return 'false', right? That means that when
comparing 5 and 7 it would determine that 5 is not less than 7. And
when comparing 7 and 5 it would determine that 7 is not less than 5.
That seems to me that 5 is the same as 7. That is, 5 and 7 cannot
coexist in the set that has your 'EvenOddSorting ' as the predicate.

Do the same with two evens.
Yes, I see what you mean and it makes perfect sense now.

[...]
OK, that's what it *should* read (you believe). What *does* it read?
Sorry for not posting the results. You were right, only 10 and 7 were
being accepted in the collection.
>Notice how my proposed output implies a hidden requirement of ordering
among even and odd numbers. That would be ideal, but I'd be satisfied
(at first) with an output like '18 10 5 7 3'. Would anybody care to
give me a hand?

Not sure what kind of help you are seeking. You've not specified all
the requirements for your predicate to implement it correctly. Have I
given you enough hints to go on?
Yes, sir, you have. Here's the modified functor class (which can
probably be further simplified):

class EvenOddSorting {
public:
bool operator()(cons t int i, const int j) const {
if (i % 2 == 0) {
if (j % 2 != 0) { // i is even and j is odd
return true;
} else { // both i and j are even
return i < j;
}
} else {
if (j % 2 == 0) { // i is odd and j is even
return false;
} else { // both i and j are odd
return i < j;
}
}
}
};

The program now outputs my desired results:

Even-Odd ordered set: 10 18 3 5 7

Do you see any remaining issue?

Thank you,

--
Ney André de Mello Zunino
Jun 27 '08 #4
ja************@ gmail.com wrote:

[...]
class EvenOddValueSor ting {
public:
bool operator()(cons t int i, const int j) const {
bool i_is_even = !(i % 2);
bool j_is_even = !(j % 2);
if (i_is_even == j_is_even) // if parity is same...
return i < j; // ... compare by value only
else
return i_is_even; // ... otherwise even always < odd.
}
};

Alternatively, you can use the predicate you have now for sorting, but
do not use a container that requires value uniqueness. For example,
use a vector with your current predicate:

std::vector<int v;
v.push_back(10) ;
v.push_back(7);
v.push_back(5);
v.push_back(18) ;
v.push_back(3);
std::sort(v.beg in(), v.end(), EvenOddSorting( ));

Doing that with EvenOddSorting will place all the even numbers before
all the odd ones. Doing it with EvenOddValueSor ting will sort by
numeric value also. Note that std::sort is not stable; but you can use
std::stable_sor t if that is a requirement. See:

http://www.sgi.com/tech/stl/table_of_contents.html
Thank you, Jason, for your insights and suggestions. I also appreciated
how simpler your predicate looks compared to mine. Before seeing your
reply, I had further simplified my own version to the following:

bool operator()(cons t int i, const int j) const {
if (i % 2 == 0 && j % 2 == 0 || i % 2 != 0 && j % 2 != 0) {
return i < j;
} else {
return i % 2 == 0;
}
}

But your version seems a bit easier to follow.

Regards,

--
Ney André de Mello Zunino
Jun 27 '08 #5
Ney André de Mello Zunino wrote:
Victor Bazarov wrote:
>What if they are both odd? What if they are both even? Does the
predicate satisfy the requirement of strict weak ordering?

The predicate returns 'true' if the first is even and the second is
odd. For the rest it would return 'false', right? That means that
when comparing 5 and 7 it would determine that 5 is not less than 7.
And when comparing 7 and 5 it would determine that 7 is not less than
5. That seems to me that 5 is the same as 7. That is, 5 and 7 cannot
coexist in the set that has your 'EvenOddSorting ' as the predicate.

Do the same with two evens.

Yes, I see what you mean and it makes perfect sense now.

[...]
>OK, that's what it *should* read (you believe). What *does* it read?

Sorry for not posting the results. You were right, only 10 and 7 were
being accepted in the collection.
>>Notice how my proposed output implies a hidden requirement of
ordering among even and odd numbers. That would be ideal, but I'd be
satisfied (at first) with an output like '18 10 5 7 3'. Would anybody
care to give me a hand?

Not sure what kind of help you are seeking. You've not specified all
the requirements for your predicate to implement it correctly. Have I
given you enough hints to go on?

Yes, sir, you have. Here's the modified functor class (which can
probably be further simplified):

class EvenOddSorting {
public:
bool operator()(cons t int i, const int j) const {
if (i % 2 == 0) {
if (j % 2 != 0) { // i is even and j is odd
return true;
} else { // both i and j are even
return i < j;
}
} else {
if (j % 2 == 0) { // i is odd and j is even
return false;
} else { // both i and j are odd
return i < j;
}
}
}
};

The program now outputs my desired results:

Even-Odd ordered set: 10 18 3 5 7

Do you see any remaining issue?
Issue? Not really. I think you got it now. You can simplify the
predicate a bit by doing

if (i % 2 == j % 2)
return i < j; // for the same oddness - just compare them
else
return i % 2 == 0; // for different, 'i' is smaller if it's even

How's that?

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Jun 27 '08 #6
Ney André de Mello Zunino wrote:
Hello.

It seems a year is all it takes for one's proficiency in C++ to become
too rusty. Professionally, I've been away from the language (and from
programming in general), but I still preserve an appreciation for it.

So I decided to toy with some idea, just for fun and for evaluating how
rusty I'd become. "Let me write a simple functor for sorting the
elements of a collection! I will start with a simple collection of
integers.", I thought. I then chose an unusual criterion for the
sorting: "I'd like the elements to be ordered so that the even members
should appear before the odd ones." The following is what I came up
with. The program is not producing the expected behavior and I suspect
it has to do with my predicate. It is probably not fully complying to
the requirements for such a function.

#include <iostream>
#include <set>
#include <functional>
#include <algorithm>
#include <iterator>

class EvenOddSorting {
public:
bool operator()(cons t int i, const int j) const {
return i % 2 == 0 && j % 2 != 0;
}
};

int main() {
std::set<int, EvenOddSortingi ntSet;
intSet.insert(1 0);
intSet.insert(7 );
intSet.insert(5 );
intSet.insert(1 8);
intSet.insert(3 );
std::cout << "Even-Odd ordered set: ";
std::copy(intSe t.begin(),
intSet.end(),
std::ostream_it erator<int>(std ::cout, " "));
std::cout << "\n";
}

Given the above program, the expected output should read:

Even-Odd ordered set: 10 18 3 5 7

Notice how my proposed output implies a hidden requirement of ordering
among even and odd numbers. That would be ideal, but I'd be satisfied
(at first) with an output like '18 10 5 7 3'. Would anybody care to give
me a hand?

Thank you!
Along with the other advice you got, I've re-written parts of your
original to make it what I consider cleaner.

#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>

class EvenOddSorting {
private:
inline bool isEven(const int i) const {
return 0 == i % 2;
}
public:
inline bool operator()(cons t int i, const int j) const {
return isEven(i+j) ? i < j : isEven(i);
}
};

int main() {
std::set<int, EvenOddSortingi ntSet;
const int values[] = {10, 7, 5, 18, 3};
std::copy(value s,
values + 5,
std::inserter(i ntSet, intSet.begin()) );
std::cout << "Even-Odd ordered set: ";
std::copy(intSe t.begin(),
intSet.end(),
std::ostream_it erator<int>(std ::cout, " "));
std::cout << "\n";
return 0;
}

--
Daniel Pitts' Tech Blog: <http://virtualinfinity .net/wordpress/>
--
Daniel Pitts' Tech Blog: <http://virtualinfinity .net/wordpress/>
Jun 27 '08 #7
In article <g1**********@a ioe.org>, zu****@inf.ufsc .br says...

[ ... ]
class EvenOddSorting {
public:
bool operator()(cons t int i, const int j) const {
return i % 2 == 0 && j % 2 != 0;
}
Just FWIW, the least significant bit of a number is 1 if the number is
odd, and 0 if the number is even. As such, 'i&1' will be 1 iff i is odd.
IOW, the even/odd ordering can be written as: (i&1) < (j&1).

As has already been mentioned, for a set you also need to provide
ordering within the odd and even numbers, so you'll need to add a normal
comparison iff the LSBs are equal.

class EvenOddSorting {
// feel free to return 'i%2' if you prefer
int lsb(int i) const { return i&1; }
public:
bool operator()(int i, int j) const {
return (lsb(i) < lsb(j)) || (lsb(i) == lsb(j) && i<j);
//
// A couple of alterative possibilities that may be more understanable
// to those who don't like boolean expressions.
//
// if (lsb(i) < lsb(j))
// return true;
// return lsb(i)==lsb(j) && i<j;
//
// Possibly even more explicit alternative:
//
// if (lsb(i) < lsb(j))
// return true;
// if (lsb(j) < lsb(i))
// return false;
// return i < j;
}
};

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jun 27 '08 #8
Some people in this thread have suggested comparison operators that
rely on the result of (i%2) being either 0 or 1, but this may be false
in case the number is negative. Many compilers implement the division
operators so that the quotient is rounded towards zero, which imply
that i%2==-1 when i<0.

Indeed, the following comparison operators have implementation-defined
behaviour (and give a wrong result on my machine when the numbers are
{10, -7, -5, 18, 3} ):

Victor Bazarov's:
class EvenOddSorting {
public:
bool operator()(int i, int j) const {
if (i % 2 == j % 2)
return i < j; // for the same oddness - just compare them
else
return i % 2 == 0; // for different, 'i' is smaller if it's even
}
};
and an alternative suggested by Jerry Coffin:
class EvenOddSorting {
* * * * // feel free to return 'i%2' if you prefer
* * * * int lsb(int i) const { return i%2; }
public:
* * * * bool operator()(int i, int j) const {
* * * * * * * * return (lsb(i) < lsb(j)) || (lsb(i) ==lsb(j) && i<j);
};
Cheers,

Dario
Jun 27 '08 #9
Stefan Ram a écrit :
Vincent Jacques <ne*******@vinc ent-jacques.netwrit es:
>If your compiler generates the same assembly, I do think that
i % 2 is more readable than i & 1, because the 'modulo 2' is
the mathematic operation for 'odd or even'.

I do not see how the readability of »i % 2« depends on the
code my compiler generates.
Sorry for not being clear:

I meant:
(1) there are two cases: (a) the generated code is the same or (b) it is
different.
(2) In general, I think that i % 2 is more readable than i & 1 when you
mean 'odd or even'
(3) I prefer to write readable code over micro-optimized code.

Then I go on the two cases of (1):
case (a): from (2), I write i % 2
case (b): from (3) and (2), I write i % 2 until I'm told (by my
customer, by my hierarchy, etc.) that I *have* to write micro-optimized
code.
»%« is /not/ the mathematical operation »modulo«.
[snip the exact meaning of %]
You're right. Yet, the reminder of the division of i by 2 carries more
about 'odd or even' than the bitwise and between i and 1. (motivation
for (2))
>If your compiler does not generate the same code, then you will have to
profile your code to choose between the two possible solutions.

I do not have to profile, because I usually do not write C++
source code for a specific compiler and execution environment,
I usually do not invest time in such non-portable
microoptimizati ons.
So do I, usually. But, from (2), I assume that the comment from Jerry
Coffin is motivated by an hypothetical win of performance. That's why I
talked about optimization.

Cheers,
--
Vincent Jacques

"S'il n'y a pas de solution, c'est qu'il n'y a pas de problème"
Devise Shadock
Jun 27 '08 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

10
3173
by: Manny | last post by:
I have a web form "Page1.asp" and it reads data from a database, does some calculations, and displays the records in pages. Works fine. I have a button that displays on the page, defined as <input type="button" onClick="OutputData()"> The OutputData() function is a javascript function that simply does this: window.location = "Page1.asp?Flag=1";
10
5628
by: serge | last post by:
Using "SELECT * " is a bad practice even when using a VIEW instead of a table? I have some stored procedures that are identical with the difference of one statement in the WHERE clause. If I create a single View and specify also in this View the WHERE clause that is common in these stored procedures, I will have the new stored procecures changed to be like:
1
2722
by: James dean | last post by:
I done a test and i really do not know the reason why a jagged array who has the same number of elements as a multidimensional array is faster here is my test. I assign a value and do a small calculation. Even if i initialise the jagged array inside the function it is still much faster. Are these results correct?. If i put the initialisation loop in the constructor its ridiculously faster but even here its 4 times faster...is this correct?...
37
2142
by: Greg | last post by:
Except for legacy or non-.NET applications, is there any reason to use VC++ anymore? It seems that for .NET applications, there would be no reason to choose C++ over C# since C# is faster to develop with (i.e. no header files, objects are easier to create and use, C# language is native to .NET) I'm sure this question will stir some emotions :-) -- Greg McPherran www.McPherran.com
13
5216
by: comp.lang.php | last post by:
Other: <input name="school_type_other" size="30" maxlength="75" value="<?php if ($_POST) echo $_POST; else echo str_replace('"', '&quot;', str_replace('\\', '', $result->school_type_other)); ?>">
10
1969
by: Doug Robertson | last post by:
First off, I'm a hardware/OS guy. I just write code on the side and I'm completely self taught - so bear in mind my total lack of expertise. I have a program originally written in VB2003 using the dotnet 1.1 framework. The program makes extensive use of Win32 API calls to help manage and track remote access sessions with out clients. I've left it running for days at a time on my system with no problems. It has always been stable. I...
9
1126
by: Ron | last post by:
How would I go about finding the even characters in a string? for example: string = I have so it would return even characters of ae thanks
6
5042
by: luvnhandfull | last post by:
Can someone please explaine to me how to write a function program. Using prototypes just throws me. Here is my prompt: write a function called is _is even that has one input parameter and int called number which is a number the user wants to determine is even or not. The Function returns an integer which has a value of 1 if the number passed is even and has a value of 0 if the number passed is not even. I'll paste the mess I came up with...
30
29599
by: bdsatish | last post by:
The built-in function round( ) will always "round up", that is 1.5 is rounded to 2.0 and 2.5 is rounded to 3.0. If I want to round to the nearest even, that is my_round(1.5) = 2 # As expected my_round(2.5) = 2 # Not 3, which is an odd num I'm interested in rounding numbers of the form "x.5" depending upon whether x is odd or even. Any idea about how to implement it ?
0
8671
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9152
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
9016
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
8887
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8856
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
7709
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
6515
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
4613
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
2
2321
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.