C++ Primer 学习笔记_40_STL实践与分析（14）--概述、初窥算法【上】

STL实践与分析

--概述、初窥算法【上】

标准库容器定义的操作非常少，并没有给容器添加大量的功能函数，而是选择提供一组算法，这些算法大都不依赖特定的容器类型，是“泛型”的，可作用在不同类型的容器和不同类型的元素上！

所谓泛型算法:一是因为它们实现共同的操作,所以称之为“算法”;而“泛型”指的是它们可以操作在多种容器类型上——不但可作用于vector或list这些标准库类型,还可用在内置数组类型、甚至其他类型的序列上,只要自定义的容器类型只要与标准库兼容,同样可以使用这些泛型算法。

大多数算法是通过遍历由两个迭代器标记的一段元素来实现其功能。典型情况下,算法在遍历一段元素范围时,操纵其中的每一个元素。算法通过迭代器访问元素,这些迭代器标记了要遍历的元素范围。

一、概述

    int searchVal = 110;
    vector<int>::const_iterator iter = find(ivec.begin(),ivec.end(),searchVal);

    if (iter != ivec.end())
    {
        cout << "The value " << *iter << " is present!" << endl;
    }
    else
    {
        cout << "The value " << searchVal << " is not present!" << endl;
    }

使用两个迭代器和一个值调用find函数,检查两个迭代器实参标记范围内的每一个元素。只要找到与给定值相等的元素,find就会返回指向该元素的迭代器。如果没有匹配的元素,find就返回它的第二个迭代器实参,表示查找失败。

由于find运算是基于迭代器的，因此可以在任意容器中使用相同的find函数查找值：

    list<int> iList;
    for (list<int>::size_type index = 0; index != 100; ++index)
    {
        iList.push_back(index);
    }

    int searchVal = 13;
    list<int>::const_iterator iter = find(iList.begin(),iList.end(),searchVal);

    if (iter != iList.end())
    {
        cout << "The value " << *iter << " is present!" << endl;
    }
    else
    {
        cout << "The value " << searchVal << " is not present!" << endl;
    }

除了容器类型与对象名称，几乎没有任何修改！

类似的，由于指针的行为与作用在内置数组上的迭代器一样，因此也可以用find来搜索数组：

    int ia[] = {27,210,12,476,109,83};
    int searchVal = 109;
    int *result = find(ia,ia+sizeof(ia)/sizeof(*ia),searchVal);

    if (result != ia+sizeof(ia)/sizeof(*ia))
    {
        cout << "The value " << *result << " is present!" << endl;
    }
    else
    {
        cout << "The value " << searchVal << " is not present!" << endl;
    }

如果需要一个子区间，则传递给这个子区间的第一个元素以及最后一个元素的下一位置的迭代器或指针。

    int *result = find(ia+2,ia+5,searchVal);

标准算法固有的独立于类型

这种算法,正如我们所指出的,与容器的类型无关:在前面的描述中,没有任何内容依赖于容器类型。这种算法只在一点上隐式地依赖元素类型:必须能够对元素做比较运算。该算法的明确要求如下:

1）需要某种遍历集合的方式:能够从一个元素向前移到下一个元素。

2）必须能够知道是否到达了集合的末尾。

3）必须能够对容器中的每一个元素与被查找的元素进行比较。

4）需要一个类型指出元素在容器中的位置,或者表示找不到该元素。

大多数情况下,每个算法都需要使用(至少)两个迭代器指出该算法操纵的元素范围。第一个迭代器指向第一个元素,而第二个迭代器则指向最后一个元素的下一位置。第二个迭代器所指向的元素【超出末端迭代器】本身不是要操作的元素,而被用作终止遍历的哨兵。

如果元素类型不支持相等(==)操作符,或者打算用不同的测试方法来比较元素,则可使用第二个版本的 find函数。这个版本需要一个额外的参数:实现元素比较的函数名字。

这些算法从不使用容器操作,因而其实现与类型无关,元素的所有访问和遍历都通过迭代器实现。实际的容器类型未知(甚至所处理的元素是否存储在容器中也是未知的)。

