alg7.cpp

Go to the documentation of this file.

 
#include <rw/_config.h>
 
#if defined (__IBMCPP__) && !defined (_RWSTD_NO_IMPLICIT_INCLUSION)
// Disable implicit inclusion to work around 
// a limitation in IBM's VisualAge 5.0.2.0 (see PR#26959) 
 
#  define _RWSTD_NO_IMPLICIT_INCLUSION 
#endif
 
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
 
#include <examples.h>
 
    
// returns a random integer in the range [0, 100)
int randomValue ()
{
    static int digits[] = {
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9
    };
 
    std::random_shuffle (digits, digits + sizeof digits / sizeof *digits);
 
    const int rnd = digits [0] * 10 + digits [1];
 
    return rnd;
}
 
 
typedef std::ostream_iterator<int, char, std::char_traits<char> > Iter;
 
void sortExample ()
{
    std::cout << "Sort algorithms\n";
 
    Iter intOut (std::cout, " ");
 
    // Fill both a std::vector and a std::deque with random integers.
    std::vector<int, std::allocator<int> > aVec (15);
    std::deque<int, std::allocator<int> >  aDec (15);
    std::generate (aVec.begin (), aVec.end (), randomValue);
    std::generate (aDec.begin (), aDec.end (), randomValue);
 
    // Sort the std::vector ascending.
    std::sort (aVec.begin (), aVec.end ());
    std::copy (aVec.begin (), aVec.end (), intOut);
    std::cout << '\n';
 
    // Sort the std::deque descending.
    std::sort (aDec.begin (), aDec.end (), std::greater<int>() );
    std::copy (aDec.begin (), aDec.end (), intOut);
    std::cout << '\n';
 
    // Sort the std::vector descending?
    std::sort (aVec.rbegin (), aVec.rend ());
    std::copy (aVec.begin (), aVec.end (), intOut);
    std::cout << '\n';
}
 
void partial_sort_example ()
{
    std::cout << "Partial sort examples\n";
 
    Iter intOut (std::cout, " ");
 
    // Make a std::vector of 15 random integers.
    std::vector<int, std::allocator<int> > aVec (15);
    std::generate (aVec.begin (), aVec.end (), randomValue);
    std::copy (aVec.begin (), aVec.end (), intOut);
    std::cout << '\n';
 
    // Partial sort the first seven positions.
    std::partial_sort (aVec.begin (), aVec.begin () + 7, aVec.end ());
    std::copy (aVec.begin (), aVec.end (), intOut);
    std::cout << '\n';
 
    // Make a std::list of random integers.
    std::list<int, std::allocator<int> > aList (15);
    std::generate (aList.begin (), aList.end (), randomValue);
    std::copy (aList.begin (), aList.end (), intOut);
    std::cout << '\n';
 
    // Sort only the first seven elements.
    std::vector<int, std::allocator<int> > start (7);
    std::partial_sort_copy (aList.begin (), aList.end (),
                            start.begin (), start.end (), std::greater<int>());
    std::copy (start.begin (), start.end (), intOut);
    std::cout << '\n';   
}
 
 
// Illustrate the use of the nth_largest function.
void nth_element_example ()
{
    std::cout << "Nth largest example\n";
 
    // Make a std::vector of random integers.
    std::vector<int, std::allocator<int> > aVec (10);
    std::generate (aVec.begin (), aVec.end (), randomValue);
 
    Iter intOut (std::cout, " ");
 
    // Now find the 5th largest.
    std::vector<int, std::allocator<int> >::iterator nth = aVec.begin () + 4;
    std::nth_element (aVec.begin (), nth, aVec.end ());
    std::cout << "fifth largest is " << *nth << " in\n";
    std::copy (aVec.begin (), aVec.end (), intOut);
    std::cout << '\n';
}
 
 
// Illustrate the use of the binary search functions.
void binary_search_example ()
{
    std::cout << "Binary search example\n";
 
    Iter intOut (std::cout, " ");
 
    // Make an ordered std::vector of 15 random integers.
    std::vector<int, std::allocator<int> > aVec (15);
    std::generate (aVec.begin (), aVec.end (), randomValue);
    std::sort (aVec.begin (), aVec.end ());
    std::copy (aVec.begin (), aVec.end (), intOut),   std::cout << '\n';
 
    // See if it contains an eleven.
    if (std::binary_search (aVec.begin (), aVec.end (), 11))
        std::cout << "contains an 11\n";
    else
        std::cout << "does not contain an 11\n";
 
    // Insert an 11 and a 14.
    std::vector<int, std::allocator<int> >::iterator where;
    where = std::lower_bound (aVec.begin (), aVec.end (), 11);
    aVec.insert (where, 11);
    where = std::upper_bound (aVec.begin (), aVec.end (), 14);
    aVec.insert (where, 14);
    std::copy (aVec.begin (), aVec.end (), intOut),   std::cout << '\n';
}
 
 
// Illustrate the use of the merge function.
void merge_example ()
{
    std::cout << "Merge algorithm examples\n";
 
    // Make a std::list and std::vector of 10 random integers.
    std::vector<int, std::allocator<int> > aVec (10);
    std::list<int, std::allocator<int> > aList (10);
    std::generate (aVec.begin (), aVec.end (), randomValue);
    std::sort (aVec.begin (), aVec.end ());
    std::generate_n (aList.begin (), 10, randomValue);
    aList.sort ();
 
    // Merge into a std::vector.
    std::vector<int, std::allocator<int> > vResult (aVec.size () + aList.size ());
    std::merge (aVec.begin (), aVec.end (), aList.begin (), aList.end (), 
           vResult.begin ());
 
    // Merge into a std::list.
    std::list<int, std::allocator<int> > lResult;
    std::merge (aVec.begin (), aVec.end (), aList.begin (), aList.end (), 
           std::inserter (lResult, lResult.begin ()));
 
    // Merge into the output.
    std::merge (aVec.begin (), aVec.end (), aList.begin (), aList.end (),
                Iter (std::cout, " "));
 
    std::cout << '\n';
}
 
