home *** CD-ROM | disk | FTP | other *** search
/ QBasic & Borland Pascal & C / Delphi5.iso / C / BC_502 / STDLIB.PAK / ALG7.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1997-05-06  |  6.7 KB  |  247 lines
  1. /**************************************************************************
  2.  *
  3.  * alg7.cpp - Illustrate the use of the sort related generic algorithms.
  4.  *    Section 13
  5.  *
  6.  * $Id: alg7.cpp,v 1.2 1995/08/29 18:43:42 oberg Exp $
  7.  *
  8.  * $$RW_INSERT_HEADER "slyrs.cpp"
  9.  *
  10.  **************************************************************************/
  11.  
  12. # include <vector>
  13. # include <deque>
  14. # include <list>
  15. # include <algorithm>
  16.  
  17. # include <iostream.h>
  18. using namespace std;
  19.  
  20. int randomInteger(unsigned int n)
  21.     { return rand() % n; }
  22.     
  23. int randomValue() { return randomInteger(100); }
  24.  
  25. ostream_iterator<int> intOut (cout, " ");
  26.         
  27. void sortExample() {
  28.     cout << "Sort algorithms"  << endl;
  29.     
  30.         // fill both a vector and a deque
  31.         // with random integers
  32.     vector<int> aVec(15);
  33.     deque<int> aDec(15);
  34.     generate (aVec.begin(), aVec.end(), randomValue);
  35.     generate (aDec.begin(), aDec.end(), randomValue);
  36.     
  37.         // sort the vector ascending
  38.     sort (aVec.begin(), aVec.end());
  39.     copy (aVec.begin(), aVec.end(), intOut);
  40.     cout << endl;
  41.     
  42.         // sort the deque descending
  43.     sort (aDec.begin(), aDec.end(), greater<int>() );
  44.     copy (aDec.begin(), aDec.end(), intOut);
  45.     cout << endl;
  46.     
  47.         // sort the vector descending?
  48.     sort (aVec.rbegin(), aVec.rend());
  49.     copy (aVec.begin(), aVec.end(), intOut);
  50.     cout << endl;
  51.  
  52. }
  53.  
  54. void partial_sort_example() {
  55.     cout << "Partial sort examples" << endl;
  56.     
  57.         // make a vector of 15 random integers
  58.     vector<int> aVec(15);
  59.     generate (aVec.begin(), aVec.end(), randomValue);
  60.     copy (aVec.begin(), aVec.end(), intOut);
  61.     cout << endl;
  62.  
  63.     
  64.         // partial sort the first seven positions
  65.     partial_sort (aVec.begin(), aVec.begin() + 7, aVec.end());
  66.     copy (aVec.begin(), aVec.end(), intOut);
  67.     cout << endl;
  68.  
  69.         // make a list of random integers
  70.     list<int> aList(15, 0);
  71.     generate (aList.begin(), aList.end(), randomValue);
  72.     copy (aList.begin(), aList.end(), intOut);
  73.     cout << endl;
  74.     
  75.         // sort only the first seven elements
  76.     vector<int> start(7);
  77.     partial_sort_copy (aList.begin(), aList.end(),
  78.         start.begin(), start.end(), greater<int>());
  79.     copy (start.begin(), start.end(), intOut);
  80.     cout << endl;    
  81. }
  82.  
  83. void nth_element_example()
  84.     // illustrate the use of the nth_largest function
  85. {
  86.     cout << "Nth largest example" << endl;
  87.  
  88.         // make a vector of random integers
  89.     vector<int> aVec(10);
  90.     generate (aVec.begin(), aVec.end(), randomValue);
  91.     
  92.         // now find the 5th largest
  93.     vector<int>::iterator nth = aVec.begin() + 4;
  94.     nth_element(aVec.begin(), nth, aVec.end());
  95.     
  96.     cout << "fifth largest is " << *nth << " in" << endl;
  97.     copy (aVec.begin(), aVec.end(), intOut);
  98.     cout << endl;
  99.     
  100.     
  101. }
  102.  
  103. void binary_search_example ()
  104.     // illustrate the use of the binary search functions
  105. {
  106.     cout << "Binary search example" << endl;
  107.     
  108.         // make an ordered vector of 15 random integers
  109.     vector<int> aVec(15);
  110.     generate (aVec.begin(), aVec.end(), randomValue);
  111.     sort (aVec.begin(), aVec.end());
  112.     copy (aVec.begin(), aVec.end(), intOut),   cout << endl;
  113.     
  114.         // see if it contains an eleven
  115.     if (binary_search(aVec.begin(), aVec.end(), 11))
  116.         cout << "contains an 11" << endl;
  117.     else
  118.         cout << "does not contain an 11"  << endl;
  119.         
  120.         // insert an 11 and a 14
  121.     vector<int>::iterator where;
  122.     where = lower_bound (aVec.begin(), aVec.end(), 11);
  123.     aVec.insert (where, 11);
  124.     
  125.     where = upper_bound (aVec.begin(), aVec.end(), 14);
  126.     aVec.insert (where, 14);
  127.     
  128.     copy (aVec.begin(), aVec.end(), intOut),   cout << endl;
  129. }
  130.  
  131. void merge_example ()
  132.     // illustrate the use of the merge function
  133. {
  134.     cout << "Merge algorithm examples" << endl;
  135.     
  136.         // make a list and vector of 10 random integers
  137.     vector<int> aVec(10);
  138.     list<int> aList(10, 0);
  139.     generate (aVec.begin(), aVec.end(), randomValue);
  140.     sort (aVec.begin(), aVec.end());
  141.     generate_n (aList.begin(), 10, randomValue);
  142.     aList.sort();
  143.     
  144.         // merge into a vector
  145.     vector<int> vResult (aVec.size() + aList.size());
  146.     merge (aVec.begin(), aVec.end(), aList.begin(), aList.end(),
  147.             vResult.begin());
  148.             
  149.         // merge into a list
  150.     list<int> lResult;
  151.     merge (aVec.begin(), aVec.end(), aList.begin(), aList.end(),
  152.             inserter(lResult, lResult.begin()));
  153.             
  154.         // merge into the output
  155.     merge (aVec.begin(), aVec.end(), aList.begin(), aList.end(),
  156.         ostream_iterator<int>  (cout, " "));
  157.     cout << endl;
  158. }
  159.  
  160.  
  161. class iotaGen {
  162. public:
  163.     iotaGen (int c = 0) : current(c) { }
  164.     int operator () () { return current++; }
  165. private:
  166.     int current;
  167. };
  168.  
  169. void set_example ()
  170.     // illustrate the use of the generic set functions
  171. {
  172.     cout << "Set operations:" << endl;
  173.     
  174.         // make a couple of ordered lists
  175.     list <int> listOne, listTwo;
  176.     generate_n (inserter(listOne, listOne.begin()), 5, iotaGen(1));
  177.     generate_n (inserter(listTwo, listTwo.begin()), 5, iotaGen(3));
  178.     
  179.         // now do the set operations
  180.         // union - 1 2 3 4 5 6 7
  181.     set_union (listOne.begin(), listOne.end(),
  182.         listTwo.begin(), listTwo.end(), intOut), cout << endl;
  183.         // merge - 1 2 3 3 4 4 5 5 6 7
  184.     merge (listOne.begin(), listOne.end(),
  185.         listTwo.begin(), listTwo.end(), intOut), cout << endl;
  186.         // intersection 3 4 5
  187.     set_intersection (listOne.begin(), listOne.end(),
  188.         listTwo.begin(), listTwo.end(), intOut), cout << endl;
  189.         // difference 1 2
  190.     set_difference (listOne.begin(), listOne.end(),
  191.         listTwo.begin(), listTwo.end(), intOut), cout << endl;
  192.         // symmetric difference 1 2 6 7
  193.     set_symmetric_difference (listOne.begin(), listOne.end(),
  194.         listTwo.begin(), listTwo.end(), intOut), cout << endl;
  195.         
  196.     if (includes(listOne.begin(), listOne.end(),
  197.             listTwo.begin(), listTwo.end()))
  198.                 cout << "set is subset" << endl;
  199.     else
  200.         cout << "set is not subset" << endl;
  201.  
  202. }
  203.  
  204.  
  205. void heap_example ()
  206.     // illustrate the use of the heap functions
  207. {
  208.     ostream_iterator<int> intOut (cout, " ");
  209.     
  210.         // make a heap of 15 random integers
  211.     vector<int> aVec(15);
  212.     generate (aVec.begin(), aVec.end(), randomValue);
  213.     make_heap (aVec.begin(), aVec.end());
  214.     copy (aVec.begin(), aVec.end(), intOut),   cout << endl;
  215.     
  216.     cout << "Largest value " << aVec.front() << endl;
  217.     
  218.         // remove largest and reheap
  219.     pop_heap(aVec.begin(), aVec.end());
  220.     aVec.pop_back();
  221.     copy (aVec.begin(), aVec.end(), intOut),   cout << endl;
  222.     
  223.         // add a 97 to the heap
  224.     aVec.push_back(97);
  225.     push_heap (aVec.begin(), aVec.end());
  226.     copy (aVec.begin(), aVec.end(), intOut),   cout << endl;
  227.     
  228.         // finally, make into sorted collection
  229.     sort_heap (aVec.begin(), aVec.end());
  230.     copy (aVec.begin(), aVec.end(), intOut),   cout << endl;
  231. }
  232.  
  233. int main() {
  234.     cout << "Sorting generic algorithms examples" << endl;
  235.  
  236.     sortExample();
  237.     partial_sort_example();
  238.     nth_element_example();
  239.     binary_search_example();
  240.     merge_example();
  241.     set_example();
  242.     heap_example();
  243.     
  244.     cout << "End sorting examples" << endl;
  245.     return 0;
  246. }
  247.