C++STL 常用算法

拼搏现实的明天。 2022-04-11 05:47 335阅读 0赞

转自
[url]http://www.cnblogs.com/BeyondAnyTime/archive/2012/05/27/2520532.html\[/url\]

[align=center][size=medium][color=red][b]一、非变异算法[/b][/color][/size][/align]

是一组不破坏操作数据的模板函数，用来对序列数据进行逐个处理、元素查找、子序列搜索、统计和匹配。非变异算法具有极为广泛的适用性，基本上可应用与各种容器。

[size=medium][color=red][b]1. 查找容器元素 - find[/b][/color][/size]
[i][b]函数功能：[/b][/i]
它用于查找等于某值的元素。它在迭代器区间[first,last)(闭开区间)上查找等于value值的元素，如果迭代器i所指的元素满足*i=value，则返回迭代器i；未找到满足条件的元素，返回last。

[i][b]函数原型：[/b][/i] 

  1. #include <algorithm>
  2. template <class InputIterator, class T>
  4. InputIterator find (InputIterator first, InputIterator last, const T& val);

[i][b]输入参数：[/b][/i]
[b]first, last[/b]
输入查询序列的开始和结束位置，注意：这两个参数为迭代器。
[b]val[/b]
　　 要查询的值

[i][b]返回值：[/b][/i]
返回查询结果的迭代器

[i][b]实例：[/b][/i] 

  1. #include <vector>
  2. #include <algorithm>
  3. #include <iostream>
  4. using namespace std;
  6. void main()
  8. {
  10.     //为vecIntegers添加数据
  11.     vector<int> vecIntegers;
  12.     for (int nNum=0; nNum<10;++nNum)
  13.     {
  15.         vecIntegers.push_back(nNum);
  16.     }
  18.     //打印数据
  19.     vector<int>::const_iterator iElementLocator;
  20.     for (iElementLocator=vecIntegers.begin(); iElementLocator != vecIntegers.end(); ++iElementLocator)
  21.     {
  23.         cout << *iElementLocator << ' ';
  24.     }
  25.     cout << endl;
  27.     /*****************关键代码******************************/
  28.     //查找数字 3
  29.     //注意：返回值为迭代器
  30.     vector<int>::iterator iElementFound;
  31.     iElementFound = find(vecIntegers.begin(), vecIntegers.end(), 3);
  32.     if (iElementFound != vecIntegers.end()) //如果找到结果
  33.     {
  35.         cout << *iElementFound << endl; 
  36.     }
  37.     else
  38.     {
  40.         cout << "没有找到结果！" << endl;
  41.     }
  42.     /****************************************************/
  44. }
  50. 0 1 2 3 4 5 6 7 8 9
  51. 3
  52. Press any key to continue

[size=medium][color=red][b]2. 条件查找容器元素 - find_if[/b][/color][/size]
利用返回布尔值的谓词判断pred，检查迭代器区间[first,last)(闭开区间)上的每一个元素，如果迭代器i满足pred（*i）＝true，表示找到元素并返回迭代值i（找到的第一个符合条件的元素）；未找到元素，返回末位置last。 

  1. 函数原型：find_if(v.begin(),v.end(),divby5);
  7. #include <vector>
  8. #include <algorithm>
  9. #include <iostream>
  10. using namespace std;
  12. bool divby5(int x)
  13. {
  15.     return x%5 ? 0:1;
  16. }
  18. void main()
  19. {
  21.     vector<int> v(20);
  22.     for (int i = 0; i < v.size(); i++)
  23.     {
  25.         v[i] = (i+1)*(i+3);
  26.         cout << v[i] << ' ';
  27.     }
  29.     cout << endl;
  31.     vector<int>::iterator ilocation;
  32.     ilocation = find_if(v.begin(),v.end(),divby5);
  33.     if(ilocation != v.end())
  34.     {
  36.         cout << "找到第一个能被5整除的元素：" << *ilocation << endl
  37.              << "元素的索引位置是： " << ilocation-v.begin() << endl;
  38.     }
  39. }
  45. 3 8 15 24 35 48 63 80 99 120 143 168 195 224 255 288 323 360 399 440
  46. 找到第一个能被5整除的元素：15
  47. 元素的索引位置是：2
  48. Press any key to continue