class iotaGen
{
public:
    iotaGen (int c = 0) : current (c) { }
    int operator () () { return current++; }
  private:
    int current;
};
 
 
// Illustrate the use of the generic set functions.
void set_example ()
{
    std::cout << "Set operations:\n";
 
    // Make a couple of ordered std::lists.
    std::list <int, std::allocator<int> > listOne, listTwo;
    std::generate_n (std::inserter (listOne, listOne.begin ()), 5, iotaGen (1));
    std::generate_n (std::inserter (listTwo, listTwo.begin ()), 5, iotaGen (3));
 
    Iter intOut (std::cout, " ");
 
    // union - 1 2 3 4 5 6 7
    std::set_union (listOne.begin (), listOne.end (),
                    listTwo.begin (), listTwo.end (), intOut);
    std::cout << '\n';
 
    // merge - 1 2 3 3 4 4 5 5 6 7
    std::merge (listOne.begin (), listOne.end (),
                listTwo.begin (), listTwo.end (), intOut);
    std::cout << '\n';
 
    // intersection 3 4 5
    std::set_intersection (listOne.begin (), listOne.end (),
                           listTwo.begin (), listTwo.end (), intOut);
    std::cout << '\n';
 
    // difference 1 2
    std::set_difference (listOne.begin (), listOne.end (),
                         listTwo.begin (), listTwo.end (), intOut);
    std::cout << '\n';
 
    // symmetric difference 1 2 6 7
    std::set_symmetric_difference (listOne.begin (), listOne.end (), 
                                   listTwo.begin (), listTwo.end (),
                                   intOut);
    std::cout << '\n';
        
    if (std::includes (listOne.begin (), listOne.end (),
                       listTwo.begin (), listTwo.end ()))
        std::cout << "set is subset\n";
    else
        std::cout << "set is not subset\n";
}
 
 
// Illustrate the use of the heap functions.
void heap_example ()
{
    Iter intOut (std::cout, " ");
 
    // Make a heap of 15 random integers.
    std::vector<int, std::allocator<int> > aVec (15);
    std::generate (aVec.begin (), aVec.end (), randomValue);
    std::make_heap (aVec.begin (), aVec.end ());
    std::copy (aVec.begin (), aVec.end (), intOut);
    std::cout << "\nLargest value " << aVec.front () << '\n';
 
    // Remove largest and reheap.
    std::pop_heap (aVec.begin (), aVec.end ());
    aVec.pop_back ();
    std::copy (aVec.begin (), aVec.end (), intOut);
    std::cout << '\n';
 
    // Add a 97 to the heap.
    aVec.push_back (97);
    std::push_heap (aVec.begin (), aVec.end ());
    std::copy (aVec.begin (), aVec.end (), intOut);
    std::cout << '\n';
 
    // Finally, make into sorted collection.
    std::sort_heap (aVec.begin (), aVec.end ());
    std::copy (aVec.begin (), aVec.end (), intOut);
    std::cout << '\n';
}
 
int main ()
{
    std::cout << "Sorting generic algorithms examples\n";
 
    sortExample ();
    partial_sort_example ();
    nth_element_example ();
    binary_search_example ();
    merge_example ();
    set_example ();
    heap_example ();
    
    std::cout << "End sorting examples\n";
 
    return 0;
}