Solved

# DEQUE and sorting

Posted on 2006-04-22
1,041 Views
I'd like to use DEQUE for numbers 1 -100 and place the odd numbers on the front of the list and the even numbers on the back of the list and  then print them to the screen.
0
Question by:Wookie68

LVL 86

Expert Comment

See http://www.sgi.com/tech/stl/partition.html

Example
Reorder a sequence so that even numbers precede odd numbers.

int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int N = sizeof(A)/sizeof(int);
partition(A, A + N,
compose1(bind2nd(equal_to<int>(), 0),
bind2nd(modulus<int>(), 2)));
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The output is "10 2 8 4 6 5 7 3 9 1". [1]
0

Author Comment

jkr -
Thanks for the code. I'm attempting to work an exercise in a book (trying to learn the basics of C++ with several different books) and I was looking for a way to do it using DEQUE and not pushing each individual value on the deque.

Thanks again - joe
0

LVL 86

Expert Comment

>>I was looking for a way to do it using DEQUE and not pushing each individual value on the deque.

You can do that using 'copy()', e.g. like

#include <algorithm>
#include <functional>
#include <deque>
#include <iostream>

using namespace std;

int main () {

int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int N = sizeof(A)/sizeof(int);

deque<int> dq;
copy(A, A + N, dq.begin());
partition(dq.begin(), dq.end(),
compose1(bind2nd(equal_to<int>(), 0),
bind2nd(modulus<int>(), 2)));
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The output is "10 2 8 4 6 5 7 3 9 1". [1]

return 0;
}
0

LVL 16

Accepted Solution

Hi Wookie68,

This seems to work:

// Return whether first element is greater than the second but odds must come first.
bool EOGreater ( int i1, int i2 )
{
return ( (i1 & 1) == 1 ?
((i2 & 1) == 1 ? /* Both Odd */ i1 < i2: /* Odd Even */ true):
((i2 & 1) == 1 ? /* Even Odd */ false: /* Even Even */ i1 < i2));
}

int _tmain(int argc, _TCHAR* argv[])
{
deque <int> d;

// Fill it.
for ( int i = 1; i < 10; i++ ) d.push_back(i);
// Sort it.
sort(d.begin(),d.end(),EOGreater);
// Print it.
for ( deque <int>::iterator i1 = d.begin( ) ; i1 != d.end( ) ; i1++ )
cout << *i1 << " ";

return 0;
}

Paul
0

Author Comment

Can you tell me what the compose1 is above? When I compile the code, I get "compose1" identifier not found.
0

Author Comment

Paul -

Thanks for the code. I'm using Visual C++ to test with. Is this the correct way to implement your code? I'm still learning so please excuse the question if it seems too low level. Thanks - Joe

#include <algorithm>
#include <functional>
#include <deque>
#include <iostream>
#include <list>

using namespace std;

// Return whether first element is greater than the second but odds must come first.
bool EOGreater ( int i1, int i2 )
{
return ( (i1 & 1) == 1 ?
((i2 & 1) == 1 ? /* Both Odd */ i1 < i2: /* Odd Even */ true):
((i2 & 1) == 1 ? /* Even Odd */ false: /* Even Even */ i1 < i2));
}

int _tmain(int argc, _TCHAR* argv[])
{
deque <int> d;

// Fill it.
for ( int i = 1; i < 10; i++ ) d.push_back(i);
// Sort it.
sort(d.begin(),d.end(),EOGreater);
// Print it.
for ( deque <int>::iterator i1 = d.begin( ) ; i1 != d.end( ) ; i1++ )
cout << *i1 << " ";

return 0;
}
0

LVL 16

Expert Comment

Hi Wookie68,

If it compiles and runs and produces the results you want then it should be fine.

Note that jkr is FAR more experienced in C++ than I am so his method is probably much more efficient. I am still playing with C++ so I sometrimes do things in unusual ways. If you are learning C++ you may find it worthwhile understanding his method, I certainly dont :-)

Paul
0

LVL 16

Expert Comment

Hi Wookie68,

Actually, thinking about it, a more correct implementation of what you are asking for would use:

bool EOGreater ( int i1, int i2 )
{
return((i1 & 1) > (i2 & 1));
}

The one I posted earlier will also sort the rest of the numbers, that is not required.

Paul
0

Author Comment

Paul -
i'm very new as well... Thanks for trying to help me out.

When I compile the code I posted above I get syntax error:identifiier  "_TCHAR" I'll play with it some more to see if I can get it to complile.
0

Author Comment

Paul -

Thanks for the help. I tried jkr's code also, but the compiler did not like the compose1 portion of it. I ended up using your code to get it to work. I'd like to understand jkr's code as well. I have read a ton of posts by him on here and agree...he definitely knows his stuff.

#include <algorithm>
#include <functional>
#include <deque>
#include <iostream>
#include <list>

using namespace std;

// Return whether first element is greater than the second but odds must come first.
bool EOGreater ( int i1, int i2 )
{
return ( (i1 & 1) == 1 ?
((i2 & 1) == 1 ? /* Both Odd */ i1 < i2: /* Odd Even */ true):
((i2 & 1) == 1 ? /* Even Odd */ false: /* Even Even */ i1 < i2));
}

int main()
{
deque <int> d;

// Fill it.
for ( int i = 1; i < 101; i++ ) d.push_back(i);
// Sort it.
sort(d.begin(),d.end(),EOGreater);
// Print it.
for ( deque <int>::iterator i1 = d.begin( ) ; i1 != d.end( ) ; i1++ )
cout << *i1 << " ";
system("pause");
return 0;
}
0

LVL 86

Expert Comment

?
0

Author Comment

jkr

I couldn't get your code to compile completely... it kept hanging on the compose1 part. I noticed it was from an SGI page. Is it possible that it will compile under Unix and not Microsoft Visual C++?
0

Author Comment

Paul -
Not sure if I am allowed to ask under same question, but can you tell me how this section of your code above works?

bool EOGreater ( int i1, int i2 )
{
return ( (i1 & 1) == 1 ?
((i2 & 1) == 1 ? /* Both Odd */ i1 < i2: /* Odd Even */ true):
((i2 & 1) == 1 ? /* Even Odd */ false: /* Even Even */ i1 < i2));
}
0

LVL 16

Expert Comment

// If the first value is odd
(i1 & 1) == 1 ?
(
// If the second value is odd then the difference is the difference between the two numbers.
(i2 & 1) == 1 ? /* Both Odd */ i1 < i2:
// If the second value is even then odd is ALWAYS less than even.
/* Odd Even */ true):
// The first value is not odd. Similar logic.
((i2 & 1) == 1 ? /* Even Odd */ false: /* Even Even */ i1 < i2)

As I said above, you'd be better to use:

bool EOGreater ( int i1, int i2 )
{
return((i1 & 1) > (i2 & 1));
}

as its simpler and is just saying 'odd numbers are less than even numbers'.

Paul
0

## Featured Post

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more adâ€¦
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilationâ€¦
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

#### Need Help in Real-Time?

Connect with top rated Experts

22 Experts available now in Live!