[size=medium][color=red][b]3. 统计等于某值的容器元素个数 - count[/b][/color][/size]
[i][b]函数原型：[/b][/i] 

  1. template<class InputIterator, class T> 
  2. inline 
  3. size_t count(
  4.       InputIterator First,
  5.       InputIterator Last,
  6.       const T& Value
  7.    )
  13. #include <iostream>  
  14. #include <algorithm>  
  15. #include <functional>  
  16. #include <string>  
  17. #include <vector>  
  19. void main()
  20. {
  22.     using namespace std;  
  23.     const int VECTOR_SIZE = 8 ;
  25.     // Define a template class vector of strings
  26.     typedef vector<string > StringVector ;
  28.     //Define an iterator for template class vector of strings
  29.     typedef StringVector::iterator StringVectorIt ;
  31.     StringVector NamesVect(VECTOR_SIZE) ;   //vector containing names
  33.     string value("Sea") ;  // stores the value used
  34.     // to count matching elements
  36.     StringVectorIt start, end, it ;
  38.     ptrdiff_t result = 0 ;   // stores count of elements
  39.     // that match value.
  41.     // Initialize vector NamesVect
  42.     NamesVect[0] = "She" ;
  43.     NamesVect[1] = "Sells" ;
  44.     NamesVect[2] = "Sea" ;
  45.     NamesVect[3] = "Shells" ;
  46.     NamesVect[4] = "by" ;
  47.     NamesVect[5] = "the" ;
  48.     NamesVect[6] = "Sea" ;
  49.     NamesVect[7] = "Shore" ;
  51.     start = NamesVect.begin() ;   // location of first  
  52.     // element of NamesVect  
  54.     end = NamesVect.end() ;       // one past the location  
  55.     // last element of NamesVect  
  57.     // print content of NamesVect
  58.     cout << "NamesVect { " ;  
  59.     for(it = start; it != end; it++)
  60.     {
  62.         cout << *it << " " ;
  63.     }
  64.     cout << " }\n" << endl ;
  66.     // Count the number of elements in the range [first, last +1)  
  67.     // that match value.  
  68.     result = count(start, end, value) ;  
  70.     // print the count of elements that match value  
  71.     cout << "Number of elements that match \"Sea\" = "  
  72.         << result << endl  ; 
  73. }
  78. NamesVect {She Sells Sea Shells by the Sea Shore}
  79. Number of elements that match "Sea" = 2 
  80. Press any key to continue

[size=medium][color=red][b]4. 条件统计 - count_if[/b][/color][/size] 

  1. count_if（l.begin（），l.end()，pred）

谓词pred含义同find_if中的谓词。例子可以参考例2.

[i][b]函数原型：[/b][/i] 

  1. template<class _InIt, class _Pr>
  2. inline
  3. typename iterator_traits<_InIt>::difference_type
  4.      count_if(_InIt _First, _InIt _Last, _Pr _Pred);

[i][b]示例：[/b][/i] 

  1. #include <iostream>  
  2. #include <algorithm>  
  3. #include <functional>  
  4. #include <string>  
  5. #include <vector>  
  7. using namespace std; 
  8. // Return true if string str starts with letter 'S'  
  9. int MatchFirstChar( const string& str)  
  10. {  
  11.     string s("S") ;  
  12.     return s == str.substr(0,1) ;  
  13. }  
  15. void main()
  16. {  
  17.     const int VECTOR_SIZE = 8 ;
  19.     // Define a template class vector of strings
  20.     typedef vector<string > StringVector ;
  22.     //Define an iterator for template class vector of strings
  23.     typedef StringVector::iterator StringVectorIt ;
  25.     StringVector NamesVect(VECTOR_SIZE) ;   //vector containing names
  27.     StringVectorIt start, end, it ;
  29.     ptrdiff_t result = 0 ;   // stores count of elements
  30.     // that match value.  
  32.     // Initialize vector NamesVect  
  33.     NamesVect[0] = "She" ;  
  34.     NamesVect[1] = "Sells" ;  
  35.     NamesVect[2] = "Sea" ;  
  36.     NamesVect[3] = "Shells" ;  
  37.     NamesVect[4] = "by" ;  
  38.     NamesVect[5] = "the" ;  
  39.     NamesVect[6] = "Sea" ;  
  40.     NamesVect[7] = "Shore" ;  
  42.     start = NamesVect.begin() ;   // location of first  
  43.     // element of NamesVect  
  45.     end = NamesVect.end() ;       // one past the location  
  46.     // last element of NamesVect  
  48.     // print content of NamesVect  
  49.     cout << "NamesVect { " ;  
  50.     for(it = start; it != end; it++)  
  51.         cout << *it << " " ;  
  52.     cout << " }\n" << endl ;  
  54.     // Count the number of elements in the range [first, last +1)  
  55.     // that start with letter 'S'  
  56.     result = count_if(start, end, MatchFirstChar) ;  
  58.     // print the count of elements that start with letter 'S'  
  59.     cout << "Number of elements that start with letter \"S\" = "  
  60.         << result << endl  ;  
  61. }
  66. NamesVect {She Sells Sea Shells by the Sea Shore}
  67. Number of elements that start with letter  "S" = 6 
  68. Press any key to continue