//P338 习题11.1
int main()
{
    ifstream inFile("input");
    vector<int> iVec;
    int val;

    while (inFile >> val)
    {
        iVec.push_back(val);
    }

    int searchVal;
    while (cin >> searchVal)
    {
        cout << searchVal << " have present "
             << count(iVec.begin(),iVec.end(),searchVal)
             << " times" << endl;
    }
}

//习题11.2
int main()
{
    ifstream inFile("input");
    list<string> strList;
    string val;

    while (inFile >> val)
    {
        strList.push_back(val);
    }

    string searchVal;
    while (cin >> searchVal)
    {
        cout << searchVal << " have present "
             << count(strList.begin(),strList.end(),searchVal)
             << " times" << endl;
    }
}

【关键概念：算法永不执行容器提供的操作】

泛型算法本身从不执行容器操作,只是单独依赖迭代器和迭代器操作实现。算法基于迭代器及其操作实现,而并非基于容器操作。【P338推荐！】

二、初窥算法【上】

使用泛型算法必须包含algorithm头文件：

#include <algorithm>

标准库还定义了一组泛化的算术算法，其命名习惯与泛型算法相同，使用这些算法必须包含numeric头文件：

#include <numeric>

除了少数例外情况,所有算法都在一段范围内的元素上操作,我们将这段范围称为“输出范围”。带有输入范围参数的算法总是使用头两个形参标记该范围。这两个形参是分别指向要处理的第一个元素和最后一个元素的下一位置的迭代器。

1、只读算法

accumulate的使用：

一个简单的只读算法accumulate,该算法在numeric头文件中定义。

    int sum = accumulate(iVec.begin(),iVec.end(),0);
    cout << sum << endl;

将sum设置为 vec的元素之和再加上0。accumulate带有三个形参。头两个形参指定要累加的元素范围。第三个形参则是累加的初值。

首先,调用该函数时必须传递一个起始值,否则,accumulate将不知道使用什么起始值。其次,容器内的元素类型必须与第三个实参的类型匹配,或者可转换为第三个实参的类型。在accumulate内部,第三个实参用作累加的起点;容器内的元素按顺序连续累加到总和之中。因此,必须能够将元素类型加到总和类型上。

类似的，也可以使用accumulate把string类型的vector容器中的元素连接起来：

string sum = accumulate(strVec.begin(),strVec.end(),string(""));

【注意】

程序显式地创建了一个string对象,用该函数调用的第三个实参。传递一个字符串字面值,将会导致编译时错误。因为此时,累加和的类型将是 constchar*,而 string的加法操作符所使用的操作数则分别是string和 constchar* 类型,加法的结果将产生一个string对象,而不是 constchar* 指针。

find_first_of的使用：

这个算法带有两对迭代器参数来标记两段元素范围，在第一段元素范围内查找与第二段范围中任意元素匹配的元素，然后返回一个迭代器，指向第一个匹配的元素，如果找不到匹配元素，则返回第一个范围的end迭代器。

//使用find_first_of统计有多少个数字在这两个容器中同时出现
    size_t cnt = 0;
    vector<int>::iterator iter = iVec1.begin();

    //在while的第一次循环中，遍历整个iVec1范围。
    //第二次以及后续的循环迭代则只考虑iVec1中尚未匹配的部分
    while ((iter = find_first_of(iter,iVec1.end(),iVec2.begin(),iVec2.end())) != iVec1.end())
    {
        cout << *iter << endl;
        ++ cnt;
        ++ iter;
    }
    cout << "cnt = " << cnt << endl;

【关键概念:迭代器实参类型，P340，值得仔细品读】

//P341 习题11.3
int main()
{
    vector<int> iVec;
    ifstream inFile("input");
    int val;

    while (inFile >> val)
    {
        iVec.push_back(val);
    }

    int sum = accumulate(iVec.begin(),iVec.end(),0);
    cout << sum << endl;
}

C++ Primer 学习笔记_40_STL实践与分析（14）-概述、初窥算法【上】

STL实践与分析

--概述、初窥算法【上】

相关推荐