DEQUE and sorting

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.
Wookie68Asked:
Who is Participating?
 
PaulCaswellCommented:
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
 
jkrCommented:
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
 
Wookie68Author Commented:
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
Cloud Class® Course: Amazon Web Services - Basic

Are you thinking about creating an Amazon Web Services account for your business? Not sure where to start? In this course you’ll get an overview of the history of AWS and take a tour of their user interface.

 
jkrCommented:
>>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
 
Wookie68Author Commented:
Can you tell me what the compose1 is above? When I compile the code, I get "compose1" identifier not found.
0
 
Wookie68Author Commented:
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
 
PaulCaswellCommented:
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
 
PaulCaswellCommented:
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
 
Wookie68Author Commented:
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
 
Wookie68Author Commented:
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
 
jkrCommented:
?
0
 
Wookie68Author Commented:
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
 
Wookie68Author Commented:
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
 
PaulCaswellCommented:
// 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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.