[color=red][b]5. 子序列搜索 - search[/b][/color]
search算法函数在一个序列中搜索与另一序列匹配的子序列。参数分别为一个序列的开始位置，结束位置和另一个序列的开始，结束位置。 

  1. 函数原型：search(v1.begin(),v1.end(),v2.begin(),v2.end());
  7. #include <vector>
  8. #include <algorithm>
  9. #include <iostream>
  10. using namespace std;
  12. void main()
  13. {
  15.     vector<int> v1;
  16.     cout << "v1:";
  18.     for (int i = 0; i < 5; i++)
  19.     {
  21.         v1.push_back(i+5);
  23.         //注意：v1定义时没有给定大小，因此这里不能直接使用赋值语句。
  24.         cout<<v1[i]<<' ';
  25.     }
  27.     cout << endl;
  29.     vector<int> v2;
  30.     cout << "v2:";
  31.     for (int i = 0; i < 2; i++)
  32.     {
  34.         v2.push_back(i+7);
  35.         cout << v2[i] << ' ';
  36.     }
  37.     cout << endl;
  39.     vector<int>::iterator ilocation;
  41.     ilocation = search(v1.begin(),v1.end(),v2.begin(),v2.end());
  42.     if (ilocation != v1.end())
  43.     {
  45.         cout << "v2的元素包含在v1中，起始元素为" << "v1[" << ilocation-v1.begin() << ']' << endl;
  46.     }
  47.     else
  48.     {
  50.         cout << "v2的元素不包含在v1中" << endl;
  51.     }
  52. }
  57. v1: 5 6 7 8 9 
  58. v2: 7 8
  59. v2的元素包含在v1中，起始元素为v1[2]

[color=red][b]6重复元素子序列搜索search_n[/b][/color]

search_n算法函数搜索序列中是否有一系列元素值均为某个给定值的子序列。 

  1. 函数原型：search_n(v.begin(),v.end(),3,8)，

在v中找到3个连续的元素8 

  1. #include <vector>
  2. #include <algorithm>
  3. #include <iostream>
  4. using namespace std;
  6. void main()
  7. {
  9.     vector<int> v;
  10.     v.push_back(1);
  11.     v.push_back(8);
  12.     v.push_back(8);
  13.     v.push_back(8);
  14.     v.push_back(6);
  15.     v.push_back(6);
  16.     v.push_back(8);
  18.     vector<int>::iterator i;
  19.     i = search_n(v.begin(),v.end(),3,8);
  20.     if (i != v.end())
  21.     {
  23.         cout<<"在v中找到3个连续的元素8"<<endl;
  24.     }
  25.     else
  26.     {
  28.         cout<<"在v中未找到3个连续的元素8"<<endl;
  29.     }
  30. }
  35. 在v中找到3个连续的元素8

[color=red][b]7最后一个子序列搜索find_end[/b][/color] 

  1. 函数原型find_end(v1.begin(),v1.end(),v2.begin(),v2.end());

