• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1078
  • Last Modified:

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.
0
Wookie68
Asked:
Wookie68
  • 7
  • 4
  • 3
1 Solution
 
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
 
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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 7
  • 4
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now