泛型算法

发表于 | 分类于 | |
字数统计: 975 | 阅读时长 ≈ 4

C++标准库提供了vector，map，set，list等等的容器，对于这些不同的容器，他们都应该有一些相通的算法，比如find，copy等等。那么我们是否每个算法要对每个容器都实行一遍实现呢？实际上虽然不同的容器的同一个算法的实现可能不同，但是他们的抽象思想确实一致的，因此我们可以用同一的格式来解决，这就是泛型算法。

泛型算法的基础

算法有很多，然而究其本质只有一条，那就是对数据的遍历。

对于不同的容器，他们的数据组织格式千差万别，那么我们的泛型算法在遍历的时候需要同一个的一种方式来对数据结构进行遍历，有什么方法能做到呢？当然就是迭代器了。不得不说迭代器是一个很伟大的发明，它屏蔽了不同数据结构内部的差异，用统一的方式对数据进行遍历。

常用的泛型算法

只读算法

find

find用于查找操作，返回值是迭代器。如下所示：

1
2
auto pos = find(ivec.begin(), ivec.end(), 5);
cout << *pos << endl;

accumulate

accumulate执行的是累加操作，可用于定义了operator+操作符的类型，如int，string等等

1
2
3
#include "numeric"
int sum = accumulate(ivec.begin(), ivec.end(), 0);
string sum1 = accumulate(svec.begin(), svec.end(), “”);

equal

equal用于比较两个序列是否保存相同的值，如下所示：

1
bool ret = equal(ivec.begin(), ivec.end(), ivec1.begin());

equal要求第二个序列至少要跟第一个一样长。

for_each

for_each就是for循环。

1
2
3
4
void printWords(char c = ' ')
{
    for_each(words.begin(), words.end(), [=, &os] (const string& s) {os << s << c});
}

写容器的算法

fill

用于给序列赋值

1
fill(vec.begin(), vec.end(), 0);

fill_n

与fill一样，用于给序列赋值，但是fill_n的参数如下：

1
fill(vec.begin(), n, 0);

它的第二个参数是数量，但是如果我们的容器是空的，如下所示，就有可能会导致未定义的行为

1
2
vector<int> vec;
fill_n(vec.begin(), 10, 0);

为了解决这个问题，可以使用back_inserter

1
2
vector<int> vec;
fill_n(back_inserter(vec), 10, 0);

copy

copy可以用于两个数组的copy操作

1
2
3
int a1[] = {0, 1, 2, 3};
int a2[sizeof(a1)/ sizeof(int)];
copy(begin(a1), end(a2), a2);

replace

replace用于在一个序列中，将val1的值替换为val2的值

1
replace(vec.begin(), vec.end(), val1, val2);

排序

sort

sort是最重要的算法之一。sort的定义如下，它有三个参数，前两个微迭代器控制范围，最后一个是比较函数。这里如果不写，则用默认的比较函数
对于数值类型，默认重小到大排列，
对于字符串，默认为字典序排列。

而比较函数，可以是结构中定义operator<, lambda表达式，函数等方式解决。

1
void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

stable_sort

跟上面的sort一样的，是排序算法，只不过遇到相同的元素时，他会保证相同元素的最初始的位置不变动。所以我们称之为稳定的排序

unique

人如其名，unique算法保证返回的序列不存在重复元素，返回值为迭代器，为序列中不存在重复元素的下一个位置。

erase

删除，用于将序列中指定范围的元素删除

例子

假设我们有一个字符序列，我们需要将其按照字典序排列，并且删除重复的单词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "vector"
#include "iostream"
#include "fstream"
#include "sstream"

using namespace std;

int main()
{
    string sentence = "the quick red fox jumps over the slow red truple";
    istringstream ss(sentence);
    vector<string> words;
    string word;
    while (ss >> word) {
        words.push_back(word);
    }
    stable_sort(words.begin(), words.end());
    auto uPtr = unique(words.begin(), words.end());
    words.erase(uPtr, words.end());
    return 0;
}
显示 Gitment 评论