在V1中要求的位置查找V2中要求的序列。 

  1. #include <vector>
  2. #include <algorithm>
  3. #include <iostream>
  4. using namespace std;
  6. void main()
  7. {
  9.     vector<int> v1;
  10.     v1.push_back(-5);
  11.     v1.push_back(1);
  12.     v1.push_back(2);
  13.     v1.push_back(-6);
  14.     v1.push_back(-8);
  15.     v1.push_back(1);
  16.     v1.push_back(2);
  17.     v1.push_back(-11);
  19.     vector<int> v2;
  20.     v2.push_back(1);
  21.     v2.push_back(2);
  23.     vector<int>::iterator i;
  24.     i = find_end(v1.begin(), v1.end(), v2.begin(), v2.end());
  25.     if (i != v1.end())
  26.     {
  28.         cout << "v1中找到最后一个匹配v2的子序列，位置在" << "v1[" << i-v1.begin() << "]" << endl;
  29.     }
  30. }
  35. "v1中找到最后一个匹配v2的子序列，位置在v1[5]

[align=center][size=medium][color=red][b]二、变异算法[/b][/color][/size][/align]

是一组能够修改容器元素数据的模板函数。copy(v.begin(),v.end(),l.begin());将v中的元素复制到l中。

[color=red][b]1元素复制copy[/b][/color] 

  1. #include <vector>
  3. #include <list>
  5. #include <algorithm>
  7. #include <iostream>
  9. using namespace std;
  13. void main()
  15. {
  18. vector<int> v;
  20. v.push_back(1);
  22. v.push_back(3);
  24. v.push_back(5);
  28. list<int> l;
  30. l.push_back(2);
  32. l.push_back(4);
  34. l.push_back(6);
  36. l.push_back(8);
  38. l.push_back(10);
  40. copy(v.begin(),v.end(),l.begin());
  42. list<int>::iterator i;
  44. for(i=l.begin();i!=l.end();i++)
  46. cout<<*i<<' ';
  48. cout<<endl;
  50. }

[color=red][b]2元素变换transform改变[/b][/color] 

  1. 函数原型：transform(v.begin(),v.end(),l.begin(),square);

也是复制，但是要按某种方案复制。 

  1. #include <vector>
  3. #include <list>
  5. #include <algorithm>
  7. #include <iostream>
  9. using namespace std;
  13. int square(int x)
  15. {
  18. return x*x;
  20. }
  22. void main()
  24. {
  27. vector<int> v;
  29. v.push_back(5);
  31. v.push_back(15);
  33. v.push_back(25);
  35. list<int> l(3);
  37. transform(v.begin(),v.end(),l.begin(),square);
  39. list<int>::iterator i;
  41. for(i=l.begin();i!=l.end();i++)
  43. cout<<*i<<' ';
  45. cout<<endl;
  47. }

[color=red][b]3替换replace[/b][/color]

replace算法将指定元素值替换为新值。 

  1. #include <vector>
  3. #include <algorithm>
  5. #include <iostream>
  7. using namespace std;
  11. void main()
  13. {
  16. vector<int> v;
  18. v.push_back(13);
  20. v.push_back(25);
  22. v.push_back(27);
  24. v.push_back(25);
  26. v.push_back(29);
  28. replace(v.begin(),v.end(),25,100);
  30. vector<int>::iterator i;
  32. for(i=v.begin();i!=v.end();i++)
  34. cout<<*i<<' ';
  36. cout<<endl;
  38. }
  44. 13 100 27 100 29

[color=red][b]4条件替换replace_if[/b][/color] 

  1. 函数原型：replace_if(v.begin(),v.end(),odd,100);
  7. #include <vector>
  9. #include <algorithm>
  11. #include <iostream>
  13. using namespace std;
  17. bool odd(int x)
  19. {
  22. return x%2;
  24. }
  26. void main()
  28. {
  31. vector<int> v;
  33. for(int i=1;i<10;i++)
  35. v.push_back(i);
  37. replace_if(v.begin(),v.end(),odd,100);
  39. vector<int>::iterator ilocation;
  41. for(ilocation=v.begin();ilocation!=v.end();ilocation++)
  43. cout<<*ilocation<<' ';
  45. cout<<endl;
  47. }

[color=red][b]5n次填充fill_n[/b][/color]

