`

C++STL 常用算法

 
阅读更多
转自
http://www.cnblogs.com/BeyondAnyTime/archive/2012/05/27/2520532.html

一、非变异算法


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

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

函数原型： 
#include <algorithm>
template <class InputIterator, class T>
 
InputIterator find (InputIterator first, InputIterator last, const T& val);


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

返回值：
    返回查询结果的迭代器


实例： 
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

void main()

{
    //为vecIntegers添加数据
    vector<int> vecIntegers;
    for (int nNum=0; nNum<10;++nNum)
    {
        vecIntegers.push_back(nNum);
    }

    //打印数据
    vector<int>::const_iterator iElementLocator;
    for (iElementLocator=vecIntegers.begin(); iElementLocator != vecIntegers.end(); ++iElementLocator)
    {
        cout << *iElementLocator << ' ';
    }
    cout << endl;

    /*****************关键代码******************************/
    //查找数字 3
    //注意：返回值为迭代器
    vector<int>::iterator iElementFound;
    iElementFound = find(vecIntegers.begin(), vecIntegers.end(), 3);
    if (iElementFound != vecIntegers.end()) //如果找到结果
    {
        cout << *iElementFound << endl; 
    }
    else
    {
        cout << "没有找到结果！" << endl;
    }
    /****************************************************/

}


0 1 2 3 4 5 6 7 8 9
3
Press any key to continue


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

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


#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool divby5(int x)
{
    return x%5 ? 0:1;
}

void main()
{
    vector<int> v(20);
    for (int i = 0; i < v.size(); i++)
    {
        v[i] = (i+1)*(i+3);
        cout << v[i] << ' ';
    }

    cout << endl;

    vector<int>::iterator ilocation;
    ilocation = find_if(v.begin(),v.end(),divby5);
    if(ilocation != v.end())
    {
        cout << "找到第一个能被5整除的元素：" << *ilocation << endl
             << "元素的索引位置是： " << ilocation-v.begin() << endl;
    }
}


3 8 15 24 35 48 63 80 99 120 143 168 195 224 255 288 323 360 399 440
找到第一个能被5整除的元素：15
元素的索引位置是：2
Press any key to continue


3. 统计等于某值的容器元素个数 - count
函数原型： 
template<class InputIterator, class T> 
inline 
size_t count(
      InputIterator First,
      InputIterator Last,
      const T& Value
   )



#include <iostream>  
#include <algorithm>  
#include <functional>  
#include <string>  
#include <vector>  
  
void main()
{
    using namespace std;  
    const int VECTOR_SIZE = 8 ;

    // Define a template class vector of strings
    typedef vector<string > StringVector ;

    //Define an iterator for template class vector of strings
    typedef StringVector::iterator StringVectorIt ;

    StringVector NamesVect(VECTOR_SIZE) ;   //vector containing names

    string value("Sea") ;  // stores the value used
    // to count matching elements

    StringVectorIt start, end, it ;

    ptrdiff_t result = 0 ;   // stores count of elements
    // that match value.

    // Initialize vector NamesVect
    NamesVect[0] = "She" ;
    NamesVect[1] = "Sells" ;
    NamesVect[2] = "Sea" ;
    NamesVect[3] = "Shells" ;
    NamesVect[4] = "by" ;
    NamesVect[5] = "the" ;
    NamesVect[6] = "Sea" ;
    NamesVect[7] = "Shore" ;

    start = NamesVect.begin() ;   // location of first  
    // element of NamesVect  

    end = NamesVect.end() ;       // one past the location  
    // last element of NamesVect  

    // print content of NamesVect
    cout << "NamesVect { " ;  
    for(it = start; it != end; it++)
    {
        cout << *it << " " ;
    }
    cout << " }\n" << endl ;

    // Count the number of elements in the range [first, last +1)  
    // that match value.  
    result = count(start, end, value) ;  

    // print the count of elements that match value  
    cout << "Number of elements that match \"Sea\" = "  
        << result << endl  ; 
} 


NamesVect {She Sells Sea Shells by the Sea Shore}
Number of elements that match "Sea" = 2 
Press any key to continue


4. 条件统计 - count_if
    
count_if（l.begin（），l.end()，pred）

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

函数原型： 
template<class _InIt, class _Pr>
inline
typename iterator_traits<_InIt>::difference_type
     count_if(_InIt _First, _InIt _Last, _Pr _Pred);


示例： 
#include <iostream>  
#include <algorithm>  
#include <functional>  
#include <string>  
#include <vector>  
  
using namespace std; 
// Return true if string str starts with letter 'S'  
int MatchFirstChar( const string& str)  
{  
    string s("S") ;  
    return s == str.substr(0,1) ;  
}  

void main()
{  
    const int VECTOR_SIZE = 8 ;

    // Define a template class vector of strings
    typedef vector<string > StringVector ;

    //Define an iterator for template class vector of strings
    typedef StringVector::iterator StringVectorIt ;

    StringVector NamesVect(VECTOR_SIZE) ;   //vector containing names

    StringVectorIt start, end, it ;

    ptrdiff_t result = 0 ;   // stores count of elements
    // that match value.  

    // Initialize vector NamesVect  
    NamesVect[0] = "She" ;  
    NamesVect[1] = "Sells" ;  
    NamesVect[2] = "Sea" ;  
    NamesVect[3] = "Shells" ;  
    NamesVect[4] = "by" ;  
    NamesVect[5] = "the" ;  
    NamesVect[6] = "Sea" ;  
    NamesVect[7] = "Shore" ;  

    start = NamesVect.begin() ;   // location of first  
    // element of NamesVect  

    end = NamesVect.end() ;       // one past the location  
    // last element of NamesVect  

    // print content of NamesVect  
    cout << "NamesVect { " ;  
    for(it = start; it != end; it++)  
        cout << *it << " " ;  
    cout << " }\n" << endl ;  

    // Count the number of elements in the range [first, last +1)  
    // that start with letter 'S'  
    result = count_if(start, end, MatchFirstChar) ;  

    // print the count of elements that start with letter 'S'  
    cout << "Number of elements that start with letter \"S\" = "  
        << result << endl  ;  
} 


NamesVect {She Sells Sea Shells by the Sea Shore}
Number of elements that start with letter  "S" = 6 
Press any key to continue




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

函数原型：search(v1.begin(),v1.end(),v2.begin(),v2.end());


#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

void main()
{
    vector<int> v1;
    cout << "v1:";

    for (int i = 0; i < 5; i++)
    {
        v1.push_back(i+5);

        //注意：v1定义时没有给定大小，因此这里不能直接使用赋值语句。
        cout<<v1[i]<<' ';
    }

    cout << endl;

    vector<int> v2;
    cout << "v2:";
    for (int i = 0; i < 2; i++)
    {
        v2.push_back(i+7);
        cout << v2[i] << ' ';
    }
    cout << endl;

    vector<int>::iterator ilocation;

    ilocation = search(v1.begin(),v1.end(),v2.begin(),v2.end());
    if (ilocation != v1.end())
    {
        cout << "v2的元素包含在v1中，起始元素为" << "v1[" << ilocation-v1.begin() << ']' << endl;
    }
    else
    {
        cout << "v2的元素不包含在v1中" << endl;
    }
}


v1: 5 6 7 8 9 
v2: 7 8
v2的元素包含在v1中，起始元素为v1[2]



6重复元素子序列搜索search_n

    search_n算法函数搜索序列中是否有一系列元素值均为某个给定值的子序列。 
函数原型：search_n(v.begin(),v.end(),3,8)，

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

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

void main()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(8);
    v.push_back(8);
    v.push_back(8);
    v.push_back(6);
    v.push_back(6);
    v.push_back(8);

    vector<int>::iterator i;
    i = search_n(v.begin(),v.end(),3,8);
    if (i != v.end())
    {
        cout<<"在v中找到3个连续的元素8"<<endl;
    }
    else
    {
        cout<<"在v中未找到3个连续的元素8"<<endl;
    }
}


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


7最后一个子序列搜索find_end 
   函数原型find_end(v1.begin(),v1.end(),v2.begin(),v2.end());

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

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

void main()
{
    vector<int> v1;
    v1.push_back(-5);
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(-6);
    v1.push_back(-8);
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(-11);

    vector<int> v2;
    v2.push_back(1);
    v2.push_back(2);

    vector<int>::iterator i;
    i = find_end(v1.begin(), v1.end(), v2.begin(), v2.end());
    if (i != v1.end())
    {
        cout << "v1中找到最后一个匹配v2的子序列，位置在" << "v1[" << i-v1.begin() << "]" << endl;
    }
}


"v1中找到最后一个匹配v2的子序列，位置在v1[5]



二、变异算法


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

1元素复制copy 

#include <vector>

#include <list>

#include <algorithm>

#include <iostream>

using namespace std;

 

void main()

{

vector<int> v;

v.push_back(1);

v.push_back(3);

v.push_back(5);

 

list<int> l;

l.push_back(2);

l.push_back(4);

l.push_back(6);

l.push_back(8);

l.push_back(10);

copy(v.begin(),v.end(),l.begin());

list<int>::iterator i;

for(i=l.begin();i!=l.end();i++)

cout<<*i<<' ';

cout<<endl;

}



2元素变换transform改变

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

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

#include <vector>

#include <list>

#include <algorithm>

#include <iostream>

using namespace std;

 

int square(int x)

{

return x*x;

}

void main()

{

vector<int> v;

v.push_back(5);

v.push_back(15);

v.push_back(25);

list<int> l(3);

transform(v.begin(),v.end(),l.begin(),square);

list<int>::iterator i;

for(i=l.begin();i!=l.end();i++)

cout<<*i<<' ';

cout<<endl;

}


3替换replace

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

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

void main()

{

vector<int> v;

v.push_back(13);

v.push_back(25);

v.push_back(27);

v.push_back(25);

v.push_back(29);

replace(v.begin(),v.end(),25,100);

vector<int>::iterator i;

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

cout<<*i<<' ';

cout<<endl;

}


13 100 27 100 29






4条件替换replace_if 

函数原型：replace_if(v.begin(),v.end(),odd,100);


#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

bool odd(int x)

{

return x%2;

}

void main()

{

vector<int> v;

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

v.push_back(i);

replace_if(v.begin(),v.end(),odd,100);

vector<int>::iterator ilocation;

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

cout<<*ilocation<<' ';

cout<<endl;

}




5n次填充fill_n

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



#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

vector<int> v(10);

fill_n(v.begin(),5,-1);

vector<int>::iterator ilocation;

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

cout<<*ilocation<<' ';

cout<<endl;

}

输出结果：-1 -1 -1 -1 -1 0 0 0 0 0




6随机生成n个元素generate

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



#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

void main()

{

vector<int> v(10);

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

vector<int>::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 <vector>

#include <algorithm>

#include <iostream>

using namespace std;



bool even(int x)

{

return x%2?0:1;

}

void main()

{

vector<int> v;

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

v.push_back(i);

vector<int>::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 <vector>

#include <algorithm>

#include <iostream>

using namespace std;



void main()

{

vector<int> 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<int>::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



三、排序算法


1、创建堆make_heap

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

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

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

void main()
{
    vector<int> v;
    v.push_back(5);
    v.push_back(6);
    v.push_back(4);
    v.push_back(8);
    v.push_back(2);
    v.push_back(3);
    v.push_back(7);
    v.push_back(1);
    v.push_back(9);

    make_heap(v.begin(), v.end());
    v.push_back(20);
    push_heap(v.begin(), v.end());

    vector<int>::iterator ilocation;
    for(ilocation = v.begin(); ilocation != v.end(); ilocation++)
    {
        cout << *ilocation << ' ';
    }

    cout << endl;

    pop_heap(v.begin(), v.end());
    for (ilocation = v.begin(); ilocation != v.end(); ilocation++)
    {
        cout << *ilocation << ' ';
    }

    cout << endl;
}


20 9 7 6 8 3 4 1 5 2
9 8 7 6 2 3 4 1 5 20


4. 堆排序 - sort_heap

使用： 
make_heap(v.begin(),v.end());
sort_heap(v.begin(),v.end());



#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

void main()
{
    vector<int> v;
    v.push_back(3);
    v.push_back(9);
    v.push_back(6);
    v.push_back(3);
    v.push_back(17);
    v.push_back(20);
    v.push_back(12);

    vector<int>::iterator ilocation;
    for (ilocation = v.begin(); ilocation != v.end(); ilocation++)
    {
        cout << *ilocation << ' ';
    }

    cout << endl;

    make_heap(v.begin(),v.end());
    sort_heap(v.begin(),v.end());

    for (ilocation = v.begin(); ilocation != v.end(); ilocation++)
    {
        cout << *ilocation << ' ';
    }

    cout << endl;
}



3 9 6 3 17 20 12
3 3 6 9 12 17 20


5. 排序 - sort
    sort详细解释参考linkhttp://www.cppblog.com/mzty/archive/2005/12/15/1770.html

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

函数原型： 
template<class RanIt>
       void sort(RanIt fist, RanIt last);
template<class RanIt, class Pred>
       void sort(RanIt fist, RanIt last, Pred pr);



#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

void main()
{
    vector<int> v;
    v.push_back(2);
    v.push_back(8);
    v.push_back(-15);
    v.push_back(90);
    v.push_back(26);
    v.push_back(7);
    v.push_back(23);
    v.push_back(30);
    v.push_back(-27);
    v.push_back(39);
    v.push_back(55);

    vector<int>::iterator ilocation;
    for (ilocation = v.begin(); ilocation != v.end(); ilocation++)
    {
        cout << *ilocation << ' ';
    }

    cout << endl;

    sort(v.begin(), v.end());//比较函数默认
    for (ilocation = v.begin(); ilocation != v.end(); ilocation++)
    {
        cout << *ilocation << ' ';
    }

    cout << endl;
}


2 8 -15 90 26 7 23 30 -27 39 55
-27 -15 2 7 8 23 26 30 39 55 90
分享到：
| Efficient C++ 第十二章 引用计数
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    c++模板stl常用算法

    #### 模板与STL算法 STL中的许多算法都是通过模板实现的，这样可以使其适用于不同的数据类型。例如，`std::sort`函数就是一个函数模板，它可以对任何容器中的元素进行排序。 ```cpp #include #include std::...

    C++库函数及STL算法

    本文将深入探讨C++库函数和STL算法，以及如何在实际编程中应用这些概念。 首先，C++库函数是预定义的函数集合，为程序员提供了各种基本操作，例如输入/输出、数学计算、字符串处理等。例如，`std::cin`和`std::cout...

    C++ STL--数据结构与算法实现（余文溪）示例程序代码.rar

    C++ STL，全称为Standard Template Library（标准模板库），是C++编程语言中的一部分，它提供了丰富的容器、迭代器、算法和函数对象等组件，极大地简化了数据结构和算法的实现。余文溪的《C++ STL--数据结构与算法...

    C++ STL程序员面试题

    - 举例说明如何自定义一个函数对象，并在STL算法中使用。 - 描述STL容器的内存管理和效率特点，比如vector的连续存储和list的跳跃访问。 4. **STL.doc** 另一份全面的STL文档可能详细解释了各个组件的内部工作...

    C++常用stl算法.pdf

    这篇文档主要讨论了C++ STL中的一些常用算法，包括函数对象适配器，如`for_each`、`bind`等。让我们深入探讨这些概念。 首先，函数对象在C++中是一个重要的概念，它是一个类，通过重载`()`操作符使得类的对象能够像...

    C++ STL教程pdf

    2. **标准模板**：在C++ STL中，模板被用来定义泛型类（如容器和迭代器）和泛型函数（如算法）。例如，`vector`、`list`、`map`等都是标准模板类，它们可以存储不同类型的数据。模板使代码更加模块化，易于维护和...

    C++ STL 参考手册Cpp_STL_ReferenceManual.pdf

    C++ 对模板（Template）支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。例如，vector 的底层为顺序表（数组），list 的底层为双向链表，deque 的底层为循环...

    C/C++ STL参考手册 STL帮助文档 中文/英文版都有

    STL，全称为Standard Template Library（标准模板库），是C++编程语言中不可或缺的一部分，它为程序员提供了高效且灵活的数据结构和算法。STL的主要组件包括容器、迭代器、算法和函数对象，这些组件共同构成了一个...

    STL数值算法源码

    参考自侯捷先生的《STL源码剖析》，C++ STL 的数值算法(Numeric algorithms)是一组对容器元素进行数值计算的模板函数，包括容器元素求和 accumulate 、两序列元素的内积 inner_product 、容器元素的一系列部分元素和...

    C++ STL标准程序库开发指南 源代码.rar

    C++ STL（Standard Template Library，标准模板库）是C++编程中的一个重要组成部分，它提供了一系列高效、可重用的数据结构和算法。这个压缩包“C++ STL标准程序库开发指南 源代码.rar”包含了C++ STL的源代码，对于...

    C++ STL源码剖析（侯捷版本）_C语言_pdf_数据结构_

    书中会介绍如何创建和使用自定义的函数对象来增强STL算法的功能。 6. 分配器：分配器在STL中负责内存管理，不同的分配器可以适应不同的内存需求和性能目标。通过深入理解分配器，读者能更好地控制STL容器的内存行为...

    C++ STL算法实现大数计算

    C++ STL算法实现大数计算 本文将详细介绍C++ STL算法实现大数计算的知识点，包括大数计算的原理、C++ STL容器的应用、算法实现的步骤等。 大数计算的原理 大数计算是指对非常大的整数进行运算的过程。在计算机...

    c++ STL中文版

    C++ STL，全称为Standard Template Library（标准模板库），是C++编程语言中的一部分，它提供了高效、灵活的容器、算法和迭代器等组件。这些组件使得程序员能够以一种更抽象、更模块化的方式处理数据结构和算法，...

    c++ STL思维导图（自己总结）

    Vector容器是C++ STL中最常用的容器之一，用于存储同类型的元素。Vector容器提供了多种构造函数，例如`V(v1.begin(), v1.end())`和`V(v1)`，用于将其他容器的元素复制到Vector容器中。Vector容器也提供了多种操作，...

    C++STL Source.rar

    这个"C++STL Source.rar"文件很可能包含了C++ STL的源代码，对于深入理解STL的工作原理和实现细节非常有帮助。 STL的核心组成部分包括： 1. 容器（Containers）：这是STL的基础，提供了数据结构来存储和管理元素...

    C++ STL库源代码(SGI版本)

    4. **stl_algo.h**：这是一个头文件，包含了STL算法的声明。通过阅读源代码，你可以了解各种算法如何与容器和迭代器协同工作，以及如何实现通用性和效率。 5. **stl_rope.h, ropeimpl.h**：Rope是一种特殊的数据...

    c++ STL阐述了各种查找算法的异同以及使用他们的时机

    C++ STL 查找算法详解 C++ STL 中提供了多种查找算法，每种算法都有其特点和使用场景，本文将对这些算法进行详细的介绍和比较。 首先，需要注意的是，STL 中的查找算法可以分为两组：A 组和 B 组。A 组包括 count ...

    C++STL详解PPT

    C++STL 库是 C++ 语言中非常重要的一部分，它提供了许多有用的容器、算法和迭代器，帮助开发者更方便地编写高效、可重用的代码。 泛型程序设计是 C++ 语言中非常重要的一部分，它允许开发者编写通用的代码，从而...

    深入C++STL中文版

    接下来，我们将围绕“深入C++STL中文版”这一主题展开详细的讲解，涵盖C++ STL的基本概念、核心组件以及如何利用STL提高编程效率等方面。 ### C++ STL简介 C++标准模板库（Standard Template Library，简称STL）是...

    数据结构 C++ STL 二叉树

    C++ Standard Template Library (STL) 提供了对多种数据结构和算法的支持，其中包括对二叉树的操作。在这个主题中，我们将深入探讨二叉树的递归遍历、非递归遍历、二叉树的迭代器以及线索二叉树的中序遍历。 首先，...

Magicbox
Global site tag (gtag.js) - Google Analytics