home *** CD-ROM | disk | FTP | other *** search
/ Chip 2002 May / Chip_2002-05_cd1.bin / chplus / cpp / 3 / stl.exe / alg7.cpp < prev    next >
C/C++ Source or Header  |  1998-02-09  |  10KB  |  343 lines
  1. #include "stlexam.h"
  2. #pragma hdrstop
  3. /**************************************************************************
  4.  *
  5.  * alg7.cpp - Illustrate the use of the sort related generic algorithms.
  6.  *    Section 13
  7.  *
  8.  * $Id: alg7.cpp,v 1.11 1996/08/28 01:18:55 smithey Exp $
  9.  *
  10.  ***************************************************************************
  11.  *
  12.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  13.  * ALL RIGHTS RESERVED *
  14.  * The software and information contained herein are proprietary to, and
  15.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  16.  * intends to preserve as trade secrets such software and information.
  17.  * This software is furnished pursuant to a written license agreement and
  18.  * may be used, copied, transmitted, and stored only in accordance with
  19.  * the terms of such license and with the inclusion of the above copyright
  20.  * notice.  This software and information or any other copies thereof may
  21.  * not be provided or otherwise made available to any other person.
  22.  *
  23.  * Notwithstanding any other lease or license that may pertain to, or
  24.  * accompany the delivery of, this computer software and information, the
  25.  * rights of the Government regarding its use, reproduction and disclosure
  26.  * are as set forth in Section 52.227-19 of the FARS Computer
  27.  * Software-Restricted Rights clause.
  28.  * 
  29.  * Use, duplication, or disclosure by the Government is subject to
  30.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  31.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  32.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  33.  * P.O. Box 2328, Corvallis, Oregon 97339.
  34.  *
  35.  * This computer software and information is distributed with "restricted
  36.  * rights."  Use, duplication or disclosure is subject to restrictions as
  37.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  38.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  39.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  40.  * then the "Alternate III" clause applies.
  41.  *
  42.  **************************************************************************/
  43.  
  44.  
  45. #ifndef _RWSTD_HEADER_REQUIRES_HPP
  46. #include <vector>
  47. #include <deque>
  48. #include <list>
  49. #include <algorithm>
  50. #include <functional>
  51. #else
  52. #include <vector.hpp>
  53. #include <deque.hpp>
  54. #include <list.hpp>
  55. #include <algorithm.hpp>
  56. #include <functional.hpp>
  57. #endif
  58.  
  59. #ifdef _RW_STD_IOSTREAM
  60. #include <iostream>
  61. #else
  62. #include <iostream.h>
  63. #endif
  64.  
  65. #ifndef _RWSTD_NO_NAMESPACE
  66.   using namespace std;
  67. #endif
  68.     
  69. int randomInteger (unsigned int n) { return rand() % n; }
  70.     
  71. int randomValue () { return randomInteger(100); }
  72.  
  73. ostream_iterator<int,char,char_traits<char> > intOut(cout, " ");
  74.         
  75. void sortExample ()
  76. {
  77.     cout << "Sort algorithms"  << endl;
  78.     //
  79.     // Fill both a vector and a deque with random integers.
  80.     //
  81.     vector<int,allocator<int> > aVec(15);
  82.     deque<int,allocator<int> >  aDec(15);
  83.     generate (aVec.begin(), aVec.end(), randomValue);
  84.     generate (aDec.begin(), aDec.end(), randomValue);
  85.     //
  86.     // Sort the vector ascending.
  87.     //
  88.     sort (aVec.begin(), aVec.end());
  89.     copy (aVec.begin(), aVec.end(), intOut);
  90.     cout << endl;
  91.     //
  92.     // Sort the deque descending.
  93.     //
  94.     sort (aDec.begin(), aDec.end(), greater<int>() );
  95.     copy (aDec.begin(), aDec.end(), intOut);
  96.     cout << endl;
  97.     //
  98.     // Sort the vector descending?
  99.     //
  100.     sort (aVec.rbegin(), aVec.rend());
  101.     copy (aVec.begin(), aVec.end(), intOut);
  102.     cout << endl;
  103. }
  104.  
  105. void partial_sort_example ()
  106. {
  107.     cout << "Partial sort examples" << endl;
  108.     //
  109.     // Make a vector of 15 random integers.
  110.     //
  111.     vector<int,allocator<int> > aVec(15);
  112.     generate (aVec.begin(), aVec.end(), randomValue);
  113.     copy (aVec.begin(), aVec.end(), intOut);
  114.     cout << endl;
  115.     //
  116.     // Partial sort the first seven positions.
  117.     //
  118.     partial_sort (aVec.begin(), aVec.begin() + 7, aVec.end());
  119.     copy (aVec.begin(), aVec.end(), intOut);
  120.     cout << endl;
  121.     //
  122.     // Make a list of random integers.
  123.     //
  124.     list<int,allocator<int> > aList(15, 0);
  125.     generate (aList.begin(), aList.end(), randomValue);
  126.     copy (aList.begin(), aList.end(), intOut);
  127.     cout << endl;
  128.     //
  129.     // Sort only the first seven elements.
  130.     //
  131.     vector<int,allocator<int> > start(7);
  132.     partial_sort_copy (aList.begin(), aList.end(),
  133.                        start.begin(), start.end(), greater<int>());
  134.     copy (start.begin(), start.end(), intOut);
  135.     cout << endl;   
  136. }
  137.  
  138. //
  139. // Illustrate the use of the nth_largest function.
  140. //
  141.  
  142. void nth_element_example () 
  143. {
  144.     cout << "Nth largest example" << endl;
  145.     //
  146.     // Make a vector of random integers.
  147.     //
  148.     vector<int,allocator<int> > aVec(10);
  149.     generate (aVec.begin(), aVec.end(), randomValue);
  150.     //
  151.     // Now find the 5th largest.
  152.     //
  153.     vector<int,allocator<int> >::iterator nth = aVec.begin() + 4;
  154.     nth_element(aVec.begin(), nth, aVec.end());
  155.     cout << "fifth largest is " << *nth << " in" << endl;
  156.     copy (aVec.begin(), aVec.end(), intOut);
  157.     cout << endl;
  158. }
  159.  
  160. //
  161. // Illustrate the use of the binary search functions.
  162. //
  163.  
  164. void binary_search_example ()
  165. {
  166.     cout << "Binary search example" << endl;
  167.     //
  168.     // Make an ordered vector of 15 random integers.
  169.     //
  170.     vector<int,allocator<int> > aVec(15);
  171.     generate (aVec.begin(), aVec.end(), randomValue);
  172.     sort (aVec.begin(), aVec.end());
  173.     copy (aVec.begin(), aVec.end(), intOut),   cout << endl;
  174.     //
  175.     // See if it contains an eleven.
  176.     //
  177.     if (binary_search(aVec.begin(), aVec.end(), 11))
  178.         cout << "contains an 11" << endl;
  179.     else
  180.         cout << "does not contain an 11"  << endl;
  181.     //
  182.     // Insert an 11 and a 14.
  183.     //
  184.     vector<int,allocator<int> >::iterator where;
  185.     where = lower_bound (aVec.begin(), aVec.end(), 11);
  186.     aVec.insert (where, 11);
  187.     where = upper_bound (aVec.begin(), aVec.end(), 14);
  188.     aVec.insert (where, 14);
  189.     copy (aVec.begin(), aVec.end(), intOut),   cout << endl;
  190. }
  191.  
  192. //
  193. // Illustrate the use of the merge function.
  194. //
  195.  
  196. void merge_example ()
  197. {
  198.     cout << "Merge algorithm examples" << endl;
  199.     //
  200.     // Make a list and vector of 10 random integers.
  201.     //
  202.     vector<int,allocator<int> > aVec(10);
  203.     list<int,allocator<int> > aList(10, 0);
  204.     generate (aVec.begin(), aVec.end(), randomValue);
  205.     sort (aVec.begin(), aVec.end());
  206.     generate_n (aList.begin(), 10, randomValue);
  207.     aList.sort();
  208.     //
  209.     // Merge into a vector.
  210.     //
  211.     vector<int,allocator<int> > vResult (aVec.size() + aList.size());
  212.     merge (aVec.begin(), aVec.end(), aList.begin(), aList.end(), 
  213.            vResult.begin());
  214.     //
  215.     // Merge into a list.
  216.     //
  217.     list<int,allocator<int> > lResult;
  218.     merge (aVec.begin(), aVec.end(), aList.begin(), aList.end(), 
  219.            inserter(lResult, lResult.begin()));
  220.     //
  221.     // Merge into the output.
  222.     //
  223.     merge (aVec.begin(), aVec.end(), aList.begin(), aList.end(), 
  224.            ostream_iterator<int,char,char_traits<char> >(cout, " "));
  225.     cout << endl;
  226. }
  227.  
  228. class iotaGen
  229. {
  230.   public:
  231.     iotaGen (int c = 0) : current(c) { }
  232.     int operator () () { return current++; }
  233.   private:
  234.     int current;
  235. };
  236.  
  237. //
  238. // Illustrate the use of the generic set functions.
  239. //
  240.  
  241. void set_example ()
  242.  
  243. {
  244.     cout << "Set operations:" << endl;
  245.     //
  246.     // Make a couple of ordered lists.
  247.     //
  248.     list <int,allocator<int> > listOne, listTwo;
  249.     generate_n (inserter(listOne, listOne.begin()), 5, iotaGen(1));
  250.     generate_n (inserter(listTwo, listTwo.begin()), 5, iotaGen(3));
  251.     //
  252.     // union - 1 2 3 4 5 6 7
  253.     //
  254.     set_union (listOne.begin(), listOne.end(),
  255.                listTwo.begin(), listTwo.end(), intOut);
  256.     cout << endl;
  257.     //
  258.     // merge - 1 2 3 3 4 4 5 5 6 7
  259.     //
  260.     merge (listOne.begin(), listOne.end(),
  261.            listTwo.begin(), listTwo.end(), intOut);
  262.     cout << endl;
  263.     //
  264.     // intersection 3 4 5
  265.     //
  266.     set_intersection (listOne.begin(), listOne.end(),
  267.                       listTwo.begin(), listTwo.end(), intOut);
  268.     cout << endl;
  269.     //
  270.     // difference 1 2
  271.     //
  272.     set_difference (listOne.begin(), listOne.end(),
  273.                     listTwo.begin(), listTwo.end(), intOut);
  274.     cout << endl;
  275.     //
  276.     // symmetric difference 1 2 6 7
  277.     //
  278.     set_symmetric_difference (listOne.begin(), listOne.end(), 
  279.                               listTwo.begin(), listTwo.end(), intOut);
  280.     cout << endl;
  281.         
  282.     if (includes(listOne.begin(), listOne.end(),
  283.             listTwo.begin(), listTwo.end()))
  284.                 cout << "set is subset" << endl;
  285.     else
  286.         cout << "set is not subset" << endl;
  287. }
  288.  
  289. //
  290. // Illustrate the use of the heap functions.
  291. //
  292.  
  293. void heap_example ()
  294. {
  295.     ostream_iterator<int,char,char_traits<char> > intOut(cout, " ");
  296.     //
  297.     // Make a heap of 15 random integers.
  298.     //
  299.     vector<int,allocator<int> > aVec(15);
  300.     generate (aVec.begin(), aVec.end(), randomValue);
  301.     make_heap (aVec.begin(), aVec.end());
  302.     copy (aVec.begin(), aVec.end(), intOut);
  303.     cout << endl;
  304.     cout << "Largest value " << aVec.front() << endl;
  305.     //
  306.     // Remove largest and reheap.
  307.     //
  308.     pop_heap(aVec.begin(), aVec.end());
  309.     aVec.pop_back();
  310.     copy (aVec.begin(), aVec.end(), intOut);
  311.     cout << endl;
  312.     //
  313.     // Add a 97 to the heap.
  314.     //
  315.     aVec.push_back(97);
  316.     push_heap (aVec.begin(), aVec.end());
  317.     copy (aVec.begin(), aVec.end(), intOut);
  318.     cout << endl;
  319.     //
  320.     // Finally, make into sorted collection.
  321.     //
  322.     sort_heap (aVec.begin(), aVec.end());
  323.     copy (aVec.begin(), aVec.end(), intOut);
  324.     cout << endl;
  325. }
  326.  
  327. int main ()
  328. {
  329.     cout << "Sorting generic algorithms examples" << endl;
  330.  
  331.     sortExample();
  332.     partial_sort_example();
  333.     nth_element_example();
  334.     binary_search_example();
  335.     merge_example();
  336.     set_example();
  337.     heap_example();
  338.     
  339.     cout << "End sorting examples" << endl;
  340.  
  341.     return 0;
  342. }
  343.