函数原型fill_n(v.begin(),5,-1)；向从v.begin开始的后面5个位置跳入-1 

  1. #include <vector>
  3. #include <algorithm>
  5. #include <iostream>
  7. using namespace std;
  9. void main()
  11. {
  14. vector<int> v(10);
  16. fill_n(v.begin(),5,-1);
  18. vector<int>::iterator ilocation;
  20. for(ilocation=v.begin();ilocation!=v.end();ilocation++)
  22. cout<<*ilocation<<' ';
  24. cout<<endl;
  26. }
  28. 输出结果：-1 -1 -1 -1 -1 0 0 0 0 0

6随机生成n个元素generate

函数原型：generate_n(v.begin(),5,rand);向从v.begin开始的后面5个位置随机填写数据。

#include

#include

#include

using namespace std;

void main()

{

vector v(10);

generate_n(v.begin(),5,rand);

vector::iterator ilocation;

for(ilocation=v.begin();ilocation!=v.end();ilocation++)

cout<<*ilocation<<’ ‘;

cout<<endl;

}

7条件移除remove_if

返回值相当于移除满足条件的元素后形成的新向量的end（）值。

函数原型：remove_if(v.begin(),v.end(),even);

#include

#include

#include

using namespace std;

bool even(int x)

{

return x%2?0:1;

}

void main()

{

vector v;

for(int i=1;i<=10;i++)

v.push_back(i);

vector::iterator ilocation,result;

cout<<”移除前：”;

for(ilocation=v.begin();ilocation!=v.end();ilocation++)

cout<<*ilocation<<’ ‘;

cout<<endl;

result=remove_if(v.begin(),v.end(),even);

cout<<”移除后：”;

for(ilocation=v.begin();ilocation!=result;ilocation++)

cout<<*ilocation<<’ ‘;

cout<<endl;

}

8剔除连续重复元素unique

函数原型：unique(v.begin(),v.end());

#include

#include

#include

using namespace std;

void main()

{

vector v;

v.push_back(2);

v.push_back(6);

v.push_back(6);

v.push_back(6);

v.push_back(9);

v.push_back(6);

v.push_back(3);

vector::iterator ilocation,result;

result=unique(v.begin(),v.end());

for(ilocation=v.begin();ilocation!=result;ilocation++)

cout<<*ilocation<<’ ‘;

cout<<endl;

}

输出结果：2 6 9 6 3

[align=center][size=medium][color=red][b]三、排序算法[/b][/color][/size][/align]

[b]1、创建堆make_heap[/b]

[b]2、元素入堆push_heap（默认插入最后一个元素）[/b]

[b]3、元素出堆pop_heap（与push_heap一样，pop_heap必须对堆操作才有意义）[/b] 

  1. #include <vector>
  2. #include <algorithm>
  3. #include <iostream>
  4. using namespace std;
  6. void main()
  7. {
  9.     vector<int> v;
  10.     v.push_back(5);
  11.     v.push_back(6);
  12.     v.push_back(4);
  13.     v.push_back(8);
  14.     v.push_back(2);
  15.     v.push_back(3);
  16.     v.push_back(7);
  17.     v.push_back(1);
  18.     v.push_back(9);
  20.     make_heap(v.begin(), v.end());
  21.     v.push_back(20);
  22.     push_heap(v.begin(), v.end());
  24.     vector<int>::iterator ilocation;
  25.     for(ilocation = v.begin(); ilocation != v.end(); ilocation++)
  26.     {
  28.         cout << *ilocation << ' ';
  29.     }
  31.     cout << endl;
  33.     pop_heap(v.begin(), v.end());
  34.     for (ilocation = v.begin(); ilocation != v.end(); ilocation++)
  35.     {
  37.         cout << *ilocation << ' ';
  38.     }
  40.     cout << endl;
  41. }
  46. 20 9 7 6 8 3 4 1 5 2
  47. 9 8 7 6 2 3 4 1 5 20

[size=medium][color=red][b]4. 堆排序 - sort_heap[/b][/color][/size]

