C++步步为营

C++---CHAPTER 10: GENERIC ALGORI

2019-08-03  本文已影响0人  世界上的一道风

初识

int val = 42;
auto result = find(vec.cbegin(), vec.cend(), val)

可以看到，find内部使用迭代器进行，这使得迭代器令算法不依赖与容器。
但是算法依赖于元素类型的操作：比如find要求元素类型支持<云算符。
并且多数算法支持我们自定义的操作代替默认的比较运算符。

只读算法：只会读取范围内的元素，不会改变元素，如find、count。
对vec中的元素求和，和的初值是0 （第三个参数）
int sum = accumulate(vec.cbegin(),vec.cend(), 0);

编程假定：元素类型加到和的类型上的操作必须是可行的。

连接所有的string元素。
string sum = accumulate(v.cbegin(), v.cend(), string(""));

错误的，因为const char*上没有定义+运算符
string sum = accumulate(v.cbegin(), v.cend(), "");

roster2中的元素数目应该至少与roster1一样多
equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

上面的equal接受一个单一迭代器表示第二个序列，一般这样的算法都假定了第二个序列至少与第一个序列一样长。

写容器算法：这类算法要求确保序列大小至少不小于我们要求算法写入的元素数目。
将每个元素重置为0
fill(vec.begin(), vec.end(), 0); 

将容器的子序列设置为10
fill(vec.begin(), vec.begin() + vec.size() / 2, 10);

vector<int> vec;

将所有元素重置为0
fill_n(vec.begin(), vec.size(), 0); 

fill_n(dest, n, val);

上面的fill_n假设了dest开始的序列至少有包含了n个元素，可能犯的错误：

vector<int> vec; // 空容器
fill_n(vec, 10, 0);  // 错误， 该10个位置都不存在

vector<int> vec;
auto it = back_iterator(vec);
* it = 42; // vec中现在多了一个元素42

可以使用back_iterator作为算法的目的位置使用：

vector<int> vec; 
fill_n(back_inserter(vec), 10, 0); //现在添加了10个元素到vec

int a1[] = {0,1,2};
int a2[ sizeof(a1) / sizeof(*a1)]; // 与a1大小一样
auto ret = copy(begin(a1), end(a1), a2);  //把a1的内容复制给a2；

copy返回目的的位置迭代器，即ret恰好指向a2的尾元素之后的位置。

把所有0元素变为42
replace(ilst.begin(), ilst.end(), 0, 42); 

使得原来的ilst序列不变，ivec保存了replace操作的序列
replace_copy(ilst.cbegin(), ilst.end(), back_inserter(ivec), 0, 42);
重排容器元素的算法

一个消除重复单词的例子：

void elimDups(vector<string> &words)
{
  sort(words.begin(), words.end());
  // unique重拍输入范围,使得每一个单词只出现一次
  auto end_unique = unique(words.begin(), words.end());
  words.erase(end_unique, words.end());
}
int main() {
  vector<string> words = {"the", "quick", "red", "fox", "jumps",
  "over", "the", "slow","red","turtle"};
  elimDups(words);
  for (auto i: words)
    cout << i << " ";
}

fox jumps over quick red slow the turtle

定制操作

比如sort算法默认使用<运算符，但我们希望排序顺序与<所定义的顺序不同，或者保存的序列元素未定义<运算符，因此都需要重载sort的默认行为，为此需要定制我们自己的操作。

传递函数给算法

接受谓词参数的算法对输入序列中的元素调用谓词。因此，元素类型必须能够转换为谓词的参数类型。

bool isShorter(const string &s1, const string &s2)
{
  return s1.size() < s2.size();
}

elimDups(words);

这使得短的单词排在长的单词的前面；
stable_sort(words.begin(), words.end(), isShorter);
  for (const auto &s: words) //无须拷贝字符串
    cout << s << " ";


fox red the over slow jumps quick turtle

lambda表达式

一个lambda表达式可理解为一个未命名的内联函数，其形式如下：

[capture list] (parameter list) -> return type{function body}

capture list是一个lambda所在函数中定义的局部变量的列表（通常为空），其他参数与普通函数类似。
与其他函数的不同，lambda必须使用尾置返回来指定返回类型。

func接受一个int类型的实参，返回一个指针，该指针指向含有是个整数的数组。
auto func(int i) -> int(*)[10];
可以看到，函数的返回类型放在了形式参数列表的后面。

lambda表达式必须永远包含捕获列表和函数体：

auto f= [] {return 42;};

调用lambda表达式：
cout << f() << endl;

注：如果lambda函数体包含任何单一return语句之外的内容，且未指定返回类型，则返回void。

 [](const string &a, const string &b){return a.size() < b.size();}

lambda表达式通过将局部变量包含在捕获列表中来指出将会使用这些变量。

一个例子，上述的sort单词，要求出大于等于一个给定长度的单词有多少，修改输出，打印这些单词；

定义一个给定长度`sz`，然后把`sz`加入捕获列表,在函数体内使用。
[sz](const string &a){return a.size() >= sz;};

错误，sz未捕获
[](const string &a){return a.size() >= sz;};

for_each(wc, words.end(), [](const string &s){cout << s << " ";});

上面的lambda空捕获列表,但是函数体使用了s、cout，因为：
Note: 捕获列表只用于局部非static变量，lambda可以之间直接使用局部static变量还有它所在函数之外声明的名字。

代码：

string make_plural(size_t ctr, const string &word, const string &ending)
{
  return (ctr > 1) ? word + ending: word;
}

  //vector<string> words = {"the", "quick", "red", "fox", "jumps","over", "the", "slow", "red", "turtle"};

void biggies(vector<string> &words, vector<string>::size_type sz) {
  elimDups(words);
  stable_sort(words.begin(), words.end(), 
  [](const string &a, const string &b){return a.size() < b.size();});
  for (const auto &s: words) //无须拷贝字符串
    cout << s << " ";
  cout << endl;
  auto wc = find_if(words.begin(),words.end(),
 
 //sz不在函数体内
  [sz](const string &a){return a.size() >= sz;});
  // wc指向words中第一个string长度大于等于5的位置，用end减去便是剩下都大于等于5的string数目
  auto count = words.end() - wc;
  cout << count << " " << make_plural(count, "word", "s")
    << " of length " << sz << " or longer " << endl;
  for_each(wc, words.end(), [](const string &s){cout << s << " ";});
}

fox red the over slow jumps quick turtle
3 words of length 5 or longer
jumps quick turtle
参数绑定

再探迭代器

  1. inserter的例子：设it是由inserter生成的迭代器，则：
*it = val;

等价于：
it = c.insert(it, val); //it指向新加入的元素
++it; // 递增it使它指向原来的元素
  1. front_inserter的例子：
list<int> lst = {1, 2, 3, 4, 5};
list<int> lst2, lst3; 

// 拷贝完成后， lst2包含4，3，2，1
copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
// lst3包含1，2，3，4
copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));

泛型算法结构

特定容器算法

上一篇下一篇

猜你喜欢

热点阅读