firemail

标题: 算法 [打印本页]

作者: Qter    时间: 2020-1-1 14:59
标题: 算法
  1. /*
  2. * Copyright (c) 2009,CVICSE
  3. * All rights reserved.
  4. *
  5. * 文件名称:algorithm.cpp
  6. * 文件标识:通用算法技术
  7. * 摘 要:常用算法
  8. *
  9. * 当前版本:1.0
  10. * 作 者:draeag
  11. * 完成日期:2009年7月10日
  12. *
  13. * 取代版本:
  14. * 原作者 :
  15. * 完成日期:
  16. *
  17. * 参考文献:C++STL程序员开发指南
  18. * 页码 :p469   PDF:p448
  19. */


  20. #include "stl.h"
  21. //模板函数对象:打印元素
  22. template <class Type>
  23. class Print
  24. {
  25. public:
  26.         void operator() (Type& elem) const
  27.         {
  28.                 cout << elem << " ";
  29.         }
  30. };
  31. //模板函数对象:元素与给定的因子相乘
  32. template <class Type>
  33. class MultValue
  34. {
  35. private:
  36.         Type Factor;
  37. public:
  38.         MultValue(const Type& _Val) : Factor( _Val )
  39.         {
  40.         }
  41.         int operator() ( Type& elem ) const
  42.         {
  43.                 elem *= Factor;
  44.                 return elem;
  45.         }
  46. };
  47. //函数对象:计算平均数
  48. class Average
  49. {
  50. private:
  51.         long num;
  52.         long sum;
  53. public:
  54.         Average() : num(0), sum(0)
  55.         {
  56.         }
  57.         void operator() (int elem)
  58.         {
  59.                 num ++;
  60.                 sum += elem;
  61.         }
  62.         operator double () ///////////////////////////////////??????????????????????? 返回容器中所有元素的平均值
  63.         {
  64.                 return static_cast<double>(sum)/static_cast<double>(num);
  65.         }
  66. };
  67. /*
  68. * 函数介绍:参数1*2是否等于参数2
  69. * 输入参数:
  70. * 输出参数:
  71. * 返回值:bool
  72. */
  73. bool twice( int elem1, int elem2)
  74. {
  75.         return elem1 * 2 == elem2;
  76. }
  77. bool DEGreater(int elem1, int elem2)
  78. {
  79.         return elem1 > elem2;
  80. }
  81. bool mod_equal(int elem1, int elem2)
  82. {
  83.         if (elem1 < 0 )
  84.                 elem1 = -elem1;
  85.         if (elem2 < 0 )
  86.                 elem2 = -elem2;
  87.         return elem1 == elem2;
  88. }
  89. int settwo(void)
  90. {
  91.         return 2;
  92. }

  93. bool great5(int value)
  94. {
  95.         return value > 5;
  96. }
  97. //函数对象字符串比较

  98. struct twicefun
  99. {
  100.         bool inline operator()  (int elem1, int elem2)
  101.         {
  102.                 return elem1 * 2 == elem2;
  103.         }
  104. };
  105.         /*
  106. * 函数介绍:输出iterator的模板函数
  107. * 输入参数:@it:迭代器
  108. * 输出参数:
  109. * 返回值:void
  110. */
  111. template <class ITERATOR>
  112. void print_map_item(ITERATOR it)
  113. {
  114.         cout << (*it).first << ", " << (*it).second << endl;
  115. }

  116. //函数对象字符串比较

  117. struct ltstr
  118. {
  119. public:
  120.         bool operator()(const char* s1, const char* s2) const
  121.         {
  122.                 return strcmp(s1, s2) < 0;
  123.         }
  124. };

  125.        

  126. void main()
  127. {
  128.         // system("cls");
  129.        
  130.         cout << endl;
  131.         cout << "      ***********************************************************" << endl;
  132.     cout << "      **              非修正序列算法              **" << endl;
  133.     cout << "      ***********************************************************" << endl;

  134.         cout << endl;
  135.         cout << "      ******************************" << endl;
  136.     cout << "      **                            **" << endl;
  137.     cout << "      ** 1.查找容器中相邻的元素 adjacent_find  **" << endl;
  138.     cout << "      **                            **" << endl;
  139.     cout << "      ******************************" << endl;

  140.         //adjacent_find差额函数:查找相邻相同元素,返回指向一对临近相等元素中的第一个元素的迭代器
  141.         const int ARRAY_SIZE = 8;
  142.         int IntArray[ARRAY_SIZE] = {1, 2, 3, 4, 4, 5, 6, 7};
  143.         int *location;
  144.         location = adjacent_find(IntArray, IntArray + ARRAY_SIZE);
  145.         cout << "在数组中相邻两个元素相等: "<< "(" << *location << ", " << *(location+1) << ")" << endl;
  146.         cout <<"位置在 " << location - IntArray << endl;

  147.         int counresult;
  148.         //在first和end范围内统计value元素的个数,语法如下
  149.         /*template< class InputIterator, class T> inline
  150.                 size_t count(InputIterator first, InputIterator last, const T& value)*/
  151.         counresult = count(IntArray, IntArray + ARRAY_SIZE, 4);
  152.         cout << "元素4的个数为: "<< counresult << endl;

  153.         cout << lin;
  154.         cout << "      ******************************" << endl;
  155.     cout << "      **                            **" << endl;
  156.     cout << "      ** 2.容器对象变量比较 equal  **" << endl;
  157.     cout << "      **                            **" << endl;
  158.     cout << "      ******************************" << endl;

  159.         vector<int> v1, v2, v3;
  160.        
  161.         for ( int i = 0; i <=5; i++)
  162.         {
  163.                 v1.push_back(i);
  164.                 v2.push_back(i);
  165.                 v3.push_back(i*2);
  166.         }

  167.         v2.push_back(3);
  168.         bool b = false;

  169.         cout << endl;
  170.         cout << "v1: ";
  171.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  172.         cout << endl;
  173.         cout << "v2: ";
  174.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  175.         cout << endl;
  176.         //equal如果两个对象变量相等返回true否则返回false  只能比较同类型不同变量,
  177.         //且只要first1到last1范围的值与first2起始相同范围的值相等,则函数返回true.
  178.         b = equal(v1.begin(), v1.end(), v2.begin());
  179.         if ( b )
  180.         {
  181.                 cout << "v1 = v2" << endl;
  182.         }
  183.         else
  184.         {
  185.                 cout << "v1 != v2" << endl;
  186.         }

  187.         //b = equal(v1.begin(), v1.end(), v3.begin(), twice); //函数指针法
  188.         b = equal(v1.begin(), v1.end(), v3.begin(), twicefun()); //函数对象法
  189.         if ( b )
  190.         {
  191.                 cout << "v1*2 = v3" << endl;
  192.         }
  193.         else
  194.         {
  195.                 cout << "v1*2 != v3" << endl;
  196.         }

  197.         cout << lin;
  198.         cout << "      ******************************" << endl;
  199.     cout << "      **                            **" << endl;
  200.     cout << "      ** 3.查找元素find list vector   **" << endl;
  201.     cout << "      **                            **" << endl;
  202.     cout << "      ******************************" << endl;

  203.         //find函数返回first和last所规定的范围内的第一个数值等于value的元素的迭代器
  204.         //find引申很多谓词版本,如加一个比较函数,就产生算法find_if
  205.         //find_end(),find_first_of(),返回迭代器,
  206.         //指向最后(第一次)在first和last规定范围内找到first2和last2序列相等的子序列的位置

  207.         list<int> l;
  208.         l.push_back(10);
  209.         l.push_back(20);
  210.         l.push_back(30);
  211.         l.push_back(40);

  212.         list<int>::iterator relst;
  213.         relst = find(l.begin(), l.end(), 30);
  214.         if(relst != l.end())
  215.         {
  216.                 cout << "30 在 l中,位置为: " /*<< relst - l.begin()*/ << endl; // 列表中不能直接减
  217.         }
  218.         else
  219.         {
  220.                 cout << "30不在l中!"<< endl;
  221.         }

  222.         vector<int>::iterator result2;
  223.         result2 = find_end(v1.begin(),v1.end(),v3.begin(),v3.end(),twice);
  224.         if(result2 == v1.end())
  225.         {
  226.                 cout << "v3不在v1中" << endl;
  227.         }
  228.         else
  229.         {
  230.                 cout << "v3在v1中,开始位置为: " << result2 - v1.begin() << endl;
  231.         }


  232.         cout << lin;
  233.         cout << "      ******************************" << endl;
  234.     cout << "      **                            **" << endl;
  235.     cout << "      ** 4.特殊循环函数 for_each()   **" << endl;
  236.     cout << "      **                            **" << endl;
  237.     cout << "      ******************************" << endl;

  238.         vector<int>::iterator Iter1;
  239.         v1.clear();
  240.         int i;
  241.         for ( i = -4; i <= 2; i++)
  242.         {
  243.                 v1.push_back( i );
  244.         }

  245.         cout << "原v1 = ( ";
  246.         for (Iter1 = v1.begin(); Iter1 != v1.end(); Iter1++)
  247.         {
  248.                 cout << *Iter1 << " ";
  249.         }
  250.         cout << ")." << endl;

  251.         //把每个元素都乘以因子-2
  252.         for_each( v1.begin(), v1.end(), MultValue<int>(-2));
  253.         cout << "乘-2后: v1 = ( ";
  254.         for_each(v1.begin(), v1.end(), Print<int>());
  255.         cout << ")." << endl;
  256.                 //把每个元素都乘以因子5
  257.         for_each( v1.begin(), v1.end(), MultValue<int>(5));
  258.         cout << "乘5后: v1 = ( ";
  259.         for_each(v1.begin(), v1.end(), Print<int>());
  260.         cout << ")." << endl;

  261.         //求平均值
  262.         double avemod2 = for_each( v1.begin(), v1.end(), Average());
  263.         cout << "v1的平均值为: " << avemod2 << endl;


  264.         cout << lin;
  265.         cout << "      ******************************" << endl;
  266.     cout << "      **                            **" << endl;
  267.     cout << "      ** 3.不相等元素查找   **" << endl;
  268.     cout << "      **                            **" << endl;
  269.     cout << "      ******************************" << endl;

  270.         vector<int>::iterator it1;

  271.         pair<vector<int>::iterator, list<int>::iterator> pair_results1;
  272.         pair<vector<int>::iterator, vector<int>::iterator> pair_results2;
  273.         //mismatch(),不相等元素查找,返回一对迭代器,指向在first和last所规定的范围内第一个不相等的元素的位置,以及first2开始与first及last相同的长度的序列中第一个不相同的元素的位置
  274.         v1.clear();
  275.         v2.clear();
  276.         list<int> l1;
  277.         for (int i = 0; i <= 5; i++)
  278.         {
  279.                 v1.push_back(i);
  280.                 v2.push_back(i*2);
  281.         }
  282.         for(int i = 0; i<= 7; i++)
  283.         {
  284.                 l1.push_back(i*10);
  285.         }

  286.        
  287.         v2.push_back(16);

  288.         cout << "vector v1: ";
  289.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  290.         cout << endl;
  291.         cout << "list l1: ";
  292.         copy(l1.begin(), l1.end(), ostream_iterator<int>(cout, " "));
  293.         cout << endl;
  294.         cout << "vector v2: ";
  295.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  296.         cout << endl;

  297.         pair_results1 = mismatch(v1.begin(), v1.end(), l1.begin());
  298.         if (pair_results1.first == v1.end())
  299.         {
  300.                 cout << "v1和l1相匹配"<<endl;
  301.         }
  302.         else
  303.         {
  304.                 cout << "v1和l1有差异,第一次不匹配出现在" << *pair_results1.first << "和" << *pair_results1.second << endl;
  305.         }
  306.        
  307.         pair_results2 = mismatch(v1.begin(), v1.end(), v2.begin(), twice);

  308.         if (pair_results2.first == v1.end())
  309.         {
  310.                 cout << "v1和v2相匹配,且v2是v1元素的两倍"<<endl;
  311.         }
  312.         else
  313.         {
  314.                 cout << "v1和v2第一次不匹配出现在" << *pair_results2.first << "和" << *pair_results2.second << endl;
  315.         }

  316.         cout << endl;

  317.         v2.clear();
  318.         v2.push_back(2);
  319.         v2.push_back(3);

  320.         cout << "vector v1: ";
  321.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  322.         cout << endl;
  323.         cout << "vector v2: ";
  324.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  325.         cout << endl;

  326.         //search返回第一次出现在first1和last1所规定的范围内与序列first2和last2相等的位置
  327.         it1 = search(v1.begin(), v1.end(), v2.begin(), v2.end());
  328.         if (it1 == v1.end())
  329.         {
  330.                 cout << "在v1中找不到v2" << endl;
  331.         }
  332.         else
  333.         {
  334.                 cout << "v2在v1中第一次出现的相对位置为" << it1 - v1.begin() << endl;
  335.         }
  336.        

  337.         cout << endl;
  338.         cout << "      ***********************************************************" << endl;
  339.     cout << "      **              修正序列算法              **" << endl;
  340.     cout << "      ***********************************************************" << endl;

  341.         cout << endl;
  342.         cout << "      ******************************" << endl;
  343.     cout << "      **                            **" << endl;
  344.     cout << "      ** 1.元素复制 copy copy_backward  **" << endl;
  345.     cout << "      **                            **" << endl;
  346.     cout << "      ******************************" << endl;

  347.         //copy把first及last所规定的范围内的元素复制到另外一个由迭代器_DestBeg指向的元素所开始的范围,原来的元素则被覆盖,被拷贝的最后一个元素不包含在内
  348.         //copy_backward区别是从最后一个元素开始复制由后向前直到第一个元素

  349.         v1.clear();
  350.         v2.clear();
  351.         for (int i = 0; i < 10; i++)
  352.         {
  353.                 v1.push_back(i);
  354.                 v2.push_back(i+100);
  355.         }
  356.        
  357.         cout << "vector v1: ";
  358.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  359.         cout << endl;
  360.         cout << "vector v2: ";
  361.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  362.         cout << endl;

  363.         cout << "把v1的前三个元素拷贝到v2中第五个元素开始的连续三个元素";
  364.         copy( v1.begin(), v1.begin() + 3, v2.begin() + 4);
  365.         cout << endl;
  366.         cout << "*v1.begin(): " << *v1.begin() << endl;
  367.         cout << "*(v1.begin()+3): " << *(v1.begin()+3) << "最后一个元素不包含在内" << endl;       
  368.         cout << endl;
  369.         cout << "vector v2: ";
  370.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  371.         cout << endl;

  372.         cout << "把v2的倒数第二和倒第三的两个元素拷贝到第一和第二" << endl ;
  373.         copy( v2.begin()+7, v2.begin() + 9, v2.begin());
  374.         cout << endl;
  375.         cout << "vector v2: ";
  376.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  377.         cout << endl;

  378.         copy_backward(v1.begin() + 1, v1.begin() + 4, v1.begin() + 9);
  379.         cout << "vector v1: ";
  380.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  381.         cout << endl;

  382.         cout << endl;
  383.         cout << "      ******************************" << endl;
  384.     cout << "      **                            **" << endl;
  385.     cout << "      ** 2.赋值操作  fill  **" << endl;
  386.     cout << "      **                            **" << endl;
  387.     cout << "      ******************************" << endl;

  388.         //fill把数值val赋值到由迭代器first及last所规定的范围内的所有元素
  389.         //fill_n把count个元素赋值
  390.         cout << "vector v1: ";
  391.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  392.         cout << endl;
  393.         cout << "vector v2: ";
  394.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  395.         cout << endl;

  396.         cout << "把v1中的后5个元素赋值为100" << endl;
  397.         fill(v1.begin() + 5, v1.end(), 100);
  398.         //fill(v1.end() - 5, v1.end(), 100);

  399.         cout << "vector v1: ";
  400.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  401.         cout << endl;

  402.         cout << "把v2中的前6个元素赋值为99" << endl;
  403.         fill_n(v2.begin(), 6, 99);
  404.         cout << "vector v2: ";
  405.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  406.         cout << endl;

  407.         //generate对每一个元素调用_Gen函数,并把函数的结果复制到容器的元素中.
  408.         deque<int> deq1(5,1); //初始化大小为5,值为1;
  409.         copy(deq1.begin(), deq1.end(), ostream_iterator<int>(cout, " "));
  410.         cout << endl;
  411.         cout << "通过generate调用rand随机函数赋值后:" ;
  412.         generate(deq1.begin(), deq1.end(), rand);
  413.         cout << endl;
  414.         copy(deq1.begin(), deq1.end(), ostream_iterator<int>(cout, " "));
  415.         cout << endl;
  416.         cout << "前3个元素赋值为2" << endl;
  417.         generate_n(deq1.begin(), 5, settwo);
  418.         cout << endl;
  419.         copy(deq1.begin(), deq1.end(), ostream_iterator<int>(cout, " "));
  420.         cout << endl;
  421.        
  422.         cout << endl;
  423.         cout << "      ******************************" << endl;
  424.     cout << "      **                            **" << endl;
  425.     cout << "      ** 3.容器拆分技术 随机排列元素 partition  **" << endl;
  426.     cout << "      **                            **" << endl;
  427.     cout << "      ******************************" << endl;
  428.        
  429.         //partition()算法将一个序列分成两个部分,其中第一个部分被谓词_Comp作用后返回true值的元素,第二部分是返回false的元素
  430.         //这个函数返回一个指向两个部分分界点的迭代器
  431.         //random_shuffle()算法在first及last所规定范围内随机排列元素
  432.         v1.clear();
  433.         for (int i = 0; i < 10; i++ )
  434.         {
  435.                 v1.push_back(i);
  436.         }
  437.         cout << "原v1: ";
  438.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  439.         cout << endl;
  440.         cout << "打乱顺序v1:";
  441.         random_shuffle(v1.begin(), v1.end());
  442.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  443.         cout << endl;
  444.         cout << "根据是否大于5分组后的v1:";
  445.         it1 = partition(v1.begin(), v1.end(), great5 );
  446.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  447.         cout << endl;
  448.         cout <<"分组后指向分界点的元素为: "<<  *it1 << endl;


  449.         cout << endl;
  450.         cout << "      ******************************" << endl;
  451.     cout << "      **                            **" << endl;
  452.     cout << "      ** 4.元素删除 remove  **" << endl;
  453.     cout << "      **                            **" << endl;
  454.     cout << "      ******************************" << endl;

  455.         //remove在first及last所规定的范围内删除所有等于_Val的元素,返回新的迭代器结束点。
  456.         //删除后若大小不改变,或输出的结束位置仍和原来一样,则会发现后面原来位置的元素没有变,帮要重新设置大小
  457.        
  458.        
  459.         for (int i = 0; i < 3; i++ )
  460.         {
  461.                 v1.push_back(7);
  462.         }
  463.         random_shuffle(v1.begin(), v1.end());
  464.         cout << "    vector v1: ";
  465.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  466.         cout << endl;

  467.         vector<int>::iterator new_end;
  468.         new_end = remove(v1.begin(), v1.end(), 7);
  469.         cout << "remove 7后 v1: ";
  470.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  471.         cout << endl;

  472.         cout << "    resize 后: ";
  473.         v1.erase(new_end, v1.end());
  474.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  475.         cout << endl;

  476.         cout << endl;
  477.         cout << "      ******************************" << endl;
  478.     cout << "      **                            **" << endl;
  479.     cout << "      ** 5.元素替换 replace  **" << endl;
  480.     cout << "      **                            **" << endl;
  481.     cout << "      ******************************" << endl;

  482.         for (int i = 0; i < 3; i++ )
  483.         {
  484.                 v1.push_back(7);
  485.         }
  486.         random_shuffle(v1.begin(), v1.end());
  487.         cout << "vector v1: ";
  488.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  489.         cout << endl;
  490.         cout << "将v1中的7替换为700:" << endl;
  491.         replace(v1.begin(), v1.end(), 7, 700);
  492.         cout << "替换后vector v1: ";
  493.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  494.         cout << endl;

  495.         cout << endl;
  496.         cout << lin;
  497.         cout << "      ******************************" << endl;
  498.     cout << "      **                            **" << endl;
  499.     cout << "      ** 5.元素的旋转 rotate  **" << endl;
  500.     cout << "      **                            **" << endl;
  501.     cout << "      ******************************" << endl;

  502.         //rotate():把middle到last范围中的元素向左旋转到由first开始的范围中去。
  503.         v1.clear();
  504.         deq1.clear();

  505.         for (int i = -3; i <= 5; i++)
  506.         {
  507.                 v1.push_back(i);
  508.         }
  509.         for ( int i= 0; i <= 5; i++)
  510.         {
  511.                 deq1.push_back(i);
  512.         }
  513.         cout << "vector v1: ";
  514.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  515.         cout << endl;

  516.         cout << "deque deq1: ";
  517.         copy(deq1.begin(), deq1.end(), ostream_iterator<int>(cout, " "));
  518.         cout << endl;

  519.        
  520.         rotate(v1.begin(), v1.begin() + 3, v1.end());

  521.         cout << "旋转后v1:";
  522.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  523.         cout << endl;

  524.         int iii = 1;
  525.         while ( iii <= deq1.end() - deq1.begin() )
  526.         {
  527.                 rotate(deq1.begin(), deq1.begin() + 1, deq1.end());
  528.                 cout << "After the rotation of a single deque element to the back, \n deq1 is ( " ;
  529.                 copy(deq1.begin(), deq1.end(), ostream_iterator<int>(cout, " "));
  530.                 cout << " )." << endl;
  531.                 iii++;
  532.         }
  533.        
  534.         cout << endl;
  535.         cout << lin;
  536.         cout << endl;
  537.         cout << "      ******************************" << endl;
  538.     cout << "      **                            **" << endl;
  539.     cout << "      ** 6.元素的颠倒 reverse  **" << endl;
  540.     cout << "      **                            **" << endl;
  541.     cout << "      ******************************" << endl;

  542.         //reverse把双向迭代器first和last所规定范围中的元素颠倒排列。
  543.         cout << "vector v1: ";
  544.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  545.         cout << endl;

  546.         reverse(v1.begin(), v1.end());

  547.         cout << "颠倒后 v1: ";
  548.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  549.         cout << endl;

  550.         cout << endl;
  551.         cout << lin;
  552.         cout << endl;
  553.         cout << "      ******************************" << endl;
  554.     cout << "      **                            **" << endl;
  555.     cout << "      ** 6.元素的交换 swap swap_ranges  **" << endl;
  556.     cout << "      **                            **" << endl;
  557.     cout << "      ******************************" << endl;

  558.         //swap交换所有的容器元素
  559.         //swap_ranges把first和last规定范围中的元素以及由first2所开始的等长范围中的元素进行互相交换。
  560.         cout << "vector v1: ";
  561.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  562.         cout << endl;

  563.         cout << "vector v2: ";
  564.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  565.         cout << endl;

  566.         cout << "deque deq1: ";
  567.         copy(deq1.begin(), deq1.end(), ostream_iterator<int>(cout, " "));
  568.         cout << endl;

  569.         cout << "v1与v2交换后:" << endl;
  570.         swap(v1,v2);

  571.         cout << "vector v1: ";
  572.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  573.         cout << endl;

  574.         cout << "vector v2: ";
  575.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  576.         cout << endl;



  577.         v2.erase(v2.end() - 4, v2.end());
  578.         cout << "*(v2.end()-2):的元素是" << *(v2.end()-2) << endl;
  579.         cout << "vector v2: ";
  580.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  581.         cout << endl;
  582.         cout << "v2全部元素-4后与deq1相同数量的元素交换后:" << endl;
  583.         swap_ranges(v2.begin(), v2.end(), deq1.begin() );


  584.         cout << "vector v2: ";
  585.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  586.         cout << endl;


  587.         cout << "deque deq1: ";
  588.         copy(deq1.begin(), deq1.end(), ostream_iterator<int>(cout, " "));
  589.         cout << endl;

  590.         cout << endl;
  591.         cout << lin;
  592.         cout << endl;
  593.         cout << "      ******************************" << endl;
  594.     cout << "      **                            **" << endl;
  595.     cout << "      ** 7.容器运算技术 transform  **" << endl;
  596.     cout << "      **                            **" << endl;
  597.     cout << "      ******************************" << endl;

  598.         //transform对first和last所规定范围中的元素调用函数_Func,并把运算的结果存储在_Result所开始的等长范围内 .
  599.         v1.clear();
  600.         v2.clear();
  601.         v3.clear();


  602.         v2.resize(6); //用transform给v2赋值时注意设置v2的大小
  603.         v3.resize(6);
  604.         for (int i = -4; i < 2; i++)
  605.         {
  606.                 v1.push_back(i);
  607.         }
  608.         cout << "vector v1: ";
  609.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  610.         cout << endl;

  611.         cout << "vector v2: ";
  612.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  613.         cout << endl;

  614.         cout << "vector v3: ";
  615.         copy(v3.begin(), v3.end(), ostream_iterator<int>(cout, " "));
  616.         cout << endl;

  617.        
  618.         cout << "把v1中的元素都乘2." << endl ;
  619.         transform(v1.begin(), v1.end(), v1.begin(), MultValue<int>(2));
  620.        
  621.         cout << "vector v1: ";
  622.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  623.         cout << endl;

  624.         cout << "把v1中的元素*5后放v2中.其实v1中的元素也已经被改变." << endl;
  625.         cout << "v2.size(): " << v2.size() << endl;
  626.         transform(v1.begin(), v1.end(), v2.begin(), MultValue<int>(5));

  627.         cout << "vector v1: ";
  628.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  629.         cout << endl;
  630.         cout << "vector v2: ";
  631.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  632.         cout << endl;

  633.         cout << "把v1中的元素乘v2中的元素放v3中." << endl ;
  634.         transform(v1.begin(), v1.end(), v2.begin(),v3.begin(), multiplies<int>());

  635.         cout << "vector v3: ";
  636.         copy(v3.begin(), v3.end(), ostream_iterator<int>(cout, " "));
  637.         cout << endl;

  638.         cout << endl;
  639.         cout << lin;
  640.         cout << endl;
  641.         cout << "      ******************************" << endl;
  642.     cout << "      **                            **" << endl;
  643.     cout << "      ** 8.删除容器中的重复元素 unique  **" << endl;
  644.     cout << "      **                            **" << endl;
  645.     cout << "      ******************************" << endl;

  646.         //unique删除first和last范围中所有重复的相邻元素
  647.         v1.clear();

  648.         for (int i = 0; i <= 3; i++)
  649.         {
  650.                 v1.push_back(5);
  651.                 v1.push_back(-5);
  652.         }
  653.         for (int i = 0; i <= 3; i++)
  654.         {
  655.                 v1.push_back(4);
  656.         }
  657.         v1.push_back(7);

  658.         cout << "vector v1: ";
  659.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  660.         cout << endl;

  661.         vector<int>::iterator it_new_end1 ;
  662.         it_new_end1 = unique(v1.begin(), v1.end());

  663.         cout << "去掉相邻重复元素 v1: ";
  664.         copy(v1.begin(),it_new_end1, ostream_iterator<int>(cout, " "));//结束位置为it_new_end1
  665.         cout << endl;

  666.         it_new_end1 = unique(v1.begin(),it_new_end1, mod_equal);
  667.         cout << "按绝对值去掉相邻重复元素 v1: ";
  668.         copy(v1.begin(),it_new_end1, ostream_iterator<int>(cout, " "));//结束位置为it_new_end1
  669.         cout << endl;

  670.         it_new_end1 = unique(v1.begin(),it_new_end1, greater<int>());
  671.         cout << "按大于比较确保相邻元素按递增排列 v1: ";
  672.         copy(v1.begin(),it_new_end1, ostream_iterator<int>(cout, " "));//结束位置为it_new_end1
  673.         cout << endl;

  674.         cout << endl;
  675.         cout << "      ***********************************************************" << endl;
  676.     cout << "      **              排序算法              **" << endl;
  677.     cout << "      ***********************************************************" << endl;

  678.         cout << endl;
  679.         cout << "      ******************************" << endl;
  680.     cout << "      **                            **" << endl;
  681.     cout << "      ** 1.排序 sort  stable_sort() partial_sort() **" << endl;
  682.     cout << "      **                            **" << endl;
  683.     cout << "      ******************************" << endl;
  684.        
  685.         v1.clear();
  686.         v2.clear();
  687.         l1.clear();

  688.         for (int i = 0; i <= 5; i++)
  689.         {
  690.                 v1.push_back( 2 * i);
  691.         }
  692.         for (int i=0; i <= 5; i++)
  693.         {
  694.                 v1.push_back(2 * i + 1);
  695.         }

  696.         l1.push_back(60);
  697.         l1.push_back(50);
  698.         l1.push_back(40);
  699.         l1.push_back(30);
  700.         l1.push_back(20);
  701.         l1.push_back(10);

  702.         for (int i=0; i <= 9; i++)
  703.         {
  704.                 v2.push_back( i );
  705.         }


  706.         cout << "vector v1: ";
  707.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  708.         cout << endl;

  709.         cout << "vector v2: ";
  710.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  711.         cout << endl;

  712.         cout << "list l1: ";
  713.         copy(l1.begin(), l1.end(), ostream_iterator<int>(cout, " "));
  714.         cout << endl;

  715.         cout << "排序后v1: " ;
  716.         sort (v1.begin(), v1.end());
  717.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  718.         cout << endl;

  719.         cout << "greater排序后v1: ";
  720.         sort(v1.begin(), v1.end(), greater<int>());
  721.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  722.         cout << endl;

  723.         cout << "DEGreater排序后v1: ";
  724.         sort(v1.begin(), v1.end(), DEGreater);
  725.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  726.         cout << endl;

  727.         cout << "打乱排序后v1: ";
  728.         random_shuffle(v1.begin(), v1.end());
  729.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  730.         cout << endl;

  731.         cout << "partital_sort对前四个数字排序后v1: ";
  732.         partial_sort(v1.begin(), v1.begin() + 4, v1.end(), DEGreater);
  733.         copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
  734.         cout << endl;

  735.         cout << "partital_sort_copy l1 into v2: ";
  736.         it1 = partial_sort_copy(l1.begin(), l1.end(),v2.begin(), v2.begin() + 6,greater<int>());
  737.         copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
  738.         cout << endl;
  739.         cout << "The first v2 element one position beyond" << "\n the last l1 element inserted was "<< *it1 << endl;
  740.        
  741.        

  742. }
复制代码





欢迎光临 firemail (http://firemail.wang:8088/) Powered by Discuz! X3