使用： 

  1. make_heap(v.begin(),v.end());
  2. sort_heap(v.begin(),v.end());
  8. #include <vector>
  9. #include <algorithm>
  10. #include <iostream>
  11. using namespace std;
  13. void main()
  14. {
  16.     vector<int> v;
  17.     v.push_back(3);
  18.     v.push_back(9);
  19.     v.push_back(6);
  20.     v.push_back(3);
  21.     v.push_back(17);
  22.     v.push_back(20);
  23.     v.push_back(12);
  25.     vector<int>::iterator ilocation;
  26.     for (ilocation = v.begin(); ilocation != v.end(); ilocation++)
  27.     {
  29.         cout << *ilocation << ' ';
  30.     }
  32.     cout << endl;
  34.     make_heap(v.begin(),v.end());
  35.     sort_heap(v.begin(),v.end());
  37.     for (ilocation = v.begin(); ilocation != v.end(); ilocation++)
  38.     {
  40.         cout << *ilocation << ' ';
  41.     }
  43.     cout << endl;
  44. }
  50. 3 9 6 3 17 20 12
  51. 3 3 6 9 12 17 20

[size=medium][color=red][b]5. 排序 - sort[/b][/color][/size]
sort详细解释参考link[url]http://www.cppblog.com/mzty/archive/2005/12/15/1770.html\[/url\]

[i][b]函数说明：[/b][/i]
这个函数可以传两个参数或三个参数。第一个参数是要排序的区间首地址，第二个参数是区间 尾地址的下一地址。也就是说，排序的区间是[a,b)。简单来说，有一个数组int a[100]，要对从a[0]到a[99]的元素进行排序，只要写sort(a,a+100)就行了，默认的排序方式是升序。

[i][b]函数原型：[/b][/i] 

  1. template<class RanIt>
  2.        void sort(RanIt fist, RanIt last);
  3. template<class RanIt, class Pred>
  4.        void sort(RanIt fist, RanIt last, Pred pr);
  10. #include <vector>
  11. #include <algorithm>
  12. #include <iostream>
  13. using namespace std;
  15. void main()
  16. {
  18.     vector<int> v;
  19.     v.push_back(2);
  20.     v.push_back(8);
  21.     v.push_back(-15);
  22.     v.push_back(90);
  23.     v.push_back(26);
  24.     v.push_back(7);
  25.     v.push_back(23);
  26.     v.push_back(30);
  27.     v.push_back(-27);
  28.     v.push_back(39);
  29.     v.push_back(55);
  31.     vector<int>::iterator ilocation;
  32.     for (ilocation = v.begin(); ilocation != v.end(); ilocation++)
  33.     {
  35.         cout << *ilocation << ' ';
  36.     }
  38.     cout << endl;
  40.     sort(v.begin(), v.end());//比较函数默认
  41.     for (ilocation = v.begin(); ilocation != v.end(); ilocation++)
  42.     {
  44.         cout << *ilocation << ' ';
  45.     }
  47.     cout << endl;
  48. }
  53. 2 8 -15 90 26 7 23 30 -27 39 55
  54. -27 -15 2 7 8 23 26 30 39 55 90

发表评论

表情：
评论列表 （有 0 条评论，335人围观）

还没有评论，来说两句吧...

相关阅读

    相关 常用算法总结

    -------------------- [KMP算法][KMP] 简介 kmp算法又称“看毛片”算法，是一个效率非常高的字符串匹配算法。 kmp算法完成的任

    桃扇骨桃扇骨/ 0 赞/ 257 阅读

    相关 常用算法介绍

    递归法 算法定义：递归法是指一个过程或函数在定义或说明中又直接或间接调用自身的一种方法。在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。在递归调用的过程中系统

    男娘i男娘i/ 0 赞/ 346 阅读

    相关 常用算法

    冒泡排序： 冒泡排序是一种极其简单的排序算法，也是我接触到的第一种算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复

    素颜马尾好姑娘i素颜马尾好姑娘i/ 0 赞/ 305 阅读

    相关 常用道德算法

        6. 一行三列算法                思路：                  第一，要计算出总行数（用户获取所有数据%每行要显示的数据

    清疚清疚/ 0 赞/ 331 阅读

    相关 面试常用算法

    1. 求数组中和最大的子序列 2. 快速排序 基本思想在于把排序对象分割为两列子序列，而其中一个子序列的值都大雨另一子序列，并且进一步递归排序所有子序列 stat

    傷城~傷城~/ 0 赞/ 455 阅读

    相关 常用字符串算法

    一、判断两个字符串是否包含相同的内容 1.巧用数组下标实现，把用字符的ASCII码值当作下标，记录出现的字符，然后对两字符串进行遍历 / 判断s

    Dear 丶Dear 丶/ 0 赞/ 475 阅读